gdunlap/sched-sim.hg

view sched_credit02.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_RESET 0
14 #define MAX_TIMER 200
15 #define MIN_TIMER 50
17 struct sched_vm {
18 struct list_head runq_elem;
19 struct vm *v;
21 int weight;
23 int credit;
24 int credit_per_min_timer; /* ? */
25 int start_time;
26 int vid;
27 };
29 struct {
30 struct list_head runq; /* Global run queue */
31 int max_vm;
32 struct sched_vm vms[MAX_VMS];
33 int ncpus;
35 int global_weight;
36 int scale_factor; /* ? */
38 int next_check;
39 } sched_priv;
41 /*
42 * - Everyone starts at fixed value
43 * - Burn credit at a constant rate
44 * - Insert in runq based on credit
45 * - Reset
46 * - Triggered when someone reaches zero
47 * - Sets everyone to init
48 * - Timeslice
49 * - Start with basic timeslice
50 * - Don't run for more credit than you have
51 * + Only run until your credit would equal next VM in runqueue
52 * - Never less than MIN_TIMER
53 */
55 static void reset_credit(int time)
56 {
57 int i;
58 for ( i=0; i<=sched_priv.max_vm; i++)
59 {
60 sched_priv.vms[i].credit = CREDIT_INIT;
61 sched_priv.vms[i].start_time = time;
62 }
63 /* No need to resort runq, as everyone's credit is now zero */
64 }
66 static void dump_credit(int time, struct sched_vm *svm)
67 {
68 printf("credit v%d %d %d\n", svm->vid, time, svm->credit);
69 }
71 static void burn_credit(struct sched_vm *svm, int time)
72 {
73 ASSERT(time >= svm->start_time);
75 svm->credit -= (time - svm->start_time);
76 svm->start_time = time;
78 dump_credit(time, svm);
79 }
81 static int calc_timer(struct sched_vm *svm)
82 {
83 int time;
85 /* Start with basic timeslice */
86 time = MAX_TIMER;
88 /* If we have less credit than that, cut it down to our credits */
89 if ( time > svm->credit )
90 time = svm->credit;
92 /* If there are other VMs on the runqueue, calculate
93 * how much time until our credit will equal their credit.
94 * If this is less than our timeslice, cut it down again. */
95 if ( !list_empty(&sched_priv.runq) )
96 {
97 struct sched_vm *sq = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
99 ASSERT(svm->credit >= sq->credit);
101 if ( time > (svm->credit - sq->credit) )
102 time = (svm->credit - sq->credit);
103 }
105 /* No matter what, always run for at least MIN_TIMER */
106 if ( time < MIN_TIMER )
107 time = MIN_TIMER;
109 return time;
110 }
112 static void runq_insert(struct sched_vm *svm)
113 {
114 struct list_head *iter;
115 int pos = 0;
117 list_for_each( iter, &sched_priv.runq )
118 {
119 struct sched_vm * iter_svm;
121 iter_svm = list_entry(iter, struct sched_vm, runq_elem);
123 if ( svm->credit > iter_svm->credit )
124 {
125 printf(" p%d v%d\n",
126 pos,
127 iter_svm->vid);
128 break;
129 }
130 pos++;
131 }
133 list_add_tail(&svm->runq_elem, iter);
134 }
136 static void sched_credit_init(void)
137 {
138 printf("%s()\n", __func__);
139 INIT_LIST_HEAD(&sched_priv.runq);
140 sched_priv.max_vm=0;
141 }
143 static void sched_credit_vm_init(int vid)
144 {
145 struct sched_vm *svm;
147 printf("%s: vm %d\n", __func__, vid);
149 if ( vid > MAX_VMS )
150 {
151 fprintf(stderr, "vid %d > MAX_VMS %d!\n", vid, MAX_VMS);
152 exit(1);
153 }
155 svm = sched_priv.vms + vid;
157 INIT_LIST_HEAD(&svm->runq_elem);
159 svm->vid = vid;
160 svm->v = vm_from_vid(vid);
162 svm->credit = CREDIT_INIT;
163 svm->weight = 1;
164 svm->start_time = 0;
166 if ( vid > sched_priv.max_vm )
167 sched_priv.max_vm = vid;
168 }
170 static void sched_credit_wake(int time, int vid)
171 {
172 struct vm *v;
173 struct sched_vm *svm;
175 v = vm_from_vid(vid);
177 printf("%s: time %d vid %d\n",
178 __func__, time, v->vid);
180 svm = sched_priv.vms + v->vid;
182 ASSERT(list_empty(&svm->runq_elem));
184 runq_insert(svm);
186 /* Scan for either:
187 * + an idle cpu to wake up, or
188 * + if there are cpus with lower credits, the lowest one
189 */
190 {
191 int i, ipid=-1, lowest = svm->credit;
194 for ( i=0; i<P.count; i++ )
195 {
196 if ( P.pcpus[i].idle )
197 {
198 printf(" %s: p%d idle, waking\n", __func__, i);
199 ipid=i;
200 break;
201 }
202 else if ( P.pcpus[i].current )
203 {
204 struct vm* ovm = P.pcpus[i].current;
205 int ovid = ovm->vid;
206 struct sched_vm *osvm = sched_priv.vms + ovid;
208 /* Update credits of currently running VM */
209 burn_credit(osvm, time);
211 if ( osvm->credit < lowest )
212 {
213 ipid = i;
214 lowest = osvm->credit;
215 }
216 }
218 }
220 if ( ipid >= 0 )
221 sim_sched_timer(0, ipid);
222 else
223 dump_credit(time, svm);
224 }
225 }
227 static struct vm* sched_credit_schedule(int time, int pid)
228 {
229 struct sched_vm *svm;
230 struct vm *next, *prev;
231 int timer;
233 printf("%s: time %d pid %d\n",
234 __func__, time, pid);
235 prev = current(pid);
237 if ( prev )
238 {
239 printf(" current v%d\n", prev->vid);
240 svm = sched_priv.vms + prev->vid;
242 burn_credit(svm, time);
244 if ( svm->v->runstate == RUNSTATE_RUNNING )
245 {
246 printf(" adding to runqueue\n");
247 runq_insert(svm);
248 }
249 }
251 /* Take guy on front of runqueue, set new timer */
252 if ( list_empty(&sched_priv.runq) )
253 {
254 printf(" No runnable entities\n");
255 return NULL;
256 }
258 svm = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
260 list_del_init(&svm->runq_elem);
262 next = svm->v;
264 if ( svm->credit <= CREDIT_RESET )
265 {
266 printf(" vid %d credit %c, resetting credit at time %d\n",
267 svm->vid,
268 svm->credit,
269 time);
270 reset_credit(time);
271 }
273 dump_credit(time, svm);
274 svm->start_time = time;
276 timer = calc_timer(svm);
278 sim_sched_timer(timer, pid);
280 printf(" next: v%d\n", next->vid);
282 return next;
283 }
285 struct scheduler sched_credit02 =
286 {
287 .name="credit02",
288 .desc="c01 + Preempt when your credit equals the next VM on the runqueue",
289 .ops = {
290 .sched_init = sched_credit_init,
291 .vm_init = sched_credit_vm_init,
292 .wake = sched_credit_wake,
293 .schedule = sched_credit_schedule
294 }
295 };