gdunlap/sched-sim.hg

view simulator.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 f289f886cbcc
children
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"
11 #include "sched.h"
12 #include "options.h"
14 FILE *warn;
16 enum event_type {
17 EVT_BLOCK,
18 EVT_WAKE,
19 EVT_TIMER,
20 EVT_MAX
21 };
23 char *event_name[EVT_MAX] = {
24 [EVT_BLOCK]="block",
25 [EVT_WAKE] ="wake ",
26 [EVT_TIMER]="timer"
27 };
29 struct event {
30 struct list_head event_list;
31 enum event_type type;
32 int time;
33 int param; /* Usually VM ID */
34 };
36 char * state_name[STATE_MAX] = {
37 [STATE_RUN]= "run ",
38 [STATE_PREEMPT]="preempt",
39 [STATE_WAKE]= "wake ",
40 [STATE_BLOCK]= "block ",
41 };
43 struct {
44 int now;
45 struct list_head events;
46 struct list_head *timer;
47 const struct sched_ops *sched_ops;
48 } sim;
51 #ifndef VM_DATA_PUBLIC
52 struct global_vm_data {
53 int count;
54 struct vm vms[MAX_VMS];
55 };
56 #endif
57 struct global_vm_data V;
59 extern struct scheduler sched_rr;
60 extern struct scheduler sched_credit01;
61 extern struct scheduler sched_credit02;
62 extern struct scheduler sched_credit03;
63 int default_scheduler = 0;
64 struct scheduler *schedulers[] =
65 {
66 &sched_rr,
67 &sched_credit01,
68 &sched_credit02,
69 &sched_credit03,
70 NULL
71 };
73 /* Options */
75 struct global_pcpu_data P;
77 /* Sim list interface */
78 /* NB: Caller must free if they're not going to use it! */
79 #define list_event(_l) (list_entry((_l), struct event, event_list))
81 struct event* sim_remove_event(int type, int param)
82 {
83 struct event* ret = NULL;
84 struct list_head *pos, *tmp;
86 /* Look for an event that matches this one and remove it */
87 list_for_each_safe(pos, tmp, &sim.events)
88 {
89 struct event *tevt = list_event(pos);
90 if ( tevt->type == type
91 && tevt->param == param )
92 {
93 list_del(pos);
94 ret = tevt;
95 break;
96 }
97 }
99 return ret;
100 }
102 void sim_insert_event(int time, int type, int param, int reset)
103 {
104 struct list_head *pos = NULL;
105 struct event *evt=NULL;
107 ASSERT(time >= sim.now);
109 if ( reset )
110 evt=sim_remove_event(type, param);
112 if ( !evt )
113 evt = (struct event *)malloc(sizeof(*evt));
115 evt->time = time;
116 evt->type = type;
117 evt->param = param;
119 printf(" [insert t%d %s param%d]\n",
120 evt->time, event_name[evt->type], evt->param);
122 INIT_LIST_HEAD(&evt->event_list);
124 list_for_each(pos, &sim.events)
125 {
126 if ( list_event(pos)->time > evt->time )
127 break;
128 }
129 list_add_tail(&evt->event_list, pos);
130 }
132 struct event sim_next_event(void)
133 {
134 struct event *evt;
135 struct list_head *next;
137 ASSERT(!list_empty(&sim.events));
139 next=sim.events.next;
141 list_del(next);
143 evt=list_event(next);
145 printf("%d: evt %s param%d\n",
146 evt->time, event_name[evt->type], evt->param);
148 free(evt);
150 /* XXX */
151 return *evt;
152 }
154 /*
155 * VM simulation
156 */
157 void vm_next_event(struct vm *v)
158 {
159 v->phase_index = ( v->phase_index + 1 ) % v->workload->phase_count;
161 v->e = v->workload->list + v->phase_index;
162 }
164 struct vm* vm_from_vid(int vid)
165 {
166 if ( vid >= V.count )
167 {
168 fprintf(stderr, "%s: v%d >= V.count %d!\n",
169 __func__, vid, V.count);
170 exit(1);
171 }
173 return V.vms + vid;
174 }
176 void vm_block(int now, struct vm *v)
177 {
178 ASSERT(v->e->type == PHASE_RUN);
179 v->time_this_phase += now - v->state_start_time;
180 printf("%s: v%d time_this_phase %d (evt %d)\n",
181 __func__, v->vid, v->time_this_phase, v->e->time);
183 ASSERT(v->time_this_phase == v->e->time);
185 vm_next_event(v);
187 ASSERT(v->e->type == PHASE_BLOCK);
189 sim_insert_event(now + v->e->time, EVT_WAKE, v->vid, 0);
190 v->time_this_phase = 0;
191 v->was_preempted = 0;
192 }
194 /* Called when wake event happens; increment timer and reset state */
195 void vm_wake(int now, struct vm *v)
196 {
197 ASSERT(v->e->type == PHASE_BLOCK);
198 ASSERT(v->time_this_phase == 0);
200 v->time_this_phase = now - v->state_start_time;
202 if ( now != 0 )
203 ASSERT(v->time_this_phase == v->e->time);
205 vm_next_event(v);
207 v->time_this_phase = 0;
208 }
210 /* Called when actually starting to run; make block event and set state */
211 void vm_run(int now, struct vm *v)
212 {
213 ASSERT(v->e->type == PHASE_RUN);
214 ASSERT(v->time_this_phase <= v->e->time);
216 sim_insert_event(now + v->e->time - v->time_this_phase, EVT_BLOCK, v->vid, 0);
217 v->state_start_time = now;
218 }
220 /* Preempt: Remove block event, update amount of runtime (so that when it runs again we can accurately
221 * generate a new block event) */
222 void vm_preempt(int now, struct vm *v)
223 {
224 struct event* evt;
226 v->time_this_phase += now - v->state_start_time;
227 printf("%s: v%d time_this_phase %d (evt %d)\n",
228 __func__, v->vid, v->time_this_phase, v->e->time);
230 ASSERT( v->time_this_phase <= v->e->time );
232 /* Only remove block event if we still have more runtime left */
233 if ( ( evt = sim_remove_event(EVT_BLOCK, v->vid) ) )
234 free(evt);
236 v->was_preempted = 1;
237 }
240 /* Callbacks the scheduler may make */
241 void sim_sched_timer(int time, int pid)
242 {
243 if ( time < 0 )
244 {
245 fprintf(stderr, "%s: Time %d < 0!\n",
246 __func__, time);
247 abort();
248 }
250 if ( pid >= P.count )
251 {
252 fprintf(stderr, "%s: p%d >= P.count %d\n",
253 __func__, pid, P.count);
254 exit(1);
255 }
257 if ( P.pcpus[pid].idle )
258 {
259 P.pcpus[pid].idle = 0;
260 P.idle--;
261 }
262 sim_insert_event(sim.now + time, EVT_TIMER, pid, 1);
263 }
265 void dump_running(int now, struct vm *v)
266 {
267 printf("runtime v%d %d %llu\n",
268 v->vid,
269 now,
270 v->stats.state[RUNSTATE_RUNNING].cycles);
271 }
273 void sim_runstate_change(int now, struct vm *v, int new_runstate)
274 {
275 int ostate, nstate;
276 int stime = now - v->state_start_time;
278 /* Valid transitions:
279 * + R->A (preemption): remove block event
280 * + R->B (block) : Insert wake event
281 * + A->R (run) : Insert block event
282 * + B->A (wake) : No action necessary
283 */
285 switch ( v->runstate )
286 {
287 case RUNSTATE_RUNNING:
288 ostate = STATE_RUN;
289 break;
290 case RUNSTATE_RUNNABLE:
291 if ( v->was_preempted )
292 ostate = STATE_PREEMPT;
293 else
294 ostate = STATE_WAKE;
295 break;
296 case RUNSTATE_BLOCKED:
297 ostate = STATE_BLOCK;
298 break;
299 }
301 update_cycles(&v->stats.state[ostate], stime);
303 if ( v->runstate == RUNSTATE_RUNNING
304 || new_runstate == RUNSTATE_RUNNING )
305 dump_running(now, v);
308 if ( v->runstate == RUNSTATE_RUNNING
309 && new_runstate == RUNSTATE_RUNNABLE )
310 {
311 nstate = STATE_PREEMPT;
312 vm_preempt(now, v);
313 }
314 else if ( v->runstate == RUNSTATE_RUNNING
315 && new_runstate == RUNSTATE_BLOCKED )
316 {
317 nstate = STATE_BLOCK;
318 vm_block(now, v);
319 }
320 else if ( v->runstate == RUNSTATE_RUNNABLE
321 && new_runstate == RUNSTATE_RUNNING )
322 {
323 nstate = STATE_RUN;
324 vm_run(now, v);
325 }
326 else if ( v->runstate == RUNSTATE_BLOCKED
327 && new_runstate == RUNSTATE_RUNNABLE )
328 {
329 nstate = STATE_WAKE;
330 vm_wake(now, v);
331 }
332 else
333 goto unexpected_transition;
335 printf("%d: v%d %s %d -> %s\n",
336 now, v->vid, state_name[ostate], stime, state_name[nstate]);
338 v->runstate = new_runstate;
339 v->state_start_time = now;
341 return;
343 unexpected_transition:
344 fprintf(stderr, "Unexpected transition for vm %d: %d->%d\n",
345 v->vid,
346 v->runstate,
347 new_runstate);
348 exit(1);
349 }
351 /*
352 * Main loop
353 */
354 void simulate(void)
355 {
356 while ( sim.now < opt.time_limit )
357 {
358 /* Take next event off list */
359 struct event evt;
361 evt = sim_next_event();
363 sim.now = evt.time;
365 switch(evt.type)
366 {
367 case EVT_WAKE:
368 {
369 struct vm *v = vm_from_vid(evt.param);
370 ASSERT(v->processor == -1);
371 sim_runstate_change(sim.now, v, RUNSTATE_RUNNABLE);
372 sim.sched_ops->wake(sim.now, v->vid);
373 }
374 break;
375 case EVT_BLOCK:
376 {
377 struct vm *v = vm_from_vid(evt.param);
379 ASSERT(v->processor != -1);
380 ASSERT(v->processor <= P.count);
382 sim_runstate_change(sim.now, v, RUNSTATE_BLOCKED);
384 evt.param = v->processor; /* FIXME */
385 }
386 /* FALL-THRU */
387 case EVT_TIMER:
388 {
389 struct vm *prev, *next;
390 int pid = evt.param;
392 ASSERT(pid < P.count);
394 prev = P.pcpus[pid].current;
396 next = sim.sched_ops->schedule(sim.now, pid);
398 if ( prev && prev != next )
399 {
400 prev->processor = -1;
401 if( prev->runstate != RUNSTATE_BLOCKED )
402 sim_runstate_change(sim.now, prev, RUNSTATE_RUNNABLE);
403 }
406 P.pcpus[pid].current = next;
407 if ( next )
408 {
409 if ( next != prev )
410 {
411 sim_runstate_change(sim.now, next, RUNSTATE_RUNNING);
412 next->processor = pid;
413 }
414 }
415 else
416 {
417 if ( P.pcpus[pid].idle )
418 {
419 fprintf(stderr, "Strange, pid %d already idle!\n",
420 pid);
421 abort();
422 }
424 /* If the pcpu is going idle, clear all timers from it */
425 sim_remove_event(EVT_TIMER, pid);
427 P.pcpus[pid].idle = 1;
428 P.idle++;
429 }
430 }
431 break;
432 default:
433 fprintf(stderr, "Unexpected event type: %d\n", evt.type);
434 exit(1);
435 break;
436 }
437 }
438 }
440 void init(void)
441 {
442 int vid, i;
443 const struct workload *w;
445 /* Initialize simulation variables */
446 sim.now=0;
447 sim.timer=NULL;
448 INIT_LIST_HEAD(&sim.events);
449 sim.sched_ops = &opt.scheduler->ops;
451 /* Initialize pcpus */
452 P.count = opt.pcpu_count;
453 P.idle = 0;
454 for ( i=0; i<P.count; i++ )
455 {
456 P.pcpus[i].pid = i;
457 P.pcpus[i].idle = 1;
458 P.idle++;
459 P.pcpus[i].current = NULL;
460 }
462 /* Initialize scheduler */
463 sim.sched_ops->sched_init();
465 /* Initialize vms */
466 w=opt.workload;
467 V.count = 0;
468 for ( vid=0; vid<w->vm_count; vid++)
469 {
470 struct vm *v = V.vms+vid;
472 v->vid = vid;
473 v->runstate = RUNSTATE_BLOCKED;
474 v->processor = -1;
475 v->private = NULL;
477 v->state_start_time = 0;
478 v->time_this_phase = 0;
481 v->phase_index = -1;
482 v->e = NULL;
483 v->workload = w->vm_workloads+vid;
485 V.count++;
487 sim.sched_ops->vm_init(vid);
488 }
490 /* Set VM starting conditions */
491 for ( vid=0; vid<V.count; vid++)
492 {
493 struct vm *v = V.vms+vid;
495 switch(v->workload->list[0].type)
496 {
497 case PHASE_RUN:
498 v->phase_index = v->workload->phase_count - 1;
499 v->e = v->workload->list + v->phase_index;
501 sim_insert_event(sim.now, EVT_WAKE, v->vid, 0);
502 v->state_start_time = sim.now;
503 v->time_this_phase = 0;
504 break;
505 case PHASE_BLOCK:
506 v->phase_index = 0;
507 v->e = v->workload->list;
509 sim_insert_event(sim.now + v->e->time, EVT_WAKE, v->vid, 0);
510 v->state_start_time = sim.now;
511 v->time_this_phase = 0;
512 break;
513 }
514 }
515 }
517 void report(void)
518 {
519 int i, j;
521 for ( i=0; i<V.count; i++ )
522 {
523 struct vm *v = V.vms + i;
525 printf("VM %d\n", i);
526 for ( j = 0; j < STATE_MAX ; j++ )
527 {
528 char s[128];
529 snprintf(s, 128, " %s", state_name[j]);
530 print_cycle_summary(&v->stats.state[j], sim.now, s);
531 }
532 }
533 }
535 int main(int argc, char * argv[])
536 {
537 warn = stdout;
539 parse_options(argc, argv);
541 /* Setup simulation */
542 init();
544 /* Run simulation */
545 simulate();
546 /* Report statistics */
547 report();
548 }