Subversion Repositories shark

/*

 * Project: S.Ha.R.K.

 *

 * Coordinators:

 *   Giorgio Buttazzo    <giorgio@sssup.it>

 *   Paolo Gai           <pj@gandalf.sssup.it>

 *

 * Authors     :

 *   Paolo Gai           <pj@gandalf.sssup.it>

 *   Massimiliano Giorgi <massy@gandalf.sssup.it>

 *   Luca Abeni          <luca@gandalf.sssup.it>

 *   (see the web pages for full authors list)

 *

 * ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy)

 *

 * http://www.sssup.it

 * http://retis.sssup.it

 * http://shark.sssup.it

 */

/**

 ------------

 CVS :        $Id: slsh.c,v 1.1 2004-06-01 11:42:46 giacomo Exp $

 File:        $File$

 Revision:    $Revision: 1.1 $

 Last update: $Date: 2004-06-01 11:42:46 $

 ------------

 This file contains the scheduling module for Slot-Shifting.

 Read slsh.h for further details.

**/

/*

 * Copyright (C) 2000 Paolo Gai

 *

 * This program is free software; you can redistribute it and/or modify

 * it under the terms of the GNU General Public License as published by

 * the Free Software Foundation; either version 2 of the License, or

 * (at your option) any later version.

 *

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 *

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 *

 */

#include "slsh.h"

#include <ll/stdio.h>

#include <ll/stdlib.h>

#include <ll/string.h>

#include <ll/math.h>    /* for ceil(...) */

#include <ll/ll.h>      /* for memcpy(...) */

#include <kernel/model.h>

#include <kernel/descr.h>

#include <kernel/var.h>

#include <kernel/func.h>

//#define eslsh_printf kern_printf

#define slsh_printf printk

/* Keeps information about static and guaranteed tasks */

typedef struct {

        int est;

        int dabs;

        int interval;

} SLSH_task;

/*+ Status used in the level +*/

#define SLSH_READY                      MODULE_STATUS_BASE

#define SLSH_WAIT                       MODULE_STATUS_BASE + 1

#define SLSH_IDLE                       MODULE_STATUS_BASE + 2

#define SLSH_WCET_VIOLATED      MODULE_STATUS_BASE + 3

/*+ defines +*/

#define MAX_INTERVALS 1000              /* 1000 intervals is max, for now */

/******+ the level redefinition for the SLOT SHIFT level +*******/

typedef struct {

        level_des l;                    /*+ the standard level descriptor+*/

        /* task lists */

        SLSH_task tasks[MAX_PROC];  /* est and dl's for static and guaranteed task */

        IQUEUE idle_statics; /* finished static tasks */

        IQUEUE unspecified;     /* tasks with only a wcet */

        /* the Intervals list */

        SLSH_interval intervals[MAX_INTERVALS];

        int current;                    /* current interval */

        int last;                       /* last interval */

        int slot;                       /* slot shifting time */

        TIME slot_length;       /* slothlength in real system time*/

        int LCM;                        /* length (in slots) of ofline schedule */

        int slot_event;         /* save the event */

} SLSH_level_des;

/* check if some tasks are ready, return 0 if ready, -1 otherwise */

static int SLSH_R(SLSH_task* tasks)

{

        int s;

        /* for all static tasks */

        for(s = 0; tasks[s].est != -1; ++s)

        {

           if(proc_table[s].status == SLSH_READY)

               return 0;

        }

        return -1;

}

/* check if unspecified exists, return 0 if it exists, -1 otherwise */

static int SLSH_T(IQUEUE *unspecified)

{

        if(!iq_isempty(unspecified))

                return 0;

        else

                return -1;

}

/* return the sc in an interval */

static int SLSH_sc(SLSH_interval* intervals, int i)

{

        return intervals[i].sc;

}

/* return a static task from current interval or a guaranted task */

static PID SLSH_staticOrGuaranteed(SLSH_level_des* lev)

{

        int lowest_dl = 0;      /* lowest dl found */

        PID pid = 0;            /* static or guaranteed task */

        int t;

        /* Decide according to EDF, go through all static & guaranteed tasks */

        for(t = 0; t < MAX_PROC; ++t)

        {

                /* static tasks */

                if(proc_table[t].pclass == STATIC_PCLASS)

                {

                        /* static task must belong to current interval */

                        if(lev->tasks[t].interval == lev->current)

                        {

                                /* only ready tasks */

                                if(proc_table[t].status == SLSH_READY)

                                {

                                        /* a new lower dl was found */

                                        if(lev->tasks[t].dabs < lowest_dl)

                                        {

                                                lowest_dl = lev->tasks[t].dabs;

                                                pid = t;

                                        }

                                }

                        }

                } /* guaranteed tasks */

                else if(proc_table[t].pclass == HARD_PCLASS)

                {

                        /* only ready tasks */

                        if(proc_table[t].status == SLSH_READY)

                        {

                                /* a new lower dl was found */

                                if(lev->tasks[t].dabs < lowest_dl)

                                {

                                        lowest_dl = lev->tasks[t].dabs;

                                        pid = t;

                        }

                        }

                }

        }/* for all tasks */

        return pid;    

}

/* return a static task among the candidates, all ready statics */

static PID SLSH_candidates(SLSH_task* tasks)

{

        int lowest_dl = 0;

        PID pid = -1;

        int t;

        /* Use the EDL algorithm again to decide which task to run */

        for(t = 0; t < MAX_PROC; ++t)

        {

                /* only static tasks */

                if(proc_table[t].pclass == STATIC_PCLASS)

                {

                        /* only ready tasks */

                        if(proc_table[t].status == SLSH_READY)

                        {      

                                /* a new lower dl was found */

                                if(tasks[t].dabs < lowest_dl)

                                {

                                        lowest_dl = tasks[t].dabs;

                                        pid = t;

                                }

                        }/* all ready tasks */

                }/* all static tasks */

        }/* for all tasks */

        return pid;

}

/* decrease the sc in a interval by amount */

void SLSH_decSc(SLSH_interval* intervals, int i, int amount)

{

        intervals[i].sc -= amount;

}

void SLSH_incSc(SLSH_interval* intervals, int i, int amount)

{

        intervals[i].sc += amount;

}

/* swap the sc between intervals, also consider intervals with negative sc */

void SLSH_swapSc(SLSH_interval* intervals, int current, int task_interval)

{

        /* decrease the sc in the current interval */

        SLSH_decSc(intervals, current, 1);

        /* update the other interval(s) */

        if(intervals[task_interval].sc < 0)     /* negative sc */

        {

                /* special case, increase next interval sc by 1 and also current interval (borrowing) */

                if(task_interval == current + 1)

                {

                        SLSH_incSc(intervals, task_interval, 1);

                        SLSH_incSc(intervals, current, 1);

                }

                else /* increase every interval sc that is negative between current and task_interval */

                {

                        while(task_interval > current && intervals[task_interval].sc < 0)

                        {

                                SLSH_incSc(intervals, task_interval, 1);

                                task_interval--;

                        }

                }

        }

        else /* ordinary swapping */

                SLSH_incSc(intervals, task_interval, 1);

}

/* The scheduler, decides which task to run. */

static PID SLSH_public_scheduler(LEVEL l)

{

        SLSH_level_des* lev = (SLSH_level_des *)(level_table[l]);

        PID pid;

        /* The scheduler choses among static, guaranteed (hard aperiodic) and

             unspecified (soft aperiodic) tasks */

        /* no ready tasks and no sc, execute idle task */

        if(SLSH_R(lev->tasks) == 0 && SLSH_sc(lev->intervals, lev->current) == 0)

                return NIL;

        /* must execute a static from current intervall or a guaranteed task */

        else if(SLSH_R(lev->tasks) > 0 && SLSH_sc(lev->intervals, lev->current) == 0)

                return SLSH_staticOrGuaranteed(lev);

        /* sc available... */

        else if(SLSH_R(lev->tasks) > 0 && SLSH_sc(lev->intervals, lev->current) > 0)

        {

                /* If unspecified exist, execute it according to FIFO order */

                if(SLSH_T(&lev->unspecified) == 0)

                {

                        SLSH_decSc(lev->intervals, lev->current, 1);    /* decrease sc by 1 */

                        return iq_getfirst(&lev->unspecified);

                }

                else /* No unspecified, execute task from candidates (statics) */

                {              

                        pid = SLSH_candidates(lev->tasks);

                        /* sc needs to be swapped */

                        if(lev->tasks[pid].interval != lev->current)

                                SLSH_swapSc(lev->intervals, lev->tasks[pid].interval, lev->current);

                        return pid;            

                }              

        }

        kern_printf("(SLSH s)");

        return NIL;

}

/* not used, slot-shifting handles all guarantees itself, it handles all bandwidth */

static int SLSH_public_guarantee(LEVEL l, bandwidth_t *freebandwidth)

{

        *freebandwidth = 0;

        return 1;

}

/* get the interval that x is in */

static int SLSH_getInterval(SLSH_interval* intervals, int x, int last)

{

        int i;

        /* search through the intervals  */

        for(i = 0; i <= last; ++i)

        {

                /* I is in the interval where start is smaller or equal and end is bigger */           

                if(intervals[i].start <= x && x < intervals[i].end)

                        return i;

        }

        return -1;

}

/* get the start of the interval I */

static int SLSH_intervalStart(SLSH_interval* intervals, int I)

{

        return intervals[I].start;

}

/* split interval I into two parts, slow because of copying. OBS!!! no check if there is

    enough space in the intervals array */

static void SLSH_splitInterval(SLSH_level_des* lev, int I, int dabs)

{

        SLSH_interval left_interval;

        int i;

        lev->last++;

        /* move every interval above and including I */

        for(i = lev->last; i > I; --i)

                memcpy(&lev->intervals[i], &lev->intervals[i - 1], sizeof(SLSH_interval));

        /* Left interval start, end and length */

        left_interval.start = lev->intervals[I].start;

        left_interval.end = dabs;

        left_interval.length = left_interval.end - left_interval.start;

        /* Right interval (uses old interval struct) start and length end remains as the old value */

        lev->intervals[I + 1].start = dabs;

        lev->intervals[I + 1].length = lev->intervals[I + 1].end - lev->intervals[I + 1].start;

        /* check if sc still exists in the right interval */

        if(lev->intervals[I + 1].length - lev->intervals[I + 1].maxt > 0)

        {

                lev->intervals[I + 1].sc = lev->intervals[I + 1].length - lev->intervals[I + 1].maxt;

                left_interval.sc = left_interval.length; /* the whole interval is free, for now... */

        }

        else /* no sc in the right interval */

        {

                lev->intervals[I + 1].maxt = lev->intervals[I + 1].length;

                left_interval.sc = lev->intervals[I + 1].sc; /* all sc in left interval */

                lev->intervals[I + 1].sc = 0;

        }        

        /* insert the new interval */

        memcpy(&lev->intervals[I], &left_interval, sizeof(SLSH_interval));

}

/* Reduce the sc from back to front by the wcet amount, interval splitting may be neccesary */

static void SLSH_updateSc(SLSH_level_des* lev, HARD_TASK_MODEL* h)

{

        int dabs = ceil((lev->slot + h->drel)/lev->slot_length); /* absolute deadline of request */

        int dabs_interval = SLSH_getInterval(lev->intervals, dabs, lev->last); /* interval where dabs is */

        int C = ceil(h->wcet/lev->slot_length); /* amount of sc to reduce */   

        int sc = 0;

        int i;

        /* check if interval splitting is neccesary */

        if(lev->intervals[dabs_interval].end != dabs)

                SLSH_splitInterval(lev, dabs_interval, dabs);

        /* decrease sc in all intervals that are neccesary from dabs_interval o current */

        for(i = dabs_interval; i >= lev->current && C > 0; --i)

        {

                if((sc = SLSH_sc(lev->intervals, i)) >= 0) /* only decrease where sc exists */

                {

                        if(sc > C) /* the last sc dec */

                        {

                                SLSH_decSc(lev->intervals, i, C);

                                C = 0;

                        }

                        else    /* to little sc in this interval, decrease it to 0 */

                        {

                                C -= SLSH_sc(lev->intervals, i);

                                SLSH_decSc(lev->intervals, i, SLSH_sc(lev->intervals, i));

                        }              

                }

        }/* for all intervals */

}

/* the guarantee algorithm for hard aperiodic requests */

static int SLSH_guarantee(SLSH_level_des* lev, HARD_TASK_MODEL* h)

{

        int total_sc = 0;

        int temp, i;

        int dabs = ceil((lev->slot + h->drel)/lev->slot_length); /* absolute deadline of request */

        int dabs_interval = SLSH_getInterval(lev->intervals, dabs, lev->last); /* interval where dabs is */

        /* check if the sc up until request deadline is >= request wcet */

        /* 1. the sc of the current interal */

        total_sc = SLSH_sc(lev->intervals, lev->current);

        /* 2. the sc for all whole intervals between current and the interval

            with the request deadline */

        for(i = (lev->current) + 1; i < dabs_interval; ++i)

        {

                if((temp = SLSH_sc(lev->intervals, i)) > 0)

                        total_sc += temp;

        }

        /* 3. the min of sc or the execution need in the last interval */

        total_sc += min(SLSH_sc(lev->intervals, dabs_interval),

                                dabs - SLSH_intervalStart(lev->intervals,

                                dabs_interval));

        if(total_sc >= h->wcet)

        {       /* update the sc in the intervals from back to front */

                SLSH_updateSc(lev, h);

                return 0;

        }

        else

                return -1;

}

/* check if task model is accepted and store nessecary parameters */

static int SLSH_public_create(LEVEL l, PID p, TASK_MODEL *m)

{

        SLSH_level_des *lev = (SLSH_level_des *)(level_table[l]);

        STATIC_TASK_MODEL* s;

        HARD_TASK_MODEL* h;

        SOFT_TASK_MODEL* u;

        /* Check the models */

        switch(m->pclass)

        {

        case STATIC_PCLASS:             /* offline scheduled tasks */

          break;

        case HARD_PCLASS:               /* hard aperiodic tasks */

          h = (HARD_TASK_MODEL *) m;

          if (h->drel == 0 || h->wcet == 0)     /* must be set */

            return -1;

          break;

        case SOFT_PCLASS:               /* soft aperiodic tasks */

          u = (SOFT_TASK_MODEL *) m;

          if(u->wcet == 0)              /* must be set */

            return -1;

          break;

        default:

          return -1;

        }

        /* if the SLSH_task_create is called, then the pclass must be a

        valid pclass. Slot-shifting accepts STATIC_TASK, HARD_TASK

        and SOFT_TASK models with some restrictions */

        /* est, dl and wcet is saved in slotlengths */

        switch(m->pclass)

        {      

                case STATIC_PCLASS:     /* offline scheduled tasks */

                        s = (STATIC_TASK_MODEL *) m;

                        lev->tasks[p].est = ceil(s->est/lev->slot_length);             

                        lev->tasks[p].dabs = ceil(s->dabs/lev->slot_length);

                        lev->tasks[p].interval = s->interval;

                        proc_table[p].avail_time = s->wcet;                    

                        proc_table[p].wcet = s->wcet;

                        break;

                case HARD_PCLASS:       /* hard aperiodic tasks */

                        h = (HARD_TASK_MODEL *) m;

                        if(SLSH_guarantee(lev, h) == 0)

                        {

                                /* convert drel to dabs */                     

                                lev->tasks[p].dabs = ceil((lev->slot + h->drel)/lev->slot_length);

                                proc_table[p].avail_time = h->wcet;

                                proc_table[p].wcet = h->wcet;

                        }

                        else /* task not guaranteed */

                                return -1;                     

                        break;

                case SOFT_PCLASS:

                        u = (SOFT_TASK_MODEL *) m;

                        proc_table[p].avail_time = u->wcet;

                        proc_table[p].wcet = u->wcet;

                        iq_insertlast(p, &lev->unspecified);    /* respect FIFO order */

                        break;

                default:        /* a task model not supported */

                        return -1;

        }

        /* enable wcet check in the kernel */

        proc_table[p].control |= CONTROL_CAP;

        return 0;

}

/************* The slot end event handler *************/

static void SLSH_slot_end(void* p)

{

        SLSH_level_des* lev = (SLSH_level_des *) p;

        PID pid;

        int i;

        /* increase slot "time" by 1 */

        if(lev->slot < lev->LCM)

        {

                lev->slot++;

                /* check if new statics are ready */

                for(i = 0; lev->tasks[i].interval != -1; ++i)

                {

                        if(lev->tasks[i].est <= lev->slot && proc_table[i].status == SLSH_WAIT)

                                proc_table[i].status = SLSH_READY;

                }

                /* check if current (interval) needs updating */

                if(lev->current < SLSH_getInterval(lev->intervals, lev->slot, lev->last))

                        lev->current++;

        }

        else /* restart from the beginning of the offline schedule */

        {

                lev->slot = 0;

                while((pid = iq_getfirst(&lev->idle_statics)) != NIL)

                {

                        if(lev->tasks[pid].est <= lev->slot)

                                proc_table[pid].status = SLSH_READY;

                        else

                                proc_table[pid].status = SLSH_WAIT;

                }

        }

        /* call for a rescheduling, reset event flag and increase slot by 1  */

        lev->slot_event = -1;

        kern_printf("*");

        event_need_reschedule();

}

/* when a task becomes executing (EXE status) */

static void SLSH_public_dispatch(LEVEL l, PID pid, int nostop)

{

        SLSH_level_des *lev = (SLSH_level_des *)(level_table[l]);

        struct timespec t;

        /* the task state is set EXE by the scheduler()

        we extract the task from the unspecified queue.

        NB: we can't assume that p is the first task in the queue!!! */

        if(proc_table[pid].pclass == SOFT_PCLASS)

                iq_extract(pid, &lev->unspecified);

        /* also start the timer for one slot length */

        lev->slot_event = kern_event_post(&TIME2TIMESPEC(lev->slot_length, t),

                                          SLSH_slot_end, (void*) lev);

}

/* called when task is moved from EXE status */

static void SLSH_public_epilogue(LEVEL l, PID pid)

{

        SLSH_level_des *lev = (SLSH_level_des *)(level_table[l]);

        /* check if the wcet is finished... */

        if (proc_table[pid].avail_time <= 0)

        {

                /* if it is, raise a XWCET_VIOLATION exception */

                kern_raise(XWCET_VIOLATION, pid);

                proc_table[pid].status = SLSH_WCET_VIOLATED;

        }

        else /* the end of a slot. the task returns into the ready queue... */

        {

                if(proc_table[pid].pclass == SOFT_PCLASS)

                        iq_insertfirst(pid,&lev->unspecified);

                proc_table[pid].status = SLSH_READY;

        }

}

/* when task go from SLEEP to SLSH_READY or SLSH_WAIT */

static void SLSH_public_activate(LEVEL l, PID pid)

{

        SLSH_level_des *lev = (SLSH_level_des *)(level_table[l]);

        WORD type = proc_table[pid].pclass;

        /* Test if we are trying to activate a non sleeping task    */

        /* Ignore this; the task is already active                  */

        if (proc_table[pid].status != SLEEP && proc_table[pid].status != SLSH_WCET_VIOLATED)

                return;

        /* make task ready or waiting, dependong on slot (the time) for static tasks only*/

        if(type == STATIC_PCLASS && lev->tasks[pid].est <= lev->slot)

                proc_table[pid].status = SLSH_READY;

        else

                proc_table[pid].status = SLSH_WAIT;

        if(type == HARD_PCLASS)

                proc_table[pid].status = SLSH_READY;

        /* insert unspecified tasks in QQUEUE and make it ready */

        if(type == SOFT_PCLASS)

        {              

                iq_insertlast(pid ,&lev->unspecified);

                proc_table[pid].status = SLSH_READY;

        }

}

/* when a task i returned to module from a semaphore, mutex ... */

static void SLSH_public_unblock(LEVEL l, PID pid)

{

        SLSH_level_des *lev = (SLSH_level_des *)(level_table[l]);

        /* change staus of task */

        proc_table[pid].status = SLSH_READY;

        if(proc_table[pid].pclass == SOFT_PCLASS)

                iq_insertfirst(pid ,&lev->unspecified);

}

/* when a semaphore, mutex ... taskes a task from module */

static void SLSH_public_block(LEVEL l, PID pid)

{

        /* Extract the running task from the level

        . we have already extract it from the ready queue at the dispatch time.

        . the capacity event have to be removed by the generic kernel

        . the wcet don't need modification...

        . the state of the task is set by the calling function

        . the deadline must remain...

        So, we do nothing!!!

        */

}

/* the task has finihed its wcet, kill task (dont kill static tasks)  */

static void SLSH_public_end(LEVEL l, PID pid)

{

        SLSH_level_des *lev = (SLSH_level_des *)(level_table[l]);

        if(proc_table[pid].pclass == SOFT_PCLASS)

        {      

                if (proc_table[pid].status == SLSH_READY)

                        iq_extract(pid, &lev->unspecified);

        }

        else if(proc_table[pid].pclass == HARD_PCLASS)

        {

                if (proc_table[pid].status == SLSH_READY)

                        lev->tasks[pid].dabs = 0;

        }

        /* static tasks: put them in idle QUEUE, reset status and avail_time */

        else if(proc_table[pid].pclass == STATIC_PCLASS)

        {

                proc_table[pid].avail_time = proc_table[pid].wcet;

                proc_table[pid].status = SLSH_IDLE;

                iq_priority_insert(pid, &lev->idle_statics);

        }

        proc_table[pid].status = FREE;

}

/* called when a task should sleep but not execute for awhile, mabe a mode change */

//static void SLSH_task_sleep(LEVEL l, PID pid)

//{

//

//      /* the task has terminated his job before it consume the wcet. All OK! */

//      proc_table[pid].status = SLEEP;

//      

//      /* we reset the capacity counters... only for static tasks */

//      if (proc_table[pid].pclass == STATIC_PCLASS)

//              proc_table[pid].avail_time = proc_table[pid].wcet;

//              

//}

/** Guest Functions, slot shifing accepts no guests, so all generates exceptions **/

/******* Registration functions *******/

/*+ Registration function: */

LEVEL SLSH_register_level()

{

        LEVEL l;            /* the level that we register */

        SLSH_level_des *lev;  /* for readableness only */

        PID i;              /* a counter */

        kern_printf("SLSH_register_level\n");

        /* request an entry in the level_table */

        l = level_alloc_descriptor(sizeof(SLSH_level_des));

        lev = (SLSH_level_des *)level_table[l];

        printk("    lev=%d\n",(int)lev);

        /* fill the standard descriptor */

        lev->l.public_scheduler = SLSH_public_scheduler;

        lev->l.public_guarantee = SLSH_public_guarantee;

        lev->l.public_create    = SLSH_public_create;

        lev->l.public_end       = SLSH_public_end;

        lev->l.public_dispatch  = SLSH_public_dispatch;

        lev->l.public_epilogue  = SLSH_public_epilogue;

        lev->l.public_activate  = SLSH_public_activate;

        lev->l.public_unblock   = SLSH_public_unblock;

        lev->l.public_block     = SLSH_public_block;

        /* fill the SLSH descriptor part */

        for(i = 0; i < MAX_PROC; i++)

        {

                lev->tasks[i].est = -1;

                lev->tasks[i].dabs = 0;

                lev->tasks[i].interval = -1;

        }

        for(i = 0; i < MAX_INTERVALS; i++)

        {

                lev->intervals[i].start = -1;

                lev->intervals[i].end = -1;

                lev->intervals[i].length = 0;

                lev->intervals[i].maxt = 0;

                lev->intervals[i].sc = 0;

        }

        lev->current = 0;

        lev->last = NIL;

        lev->slot = 0;

        lev->slot_length = 0;

        lev->slot_event = -1;

        return l;

}

void SLSH_set_interval(LEVEL l, int start, int end, int maxt)

{

        SLSH_level_des* lev = (SLSH_level_des *)(level_table[l]);

        static int i = -1;     

        i++;

        lev->intervals[i].start = start;

        lev->intervals[i].end = end;

        lev->intervals[i].length = end - start;

        lev->intervals[i].maxt = maxt;

        lev->intervals[i].sc = lev->intervals[i].length - maxt;

        lev->last = i;

}

void SLSH_set_variables(LEVEL l, TIME length)

{

        SLSH_level_des* lev = (SLSH_level_des *)(level_table[l]);

        lev->slot_length = length;                     

}