gdunlap/sched-sim.hg

changeset 11:31f36108fc43

c02: Initial commit (clone of c01)
author George Dunlap <gdunlap@xensource.com>
date Tue Oct 20 18:14:37 2009 +0100 (2009-10-20)
parents a0da04ca71ee
children f34462422a94
files Makefile sched_credit02.c simulator.c
line diff
     1.1 --- a/Makefile	Tue Oct 20 18:12:57 2009 +0100
     1.2 +++ b/Makefile	Tue Oct 20 18:14:37 2009 +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
     1.8 +simulator: simulator.o workloads.o sched_rr.o stats.o options.o sched_credit01.o sched_credit02.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_credit02.c	Tue Oct 20 18:14:37 2009 +0100
     2.3 @@ -0,0 +1,276 @@
     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_RESET 0
    2.17 +#define MAX_TIMER 200
    2.18 +#define MIN_TIMER 100
    2.19 +
    2.20 +struct sched_vm {
    2.21 +    struct list_head runq_elem;
    2.22 +    struct vm *v;
    2.23 +
    2.24 +    int weight;
    2.25 +
    2.26 +    int credit;
    2.27 +    int credit_per_min_timer; /* ? */
    2.28 +    int start_time;
    2.29 +    int vid;
    2.30 +};
    2.31 +
    2.32 +struct {
    2.33 +    struct list_head runq; /* Global run queue */
    2.34 +    int max_vm;
    2.35 +    struct sched_vm vms[MAX_VMS];
    2.36 +    int ncpus;
    2.37 +
    2.38 +    int global_weight;
    2.39 +    int scale_factor; /* ? */
    2.40 +
    2.41 +    int next_check;
    2.42 +} sched_priv;
    2.43 +
    2.44 +
    2.45 +
    2.46 +static void reset_credit(int time)
    2.47 +{
    2.48 +    int i;
    2.49 +    for ( i=0; i<=sched_priv.max_vm; i++)
    2.50 +    {
    2.51 +        sched_priv.vms[i].credit = CREDIT_INIT;
    2.52 +        sched_priv.vms[i].start_time = time;
    2.53 +    }
    2.54 +    /* No need to resort runq, as everyone's credit is now zero */
    2.55 +}
    2.56 +
    2.57 +static void dump_credit(int time, struct sched_vm *svm)
    2.58 +{
    2.59 +    printf("credit v%d %d %d\n", svm->vid, time, svm->credit);
    2.60 +}
    2.61 +
    2.62 +static void burn_credit(struct sched_vm *svm, int time)
    2.63 +{
    2.64 +    ASSERT(time >= svm->start_time);
    2.65 +
    2.66 +    svm->credit -= (time - svm->start_time);
    2.67 +    svm->start_time = time;
    2.68 +
    2.69 +    dump_credit(time, svm);
    2.70 +}
    2.71 +
    2.72 +static int calc_timer(struct sched_vm *svm)
    2.73 +{
    2.74 +    int time = MAX_TIMER;
    2.75 +
    2.76 +    if ( time > svm->credit )
    2.77 +        time = svm->credit;
    2.78 +#if 0
    2.79 +    if ( !list_empty(&sched_priv.runq) )
    2.80 +    {
    2.81 +        struct sched_vm *sq = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
    2.82 +
    2.83 +        ASSERT(svm->credit >= sq->credit);
    2.84 +
    2.85 +        if ( (svm->credit - sq->credit) < time )
    2.86 +            time = (svm->credit - sq->credit);
    2.87 +    }
    2.88 +
    2.89 +#endif
    2.90 +
    2.91 +    if ( time < MIN_TIMER )
    2.92 +        time = MIN_TIMER;
    2.93 +    return time;
    2.94 +}
    2.95 +
    2.96 +static void runq_insert(struct sched_vm *svm)
    2.97 +{
    2.98 +    struct list_head *iter;
    2.99 +    int pos = 0;
   2.100 +
   2.101 +    list_for_each( iter, &sched_priv.runq )
   2.102 +    {
   2.103 +        struct sched_vm * iter_svm;
   2.104 +
   2.105 +        iter_svm = list_entry(iter, struct sched_vm, runq_elem);
   2.106 +
   2.107 +        if ( svm->credit > iter_svm->credit )
   2.108 +        {
   2.109 +            printf(" p%d v%d\n",
   2.110 +                   pos,
   2.111 +                   iter_svm->vid);
   2.112 +            break;
   2.113 +        }
   2.114 +        pos++;
   2.115 +    }
   2.116 +
   2.117 +    list_add_tail(&svm->runq_elem, iter);
   2.118 +}
   2.119 +
   2.120 +static void sched_credit_init(void)
   2.121 +{
   2.122 +    printf("%s()\n", __func__);
   2.123 +    INIT_LIST_HEAD(&sched_priv.runq);
   2.124 +    sched_priv.max_vm=0;
   2.125 +}
   2.126 +
   2.127 +static void sched_credit_vm_init(int vid)
   2.128 +{
   2.129 +    struct sched_vm *svm;
   2.130 +
   2.131 +    printf("%s: vm %d\n", __func__, vid);
   2.132 +
   2.133 +    if ( vid > MAX_VMS )
   2.134 +    {
   2.135 +        fprintf(stderr, "vid %d > MAX_VMS %d!\n", vid, MAX_VMS);
   2.136 +        exit(1);
   2.137 +    }
   2.138 +
   2.139 +    svm = sched_priv.vms + vid;
   2.140 +
   2.141 +    INIT_LIST_HEAD(&svm->runq_elem);
   2.142 +
   2.143 +    svm->vid = vid;
   2.144 +    svm->v = vm_from_vid(vid);
   2.145 +
   2.146 +    svm->credit = CREDIT_INIT;
   2.147 +    svm->weight = 1;
   2.148 +    svm->start_time = 0;
   2.149 +    
   2.150 +    if ( vid > sched_priv.max_vm )
   2.151 +        sched_priv.max_vm = vid;
   2.152 +}
   2.153 +
   2.154 +static void sched_credit_wake(int time, int vid)
   2.155 +{
   2.156 +    struct vm *v;
   2.157 +    struct sched_vm *svm;
   2.158 +
   2.159 +    v = vm_from_vid(vid);
   2.160 +
   2.161 +    printf("%s: time %d vid %d\n",
   2.162 +           __func__, time, v->vid);
   2.163 +
   2.164 +    svm = sched_priv.vms + v->vid;
   2.165 +
   2.166 +    ASSERT(list_empty(&svm->runq_elem));
   2.167 +
   2.168 +    runq_insert(svm);
   2.169 +
   2.170 +    /* Scan for either:
   2.171 +     * + an idle cpu to wake up, or
   2.172 +     * + if there are cpus with lower credits, the lowest one
   2.173 +     */
   2.174 +    {
   2.175 +        int i, ipid=-1, lowest = svm->credit;
   2.176 +        
   2.177 +
   2.178 +        for ( i=0; i<P.count; i++ )
   2.179 +        {
   2.180 +            if ( P.pcpus[i].idle )
   2.181 +            {
   2.182 +                printf(" %s: p%d idle, waking\n", __func__, i);
   2.183 +                ipid=i;
   2.184 +                break;
   2.185 +            }
   2.186 +            else if ( P.pcpus[i].current )
   2.187 +            {
   2.188 +                struct vm* ovm = P.pcpus[i].current;
   2.189 +                int ovid = ovm->vid;
   2.190 +                struct sched_vm *osvm = sched_priv.vms + ovid;
   2.191 +
   2.192 +                /* Update credits of currently running VM */
   2.193 +                burn_credit(osvm, time);
   2.194 +
   2.195 +                if ( osvm->credit < lowest )
   2.196 +                {
   2.197 +                    ipid = i;
   2.198 +                    lowest = osvm->credit;
   2.199 +                }
   2.200 +            }
   2.201 +            
   2.202 +        }
   2.203 +
   2.204 +        if ( ipid >= 0 )
   2.205 +            sim_sched_timer(0, ipid);
   2.206 +        else
   2.207 +            dump_credit(time, svm);
   2.208 +    }
   2.209 +}
   2.210 +
   2.211 +static struct vm* sched_credit_schedule(int time, int pid)
   2.212 +{
   2.213 +    struct sched_vm *svm;
   2.214 +    struct vm *next, *prev;
   2.215 +    int timer;
   2.216 +
   2.217 +    printf("%s: time %d pid %d\n",
   2.218 +           __func__, time, pid);
   2.219 +    prev = current(pid);
   2.220 +
   2.221 +    if ( prev )
   2.222 +    {
   2.223 +        printf(" current v%d\n", prev->vid);
   2.224 +        svm = sched_priv.vms + prev->vid;
   2.225 +
   2.226 +        burn_credit(svm, time);
   2.227 +
   2.228 +        if ( svm->v->runstate == RUNSTATE_RUNNING )
   2.229 +        {
   2.230 +            printf(" adding to runqueue\n");
   2.231 +            runq_insert(svm);
   2.232 +        }
   2.233 +    }
   2.234 +
   2.235 +    /* Take guy on front of runqueue, set new timer */
   2.236 +    if ( list_empty(&sched_priv.runq) )
   2.237 +    {
   2.238 +        printf(" No runnable entities\n");
   2.239 +        return NULL;
   2.240 +    }
   2.241 +
   2.242 +    svm = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
   2.243 +
   2.244 +    list_del_init(&svm->runq_elem);
   2.245 +
   2.246 +    next = svm->v;
   2.247 +
   2.248 +    if ( svm->credit <= CREDIT_RESET )
   2.249 +    {
   2.250 +        printf(" vid %d credit %c, resetting credit at time %d\n",
   2.251 +               svm->vid,
   2.252 +               svm->credit,
   2.253 +               time);
   2.254 +        reset_credit(time);
   2.255 +    }
   2.256 +
   2.257 +    dump_credit(time, svm);
   2.258 +    svm->start_time = time;
   2.259 +
   2.260 +    timer = calc_timer(svm);
   2.261 +
   2.262 +    sim_sched_timer(timer, pid);
   2.263 +
   2.264 +    printf(" next: v%d\n", next->vid);
   2.265 +    
   2.266 +    return next;
   2.267 +}
   2.268 +
   2.269 +struct scheduler sched_credit02 =
   2.270 +{
   2.271 +    .name="credit02",
   2.272 +    .desc="Zero-start, burn based on weight, reset to zero at negative credit",
   2.273 +    .ops = {
   2.274 +        .sched_init = sched_credit_init,
   2.275 +        .vm_init    = sched_credit_vm_init,
   2.276 +        .wake       = sched_credit_wake,
   2.277 +        .schedule   = sched_credit_schedule
   2.278 +    }
   2.279 +};
     3.1 --- a/simulator.c	Tue Oct 20 18:12:57 2009 +0100
     3.2 +++ b/simulator.c	Tue Oct 20 18:14:37 2009 +0100
     3.3 @@ -58,11 +58,13 @@ struct global_vm_data V;
     3.4  
     3.5  extern struct scheduler sched_rr;
     3.6  extern struct scheduler sched_credit01;
     3.7 +extern struct scheduler sched_credit02;
     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      NULL
    3.15  };
    3.16