gdunlap/sched-sim.hg

view simulator.c @ 1:ec2d50e41437

Handle multiple cpus.
author George Dunlap <gdunlap@xensource.com>
date Tue Oct 13 17:29:50 2009 +0100 (2009-10-13)
parents d27bb3c56e71
children 1d7310217c5a
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 #ifndef VM_DATA_PUBLIC
50 struct global_vm_data {
51 int count;
52 struct vm vms[MAX_VMS];
53 };
54 #endif
55 struct global_vm_data V;
57 extern struct scheduler sched_rr;
58 int default_scheduler = 0;
59 struct scheduler *schedulers[] =
60 {
61 &sched_rr,
62 };
64 /* Options */
65 struct {
66 int time_limit;
67 int pcpu_count;
68 const struct workload * workload;
69 const struct scheduler * scheduler;
70 } opt = {
71 .time_limit = 100000,
72 .pcpu_count = 2,
73 .workload = NULL,
74 };
76 struct global_pcpu_data P;
78 /* Sim list interface */
79 /* NB: Caller must free if they're not going to use it! */
80 #define list_event(_l) (list_entry((_l), struct event, event_list))
82 struct event* sim_remove_event(int type, int param)
83 {
84 struct event* ret = NULL;
85 struct list_head *pos, *tmp;
87 /* Look for an event that matches this one and remove it */
88 list_for_each_safe(pos, tmp, &sim.events)
89 {
90 struct event *tevt = list_event(pos);
91 if ( tevt->type == type
92 && tevt->param == param )
93 {
94 list_del(pos);
95 ret = tevt;
96 break;
97 }
98 }
100 return ret;
101 }
103 void sim_insert_event(int time, int type, int param, int reset)
104 {
105 struct list_head *pos = NULL;
106 struct event *evt=NULL;
108 ASSERT(time >= sim.now);
110 if ( reset )
111 evt=sim_remove_event(type, param);
113 if ( !evt )
114 evt = (struct event *)malloc(sizeof(*evt));
116 evt->time = time;
117 evt->type = type;
118 evt->param = param;
120 printf(" [insert t%d %s param%d]\n",
121 evt->time, event_name[evt->type], evt->param);
123 INIT_LIST_HEAD(&evt->event_list);
125 list_for_each(pos, &sim.events)
126 {
127 if ( list_event(pos)->time > evt->time )
128 break;
129 }
130 list_add_tail(&evt->event_list, pos);
131 }
133 struct event sim_next_event(void)
134 {
135 struct event *evt;
136 struct list_head *next;
138 ASSERT(!list_empty(&sim.events));
140 next=sim.events.next;
142 list_del(next);
144 evt=list_event(next);
146 printf("%d: evt %s param%d\n",
147 evt->time, event_name[evt->type], evt->param);
149 free(evt);
151 /* XXX */
152 return *evt;
153 }
155 /*
156 * VM simulation
157 */
158 void vm_next_event(struct vm *v)
159 {
160 v->phase_index = ( v->phase_index + 1 ) % v->workload->phase_count;
162 v->e = v->workload->list + v->phase_index;
163 }
165 struct vm* vm_from_vid(int vid)
166 {
167 if ( vid >= V.count )
168 {
169 fprintf(stderr, "%s: v%d >= V.count %d!\n",
170 __func__, vid, V.count);
171 exit(1);
172 }
174 return V.vms + vid;
175 }
177 void vm_block(int now, struct vm *v)
178 {
179 ASSERT(v->e->type == PHASE_RUN);
180 v->time_this_phase += now - v->state_start_time;
181 printf("%s: v%d time_this_phase %d\n",
182 __func__, v->vid, v->time_this_phase);
184 ASSERT(v->time_this_phase == v->e->time);
186 vm_next_event(v);
188 ASSERT(v->e->type == PHASE_BLOCK);
190 sim_insert_event(now + v->e->time, EVT_WAKE, v->vid, 0);
191 v->time_this_phase = 0;
192 v->was_preempted = 0;
193 }
195 /* Called when wake event happens; increment timer and reset state */
196 void vm_wake(int now, struct vm *v)
197 {
198 ASSERT(v->e->type == PHASE_BLOCK);
199 ASSERT(v->time_this_phase == 0);
201 v->time_this_phase = now - v->state_start_time;
203 if ( now != 0 )
204 ASSERT(v->time_this_phase == v->e->time);
206 vm_next_event(v);
208 v->time_this_phase = 0;
209 }
211 /* Called when actually starting to run; make block event and set state */
212 void vm_run(int now, struct vm *v)
213 {
214 ASSERT(v->e->type == PHASE_RUN);
215 ASSERT(v->time_this_phase < v->e->time);
217 sim_insert_event(now + v->e->time - v->time_this_phase, EVT_BLOCK, v->vid, 0);
218 v->state_start_time = now;
219 }
221 /* Preempt: Remove block event, update amount of runtime (so that when it runs again we can accurately
222 * generate a new block event) */
223 void vm_preempt(int now, struct vm *v)
224 {
225 struct event* evt;
227 if ( ( evt = sim_remove_event(EVT_BLOCK, v->vid) ) )
228 free(evt);
230 v->time_this_phase += now - v->state_start_time;
231 printf("%s: v%d time_this_phase %d\n",
232 __func__, v->vid, v->time_this_phase);
234 ASSERT(v->time_this_phase < v->e->time);
236 v->was_preempted = 1;
237 }
240 /* Callbacks the scheduler may make */
241 void sim_sched_timer(int time, int pid)
242 {
243 if ( pid >= P.count )
244 {
245 fprintf(stderr, "%s: p%d >= P.count %d\n",
246 __func__, pid, P.count);
247 exit(1);
248 }
250 if ( P.pcpus[pid].idle )
251 {
252 P.pcpus[pid].idle = 0;
253 P.idle--;
254 }
255 sim_insert_event(sim.now + time, EVT_TIMER, pid, 1);
256 }
258 void sim_runstate_change(int now, struct vm *v, int new_runstate)
259 {
260 int ostate, nstate;
261 int stime = now - v->state_start_time;
263 /* Valid transitions:
264 * + R->A (preemption): remove block event
265 * + R->B (block) : Insert wake event
266 * + A->R (run) : Insert block event
267 * + B->A (wake) : No action necessary
268 */
270 switch ( v->runstate )
271 {
272 case RUNSTATE_RUNNING:
273 ostate = STATE_RUN;
274 break;
275 case RUNSTATE_RUNNABLE:
276 if ( v->was_preempted )
277 ostate = STATE_PREEMPT;
278 else
279 ostate = STATE_WAKE;
280 break;
281 case RUNSTATE_BLOCKED:
282 ostate = STATE_BLOCK;
283 break;
284 }
286 update_cycles(&v->stats.state[ostate], stime);
289 if ( v->runstate == RUNSTATE_RUNNING
290 && new_runstate == RUNSTATE_RUNNABLE )
291 {
292 nstate = STATE_PREEMPT;
293 vm_preempt(now, v);
294 }
295 else if ( v->runstate == RUNSTATE_RUNNING
296 && new_runstate == RUNSTATE_BLOCKED )
297 {
298 nstate = STATE_BLOCK;
299 vm_block(now, v);
300 }
301 else if ( v->runstate == RUNSTATE_RUNNABLE
302 && new_runstate == RUNSTATE_RUNNING )
303 {
304 nstate = STATE_RUN;
305 vm_run(now, v);
306 }
307 else if ( v->runstate == RUNSTATE_BLOCKED
308 && new_runstate == RUNSTATE_RUNNABLE )
309 {
310 nstate = STATE_WAKE;
311 vm_wake(now, v);
312 }
313 else
314 goto unexpected_transition;
316 printf("%d: v%d %s %d -> %s\n",
317 now, v->vid, state_name[ostate], stime, state_name[nstate]);
319 v->runstate = new_runstate;
320 v->state_start_time = now;
322 return;
324 unexpected_transition:
325 fprintf(stderr, "Unexpected transition for vm %d: %d->%d\n",
326 v->vid,
327 v->runstate,
328 new_runstate);
329 exit(1);
330 }
332 /*
333 * Main loop
334 */
335 void simulate(void)
336 {
337 while ( sim.now < opt.time_limit )
338 {
339 /* Take next event off list */
340 struct event evt;
342 evt = sim_next_event();
344 sim.now = evt.time;
346 switch(evt.type)
347 {
348 case EVT_WAKE:
349 {
350 struct vm *v = vm_from_vid(evt.param);
351 ASSERT(v->processor == -1);
352 sim_runstate_change(sim.now, v, RUNSTATE_RUNNABLE);
353 sim.sched_ops->wake(sim.now, v);
354 }
355 break;
356 case EVT_BLOCK:
357 {
358 struct vm *v = vm_from_vid(evt.param);
360 ASSERT(v->processor != -1);
361 ASSERT(v->processor <= P.count);
363 sim_runstate_change(sim.now, v, RUNSTATE_BLOCKED);
365 evt.param = v->processor; /* FIXME */
366 }
367 /* FALL-THRU */
368 case EVT_TIMER:
369 {
370 struct vm *prev, *next;
371 int pid = evt.param;
373 ASSERT(pid < P.count);
375 prev = P.pcpus[pid].current;
377 next = sim.sched_ops->schedule(sim.now, pid);
379 if ( prev && prev != next )
380 {
381 prev->processor = -1;
382 if( prev->runstate != RUNSTATE_BLOCKED )
383 sim_runstate_change(sim.now, prev, RUNSTATE_RUNNABLE);
384 }
387 P.pcpus[pid].current = next;
388 if ( next )
389 {
390 if ( next != prev )
391 {
392 sim_runstate_change(sim.now, next, RUNSTATE_RUNNING);
393 next->processor = pid;
394 }
395 }
396 else
397 {
398 P.pcpus[pid].idle = 1;
399 P.idle++;
400 }
401 }
402 break;
403 default:
404 fprintf(stderr, "Unexpected event type: %d\n", evt.type);
405 exit(1);
406 break;
407 }
408 }
409 }
411 void init(void)
412 {
413 int vid, i;
414 const struct workload *w;
416 /* Initialize simulation variables */
417 sim.now=0;
418 sim.timer=NULL;
419 INIT_LIST_HEAD(&sim.events);
420 sim.sched_ops = &opt.scheduler->ops;
422 /* Initialize pcpus */
423 P.count = opt.pcpu_count;
424 P.idle = 0;
425 for ( i=0; i<P.count; i++ )
426 {
427 P.pcpus[i].pid = i;
428 P.pcpus[i].idle = 1;
429 P.idle++;
430 P.pcpus[i].current = NULL;
431 }
433 /* Initialize scheduler */
434 sim.sched_ops->sched_init();
436 /* Initialize vms */
437 w=opt.workload;
438 V.count = 0;
439 for ( vid=0; vid<w->vm_count; vid++)
440 {
441 struct vm *v = V.vms+vid;
443 v->vid = vid;
444 v->runstate = RUNSTATE_BLOCKED;
445 v->processor = -1;
446 v->private = NULL;
448 v->state_start_time = 0;
449 v->time_this_phase = 0;
452 v->phase_index = -1;
453 v->e = NULL;
454 v->workload = w->vm_workloads+vid;
456 V.count++;
458 sim.sched_ops->vm_init(vid);
459 }
461 /* Set VM starting conditions */
462 for ( vid=0; vid<V.count; vid++)
463 {
464 struct vm *v = V.vms+vid;
466 switch(v->workload->list[0].type)
467 {
468 case PHASE_RUN:
469 v->phase_index = v->workload->phase_count - 1;
470 v->e = v->workload->list + v->phase_index;
472 sim_insert_event(sim.now, EVT_WAKE, v->vid, 0);
473 v->state_start_time = sim.now;
474 v->time_this_phase = 0;
475 break;
476 case PHASE_BLOCK:
477 v->phase_index = 0;
478 v->e = v->workload->list;
480 sim_insert_event(sim.now + v->e->time, EVT_WAKE, v->vid, 0);
481 v->state_start_time = sim.now;
482 v->time_this_phase = 0;
483 break;
484 }
485 }
486 }
488 void report(void)
489 {
490 int i, j;
492 for ( i=0; i<V.count; i++ )
493 {
494 struct vm *v = V.vms + i;
496 printf("VM %d\n", i);
497 for ( j = 0; j < STATE_MAX ; j++ )
498 {
499 char s[128];
500 snprintf(s, 128, " %s", state_name[j]);
501 print_cycle_summary(&v->stats.state[j], sim.now, s);
502 }
503 }
504 }
506 int main(int argc, char * argv[])
507 {
508 warn = stdout;
510 /* Read opts, config file? */
511 if ( !opt.workload )
512 opt.workload = builtin_workloads+default_workload;
514 if ( !opt.scheduler )
515 opt.scheduler = schedulers[default_scheduler];
516 /* Setup simulation */
517 init();
519 /* Run simulation */
520 simulate();
521 /* Report statistics */
522 report();
523 }