gdunlap/sched-sim.hg

annotate sched_credit03.c @ 14:f289f886cbcc

Add sched_credit03
author George Dunlap <george.dunlap@eu.citrix.com>
date Fri Jul 16 11:12:29 2010 +0100 (2010-07-16)
parents
children cb624ff1d4fe
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@14 45 static int t2c(int time, struct sched_vm *svm)
george@14 46 {
george@14 47 return time * sched_priv.max_weight / svm->weight;
george@14 48 }
george@14 49
george@14 50 static int c2t(int credit, struct sched_vm *svm)
george@14 51 {
george@14 52 return credit * svm->weight / sched_priv.max_weight;
george@14 53 }
george@14 54
george@14 55 static void dump_credit(int time, struct sched_vm *svm)
george@14 56 {
george@14 57 printf("credit v%d %d %d\n", svm->vid, time, svm->credit);
george@14 58 }
george@14 59
george@14 60 static void reset_credit(int time)
george@14 61 {
george@14 62 int i;
george@14 63 for ( i=0; i<=sched_priv.max_vm; i++)
george@14 64 {
george@14 65 struct sched_vm *svm = sched_priv.vms + i;
george@14 66 int tmax = CREDIT_CLIP;
george@14 67
george@14 68 //sched_priv.vms[i].credit = 0;
george@14 69 //sched_priv.vms[i].credit /= (CREDIT_INIT/10);
george@14 70 if ( svm->credit > tmax )
george@14 71 svm->credit = tmax;
george@14 72 svm->credit += CREDIT_INIT;
george@14 73 svm->start_time = time;
george@14 74
george@14 75 dump_credit(time, svm);
george@14 76 }
george@14 77 /* No need to resort runq, as everyone's credit is now zero */
george@14 78 }
george@14 79
george@14 80 static void burn_credit(struct sched_vm *svm, int time)
george@14 81 {
george@14 82 ASSERT(time >= svm->start_time);
george@14 83
george@14 84 svm->credit -= t2c(time - svm->start_time, svm);
george@14 85 svm->start_time = time;
george@14 86
george@14 87 dump_credit(time, svm);
george@14 88 }
george@14 89
george@14 90 static int calc_timer(struct sched_vm *svm)
george@14 91 {
george@14 92 int time = MAX_TIMER;
george@14 93
george@14 94 if ( time > c2t(svm->credit, svm) )
george@14 95 time = c2t(svm->credit, svm);
george@14 96
george@14 97 if ( !list_empty(&sched_priv.runq) )
george@14 98 {
george@14 99 struct sched_vm *sq = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
george@14 100
george@14 101 ASSERT(svm->credit >= sq->credit);
george@14 102
george@14 103 /* Time will be used for svm, so use it to scale c2t */
george@14 104 if ( time > c2t(svm->credit - sq->credit, svm) )
george@14 105 time = c2t(svm->credit - sq->credit, svm);
george@14 106 }
george@14 107
george@14 108 if ( time < MIN_TIMER )
george@14 109 time = MIN_TIMER;
george@14 110
george@14 111 return time;
george@14 112 }
george@14 113
george@14 114 static void runq_insert(struct sched_vm *svm)
george@14 115 {
george@14 116 struct list_head *iter;
george@14 117 int pos = 0;
george@14 118
george@14 119 list_for_each( iter, &sched_priv.runq )
george@14 120 {
george@14 121 struct sched_vm * iter_svm;
george@14 122
george@14 123 iter_svm = list_entry(iter, struct sched_vm, runq_elem);
george@14 124
george@14 125 if ( svm->credit > iter_svm->credit )
george@14 126 {
george@14 127 printf(" p%d v%d\n",
george@14 128 pos,
george@14 129 iter_svm->vid);
george@14 130 break;
george@14 131 }
george@14 132 pos++;
george@14 133 }
george@14 134
george@14 135 list_add_tail(&svm->runq_elem, iter);
george@14 136 }
george@14 137
george@14 138 static void sched_credit_init(void)
george@14 139 {
george@14 140 printf("%s()\n", __func__);
george@14 141 INIT_LIST_HEAD(&sched_priv.runq);
george@14 142 sched_priv.max_vm=0;
george@14 143 sched_priv.max_weight = 0;
george@14 144 }
george@14 145
george@14 146 static void sched_credit_vm_init(int vid)
george@14 147 {
george@14 148 struct sched_vm *svm;
george@14 149
george@14 150 printf("%s: vm %d\n", __func__, vid);
george@14 151
george@14 152 if ( vid > MAX_VMS )
george@14 153 {
george@14 154 fprintf(stderr, "vid %d > MAX_VMS %d!\n", vid, MAX_VMS);
george@14 155 exit(1);
george@14 156 }
george@14 157
george@14 158 svm = sched_priv.vms + vid;
george@14 159
george@14 160 INIT_LIST_HEAD(&svm->runq_elem);
george@14 161
george@14 162 svm->vid = vid;
george@14 163 svm->v = vm_from_vid(vid);
george@14 164
george@14 165 svm->credit = CREDIT_INIT;
george@14 166 svm->weight = init_weight[vid];
george@14 167 if ( sched_priv.max_weight < svm->weight )
george@14 168 sched_priv.max_weight = svm->weight;
george@14 169 svm->start_time = 0;
george@14 170
george@14 171 if ( vid > sched_priv.max_vm )
george@14 172 sched_priv.max_vm = vid;
george@14 173 }
george@14 174
george@14 175 static void sched_credit_wake(int time, int vid)
george@14 176 {
george@14 177 struct vm *v;
george@14 178 struct sched_vm *svm;
george@14 179
george@14 180 v = vm_from_vid(vid);
george@14 181
george@14 182 printf("%s: time %d vid %d\n",
george@14 183 __func__, time, v->vid);
george@14 184
george@14 185 svm = sched_priv.vms + v->vid;
george@14 186
george@14 187 ASSERT(list_empty(&svm->runq_elem));
george@14 188
george@14 189 runq_insert(svm);
george@14 190
george@14 191 /* Scan for either:
george@14 192 * + an idle cpu to wake up, or
george@14 193 * + if there are cpus with lower credits, the lowest one
george@14 194 */
george@14 195 {
george@14 196 int i, ipid=-1, lowest=-1, cdiff;
george@14 197
george@14 198 for ( i=0; i<P.count; i++ )
george@14 199 {
george@14 200 if ( P.pcpus[i].idle )
george@14 201 {
george@14 202 printf(" %s: p%d idle, waking\n", __func__, i);
george@14 203 ipid=i;
george@14 204 lowest=0;
george@14 205 break;
george@14 206 }
george@14 207 else if ( P.pcpus[i].current )
george@14 208 {
george@14 209 struct vm* ovm = P.pcpus[i].current;
george@14 210 int ovid = ovm->vid;
george@14 211 struct sched_vm *osvm = sched_priv.vms + ovid;
george@14 212
george@14 213 /* Update credits of currently running VM */
george@14 214 burn_credit(osvm, time);
george@14 215
george@14 216 if ( lowest == -1 || osvm->credit < lowest )
george@14 217 {
george@14 218 ipid = i;
george@14 219 lowest = osvm->credit;
george@14 220 }
george@14 221 }
george@14 222
george@14 223 }
george@14 224
george@14 225 cdiff = lowest - svm->credit;
george@14 226
george@14 227 /* FIXME: c2t should be based on weight of running vm, not waiting vm! */
george@14 228 if ( ipid >= 0 )
george@14 229 sim_sched_timer((cdiff>0)?c2t(cdiff, svm):0, ipid);
george@14 230 else
george@14 231 dump_credit(time, svm);
george@14 232 }
george@14 233 }
george@14 234
george@14 235 static struct vm* sched_credit_schedule(int time, int pid)
george@14 236 {
george@14 237 struct sched_vm *svm;
george@14 238 struct vm *next, *prev;
george@14 239 int timer;
george@14 240
george@14 241 printf("%s: time %d pid %d\n",
george@14 242 __func__, time, pid);
george@14 243 prev = current(pid);
george@14 244
george@14 245 if ( prev )
george@14 246 {
george@14 247 printf(" current v%d\n", prev->vid);
george@14 248 svm = sched_priv.vms + prev->vid;
george@14 249
george@14 250 burn_credit(svm, time);
george@14 251
george@14 252 if ( svm->v->runstate == RUNSTATE_RUNNING )
george@14 253 {
george@14 254 printf(" adding to runqueue\n");
george@14 255 runq_insert(svm);
george@14 256 }
george@14 257 }
george@14 258
george@14 259 /* Take guy on front of runqueue, set new timer */
george@14 260 if ( list_empty(&sched_priv.runq) )
george@14 261 {
george@14 262 printf(" No runnable entities\n");
george@14 263 return NULL;
george@14 264 }
george@14 265
george@14 266 svm = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
george@14 267
george@14 268 list_del_init(&svm->runq_elem);
george@14 269
george@14 270 next = svm->v;
george@14 271
george@14 272 if ( svm->credit <= CREDIT_RESET )
george@14 273 {
george@14 274 printf(" vid %d credit %c, resetting credit at time %d\n",
george@14 275 svm->vid,
george@14 276 svm->credit,
george@14 277 time);
george@14 278 reset_credit(time);
george@14 279 }
george@14 280
george@14 281 dump_credit(time, svm);
george@14 282 svm->start_time = time;
george@14 283
george@14 284 timer = calc_timer(svm);
george@14 285
george@14 286 sim_sched_timer(timer, pid);
george@14 287
george@14 288 printf(" next: v%d\n", next->vid);
george@14 289
george@14 290 return next;
george@14 291 }
george@14 292
george@14 293 struct scheduler sched_credit03 =
george@14 294 {
george@14 295 .name="credit03",
george@14 296 .desc="c02 + weight",
george@14 297 .ops = {
george@14 298 .sched_init = sched_credit_init,
george@14 299 .vm_init = sched_credit_vm_init,
george@14 300 .wake = sched_credit_wake,
george@14 301 .schedule = sched_credit_schedule
george@14 302 }
george@14 303 };