gdunlap/sched-sim.hg

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