gdunlap/sched-sim.hg

view sched_credit03.c @ 17:03ad237559b4

Fix-up options, scheduler list
author George Dunlap <george.dunlap@eu.citrix.com>
date Fri Jul 16 11:58:53 2010 +0100 (2010-07-16)
parents cb624ff1d4fe
children
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 /*
46 * + Implement weights (hacky at the moment)
47 * - Everyone starts at fixed value
48 * - Burn credit based on variable weight
49 * - Insert in runq based on credit
50 * - Reset
51 * - Triggered when someone reaches zero
52 * + Clip everyone's credit and add INIT
53 * - Timeslice
54 * - Start with basic timeslice
55 * - Don't run for more credit than you have
56 * - Only run until your credit would equal next VM in runqueue
57 * - Never less than MIN_TIMER
58 */
60 static int t2c(int time, struct sched_vm *svm)
61 {
62 return time * sched_priv.max_weight / svm->weight;
63 }
65 static int c2t(int credit, struct sched_vm *svm)
66 {
67 return credit * svm->weight / sched_priv.max_weight;
68 }
70 static void dump_credit(int time, struct sched_vm *svm)
71 {
72 printf("credit v%d %d %d\n", svm->vid, time, svm->credit);
73 }
75 static void reset_credit(int time)
76 {
77 int i;
78 for ( i=0; i<=sched_priv.max_vm; i++)
79 {
80 struct sched_vm *svm = sched_priv.vms + i;
81 int tmax = CREDIT_CLIP;
83 if ( svm->credit > tmax )
84 svm->credit = tmax;
85 svm->credit += CREDIT_INIT;
86 svm->start_time = time;
88 dump_credit(time, svm);
89 }
90 /* No need to resort runq, as no one's credit is re-ordered */
91 }
93 static void burn_credit(struct sched_vm *svm, int time)
94 {
95 ASSERT(time >= svm->start_time);
97 svm->credit -= t2c(time - svm->start_time, svm);
98 svm->start_time = time;
100 dump_credit(time, svm);
101 }
103 static int calc_timer(struct sched_vm *svm)
104 {
105 int time;
107 /* Start with basic timeslice */
108 time = MAX_TIMER;
110 /* If we have less credit than that, cut it down to our credits */
111 if ( time > c2t(svm->credit, svm) )
112 time = c2t(svm->credit, svm);
114 /* If there are other VMs on the runqueue, calculate
115 * how much time until our credit will equal their credit.
116 * If this is less than our timeslice, cut it down again. */
117 if ( !list_empty(&sched_priv.runq) )
118 {
119 struct sched_vm *sq = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
121 ASSERT(svm->credit >= sq->credit);
123 /* Time will be used for svm, so use it to scale c2t */
124 if ( time > c2t(svm->credit - sq->credit, svm) )
125 time = c2t(svm->credit - sq->credit, svm);
126 }
128 /* No matter what, always run for at least MIN_TIMER */
129 if ( time < MIN_TIMER )
130 time = MIN_TIMER;
132 return time;
133 }
135 static void runq_insert(struct sched_vm *svm)
136 {
137 struct list_head *iter;
138 int pos = 0;
140 list_for_each( iter, &sched_priv.runq )
141 {
142 struct sched_vm * iter_svm;
144 iter_svm = list_entry(iter, struct sched_vm, runq_elem);
146 if ( svm->credit > iter_svm->credit )
147 {
148 printf(" p%d v%d\n",
149 pos,
150 iter_svm->vid);
151 break;
152 }
153 pos++;
154 }
156 list_add_tail(&svm->runq_elem, iter);
157 }
159 static void sched_credit_init(void)
160 {
161 printf("%s()\n", __func__);
162 INIT_LIST_HEAD(&sched_priv.runq);
163 sched_priv.max_vm=0;
164 sched_priv.max_weight = 0;
165 }
167 static void sched_credit_vm_init(int vid)
168 {
169 struct sched_vm *svm;
171 printf("%s: vm %d\n", __func__, vid);
173 if ( vid > MAX_VMS )
174 {
175 fprintf(stderr, "vid %d > MAX_VMS %d!\n", vid, MAX_VMS);
176 exit(1);
177 }
179 svm = sched_priv.vms + vid;
181 INIT_LIST_HEAD(&svm->runq_elem);
183 svm->vid = vid;
184 svm->v = vm_from_vid(vid);
186 svm->credit = CREDIT_INIT;
187 /* FIXME */
188 svm->weight = init_weight[vid];
189 if ( sched_priv.max_weight < svm->weight )
190 sched_priv.max_weight = svm->weight;
191 svm->start_time = 0;
193 if ( vid > sched_priv.max_vm )
194 sched_priv.max_vm = vid;
195 }
197 static void sched_credit_wake(int time, int vid)
198 {
199 struct vm *v;
200 struct sched_vm *svm;
202 v = vm_from_vid(vid);
204 printf("%s: time %d vid %d\n",
205 __func__, time, v->vid);
207 svm = sched_priv.vms + v->vid;
209 ASSERT(list_empty(&svm->runq_elem));
211 runq_insert(svm);
213 /* Scan for either:
214 * + an idle cpu to wake up, or
215 * + if there are cpus with lower credits, the lowest one
216 */
217 {
218 int i, ipid=-1, lowest=-1, cdiff;
220 for ( i=0; i<P.count; i++ )
221 {
222 if ( P.pcpus[i].idle )
223 {
224 printf(" %s: p%d idle, waking\n", __func__, i);
225 ipid=i;
226 lowest=0;
227 break;
228 }
229 else if ( P.pcpus[i].current )
230 {
231 struct vm* ovm = P.pcpus[i].current;
232 int ovid = ovm->vid;
233 struct sched_vm *osvm = sched_priv.vms + ovid;
235 /* Update credits of currently running VM */
236 burn_credit(osvm, time);
238 if ( lowest == -1 || osvm->credit < lowest )
239 {
240 ipid = i;
241 lowest = osvm->credit;
242 }
243 }
245 }
247 cdiff = lowest - svm->credit;
249 /* FIXME: c2t should be based on weight of running vm, not waiting vm! */
250 if ( ipid >= 0 )
251 sim_sched_timer((cdiff>0)?c2t(cdiff, svm):0, ipid);
252 else
253 dump_credit(time, svm);
254 }
255 }
257 static struct vm* sched_credit_schedule(int time, int pid)
258 {
259 struct sched_vm *svm;
260 struct vm *next, *prev;
261 int timer;
263 printf("%s: time %d pid %d\n",
264 __func__, time, pid);
265 prev = current(pid);
267 if ( prev )
268 {
269 printf(" current v%d\n", prev->vid);
270 svm = sched_priv.vms + prev->vid;
272 burn_credit(svm, time);
274 if ( svm->v->runstate == RUNSTATE_RUNNING )
275 {
276 printf(" adding to runqueue\n");
277 runq_insert(svm);
278 }
279 }
281 /* Take guy on front of runqueue, set new timer */
282 if ( list_empty(&sched_priv.runq) )
283 {
284 printf(" No runnable entities\n");
285 return NULL;
286 }
288 svm = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
290 list_del_init(&svm->runq_elem);
292 next = svm->v;
294 if ( svm->credit <= CREDIT_RESET )
295 {
296 printf(" vid %d credit %c, resetting credit at time %d\n",
297 svm->vid,
298 svm->credit,
299 time);
300 reset_credit(time);
301 }
303 dump_credit(time, svm);
304 svm->start_time = time;
306 timer = calc_timer(svm);
308 sim_sched_timer(timer, pid);
310 printf(" next: v%d\n", next->vid);
312 return next;
313 }
315 struct scheduler sched_credit03 =
316 {
317 .name="credit03",
318 .desc="c02 + implement weight + clip-and-add on reset",
319 .ops = {
320 .sched_init = sched_credit_init,
321 .vm_init = sched_credit_vm_init,
322 .wake = sched_credit_wake,
323 .schedule = sched_credit_schedule
324 }
325 };