# HG changeset patch # User George Dunlap # Date 1255979687 -3600 # Node ID 18f3d6e25ffc9a02ef947544e7043adcbc5133e8 # Parent f7c1a67cf976d3b5a1b3060a85bf07c06ec9b84a Add credit01 scheduler diff -r f7c1a67cf976 -r 18f3d6e25ffc Makefile --- a/Makefile Mon Oct 19 20:12:54 2009 +0100 +++ b/Makefile Mon Oct 19 20:14:47 2009 +0100 @@ -21,5 +21,5 @@ clean: %.o: %.c $(HDRS) Makefile $(CC) $(CFLAGS) -c -o $@ $< -simulator: simulator.o workloads.o sched_rr.o stats.o options.o +simulator: simulator.o workloads.o sched_rr.o stats.o options.o sched_credit01.o $(CC) $(CFLAGS) -o $@ $^ \ No newline at end of file diff -r f7c1a67cf976 -r 18f3d6e25ffc sched_credit01.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/sched_credit01.c Mon Oct 19 20:14:47 2009 +0100 @@ -0,0 +1,249 @@ +#include +#include +#include + +#define ASSERT assert + +#include "list.h" +#include "sim.h" + + +#define MAX_VMS 16 +#define CREDIT_INIT 500 +#define CREDIT_RESET 0 +#define MAX_TIMER 200 +#define MIN_TIMER 100 + +struct sched_vm { + struct list_head runq_elem; + struct vm *v; + + int weight; + + int credit; + int credit_per_min_timer; /* ? */ + int start_time; + int vid; +}; + +struct { + struct list_head runq; /* Global run queue */ + int max_vm; + struct sched_vm vms[MAX_VMS]; + int ncpus; + + int global_weight; + int scale_factor; /* ? */ + + int next_check; +} sched_priv; + + + +void reset_credit(int time) +{ + int i; + for ( i=0; i<=sched_priv.max_vm; i++) + { + sched_priv.vms[i].credit = CREDIT_INIT; + sched_priv.vms[i].start_time = time; + } + /* No need to resort runq, as everyone's credit is now zero */ +} + +void dump_credit(int time, struct sched_vm *svm) +{ + printf("credit v%d %d %d\n", svm->vid, time, svm->credit); +} + +void burn_credit(struct sched_vm *svm, int time) +{ + ASSERT(time >= svm->start_time); + + svm->credit -= (time - svm->start_time); + svm->start_time = time; + + dump_credit(time, svm); +} + +int calc_timer(struct sched_vm *svm) +{ + int time = MAX_TIMER; + + if ( time > svm->credit ) + time = svm->credit; +#if 0 + if ( !list_empty(&sched_priv.runq) ) + { + struct sched_vm *sq = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem); + + ASSERT(svm->credit >= sq->credit); + + if ( (svm->credit - sq->credit) < time ) + time = (svm->credit - sq->credit); + } + +#endif + + if ( time < MIN_TIMER ) + time = MIN_TIMER; + return time; +} + +void runq_insert(struct sched_vm *svm) +{ + struct list_head *iter; + int pos = 0; + + list_for_each( iter, &sched_priv.runq ) + { + struct sched_vm * iter_svm; + + iter_svm = list_entry(iter, struct sched_vm, runq_elem); + + if ( svm->credit > iter_svm->credit ) + { + printf(" p%d v%d\n", + pos, + iter_svm->vid); + break; + } + pos++; + } + + list_add_tail(&svm->runq_elem, iter); +} + +static void sched_credit_init(void) +{ + printf("%s()\n", __func__); + INIT_LIST_HEAD(&sched_priv.runq); + sched_priv.max_vm=0; +} + +static void sched_credit_vm_init(int vid) +{ + struct sched_vm *svm; + + printf("%s: vm %d\n", __func__, vid); + + if ( vid > MAX_VMS ) + { + fprintf(stderr, "vid %d > MAX_VMS %d!\n", vid, MAX_VMS); + exit(1); + } + + svm = sched_priv.vms + vid; + + INIT_LIST_HEAD(&svm->runq_elem); + + svm->vid = vid; + svm->v = vm_from_vid(vid); + + svm->credit = CREDIT_INIT; + svm->weight = 1; + svm->start_time = 0; + + if ( vid > sched_priv.max_vm ) + sched_priv.max_vm = vid; +} + +static void sched_credit_wake(int time, int vid) +{ + struct vm *v; + struct sched_vm *svm; + + v = vm_from_vid(vid); + + printf("%s: time %d vid %d\n", + __func__, time, v->vid); + + svm = sched_priv.vms + v->vid; + + ASSERT(list_empty(&svm->runq_elem)); + + runq_insert(svm); + + /* Never preempt on wake; only kick idle processors */ + if ( P.idle > 0 ) + { + int i; + + for ( i=0; ivid); + svm = sched_priv.vms + prev->vid; + + burn_credit(svm, time); + + if ( svm->v->runstate == RUNSTATE_RUNNING ) + { + printf(" adding to runqueue\n"); + runq_insert(svm); + } + } + + /* Take guy on front of runqueue, set new timer */ + if ( list_empty(&sched_priv.runq) ) + { + printf(" No runnable entities\n"); + return NULL; + } + + svm = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem); + + list_del_init(&svm->runq_elem); + + next = svm->v; + + if ( svm->credit <= CREDIT_RESET ) + { + printf(" vid %d credit %c, resetting credit at time %d\n", + svm->vid, + svm->credit, + time); + reset_credit(time); + } + + dump_credit(time, svm); + svm->start_time = time; + + timer = calc_timer(svm); + + sim_sched_timer(timer, pid); + + printf(" next: v%d\n", next->vid); + + return next; +} + +struct scheduler sched_credit01 = +{ + .name="credit01", + .desc="Zero-start, burn based on weight, reset to zero at negative credit", + .ops = { + .sched_init = sched_credit_init, + .vm_init = sched_credit_vm_init, + .wake = sched_credit_wake, + .schedule = sched_credit_schedule + } +}; diff -r f7c1a67cf976 -r 18f3d6e25ffc simulator.c --- a/simulator.c Mon Oct 19 20:12:54 2009 +0100 +++ b/simulator.c Mon Oct 19 20:14:47 2009 +0100 @@ -57,10 +57,12 @@ struct global_vm_data { struct global_vm_data V; extern struct scheduler sched_rr; +extern struct scheduler sched_credit01; int default_scheduler = 0; struct scheduler *schedulers[] = { &sched_rr, + &sched_credit01, NULL };