gdunlap/sched-sim.hg

view sched_credit03.c @ 14:f289f886cbcc

Add sched_credit03
author George Dunlap <george.dunlap@eu.citrix.com>
date Fri Jul 16 11:12:29 2010 +0100 (2010-07-16)
parents
children cb624ff1d4fe
line source
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <assert.h>
5 #define ASSERT assert
7 #include "list.h"
8 #include "sim.h"
11 #define MAX_VMS 16
12 #define CREDIT_INIT 500
13 #define CREDIT_CLIP 50
14 #define CREDIT_RESET 0
15 #define MAX_TIMER 200
16 #define MIN_TIMER 50
18 /* FIXME: hack! */
19 int init_weight[] = { 70, 100, 100, 100, 200, 200 };
21 struct sched_vm {
22 struct list_head runq_elem;
23 struct vm *v;
25 int weight;
27 int credit;
28 int credit_per_min_timer; /* ? */
29 int start_time;
30 int vid;
31 };
33 struct {
34 struct list_head runq; /* Global run queue */
35 int max_vm;
36 struct sched_vm vms[MAX_VMS];
37 int ncpus;
39 int max_weight;
40 int scale_factor; /* ? */
42 int next_check;
43 } sched_priv;
45 static int t2c(int time, struct sched_vm *svm)
46 {
47 return time * sched_priv.max_weight / svm->weight;
48 }
50 static int c2t(int credit, struct sched_vm *svm)
51 {
52 return credit * svm->weight / sched_priv.max_weight;
53 }
55 static void dump_credit(int time, struct sched_vm *svm)
56 {
57 printf("credit v%d %d %d\n", svm->vid, time, svm->credit);
58 }
60 static void reset_credit(int time)
61 {
62 int i;
63 for ( i=0; i<=sched_priv.max_vm; i++)
64 {
65 struct sched_vm *svm = sched_priv.vms + i;
66 int tmax = CREDIT_CLIP;
68 //sched_priv.vms[i].credit = 0;
69 //sched_priv.vms[i].credit /= (CREDIT_INIT/10);
70 if ( svm->credit > tmax )
71 svm->credit = tmax;
72 svm->credit += CREDIT_INIT;
73 svm->start_time = time;
75 dump_credit(time, svm);
76 }
77 /* No need to resort runq, as everyone's credit is now zero */
78 }
80 static void burn_credit(struct sched_vm *svm, int time)
81 {
82 ASSERT(time >= svm->start_time);
84 svm->credit -= t2c(time - svm->start_time, svm);
85 svm->start_time = time;
87 dump_credit(time, svm);
88 }
90 static int calc_timer(struct sched_vm *svm)
91 {
92 int time = MAX_TIMER;
94 if ( time > c2t(svm->credit, svm) )
95 time = c2t(svm->credit, svm);
97 if ( !list_empty(&sched_priv.runq) )
98 {
99 struct sched_vm *sq = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
101 ASSERT(svm->credit >= sq->credit);
103 /* Time will be used for svm, so use it to scale c2t */
104 if ( time > c2t(svm->credit - sq->credit, svm) )
105 time = c2t(svm->credit - sq->credit, svm);
106 }
108 if ( time < MIN_TIMER )
109 time = MIN_TIMER;
111 return time;
112 }
114 static void runq_insert(struct sched_vm *svm)
115 {
116 struct list_head *iter;
117 int pos = 0;
119 list_for_each( iter, &sched_priv.runq )
120 {
121 struct sched_vm * iter_svm;
123 iter_svm = list_entry(iter, struct sched_vm, runq_elem);
125 if ( svm->credit > iter_svm->credit )
126 {
127 printf(" p%d v%d\n",
128 pos,
129 iter_svm->vid);
130 break;
131 }
132 pos++;
133 }
135 list_add_tail(&svm->runq_elem, iter);
136 }
138 static void sched_credit_init(void)
139 {
140 printf("%s()\n", __func__);
141 INIT_LIST_HEAD(&sched_priv.runq);
142 sched_priv.max_vm=0;
143 sched_priv.max_weight = 0;
144 }
146 static void sched_credit_vm_init(int vid)
147 {
148 struct sched_vm *svm;
150 printf("%s: vm %d\n", __func__, vid);
152 if ( vid > MAX_VMS )
153 {
154 fprintf(stderr, "vid %d > MAX_VMS %d!\n", vid, MAX_VMS);
155 exit(1);
156 }
158 svm = sched_priv.vms + vid;
160 INIT_LIST_HEAD(&svm->runq_elem);
162 svm->vid = vid;
163 svm->v = vm_from_vid(vid);
165 svm->credit = CREDIT_INIT;
166 svm->weight = init_weight[vid];
167 if ( sched_priv.max_weight < svm->weight )
168 sched_priv.max_weight = svm->weight;
169 svm->start_time = 0;
171 if ( vid > sched_priv.max_vm )
172 sched_priv.max_vm = vid;
173 }
175 static void sched_credit_wake(int time, int vid)
176 {
177 struct vm *v;
178 struct sched_vm *svm;
180 v = vm_from_vid(vid);
182 printf("%s: time %d vid %d\n",
183 __func__, time, v->vid);
185 svm = sched_priv.vms + v->vid;
187 ASSERT(list_empty(&svm->runq_elem));
189 runq_insert(svm);
191 /* Scan for either:
192 * + an idle cpu to wake up, or
193 * + if there are cpus with lower credits, the lowest one
194 */
195 {
196 int i, ipid=-1, lowest=-1, cdiff;
198 for ( i=0; i<P.count; i++ )
199 {
200 if ( P.pcpus[i].idle )
201 {
202 printf(" %s: p%d idle, waking\n", __func__, i);
203 ipid=i;
204 lowest=0;
205 break;
206 }
207 else if ( P.pcpus[i].current )
208 {
209 struct vm* ovm = P.pcpus[i].current;
210 int ovid = ovm->vid;
211 struct sched_vm *osvm = sched_priv.vms + ovid;
213 /* Update credits of currently running VM */
214 burn_credit(osvm, time);
216 if ( lowest == -1 || osvm->credit < lowest )
217 {
218 ipid = i;
219 lowest = osvm->credit;
220 }
221 }
223 }
225 cdiff = lowest - svm->credit;
227 /* FIXME: c2t should be based on weight of running vm, not waiting vm! */
228 if ( ipid >= 0 )
229 sim_sched_timer((cdiff>0)?c2t(cdiff, svm):0, ipid);
230 else
231 dump_credit(time, svm);
232 }
233 }
235 static struct vm* sched_credit_schedule(int time, int pid)
236 {
237 struct sched_vm *svm;
238 struct vm *next, *prev;
239 int timer;
241 printf("%s: time %d pid %d\n",
242 __func__, time, pid);
243 prev = current(pid);
245 if ( prev )
246 {
247 printf(" current v%d\n", prev->vid);
248 svm = sched_priv.vms + prev->vid;
250 burn_credit(svm, time);
252 if ( svm->v->runstate == RUNSTATE_RUNNING )
253 {
254 printf(" adding to runqueue\n");
255 runq_insert(svm);
256 }
257 }
259 /* Take guy on front of runqueue, set new timer */
260 if ( list_empty(&sched_priv.runq) )
261 {
262 printf(" No runnable entities\n");
263 return NULL;
264 }
266 svm = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
268 list_del_init(&svm->runq_elem);
270 next = svm->v;
272 if ( svm->credit <= CREDIT_RESET )
273 {
274 printf(" vid %d credit %c, resetting credit at time %d\n",
275 svm->vid,
276 svm->credit,
277 time);
278 reset_credit(time);
279 }
281 dump_credit(time, svm);
282 svm->start_time = time;
284 timer = calc_timer(svm);
286 sim_sched_timer(timer, pid);
288 printf(" next: v%d\n", next->vid);
290 return next;
291 }
293 struct scheduler sched_credit03 =
294 {
295 .name="credit03",
296 .desc="c02 + weight",
297 .ops = {
298 .sched_init = sched_credit_init,
299 .vm_init = sched_credit_vm_init,
300 .wake = sched_credit_wake,
301 .schedule = sched_credit_schedule
302 }
303 };