gdunlap/sched-sim.hg

changeset 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 f378dbd3c2af
children a564c2327d2a
files Makefile sched_credit03.c simulator.c
line diff
     1.1 --- a/Makefile	Wed Oct 21 15:33:23 2009 +0100
     1.2 +++ b/Makefile	Fri Jul 16 11:12:29 2010 +0100
     1.3 @@ -21,5 +21,5 @@ clean:
     1.4  %.o: %.c $(HDRS) Makefile
     1.5  	$(CC) $(CFLAGS) -c -o $@ $<
     1.6  
     1.7 -simulator: simulator.o workloads.o sched_rr.o stats.o options.o sched_credit01.o sched_credit02.o
     1.8 +simulator: simulator.o workloads.o sched_rr.o stats.o options.o sched_credit01.o sched_credit02.o sched_credit03.o
     1.9  	$(CC) $(CFLAGS) -o $@ $^
    1.10 \ No newline at end of file
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/sched_credit03.c	Fri Jul 16 11:12:29 2010 +0100
     2.3 @@ -0,0 +1,303 @@
     2.4 +#include <stdio.h>
     2.5 +#include <stdlib.h>
     2.6 +#include <assert.h>
     2.7 +
     2.8 +#define ASSERT assert
     2.9 +
    2.10 +#include "list.h"
    2.11 +#include "sim.h"
    2.12 +
    2.13 +
    2.14 +#define MAX_VMS 16
    2.15 +#define CREDIT_INIT  500
    2.16 +#define CREDIT_CLIP  50
    2.17 +#define CREDIT_RESET 0
    2.18 +#define MAX_TIMER 200
    2.19 +#define MIN_TIMER 50
    2.20 +
    2.21 +/* FIXME: hack! */
    2.22 +int init_weight[] = { 70, 100, 100, 100, 200, 200 };
    2.23 +
    2.24 +struct sched_vm {
    2.25 +    struct list_head runq_elem;
    2.26 +    struct vm *v;
    2.27 +
    2.28 +    int weight;
    2.29 +
    2.30 +    int credit;
    2.31 +    int credit_per_min_timer; /* ? */
    2.32 +    int start_time;
    2.33 +    int vid;
    2.34 +};
    2.35 +
    2.36 +struct {
    2.37 +    struct list_head runq; /* Global run queue */
    2.38 +    int max_vm;
    2.39 +    struct sched_vm vms[MAX_VMS];
    2.40 +    int ncpus;
    2.41 +
    2.42 +    int max_weight;
    2.43 +    int scale_factor; /* ? */
    2.44 +
    2.45 +    int next_check;
    2.46 +} sched_priv;
    2.47 +
    2.48 +static int t2c(int time, struct sched_vm *svm)
    2.49 +{
    2.50 +    return time * sched_priv.max_weight / svm->weight;
    2.51 +}
    2.52 +
    2.53 +static int c2t(int credit, struct sched_vm *svm)
    2.54 +{
    2.55 +    return credit * svm->weight / sched_priv.max_weight;
    2.56 +}
    2.57 +
    2.58 +static void dump_credit(int time, struct sched_vm *svm)
    2.59 +{
    2.60 +    printf("credit v%d %d %d\n", svm->vid, time, svm->credit);
    2.61 +}
    2.62 +
    2.63 +static void reset_credit(int time)
    2.64 +{
    2.65 +    int i;
    2.66 +    for ( i=0; i<=sched_priv.max_vm; i++)
    2.67 +    {
    2.68 +        struct sched_vm *svm = sched_priv.vms + i;
    2.69 +        int tmax = CREDIT_CLIP;
    2.70 +
    2.71 +        //sched_priv.vms[i].credit = 0;
    2.72 +        //sched_priv.vms[i].credit /= (CREDIT_INIT/10);
    2.73 +        if ( svm->credit > tmax )
    2.74 +            svm->credit = tmax;
    2.75 +        svm->credit += CREDIT_INIT;
    2.76 +        svm->start_time = time;
    2.77 +
    2.78 +        dump_credit(time, svm);
    2.79 +    }
    2.80 +    /* No need to resort runq, as everyone's credit is now zero */
    2.81 +}
    2.82 +
    2.83 +static void burn_credit(struct sched_vm *svm, int time)
    2.84 +{
    2.85 +    ASSERT(time >= svm->start_time);
    2.86 +
    2.87 +    svm->credit -= t2c(time - svm->start_time, svm);
    2.88 +    svm->start_time = time;
    2.89 +
    2.90 +    dump_credit(time, svm);
    2.91 +}
    2.92 +
    2.93 +static int calc_timer(struct sched_vm *svm)
    2.94 +{
    2.95 +    int time = MAX_TIMER;
    2.96 +
    2.97 +    if ( time > c2t(svm->credit, svm) )
    2.98 +        time = c2t(svm->credit, svm);
    2.99 +
   2.100 +    if ( !list_empty(&sched_priv.runq) )
   2.101 +    {
   2.102 +        struct sched_vm *sq = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
   2.103 +
   2.104 +        ASSERT(svm->credit >= sq->credit);
   2.105 +
   2.106 +        /* Time will be used for svm, so use it to scale c2t */
   2.107 +        if ( time > c2t(svm->credit - sq->credit, svm) )
   2.108 +            time = c2t(svm->credit - sq->credit, svm);
   2.109 +    }
   2.110 +
   2.111 +    if ( time < MIN_TIMER )
   2.112 +        time = MIN_TIMER;
   2.113 +
   2.114 +    return time;
   2.115 +}
   2.116 +
   2.117 +static void runq_insert(struct sched_vm *svm)
   2.118 +{
   2.119 +    struct list_head *iter;
   2.120 +    int pos = 0;
   2.121 +
   2.122 +    list_for_each( iter, &sched_priv.runq )
   2.123 +    {
   2.124 +        struct sched_vm * iter_svm;
   2.125 +
   2.126 +        iter_svm = list_entry(iter, struct sched_vm, runq_elem);
   2.127 +
   2.128 +        if ( svm->credit > iter_svm->credit )
   2.129 +        {
   2.130 +            printf(" p%d v%d\n",
   2.131 +                   pos,
   2.132 +                   iter_svm->vid);
   2.133 +            break;
   2.134 +        }
   2.135 +        pos++;
   2.136 +    }
   2.137 +
   2.138 +    list_add_tail(&svm->runq_elem, iter);
   2.139 +}
   2.140 +
   2.141 +static void sched_credit_init(void)
   2.142 +{
   2.143 +    printf("%s()\n", __func__);
   2.144 +    INIT_LIST_HEAD(&sched_priv.runq);
   2.145 +    sched_priv.max_vm=0;
   2.146 +    sched_priv.max_weight = 0;
   2.147 +}
   2.148 +
   2.149 +static void sched_credit_vm_init(int vid)
   2.150 +{
   2.151 +    struct sched_vm *svm;
   2.152 +
   2.153 +    printf("%s: vm %d\n", __func__, vid);
   2.154 +
   2.155 +    if ( vid > MAX_VMS )
   2.156 +    {
   2.157 +        fprintf(stderr, "vid %d > MAX_VMS %d!\n", vid, MAX_VMS);
   2.158 +        exit(1);
   2.159 +    }
   2.160 +
   2.161 +    svm = sched_priv.vms + vid;
   2.162 +
   2.163 +    INIT_LIST_HEAD(&svm->runq_elem);
   2.164 +
   2.165 +    svm->vid = vid;
   2.166 +    svm->v = vm_from_vid(vid);
   2.167 +
   2.168 +    svm->credit = CREDIT_INIT;
   2.169 +    svm->weight = init_weight[vid];
   2.170 +    if ( sched_priv.max_weight < svm->weight )
   2.171 +        sched_priv.max_weight = svm->weight;
   2.172 +    svm->start_time = 0;
   2.173 +    
   2.174 +    if ( vid > sched_priv.max_vm )
   2.175 +        sched_priv.max_vm = vid;
   2.176 +}
   2.177 +
   2.178 +static void sched_credit_wake(int time, int vid)
   2.179 +{
   2.180 +    struct vm *v;
   2.181 +    struct sched_vm *svm;
   2.182 +
   2.183 +    v = vm_from_vid(vid);
   2.184 +
   2.185 +    printf("%s: time %d vid %d\n",
   2.186 +           __func__, time, v->vid);
   2.187 +
   2.188 +    svm = sched_priv.vms + v->vid;
   2.189 +
   2.190 +    ASSERT(list_empty(&svm->runq_elem));
   2.191 +
   2.192 +    runq_insert(svm);
   2.193 +
   2.194 +    /* Scan for either:
   2.195 +     * + an idle cpu to wake up, or
   2.196 +     * + if there are cpus with lower credits, the lowest one
   2.197 +     */
   2.198 +    {
   2.199 +        int i, ipid=-1, lowest=-1, cdiff;
   2.200 +
   2.201 +        for ( i=0; i<P.count; i++ )
   2.202 +        {
   2.203 +            if ( P.pcpus[i].idle )
   2.204 +            {
   2.205 +                printf(" %s: p%d idle, waking\n", __func__, i);
   2.206 +                ipid=i;
   2.207 +                lowest=0;
   2.208 +                break;
   2.209 +            }
   2.210 +            else if ( P.pcpus[i].current )
   2.211 +            {
   2.212 +                struct vm* ovm = P.pcpus[i].current;
   2.213 +                int ovid = ovm->vid;
   2.214 +                struct sched_vm *osvm = sched_priv.vms + ovid;
   2.215 +
   2.216 +                /* Update credits of currently running VM */
   2.217 +                burn_credit(osvm, time);
   2.218 +
   2.219 +                if ( lowest == -1 || osvm->credit < lowest )
   2.220 +                {
   2.221 +                    ipid = i;
   2.222 +                    lowest = osvm->credit;
   2.223 +                }
   2.224 +            }
   2.225 +            
   2.226 +        }
   2.227 +
   2.228 +        cdiff = lowest - svm->credit;
   2.229 +
   2.230 +        /* FIXME: c2t should be based on weight of running vm, not waiting vm! */
   2.231 +        if ( ipid >= 0 )
   2.232 +            sim_sched_timer((cdiff>0)?c2t(cdiff, svm):0, ipid);
   2.233 +        else
   2.234 +            dump_credit(time, svm);
   2.235 +    }
   2.236 +}
   2.237 +
   2.238 +static struct vm* sched_credit_schedule(int time, int pid)
   2.239 +{
   2.240 +    struct sched_vm *svm;
   2.241 +    struct vm *next, *prev;
   2.242 +    int timer;
   2.243 +
   2.244 +    printf("%s: time %d pid %d\n",
   2.245 +           __func__, time, pid);
   2.246 +    prev = current(pid);
   2.247 +
   2.248 +    if ( prev )
   2.249 +    {
   2.250 +        printf(" current v%d\n", prev->vid);
   2.251 +        svm = sched_priv.vms + prev->vid;
   2.252 +
   2.253 +        burn_credit(svm, time);
   2.254 +
   2.255 +        if ( svm->v->runstate == RUNSTATE_RUNNING )
   2.256 +        {
   2.257 +            printf(" adding to runqueue\n");
   2.258 +            runq_insert(svm);
   2.259 +        }
   2.260 +    }
   2.261 +
   2.262 +    /* Take guy on front of runqueue, set new timer */
   2.263 +    if ( list_empty(&sched_priv.runq) )
   2.264 +    {
   2.265 +        printf(" No runnable entities\n");
   2.266 +        return NULL;
   2.267 +    }
   2.268 +
   2.269 +    svm = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
   2.270 +
   2.271 +    list_del_init(&svm->runq_elem);
   2.272 +
   2.273 +    next = svm->v;
   2.274 +
   2.275 +    if ( svm->credit <= CREDIT_RESET )
   2.276 +    {
   2.277 +        printf(" vid %d credit %c, resetting credit at time %d\n",
   2.278 +               svm->vid,
   2.279 +               svm->credit,
   2.280 +               time);
   2.281 +        reset_credit(time);
   2.282 +    }
   2.283 +
   2.284 +    dump_credit(time, svm);
   2.285 +    svm->start_time = time;
   2.286 +
   2.287 +    timer = calc_timer(svm);
   2.288 +
   2.289 +    sim_sched_timer(timer, pid);
   2.290 +
   2.291 +    printf(" next: v%d\n", next->vid);
   2.292 +    
   2.293 +    return next;
   2.294 +}
   2.295 +
   2.296 +struct scheduler sched_credit03 =
   2.297 +{
   2.298 +    .name="credit03",
   2.299 +    .desc="c02 + weight",
   2.300 +    .ops = {
   2.301 +        .sched_init = sched_credit_init,
   2.302 +        .vm_init    = sched_credit_vm_init,
   2.303 +        .wake       = sched_credit_wake,
   2.304 +        .schedule   = sched_credit_schedule
   2.305 +    }
   2.306 +};
     3.1 --- a/simulator.c	Wed Oct 21 15:33:23 2009 +0100
     3.2 +++ b/simulator.c	Fri Jul 16 11:12:29 2010 +0100
     3.3 @@ -59,12 +59,14 @@ struct global_vm_data V;
     3.4  extern struct scheduler sched_rr;
     3.5  extern struct scheduler sched_credit01;
     3.6  extern struct scheduler sched_credit02;
     3.7 +extern struct scheduler sched_credit03;
     3.8  int default_scheduler = 0;
     3.9  struct scheduler *schedulers[] =
    3.10  {
    3.11      &sched_rr,
    3.12      &sched_credit01,
    3.13      &sched_credit02,
    3.14 +    &sched_credit03,
    3.15      NULL
    3.16  };
    3.17