gdunlap/sched-sim.hg

changeset 5:18f3d6e25ffc

Add credit01 scheduler
author George Dunlap <gdunlap@xensource.com>
date Mon Oct 19 20:14:47 2009 +0100 (2009-10-19)
parents f7c1a67cf976
children 403bd7680df6
files Makefile sched_credit01.c simulator.c
line diff
     1.1 --- a/Makefile	Mon Oct 19 20:12:54 2009 +0100
     1.2 +++ b/Makefile	Mon Oct 19 20:14:47 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
     1.8 +simulator: simulator.o workloads.o sched_rr.o stats.o options.o sched_credit01.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_credit01.c	Mon Oct 19 20:14:47 2009 +0100
     2.3 @@ -0,0 +1,249 @@
     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 +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 +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 +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 +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 +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 +    /* Never preempt on wake; only kick idle processors */
   2.171 +    if ( P.idle > 0 )
   2.172 +    {
   2.173 +        int i;
   2.174 +
   2.175 +        for ( i=0; i<P.count; i++ )
   2.176 +            if ( P.pcpus[i].idle )
   2.177 +                break;
   2.178 +
   2.179 +        printf(" %s: waking p%d\n", __func__, i);
   2.180 +        sim_sched_timer(0, i);
   2.181 +    }
   2.182 +}
   2.183 +
   2.184 +static struct vm* sched_credit_schedule(int time, int pid)
   2.185 +{
   2.186 +    struct sched_vm *svm;
   2.187 +    struct vm *next, *prev;
   2.188 +    int timer;
   2.189 +
   2.190 +    printf("%s: time %d pid %d\n",
   2.191 +           __func__, time, pid);
   2.192 +    prev = current(pid);
   2.193 +
   2.194 +    if ( prev )
   2.195 +    {
   2.196 +        printf(" current v%d\n", prev->vid);
   2.197 +        svm = sched_priv.vms + prev->vid;
   2.198 +
   2.199 +        burn_credit(svm, time);
   2.200 +
   2.201 +        if ( svm->v->runstate == RUNSTATE_RUNNING )
   2.202 +        {
   2.203 +            printf(" adding to runqueue\n");
   2.204 +            runq_insert(svm);
   2.205 +        }
   2.206 +    }
   2.207 +
   2.208 +    /* Take guy on front of runqueue, set new timer */
   2.209 +    if ( list_empty(&sched_priv.runq) )
   2.210 +    {
   2.211 +        printf(" No runnable entities\n");
   2.212 +        return NULL;
   2.213 +    }
   2.214 +
   2.215 +    svm = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
   2.216 +
   2.217 +    list_del_init(&svm->runq_elem);
   2.218 +
   2.219 +    next = svm->v;
   2.220 +
   2.221 +    if ( svm->credit <= CREDIT_RESET )
   2.222 +    {
   2.223 +        printf(" vid %d credit %c, resetting credit at time %d\n",
   2.224 +               svm->vid,
   2.225 +               svm->credit,
   2.226 +               time);
   2.227 +        reset_credit(time);
   2.228 +    }
   2.229 +
   2.230 +    dump_credit(time, svm);
   2.231 +    svm->start_time = time;
   2.232 +
   2.233 +    timer = calc_timer(svm);
   2.234 +
   2.235 +    sim_sched_timer(timer, pid);
   2.236 +
   2.237 +    printf(" next: v%d\n", next->vid);
   2.238 +    
   2.239 +    return next;
   2.240 +}
   2.241 +
   2.242 +struct scheduler sched_credit01 =
   2.243 +{
   2.244 +    .name="credit01",
   2.245 +    .desc="Zero-start, burn based on weight, reset to zero at negative credit",
   2.246 +    .ops = {
   2.247 +        .sched_init = sched_credit_init,
   2.248 +        .vm_init    = sched_credit_vm_init,
   2.249 +        .wake       = sched_credit_wake,
   2.250 +        .schedule   = sched_credit_schedule
   2.251 +    }
   2.252 +};
     3.1 --- a/simulator.c	Mon Oct 19 20:12:54 2009 +0100
     3.2 +++ b/simulator.c	Mon Oct 19 20:14:47 2009 +0100
     3.3 @@ -57,10 +57,12 @@ struct global_vm_data {
     3.4  struct global_vm_data V;
     3.5  
     3.6  extern struct scheduler sched_rr;
     3.7 +extern struct scheduler sched_credit01;
     3.8  int default_scheduler = 0;
     3.9  struct scheduler *schedulers[] =
    3.10  {
    3.11      &sched_rr,
    3.12 +    &sched_credit01,
    3.13      NULL
    3.14  };
    3.15