gdunlap/sched-sim.hg

diff sched_credit01.c @ 5:18f3d6e25ffc

Add credit01 scheduler
author George Dunlap <gdunlap@xensource.com>
date Mon Oct 19 20:14:47 2009 +0100 (2009-10-19)
parents
children e274ac3f81ff
line diff
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/sched_credit01.c	Mon Oct 19 20:14:47 2009 +0100
     1.3 @@ -0,0 +1,249 @@
     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_RESET 0
    1.17 +#define MAX_TIMER 200
    1.18 +#define MIN_TIMER 100
    1.19 +
    1.20 +struct sched_vm {
    1.21 +    struct list_head runq_elem;
    1.22 +    struct vm *v;
    1.23 +
    1.24 +    int weight;
    1.25 +
    1.26 +    int credit;
    1.27 +    int credit_per_min_timer; /* ? */
    1.28 +    int start_time;
    1.29 +    int vid;
    1.30 +};
    1.31 +
    1.32 +struct {
    1.33 +    struct list_head runq; /* Global run queue */
    1.34 +    int max_vm;
    1.35 +    struct sched_vm vms[MAX_VMS];
    1.36 +    int ncpus;
    1.37 +
    1.38 +    int global_weight;
    1.39 +    int scale_factor; /* ? */
    1.40 +
    1.41 +    int next_check;
    1.42 +} sched_priv;
    1.43 +
    1.44 +
    1.45 +
    1.46 +void reset_credit(int time)
    1.47 +{
    1.48 +    int i;
    1.49 +    for ( i=0; i<=sched_priv.max_vm; i++)
    1.50 +    {
    1.51 +        sched_priv.vms[i].credit = CREDIT_INIT;
    1.52 +        sched_priv.vms[i].start_time = time;
    1.53 +    }
    1.54 +    /* No need to resort runq, as everyone's credit is now zero */
    1.55 +}
    1.56 +
    1.57 +void dump_credit(int time, struct sched_vm *svm)
    1.58 +{
    1.59 +    printf("credit v%d %d %d\n", svm->vid, time, svm->credit);
    1.60 +}
    1.61 +
    1.62 +void burn_credit(struct sched_vm *svm, int time)
    1.63 +{
    1.64 +    ASSERT(time >= svm->start_time);
    1.65 +
    1.66 +    svm->credit -= (time - svm->start_time);
    1.67 +    svm->start_time = time;
    1.68 +
    1.69 +    dump_credit(time, svm);
    1.70 +}
    1.71 +
    1.72 +int calc_timer(struct sched_vm *svm)
    1.73 +{
    1.74 +    int time = MAX_TIMER;
    1.75 +
    1.76 +    if ( time > svm->credit )
    1.77 +        time = svm->credit;
    1.78 +#if 0
    1.79 +    if ( !list_empty(&sched_priv.runq) )
    1.80 +    {
    1.81 +        struct sched_vm *sq = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
    1.82 +
    1.83 +        ASSERT(svm->credit >= sq->credit);
    1.84 +
    1.85 +        if ( (svm->credit - sq->credit) < time )
    1.86 +            time = (svm->credit - sq->credit);
    1.87 +    }
    1.88 +
    1.89 +#endif
    1.90 +
    1.91 +    if ( time < MIN_TIMER )
    1.92 +        time = MIN_TIMER;
    1.93 +    return time;
    1.94 +}
    1.95 +
    1.96 +void runq_insert(struct sched_vm *svm)
    1.97 +{
    1.98 +    struct list_head *iter;
    1.99 +    int pos = 0;
   1.100 +
   1.101 +    list_for_each( iter, &sched_priv.runq )
   1.102 +    {
   1.103 +        struct sched_vm * iter_svm;
   1.104 +
   1.105 +        iter_svm = list_entry(iter, struct sched_vm, runq_elem);
   1.106 +
   1.107 +        if ( svm->credit > iter_svm->credit )
   1.108 +        {
   1.109 +            printf(" p%d v%d\n",
   1.110 +                   pos,
   1.111 +                   iter_svm->vid);
   1.112 +            break;
   1.113 +        }
   1.114 +        pos++;
   1.115 +    }
   1.116 +
   1.117 +    list_add_tail(&svm->runq_elem, iter);
   1.118 +}
   1.119 +
   1.120 +static void sched_credit_init(void)
   1.121 +{
   1.122 +    printf("%s()\n", __func__);
   1.123 +    INIT_LIST_HEAD(&sched_priv.runq);
   1.124 +    sched_priv.max_vm=0;
   1.125 +}
   1.126 +
   1.127 +static void sched_credit_vm_init(int vid)
   1.128 +{
   1.129 +    struct sched_vm *svm;
   1.130 +
   1.131 +    printf("%s: vm %d\n", __func__, vid);
   1.132 +
   1.133 +    if ( vid > MAX_VMS )
   1.134 +    {
   1.135 +        fprintf(stderr, "vid %d > MAX_VMS %d!\n", vid, MAX_VMS);
   1.136 +        exit(1);
   1.137 +    }
   1.138 +
   1.139 +    svm = sched_priv.vms + vid;
   1.140 +
   1.141 +    INIT_LIST_HEAD(&svm->runq_elem);
   1.142 +
   1.143 +    svm->vid = vid;
   1.144 +    svm->v = vm_from_vid(vid);
   1.145 +
   1.146 +    svm->credit = CREDIT_INIT;
   1.147 +    svm->weight = 1;
   1.148 +    svm->start_time = 0;
   1.149 +    
   1.150 +    if ( vid > sched_priv.max_vm )
   1.151 +        sched_priv.max_vm = vid;
   1.152 +}
   1.153 +
   1.154 +static void sched_credit_wake(int time, int vid)
   1.155 +{
   1.156 +    struct vm *v;
   1.157 +    struct sched_vm *svm;
   1.158 +
   1.159 +    v = vm_from_vid(vid);
   1.160 +
   1.161 +    printf("%s: time %d vid %d\n",
   1.162 +           __func__, time, v->vid);
   1.163 +
   1.164 +    svm = sched_priv.vms + v->vid;
   1.165 +
   1.166 +    ASSERT(list_empty(&svm->runq_elem));
   1.167 +
   1.168 +    runq_insert(svm);
   1.169 +
   1.170 +    /* Never preempt on wake; only kick idle processors */
   1.171 +    if ( P.idle > 0 )
   1.172 +    {
   1.173 +        int i;
   1.174 +
   1.175 +        for ( i=0; i<P.count; i++ )
   1.176 +            if ( P.pcpus[i].idle )
   1.177 +                break;
   1.178 +
   1.179 +        printf(" %s: waking p%d\n", __func__, i);
   1.180 +        sim_sched_timer(0, i);
   1.181 +    }
   1.182 +}
   1.183 +
   1.184 +static struct vm* sched_credit_schedule(int time, int pid)
   1.185 +{
   1.186 +    struct sched_vm *svm;
   1.187 +    struct vm *next, *prev;
   1.188 +    int timer;
   1.189 +
   1.190 +    printf("%s: time %d pid %d\n",
   1.191 +           __func__, time, pid);
   1.192 +    prev = current(pid);
   1.193 +
   1.194 +    if ( prev )
   1.195 +    {
   1.196 +        printf(" current v%d\n", prev->vid);
   1.197 +        svm = sched_priv.vms + prev->vid;
   1.198 +
   1.199 +        burn_credit(svm, time);
   1.200 +
   1.201 +        if ( svm->v->runstate == RUNSTATE_RUNNING )
   1.202 +        {
   1.203 +            printf(" adding to runqueue\n");
   1.204 +            runq_insert(svm);
   1.205 +        }
   1.206 +    }
   1.207 +
   1.208 +    /* Take guy on front of runqueue, set new timer */
   1.209 +    if ( list_empty(&sched_priv.runq) )
   1.210 +    {
   1.211 +        printf(" No runnable entities\n");
   1.212 +        return NULL;
   1.213 +    }
   1.214 +
   1.215 +    svm = list_entry(sched_priv.runq.next, struct sched_vm, runq_elem);
   1.216 +
   1.217 +    list_del_init(&svm->runq_elem);
   1.218 +
   1.219 +    next = svm->v;
   1.220 +
   1.221 +    if ( svm->credit <= CREDIT_RESET )
   1.222 +    {
   1.223 +        printf(" vid %d credit %c, resetting credit at time %d\n",
   1.224 +               svm->vid,
   1.225 +               svm->credit,
   1.226 +               time);
   1.227 +        reset_credit(time);
   1.228 +    }
   1.229 +
   1.230 +    dump_credit(time, svm);
   1.231 +    svm->start_time = time;
   1.232 +
   1.233 +    timer = calc_timer(svm);
   1.234 +
   1.235 +    sim_sched_timer(timer, pid);
   1.236 +
   1.237 +    printf(" next: v%d\n", next->vid);
   1.238 +    
   1.239 +    return next;
   1.240 +}
   1.241 +
   1.242 +struct scheduler sched_credit01 =
   1.243 +{
   1.244 +    .name="credit01",
   1.245 +    .desc="Zero-start, burn based on weight, reset to zero at negative credit",
   1.246 +    .ops = {
   1.247 +        .sched_init = sched_credit_init,
   1.248 +        .vm_init    = sched_credit_vm_init,
   1.249 +        .wake       = sched_credit_wake,
   1.250 +        .schedule   = sched_credit_schedule
   1.251 +    }
   1.252 +};