gdunlap/sched-sim.hg

view sched_credit01.c @ 7:e274ac3f81ff

c01: Allow wake to preempt running processes
author George Dunlap <gdunlap@xensource.com>
date Tue Oct 20 18:00:17 2009 +0100 (2009-10-20)
parents 18f3d6e25ffc
children a0da04ca71ee
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;
43 void reset_credit(int time)
44 {
45 int i;
46 for ( i=0; i<=sched_priv.max_vm; i++)
47 {
48 sched_priv.vms[i].credit = CREDIT_INIT;
49 sched_priv.vms[i].start_time = time;
50 }
51 /* No need to resort runq, as everyone's credit is now zero */
52 }
54 void dump_credit(int time, struct sched_vm *svm)
55 {
56 printf("credit v%d %d %d\n", svm->vid, time, svm->credit);
57 }
59 void burn_credit(struct sched_vm *svm, int time)
60 {
61 ASSERT(time >= svm->start_time);
63 svm->credit -= (time - svm->start_time);
64 svm->start_time = time;
66 dump_credit(time, svm);
67 }
69 int calc_timer(struct sched_vm *svm)
70 {
71 int time = MAX_TIMER;
73 if ( time > svm->credit )
74 time = svm->credit;
75 #if 0
76 if ( !list_empty(&sched_priv.runq) )
77 {
78 struct sched_vm *sq = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
80 ASSERT(svm->credit >= sq->credit);
82 if ( (svm->credit - sq->credit) < time )
83 time = (svm->credit - sq->credit);
84 }
86 #endif
88 if ( time < MIN_TIMER )
89 time = MIN_TIMER;
90 return time;
91 }
93 void runq_insert(struct sched_vm *svm)
94 {
95 struct list_head *iter;
96 int pos = 0;
98 list_for_each( iter, &sched_priv.runq )
99 {
100 struct sched_vm * iter_svm;
102 iter_svm = list_entry(iter, struct sched_vm, runq_elem);
104 if ( svm->credit > iter_svm->credit )
105 {
106 printf(" p%d v%d\n",
107 pos,
108 iter_svm->vid);
109 break;
110 }
111 pos++;
112 }
114 list_add_tail(&svm->runq_elem, iter);
115 }
117 static void sched_credit_init(void)
118 {
119 printf("%s()\n", __func__);
120 INIT_LIST_HEAD(&sched_priv.runq);
121 sched_priv.max_vm=0;
122 }
124 static void sched_credit_vm_init(int vid)
125 {
126 struct sched_vm *svm;
128 printf("%s: vm %d\n", __func__, vid);
130 if ( vid > MAX_VMS )
131 {
132 fprintf(stderr, "vid %d > MAX_VMS %d!\n", vid, MAX_VMS);
133 exit(1);
134 }
136 svm = sched_priv.vms + vid;
138 INIT_LIST_HEAD(&svm->runq_elem);
140 svm->vid = vid;
141 svm->v = vm_from_vid(vid);
143 svm->credit = CREDIT_INIT;
144 svm->weight = 1;
145 svm->start_time = 0;
147 if ( vid > sched_priv.max_vm )
148 sched_priv.max_vm = vid;
149 }
151 static void sched_credit_wake(int time, int vid)
152 {
153 struct vm *v;
154 struct sched_vm *svm;
156 v = vm_from_vid(vid);
158 printf("%s: time %d vid %d\n",
159 __func__, time, v->vid);
161 svm = sched_priv.vms + v->vid;
163 ASSERT(list_empty(&svm->runq_elem));
165 runq_insert(svm);
167 /* Scan for either:
168 * + an idle cpu to wake up, or
169 * + if there are cpus with lower credits, the lowest one
170 */
171 {
172 int i, ipid=-1, lowest = svm->credit;
175 for ( i=0; i<P.count; i++ )
176 {
177 if ( P.pcpus[i].idle )
178 {
179 printf(" %s: p%d idle, waking\n", __func__, i);
180 ipid=i;
181 break;
182 }
183 else if ( P.pcpus[i].current )
184 {
185 struct vm* ovm = P.pcpus[i].current;
186 int ovid = ovm->vid;
187 struct sched_vm *osvm = sched_priv.vms + ovid;
189 /* Update credits of currently running VM */
190 burn_credit(osvm, time);
192 if ( osvm->credit < lowest )
193 {
194 ipid = i;
195 lowest = osvm->credit;
196 }
197 }
199 }
201 if ( ipid >= 0 )
202 sim_sched_timer(0, ipid);
203 else
204 dump_credit(time, svm);
205 }
206 }
208 static struct vm* sched_credit_schedule(int time, int pid)
209 {
210 struct sched_vm *svm;
211 struct vm *next, *prev;
212 int timer;
214 printf("%s: time %d pid %d\n",
215 __func__, time, pid);
216 prev = current(pid);
218 if ( prev )
219 {
220 printf(" current v%d\n", prev->vid);
221 svm = sched_priv.vms + prev->vid;
223 burn_credit(svm, time);
225 if ( svm->v->runstate == RUNSTATE_RUNNING )
226 {
227 printf(" adding to runqueue\n");
228 runq_insert(svm);
229 }
230 }
232 /* Take guy on front of runqueue, set new timer */
233 if ( list_empty(&sched_priv.runq) )
234 {
235 printf(" No runnable entities\n");
236 return NULL;
237 }
239 svm = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
241 list_del_init(&svm->runq_elem);
243 next = svm->v;
245 if ( svm->credit <= CREDIT_RESET )
246 {
247 printf(" vid %d credit %c, resetting credit at time %d\n",
248 svm->vid,
249 svm->credit,
250 time);
251 reset_credit(time);
252 }
254 dump_credit(time, svm);
255 svm->start_time = time;
257 timer = calc_timer(svm);
259 sim_sched_timer(timer, pid);
261 printf(" next: v%d\n", next->vid);
263 return next;
264 }
266 struct scheduler sched_credit01 =
267 {
268 .name="credit01",
269 .desc="Zero-start, burn based on weight, reset to zero at negative credit",
270 .ops = {
271 .sched_init = sched_credit_init,
272 .vm_init = sched_credit_vm_init,
273 .wake = sched_credit_wake,
274 .schedule = sched_credit_schedule
275 }
276 };