gdunlap/sched-sim.hg

diff 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
line diff
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/sched_credit03.c	Fri Jul 16 11:12:29 2010 +0100
     1.3 @@ -0,0 +1,303 @@
     1.4 +#include <stdio.h>
     1.5 +#include <stdlib.h>
     1.6 +#include <assert.h>
     1.7 +
     1.8 +#define ASSERT assert
     1.9 +
    1.10 +#include "list.h"
    1.11 +#include "sim.h"
    1.12 +
    1.13 +
    1.14 +#define MAX_VMS 16
    1.15 +#define CREDIT_INIT  500
    1.16 +#define CREDIT_CLIP  50
    1.17 +#define CREDIT_RESET 0
    1.18 +#define MAX_TIMER 200
    1.19 +#define MIN_TIMER 50
    1.20 +
    1.21 +/* FIXME: hack! */
    1.22 +int init_weight[] = { 70, 100, 100, 100, 200, 200 };
    1.23 +
    1.24 +struct sched_vm {
    1.25 +    struct list_head runq_elem;
    1.26 +    struct vm *v;
    1.27 +
    1.28 +    int weight;
    1.29 +
    1.30 +    int credit;
    1.31 +    int credit_per_min_timer; /* ? */
    1.32 +    int start_time;
    1.33 +    int vid;
    1.34 +};
    1.35 +
    1.36 +struct {
    1.37 +    struct list_head runq; /* Global run queue */
    1.38 +    int max_vm;
    1.39 +    struct sched_vm vms[MAX_VMS];
    1.40 +    int ncpus;
    1.41 +
    1.42 +    int max_weight;
    1.43 +    int scale_factor; /* ? */
    1.44 +
    1.45 +    int next_check;
    1.46 +} sched_priv;
    1.47 +
    1.48 +static int t2c(int time, struct sched_vm *svm)
    1.49 +{
    1.50 +    return time * sched_priv.max_weight / svm->weight;
    1.51 +}
    1.52 +
    1.53 +static int c2t(int credit, struct sched_vm *svm)
    1.54 +{
    1.55 +    return credit * svm->weight / sched_priv.max_weight;
    1.56 +}
    1.57 +
    1.58 +static void dump_credit(int time, struct sched_vm *svm)
    1.59 +{
    1.60 +    printf("credit v%d %d %d\n", svm->vid, time, svm->credit);
    1.61 +}
    1.62 +
    1.63 +static void reset_credit(int time)
    1.64 +{
    1.65 +    int i;
    1.66 +    for ( i=0; i<=sched_priv.max_vm; i++)
    1.67 +    {
    1.68 +        struct sched_vm *svm = sched_priv.vms + i;
    1.69 +        int tmax = CREDIT_CLIP;
    1.70 +
    1.71 +        //sched_priv.vms[i].credit = 0;
    1.72 +        //sched_priv.vms[i].credit /= (CREDIT_INIT/10);
    1.73 +        if ( svm->credit > tmax )
    1.74 +            svm->credit = tmax;
    1.75 +        svm->credit += CREDIT_INIT;
    1.76 +        svm->start_time = time;
    1.77 +
    1.78 +        dump_credit(time, svm);
    1.79 +    }
    1.80 +    /* No need to resort runq, as everyone's credit is now zero */
    1.81 +}
    1.82 +
    1.83 +static void burn_credit(struct sched_vm *svm, int time)
    1.84 +{
    1.85 +    ASSERT(time >= svm->start_time);
    1.86 +
    1.87 +    svm->credit -= t2c(time - svm->start_time, svm);
    1.88 +    svm->start_time = time;
    1.89 +
    1.90 +    dump_credit(time, svm);
    1.91 +}
    1.92 +
    1.93 +static int calc_timer(struct sched_vm *svm)
    1.94 +{
    1.95 +    int time = MAX_TIMER;
    1.96 +
    1.97 +    if ( time > c2t(svm->credit, svm) )
    1.98 +        time = c2t(svm->credit, svm);
    1.99 +
   1.100 +    if ( !list_empty(&sched_priv.runq) )
   1.101 +    {
   1.102 +        struct sched_vm *sq = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
   1.103 +
   1.104 +        ASSERT(svm->credit >= sq->credit);
   1.105 +
   1.106 +        /* Time will be used for svm, so use it to scale c2t */
   1.107 +        if ( time > c2t(svm->credit - sq->credit, svm) )
   1.108 +            time = c2t(svm->credit - sq->credit, svm);
   1.109 +    }
   1.110 +
   1.111 +    if ( time < MIN_TIMER )
   1.112 +        time = MIN_TIMER;
   1.113 +
   1.114 +    return time;
   1.115 +}
   1.116 +
   1.117 +static void runq_insert(struct sched_vm *svm)
   1.118 +{
   1.119 +    struct list_head *iter;
   1.120 +    int pos = 0;
   1.121 +
   1.122 +    list_for_each( iter, &sched_priv.runq )
   1.123 +    {
   1.124 +        struct sched_vm * iter_svm;
   1.125 +
   1.126 +        iter_svm = list_entry(iter, struct sched_vm, runq_elem);
   1.127 +
   1.128 +        if ( svm->credit > iter_svm->credit )
   1.129 +        {
   1.130 +            printf(" p%d v%d\n",
   1.131 +                   pos,
   1.132 +                   iter_svm->vid);
   1.133 +            break;
   1.134 +        }
   1.135 +        pos++;
   1.136 +    }
   1.137 +
   1.138 +    list_add_tail(&svm->runq_elem, iter);
   1.139 +}
   1.140 +
   1.141 +static void sched_credit_init(void)
   1.142 +{
   1.143 +    printf("%s()\n", __func__);
   1.144 +    INIT_LIST_HEAD(&sched_priv.runq);
   1.145 +    sched_priv.max_vm=0;
   1.146 +    sched_priv.max_weight = 0;
   1.147 +}
   1.148 +
   1.149 +static void sched_credit_vm_init(int vid)
   1.150 +{
   1.151 +    struct sched_vm *svm;
   1.152 +
   1.153 +    printf("%s: vm %d\n", __func__, vid);
   1.154 +
   1.155 +    if ( vid > MAX_VMS )
   1.156 +    {
   1.157 +        fprintf(stderr, "vid %d > MAX_VMS %d!\n", vid, MAX_VMS);
   1.158 +        exit(1);
   1.159 +    }
   1.160 +
   1.161 +    svm = sched_priv.vms + vid;
   1.162 +
   1.163 +    INIT_LIST_HEAD(&svm->runq_elem);
   1.164 +
   1.165 +    svm->vid = vid;
   1.166 +    svm->v = vm_from_vid(vid);
   1.167 +
   1.168 +    svm->credit = CREDIT_INIT;
   1.169 +    svm->weight = init_weight[vid];
   1.170 +    if ( sched_priv.max_weight < svm->weight )
   1.171 +        sched_priv.max_weight = svm->weight;
   1.172 +    svm->start_time = 0;
   1.173 +    
   1.174 +    if ( vid > sched_priv.max_vm )
   1.175 +        sched_priv.max_vm = vid;
   1.176 +}
   1.177 +
   1.178 +static void sched_credit_wake(int time, int vid)
   1.179 +{
   1.180 +    struct vm *v;
   1.181 +    struct sched_vm *svm;
   1.182 +
   1.183 +    v = vm_from_vid(vid);
   1.184 +
   1.185 +    printf("%s: time %d vid %d\n",
   1.186 +           __func__, time, v->vid);
   1.187 +
   1.188 +    svm = sched_priv.vms + v->vid;
   1.189 +
   1.190 +    ASSERT(list_empty(&svm->runq_elem));
   1.191 +
   1.192 +    runq_insert(svm);
   1.193 +
   1.194 +    /* Scan for either:
   1.195 +     * + an idle cpu to wake up, or
   1.196 +     * + if there are cpus with lower credits, the lowest one
   1.197 +     */
   1.198 +    {
   1.199 +        int i, ipid=-1, lowest=-1, cdiff;
   1.200 +
   1.201 +        for ( i=0; i<P.count; i++ )
   1.202 +        {
   1.203 +            if ( P.pcpus[i].idle )
   1.204 +            {
   1.205 +                printf(" %s: p%d idle, waking\n", __func__, i);
   1.206 +                ipid=i;
   1.207 +                lowest=0;
   1.208 +                break;
   1.209 +            }
   1.210 +            else if ( P.pcpus[i].current )
   1.211 +            {
   1.212 +                struct vm* ovm = P.pcpus[i].current;
   1.213 +                int ovid = ovm->vid;
   1.214 +                struct sched_vm *osvm = sched_priv.vms + ovid;
   1.215 +
   1.216 +                /* Update credits of currently running VM */
   1.217 +                burn_credit(osvm, time);
   1.218 +
   1.219 +                if ( lowest == -1 || osvm->credit < lowest )
   1.220 +                {
   1.221 +                    ipid = i;
   1.222 +                    lowest = osvm->credit;
   1.223 +                }
   1.224 +            }
   1.225 +            
   1.226 +        }
   1.227 +
   1.228 +        cdiff = lowest - svm->credit;
   1.229 +
   1.230 +        /* FIXME: c2t should be based on weight of running vm, not waiting vm! */
   1.231 +        if ( ipid >= 0 )
   1.232 +            sim_sched_timer((cdiff>0)?c2t(cdiff, svm):0, ipid);
   1.233 +        else
   1.234 +            dump_credit(time, svm);
   1.235 +    }
   1.236 +}
   1.237 +
   1.238 +static struct vm* sched_credit_schedule(int time, int pid)
   1.239 +{
   1.240 +    struct sched_vm *svm;
   1.241 +    struct vm *next, *prev;
   1.242 +    int timer;
   1.243 +
   1.244 +    printf("%s: time %d pid %d\n",
   1.245 +           __func__, time, pid);
   1.246 +    prev = current(pid);
   1.247 +
   1.248 +    if ( prev )
   1.249 +    {
   1.250 +        printf(" current v%d\n", prev->vid);
   1.251 +        svm = sched_priv.vms + prev->vid;
   1.252 +
   1.253 +        burn_credit(svm, time);
   1.254 +
   1.255 +        if ( svm->v->runstate == RUNSTATE_RUNNING )
   1.256 +        {
   1.257 +            printf(" adding to runqueue\n");
   1.258 +            runq_insert(svm);
   1.259 +        }
   1.260 +    }
   1.261 +
   1.262 +    /* Take guy on front of runqueue, set new timer */
   1.263 +    if ( list_empty(&sched_priv.runq) )
   1.264 +    {
   1.265 +        printf(" No runnable entities\n");
   1.266 +        return NULL;
   1.267 +    }
   1.268 +
   1.269 +    svm = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
   1.270 +
   1.271 +    list_del_init(&svm->runq_elem);
   1.272 +
   1.273 +    next = svm->v;
   1.274 +
   1.275 +    if ( svm->credit <= CREDIT_RESET )
   1.276 +    {
   1.277 +        printf(" vid %d credit %c, resetting credit at time %d\n",
   1.278 +               svm->vid,
   1.279 +               svm->credit,
   1.280 +               time);
   1.281 +        reset_credit(time);
   1.282 +    }
   1.283 +
   1.284 +    dump_credit(time, svm);
   1.285 +    svm->start_time = time;
   1.286 +
   1.287 +    timer = calc_timer(svm);
   1.288 +
   1.289 +    sim_sched_timer(timer, pid);
   1.290 +
   1.291 +    printf(" next: v%d\n", next->vid);
   1.292 +    
   1.293 +    return next;
   1.294 +}
   1.295 +
   1.296 +struct scheduler sched_credit03 =
   1.297 +{
   1.298 +    .name="credit03",
   1.299 +    .desc="c02 + weight",
   1.300 +    .ops = {
   1.301 +        .sched_init = sched_credit_init,
   1.302 +        .vm_init    = sched_credit_vm_init,
   1.303 +        .wake       = sched_credit_wake,
   1.304 +        .schedule   = sched_credit_schedule
   1.305 +    }
   1.306 +};