gdunlap/sched-sim.hg

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