gdunlap/sched-sim.hg

view sched_credit01.c @ 16:cb624ff1d4fe

Clean up scheduler code to make it easier to see the differences
author George Dunlap <george.dunlap@eu.citrix.com>
date Fri Jul 16 11:55:39 2010 +0100 (2010-07-16)
parents a0da04ca71ee
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 100
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 * - Never less than MIN_TIMER
52 */
54 static void reset_credit(int time)
55 {
56 int i;
57 for ( i=0; i<=sched_priv.max_vm; i++)
58 {
59 sched_priv.vms[i].credit = CREDIT_INIT;
60 sched_priv.vms[i].start_time = time;
61 }
62 /* No need to resort runq, as everyone's credit is now zero */
63 }
65 static void dump_credit(int time, struct sched_vm *svm)
66 {
67 printf("credit v%d %d %d\n", svm->vid, time, svm->credit);
68 }
70 static void burn_credit(struct sched_vm *svm, int time)
71 {
72 ASSERT(time >= svm->start_time);
74 svm->credit -= (time - svm->start_time);
75 svm->start_time = time;
77 dump_credit(time, svm);
78 }
80 static int calc_timer(struct sched_vm *svm)
81 {
82 int time;
84 /* Start with basic timeslice */
85 time = MAX_TIMER;
87 /* If we have less credit than that, cut it down to our credits */
88 if ( time > svm->credit )
89 time = svm->credit;
91 /* No matter what, always run for at least MIN_TIMER */
92 if ( time < MIN_TIMER )
93 time = MIN_TIMER;
95 return time;
96 }
98 static void runq_insert(struct sched_vm *svm)
99 {
100 struct list_head *iter;
101 int pos = 0;
103 list_for_each( iter, &sched_priv.runq )
104 {
105 struct sched_vm * iter_svm;
107 iter_svm = list_entry(iter, struct sched_vm, runq_elem);
109 if ( svm->credit > iter_svm->credit )
110 {
111 printf(" p%d v%d\n",
112 pos,
113 iter_svm->vid);
114 break;
115 }
116 pos++;
117 }
119 list_add_tail(&svm->runq_elem, iter);
120 }
122 static void sched_credit_init(void)
123 {
124 printf("%s()\n", __func__);
125 INIT_LIST_HEAD(&sched_priv.runq);
126 sched_priv.max_vm=0;
127 }
129 static void sched_credit_vm_init(int vid)
130 {
131 struct sched_vm *svm;
133 printf("%s: vm %d\n", __func__, vid);
135 if ( vid > MAX_VMS )
136 {
137 fprintf(stderr, "vid %d > MAX_VMS %d!\n", vid, MAX_VMS);
138 exit(1);
139 }
141 svm = sched_priv.vms + vid;
143 INIT_LIST_HEAD(&svm->runq_elem);
145 svm->vid = vid;
146 svm->v = vm_from_vid(vid);
148 svm->credit = CREDIT_INIT;
149 svm->weight = 1;
150 svm->start_time = 0;
152 if ( vid > sched_priv.max_vm )
153 sched_priv.max_vm = vid;
154 }
156 static void sched_credit_wake(int time, int vid)
157 {
158 struct vm *v;
159 struct sched_vm *svm;
161 v = vm_from_vid(vid);
163 printf("%s: time %d vid %d\n",
164 __func__, time, v->vid);
166 svm = sched_priv.vms + v->vid;
168 ASSERT(list_empty(&svm->runq_elem));
170 runq_insert(svm);
172 /* Scan for either:
173 * + an idle cpu to wake up, or
174 * + if there are cpus with lower credits, the lowest one
175 */
176 {
177 int i, ipid=-1, lowest = svm->credit;
180 for ( i=0; i<P.count; i++ )
181 {
182 if ( P.pcpus[i].idle )
183 {
184 printf(" %s: p%d idle, waking\n", __func__, i);
185 ipid=i;
186 break;
187 }
188 else if ( P.pcpus[i].current )
189 {
190 struct vm* ovm = P.pcpus[i].current;
191 int ovid = ovm->vid;
192 struct sched_vm *osvm = sched_priv.vms + ovid;
194 /* Update credits of currently running VM */
195 burn_credit(osvm, time);
197 if ( osvm->credit < lowest )
198 {
199 ipid = i;
200 lowest = osvm->credit;
201 }
202 }
204 }
206 if ( ipid >= 0 )
207 sim_sched_timer(0, ipid);
208 else
209 dump_credit(time, svm);
210 }
211 }
213 static struct vm* sched_credit_schedule(int time, int pid)
214 {
215 struct sched_vm *svm;
216 struct vm *next, *prev;
217 int timer;
219 printf("%s: time %d pid %d\n",
220 __func__, time, pid);
221 prev = current(pid);
223 if ( prev )
224 {
225 printf(" current v%d\n", prev->vid);
226 svm = sched_priv.vms + prev->vid;
228 burn_credit(svm, time);
230 if ( svm->v->runstate == RUNSTATE_RUNNING )
231 {
232 printf(" adding to runqueue\n");
233 runq_insert(svm);
234 }
235 }
237 /* Take guy on front of runqueue, set new timer */
238 if ( list_empty(&sched_priv.runq) )
239 {
240 printf(" No runnable entities\n");
241 return NULL;
242 }
244 svm = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
246 list_del_init(&svm->runq_elem);
248 next = svm->v;
250 if ( svm->credit <= CREDIT_RESET )
251 {
252 printf(" vid %d credit %c, resetting credit at time %d\n",
253 svm->vid,
254 svm->credit,
255 time);
256 reset_credit(time);
257 }
259 dump_credit(time, svm);
260 svm->start_time = time;
262 timer = calc_timer(svm);
264 sim_sched_timer(timer, pid);
266 printf(" next: v%d\n", next->vid);
268 return next;
269 }
271 struct scheduler sched_credit01 =
272 {
273 .name="credit01",
274 .desc="Zero-start, reset to zero at negative credit",
275 .ops = {
276 .sched_init = sched_credit_init,
277 .vm_init = sched_credit_vm_init,
278 .wake = sched_credit_wake,
279 .schedule = sched_credit_schedule
280 }
281 };