gdunlap/sched-sim.hg

annotate sched_credit03.c @ 16:cb624ff1d4fe

Clean up scheduler code to make it easier to see the differences
author George Dunlap <george.dunlap@eu.citrix.com>
date Fri Jul 16 11:55:39 2010 +0100 (2010-07-16)
parents f289f886cbcc
children
rev   line source
george@14 1 #include <stdio.h>
george@14 2 #include <stdlib.h>
george@14 3 #include <assert.h>
george@14 4
george@14 5 #define ASSERT assert
george@14 6
george@14 7 #include "list.h"
george@14 8 #include "sim.h"
george@14 9
george@14 10
george@14 11 #define MAX_VMS 16
george@14 12 #define CREDIT_INIT 500
george@14 13 #define CREDIT_CLIP 50
george@14 14 #define CREDIT_RESET 0
george@14 15 #define MAX_TIMER 200
george@14 16 #define MIN_TIMER 50
george@14 17
george@14 18 /* FIXME: hack! */
george@14 19 int init_weight[] = { 70, 100, 100, 100, 200, 200 };
george@14 20
george@14 21 struct sched_vm {
george@14 22 struct list_head runq_elem;
george@14 23 struct vm *v;
george@14 24
george@14 25 int weight;
george@14 26
george@14 27 int credit;
george@14 28 int credit_per_min_timer; /* ? */
george@14 29 int start_time;
george@14 30 int vid;
george@14 31 };
george@14 32
george@14 33 struct {
george@14 34 struct list_head runq; /* Global run queue */
george@14 35 int max_vm;
george@14 36 struct sched_vm vms[MAX_VMS];
george@14 37 int ncpus;
george@14 38
george@14 39 int max_weight;
george@14 40 int scale_factor; /* ? */
george@14 41
george@14 42 int next_check;
george@14 43 } sched_priv;
george@14 44
george@16 45 /*
george@16 46 * + Implement weights (hacky at the moment)
george@16 47 * - Everyone starts at fixed value
george@16 48 * - Burn credit based on variable weight
george@16 49 * - Insert in runq based on credit
george@16 50 * - Reset
george@16 51 * - Triggered when someone reaches zero
george@16 52 * + Clip everyone's credit and add INIT
george@16 53 * - Timeslice
george@16 54 * - Start with basic timeslice
george@16 55 * - Don't run for more credit than you have
george@16 56 * - Only run until your credit would equal next VM in runqueue
george@16 57 * - Never less than MIN_TIMER
george@16 58 */
george@16 59
george@14 60 static int t2c(int time, struct sched_vm *svm)
george@14 61 {
george@14 62 return time * sched_priv.max_weight / svm->weight;
george@14 63 }
george@14 64
george@14 65 static int c2t(int credit, struct sched_vm *svm)
george@14 66 {
george@14 67 return credit * svm->weight / sched_priv.max_weight;
george@14 68 }
george@14 69
george@14 70 static void dump_credit(int time, struct sched_vm *svm)
george@14 71 {
george@14 72 printf("credit v%d %d %d\n", svm->vid, time, svm->credit);
george@14 73 }
george@14 74
george@14 75 static void reset_credit(int time)
george@14 76 {
george@14 77 int i;
george@14 78 for ( i=0; i<=sched_priv.max_vm; i++)
george@14 79 {
george@14 80 struct sched_vm *svm = sched_priv.vms + i;
george@14 81 int tmax = CREDIT_CLIP;
george@14 82
george@14 83 if ( svm->credit > tmax )
george@14 84 svm->credit = tmax;
george@14 85 svm->credit += CREDIT_INIT;
george@14 86 svm->start_time = time;
george@14 87
george@14 88 dump_credit(time, svm);
george@14 89 }
george@16 90 /* No need to resort runq, as no one's credit is re-ordered */
george@14 91 }
george@14 92
george@14 93 static void burn_credit(struct sched_vm *svm, int time)
george@14 94 {
george@14 95 ASSERT(time >= svm->start_time);
george@14 96
george@14 97 svm->credit -= t2c(time - svm->start_time, svm);
george@14 98 svm->start_time = time;
george@14 99
george@14 100 dump_credit(time, svm);
george@14 101 }
george@14 102
george@14 103 static int calc_timer(struct sched_vm *svm)
george@14 104 {
george@16 105 int time;
george@14 106
george@16 107 /* Start with basic timeslice */
george@16 108 time = MAX_TIMER;
george@16 109
george@16 110 /* If we have less credit than that, cut it down to our credits */
george@14 111 if ( time > c2t(svm->credit, svm) )
george@14 112 time = c2t(svm->credit, svm);
george@14 113
george@16 114 /* If there are other VMs on the runqueue, calculate
george@16 115 * how much time until our credit will equal their credit.
george@16 116 * If this is less than our timeslice, cut it down again. */
george@14 117 if ( !list_empty(&sched_priv.runq) )
george@14 118 {
george@14 119 struct sched_vm *sq = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
george@14 120
george@14 121 ASSERT(svm->credit >= sq->credit);
george@14 122
george@14 123 /* Time will be used for svm, so use it to scale c2t */
george@14 124 if ( time > c2t(svm->credit - sq->credit, svm) )
george@14 125 time = c2t(svm->credit - sq->credit, svm);
george@14 126 }
george@14 127
george@16 128 /* No matter what, always run for at least MIN_TIMER */
george@14 129 if ( time < MIN_TIMER )
george@14 130 time = MIN_TIMER;
george@14 131
george@14 132 return time;
george@14 133 }
george@14 134
george@14 135 static void runq_insert(struct sched_vm *svm)
george@14 136 {
george@14 137 struct list_head *iter;
george@14 138 int pos = 0;
george@14 139
george@14 140 list_for_each( iter, &sched_priv.runq )
george@14 141 {
george@14 142 struct sched_vm * iter_svm;
george@14 143
george@14 144 iter_svm = list_entry(iter, struct sched_vm, runq_elem);
george@14 145
george@14 146 if ( svm->credit > iter_svm->credit )
george@14 147 {
george@14 148 printf(" p%d v%d\n",
george@14 149 pos,
george@14 150 iter_svm->vid);
george@14 151 break;
george@14 152 }
george@14 153 pos++;
george@14 154 }
george@14 155
george@14 156 list_add_tail(&svm->runq_elem, iter);
george@14 157 }
george@14 158
george@14 159 static void sched_credit_init(void)
george@14 160 {
george@14 161 printf("%s()\n", __func__);
george@14 162 INIT_LIST_HEAD(&sched_priv.runq);
george@14 163 sched_priv.max_vm=0;
george@14 164 sched_priv.max_weight = 0;
george@14 165 }
george@14 166
george@14 167 static void sched_credit_vm_init(int vid)
george@14 168 {
george@14 169 struct sched_vm *svm;
george@14 170
george@14 171 printf("%s: vm %d\n", __func__, vid);
george@14 172
george@14 173 if ( vid > MAX_VMS )
george@14 174 {
george@14 175 fprintf(stderr, "vid %d > MAX_VMS %d!\n", vid, MAX_VMS);
george@14 176 exit(1);
george@14 177 }
george@14 178
george@14 179 svm = sched_priv.vms + vid;
george@14 180
george@14 181 INIT_LIST_HEAD(&svm->runq_elem);
george@14 182
george@14 183 svm->vid = vid;
george@14 184 svm->v = vm_from_vid(vid);
george@14 185
george@14 186 svm->credit = CREDIT_INIT;
george@16 187 /* FIXME */
george@14 188 svm->weight = init_weight[vid];
george@14 189 if ( sched_priv.max_weight < svm->weight )
george@14 190 sched_priv.max_weight = svm->weight;
george@14 191 svm->start_time = 0;
george@14 192
george@14 193 if ( vid > sched_priv.max_vm )
george@14 194 sched_priv.max_vm = vid;
george@14 195 }
george@14 196
george@14 197 static void sched_credit_wake(int time, int vid)
george@14 198 {
george@14 199 struct vm *v;
george@14 200 struct sched_vm *svm;
george@14 201
george@14 202 v = vm_from_vid(vid);
george@14 203
george@14 204 printf("%s: time %d vid %d\n",
george@14 205 __func__, time, v->vid);
george@14 206
george@14 207 svm = sched_priv.vms + v->vid;
george@14 208
george@14 209 ASSERT(list_empty(&svm->runq_elem));
george@14 210
george@14 211 runq_insert(svm);
george@14 212
george@14 213 /* Scan for either:
george@14 214 * + an idle cpu to wake up, or
george@14 215 * + if there are cpus with lower credits, the lowest one
george@14 216 */
george@14 217 {
george@14 218 int i, ipid=-1, lowest=-1, cdiff;
george@14 219
george@14 220 for ( i=0; i<P.count; i++ )
george@14 221 {
george@14 222 if ( P.pcpus[i].idle )
george@14 223 {
george@14 224 printf(" %s: p%d idle, waking\n", __func__, i);
george@14 225 ipid=i;
george@14 226 lowest=0;
george@14 227 break;
george@14 228 }
george@14 229 else if ( P.pcpus[i].current )
george@14 230 {
george@14 231 struct vm* ovm = P.pcpus[i].current;
george@14 232 int ovid = ovm->vid;
george@14 233 struct sched_vm *osvm = sched_priv.vms + ovid;
george@14 234
george@14 235 /* Update credits of currently running VM */
george@14 236 burn_credit(osvm, time);
george@14 237
george@14 238 if ( lowest == -1 || osvm->credit < lowest )
george@14 239 {
george@14 240 ipid = i;
george@14 241 lowest = osvm->credit;
george@14 242 }
george@14 243 }
george@14 244
george@14 245 }
george@14 246
george@14 247 cdiff = lowest - svm->credit;
george@14 248
george@14 249 /* FIXME: c2t should be based on weight of running vm, not waiting vm! */
george@14 250 if ( ipid >= 0 )
george@14 251 sim_sched_timer((cdiff>0)?c2t(cdiff, svm):0, ipid);
george@14 252 else
george@14 253 dump_credit(time, svm);
george@14 254 }
george@14 255 }
george@14 256
george@14 257 static struct vm* sched_credit_schedule(int time, int pid)
george@14 258 {
george@14 259 struct sched_vm *svm;
george@14 260 struct vm *next, *prev;
george@14 261 int timer;
george@14 262
george@14 263 printf("%s: time %d pid %d\n",
george@14 264 __func__, time, pid);
george@14 265 prev = current(pid);
george@14 266
george@14 267 if ( prev )
george@14 268 {
george@14 269 printf(" current v%d\n", prev->vid);
george@14 270 svm = sched_priv.vms + prev->vid;
george@14 271
george@14 272 burn_credit(svm, time);
george@14 273
george@14 274 if ( svm->v->runstate == RUNSTATE_RUNNING )
george@14 275 {
george@14 276 printf(" adding to runqueue\n");
george@14 277 runq_insert(svm);
george@14 278 }
george@14 279 }
george@14 280
george@14 281 /* Take guy on front of runqueue, set new timer */
george@14 282 if ( list_empty(&sched_priv.runq) )
george@14 283 {
george@14 284 printf(" No runnable entities\n");
george@14 285 return NULL;
george@14 286 }
george@14 287
george@14 288 svm = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
george@14 289
george@14 290 list_del_init(&svm->runq_elem);
george@14 291
george@14 292 next = svm->v;
george@14 293
george@14 294 if ( svm->credit <= CREDIT_RESET )
george@14 295 {
george@14 296 printf(" vid %d credit %c, resetting credit at time %d\n",
george@14 297 svm->vid,
george@14 298 svm->credit,
george@14 299 time);
george@14 300 reset_credit(time);
george@14 301 }
george@14 302
george@14 303 dump_credit(time, svm);
george@14 304 svm->start_time = time;
george@14 305
george@14 306 timer = calc_timer(svm);
george@14 307
george@14 308 sim_sched_timer(timer, pid);
george@14 309
george@14 310 printf(" next: v%d\n", next->vid);
george@14 311
george@14 312 return next;
george@14 313 }
george@14 314
george@14 315 struct scheduler sched_credit03 =
george@14 316 {
george@14 317 .name="credit03",
george@16 318 .desc="c02 + implement weight + clip-and-add on reset",
george@14 319 .ops = {
george@14 320 .sched_init = sched_credit_init,
george@14 321 .vm_init = sched_credit_vm_init,
george@14 322 .wake = sched_credit_wake,
george@14 323 .schedule = sched_credit_schedule
george@14 324 }
george@14 325 };