gdunlap/sched-sim.hg

view simulator.c @ 0:d27bb3c56e71

Inital commit.
author George Dunlap <gdunlap@xensource.com>
date Tue Oct 13 16:06:36 2009 +0100 (2009-10-13)
parents
children ec2d50e41437
line source
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <assert.h>
5 #define ASSERT assert
7 #include "stats.h"
8 #include "list.h"
9 #include "sim.h"
10 #include "workload.h"
12 FILE *warn;
14 enum event_type {
15 EVT_BLOCK,
16 EVT_WAKE,
17 EVT_TIMER,
18 EVT_MAX
19 };
21 char *event_name[EVT_MAX] = {
22 [EVT_BLOCK]="block",
23 [EVT_WAKE] ="wake ",
24 [EVT_TIMER]="timer"
25 };
27 struct event {
28 struct list_head event_list;
29 enum event_type type;
30 int time;
31 int param; /* Usually VM ID */
32 };
34 char * state_name[STATE_MAX] = {
35 [STATE_RUN]= "run ",
36 [STATE_PREEMPT]="preempt",
37 [STATE_WAKE]= "wake ",
38 [STATE_BLOCK]= "block ",
39 };
41 struct {
42 int now;
43 struct list_head events;
44 struct list_head *timer;
45 const struct sched_ops *sched_ops;
46 } sim;
49 struct {
50 int count;
51 struct vm vms[MAX_VMS];
52 } V;
54 extern struct scheduler sched_rr;
55 int default_scheduler = 0;
56 struct scheduler *schedulers[] =
57 {
58 &sched_rr,
59 };
61 /* Options */
62 struct {
63 int time_limit;
64 int pcpu_count;
65 const struct workload * workload;
66 const struct scheduler * scheduler;
67 } opt = {
68 .time_limit = 100000,
69 .pcpu_count = 1,
70 .workload = NULL,
71 };
73 struct global_pcpu_data P;
75 /* Sim list interface */
76 /* NB: Caller must free if they're not going to use it! */
77 #define list_event(_l) (list_entry((_l), struct event, event_list))
79 struct event* sim_remove_event(int type, int param)
80 {
81 struct event* ret = NULL;
82 struct list_head *pos, *tmp;
84 /* Look for an event that matches this one and remove it */
85 list_for_each_safe(pos, tmp, &sim.events)
86 {
87 struct event *tevt = list_event(pos);
88 if ( tevt->type == type
89 && tevt->param == param )
90 {
91 list_del(pos);
92 ret = tevt;
93 break;
94 }
95 }
97 return ret;
98 }
100 void sim_insert_event(int time, int type, int param, int reset)
101 {
102 struct list_head *pos = NULL;
103 struct event *evt=NULL;
105 ASSERT(time >= sim.now);
107 if ( reset )
108 evt=sim_remove_event(type, param);
110 if ( !evt )
111 evt = (struct event *)malloc(sizeof(*evt));
113 printf(" [insert t%d %s param%d]\n",
114 evt->time, event_name[evt->type], evt->param);
116 evt->time = time;
117 evt->type = type;
118 evt->param = param;
120 INIT_LIST_HEAD(&evt->event_list);
122 list_for_each(pos, &sim.events)
123 {
124 if ( list_event(pos)->time > evt->time )
125 break;
126 }
127 list_add_tail(&evt->event_list, pos);
128 }
130 struct event sim_next_event(void)
131 {
132 struct event *evt;
133 struct list_head *next;
135 ASSERT(!list_empty(&sim.events));
137 next=sim.events.next;
139 list_del(next);
141 evt=list_event(next);
143 printf("%d: evt %s param%d\n",
144 evt->time, event_name[evt->type], evt->param);
146 free(evt);
148 /* XXX */
149 return *evt;
150 }
152 /*
153 * VM simulation
154 */
155 void vm_next_event(struct vm *v)
156 {
157 v->phase_index = ( v->phase_index + 1 ) % v->workload->phase_count;
159 v->e = v->workload->list + v->phase_index;
160 }
162 struct vm* vm_from_vid(int vid)
163 {
164 ASSERT(vid < V.count);
166 return V.vms + vid;
167 }
169 void vm_block(int now, struct vm *v)
170 {
171 ASSERT(v->e->type == PHASE_RUN);
172 v->time_this_phase += now - v->state_start_time;
173 printf("%s: v%d time_this_phase %d\n",
174 __func__, v->vid, v->time_this_phase);
176 ASSERT(v->time_this_phase == v->e->time);
178 vm_next_event(v);
180 ASSERT(v->e->type == PHASE_BLOCK);
182 sim_insert_event(now + v->e->time, EVT_WAKE, v->vid, 0);
183 v->time_this_phase = 0;
184 v->was_preempted = 0;
185 }
187 /* Called when wake event happens; increment timer and reset state */
188 void vm_wake(int now, struct vm *v)
189 {
190 ASSERT(v->e->type == PHASE_BLOCK);
191 ASSERT(v->time_this_phase == 0);
193 v->time_this_phase = now - v->state_start_time;
195 if ( now != 0 )
196 ASSERT(v->time_this_phase == v->e->time);
198 vm_next_event(v);
200 v->time_this_phase = 0;
201 }
203 /* Called when actually starting to run; make block event and set state */
204 void vm_run(int now, struct vm *v)
205 {
206 ASSERT(v->e->type == PHASE_RUN);
207 ASSERT(v->time_this_phase < v->e->time);
209 sim_insert_event(now + v->e->time - v->time_this_phase, EVT_BLOCK, v->vid, 0);
210 v->state_start_time = now;
211 }
213 /* Preempt: Remove block event, update amount of runtime (so that when it runs again we can accurately
214 * generate a new block event) */
215 void vm_preempt(int now, struct vm *v)
216 {
217 struct event* evt;
219 if ( ( evt = sim_remove_event(EVT_BLOCK, v->vid) ) )
220 free(evt);
222 v->time_this_phase += now - v->state_start_time;
223 printf("%s: v%d time_this_phase %d\n",
224 __func__, v->vid, v->time_this_phase);
226 ASSERT(v->time_this_phase < v->e->time);
228 v->was_preempted = 1;
229 }
232 /* Callbacks the scheduler may make */
233 void sim_sched_timer(int time, int pid)
234 {
235 sim_insert_event(sim.now + time, EVT_TIMER, pid, 1);
236 }
238 void sim_runstate_change(int now, struct vm *v, int new_runstate)
239 {
240 int ostate, nstate;
241 int stime = now - v->state_start_time;
243 /* Valid transitions:
244 * + R->A (preemption): remove block event
245 * + R->B (block) : Insert wake event
246 * + A->R (run) : Insert block event
247 * + B->A (wake) : No action necessary
248 */
250 switch ( v->runstate )
251 {
252 case RUNSTATE_RUNNING:
253 ostate = STATE_RUN;
254 break;
255 case RUNSTATE_RUNNABLE:
256 if ( v->was_preempted )
257 ostate = STATE_PREEMPT;
258 else
259 ostate = STATE_WAKE;
260 break;
261 case RUNSTATE_BLOCKED:
262 ostate = STATE_BLOCK;
263 break;
264 }
266 update_cycles(&v->stats.state[ostate], stime);
269 if ( v->runstate == RUNSTATE_RUNNING
270 && new_runstate == RUNSTATE_RUNNABLE )
271 {
272 nstate = STATE_PREEMPT;
273 vm_preempt(now, v);
274 }
275 else if ( v->runstate == RUNSTATE_RUNNING
276 && new_runstate == RUNSTATE_BLOCKED )
277 {
278 nstate = STATE_BLOCK;
279 vm_block(now, v);
280 }
281 else if ( v->runstate == RUNSTATE_RUNNABLE
282 && new_runstate == RUNSTATE_RUNNING )
283 {
284 nstate = STATE_RUN;
285 vm_run(now, v);
286 }
287 else if ( v->runstate == RUNSTATE_BLOCKED
288 && new_runstate == RUNSTATE_RUNNABLE )
289 {
290 nstate = STATE_WAKE;
291 vm_wake(now, v);
292 }
293 else
294 goto unexpected_transition;
296 printf("%d: v%d %s %d -> %s\n",
297 now, v->vid, state_name[ostate], stime, state_name[nstate]);
299 v->runstate = new_runstate;
300 v->state_start_time = now;
302 return;
304 unexpected_transition:
305 fprintf(stderr, "Unexpected transition for vm %d: %d->%d\n",
306 v->vid,
307 v->runstate,
308 new_runstate);
309 exit(1);
310 }
312 /*
313 * Main loop
314 */
315 void simulate(void)
316 {
317 while ( sim.now < opt.time_limit )
318 {
319 /* Take next event off list */
320 struct event evt;
322 evt = sim_next_event();
324 sim.now = evt.time;
326 switch(evt.type)
327 {
328 case EVT_WAKE:
329 {
330 struct vm *v = vm_from_vid(evt.param);
331 ASSERT(v->processor == -1);
332 sim_runstate_change(sim.now, v, RUNSTATE_RUNNABLE);
333 sim.sched_ops->wake(sim.now, v);
334 }
335 break;
336 case EVT_BLOCK:
337 {
338 struct vm *v = vm_from_vid(evt.param);
340 ASSERT(v->processor != -1);
341 ASSERT(v->processor <= P.count);
343 sim_runstate_change(sim.now, v, RUNSTATE_BLOCKED);
345 evt.param = v->processor; /* FIXME */
346 }
347 /* FALL-THRU */
348 case EVT_TIMER:
349 {
350 struct vm *prev, *next;
351 int pid = evt.param;
353 ASSERT(pid < P.count);
355 prev = P.pcpus[pid].current;
357 next = sim.sched_ops->schedule(sim.now, pid);
359 if ( prev && prev != next )
360 {
361 prev->processor = -1;
362 if( prev->runstate != RUNSTATE_BLOCKED )
363 sim_runstate_change(sim.now, prev, RUNSTATE_RUNNABLE);
364 }
366 sim_runstate_change(sim.now, next, RUNSTATE_RUNNING);
367 P.pcpus[pid].current = next;
368 next->processor = pid;
369 }
370 break;
371 default:
372 fprintf(stderr, "Unexpected event type: %d\n", evt.type);
373 exit(1);
374 break;
375 }
376 }
377 }
379 void init(void)
380 {
381 int vid, i;
382 const struct workload *w;
384 /* Initialize simulation variables */
385 sim.now=0;
386 sim.timer=NULL;
387 INIT_LIST_HEAD(&sim.events);
388 sim.sched_ops = &opt.scheduler->ops;
390 /* Initialize pcpus */
391 P.count = opt.pcpu_count;
392 for ( i=0; i<P.count; i++ )
393 {
394 P.pcpus[i].pid = i;
395 P.pcpus[i].current = NULL;
396 }
398 /* Initialize scheduler */
399 sim.sched_ops->sched_init();
401 /* Initialize vms */
402 w=opt.workload;
403 for ( vid=0; vid<w->vm_count; vid++)
404 {
405 struct vm *v = V.vms+vid;
407 v->vid = vid;
408 v->runstate = RUNSTATE_BLOCKED;
409 v->processor = -1;
410 v->private = NULL;
412 v->state_start_time = 0;
413 v->time_this_phase = 0;
416 v->phase_index = -1;
417 v->e = NULL;
418 v->workload = w->vm_workloads+vid;
420 V.count++;
422 sim.sched_ops->vm_init(vid);
423 }
425 /* Set VM starting conditions */
426 for ( vid=0; vid<V.count; vid++)
427 {
428 struct vm *v = V.vms+vid;
430 switch(v->workload->list[0].type)
431 {
432 case PHASE_RUN:
433 v->phase_index = v->workload->phase_count - 1;
434 v->e = v->workload->list + v->phase_index;
436 sim_insert_event(sim.now, EVT_WAKE, v->vid, 0);
437 v->state_start_time = sim.now;
438 v->time_this_phase = 0;
439 break;
440 case PHASE_BLOCK:
441 v->phase_index = 0;
442 v->e = v->workload->list;
444 sim_insert_event(sim.now + v->e->time, EVT_WAKE, v->vid, 0);
445 v->state_start_time = sim.now;
446 v->time_this_phase = 0;
447 break;
448 }
449 }
451 /* Insert initial scheduler timer */
452 for ( i=0; i<P.count; i++)
453 sim_insert_event(sim.now, EVT_TIMER, i, 1);
454 }
456 void report(void)
457 {
458 int i, j;
460 for ( i=0; i<V.count; i++ )
461 {
462 struct vm *v = V.vms + i;
464 printf("VM %d\n", i);
465 for ( j = 0; j < STATE_MAX ; j++ )
466 {
467 char s[128];
468 snprintf(s, 128, " %s", state_name[j]);
469 print_cycle_summary(&v->stats.state[j], sim.now, s);
470 }
471 }
472 }
474 int main(int argc, char * argv[])
475 {
476 warn = stdout;
478 /* Read opts, config file? */
479 if ( !opt.workload )
480 opt.workload = builtin_workloads+default_workload;
482 if ( !opt.scheduler )
483 opt.scheduler = schedulers[default_scheduler];
484 /* Setup simulation */
485 init();
487 /* Run simulation */
488 simulate();
489 /* Report statistics */
490 report();
491 }