Blame |
Last modification |
View Log
| RSS feed
/*
* Project: S.Ha.R.K.
*
* Coordinators: Giorgio Buttazzo <giorgio@sssup.it>
* Paolo Gai <pj@hartik.sssup.it>
*
* Authors : Marco Caccamo and Paolo Gai
*
* ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy)
*
* http://www.sssup.it
* http://retis.sssup.it
* http://shark.sssup.it
*/
/**
------------
CVS : $Id: cbs_ft.c,v 1.1 2004-06-01 11:42:41 giacomo Exp $
File: $File$
Revision: $Revision: 1.1 $
Last update: $Date: 2004-06-01 11:42:41 $
------------
This file contains the server CBS_FT
Read CBS_FT.h for further details.
**/
/*
* Copyright (C) 2000 Marco Caccamo and 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 "cbs_ft.h"
/*+ Status used in the level +*/
#define CBS_FT_IDLE APER_STATUS_BASE /*+ waiting the activation +*/
#define CBS_FT_ZOMBIE APER_STATUS_BASE+1 /*+ waiting the period end +*/
/* structure of an element of the capacity queue */
struct cap_queue {
int cap;
struct timespec dead;
struct cap_queue *next;
};
/*+ the level redefinition for the CBS_FT level +*/
typedef struct {
level_des l; /*+ the standard level descriptor +*/
/* The wcet are stored in the task descriptor, but we need
an array for the deadlines. We can't use the timespec_priority
field because it is used by the master level!!!...
Notice that however the use of the timespec_priority field
does not cause any problem... */
struct timespec cbs_ft_dline[MAX_PROC]; /*+ CBS_FT deadlines +*/
TIME period[MAX_PROC]; /*+ CBS_FT activation period +*/
int maxcap[MAX_PROC]; /* amount of capacity reserved to a primary+backup
couple */
PID backup[MAX_PROC]; /* Backup task pointers, defined for primary tasks */
char CP[MAX_PROC]; /* checkpoint flag */
char P_or_B[MAX_PROC]; /* Type of task: PRIMARY or BACKUP */
struct timespec reactivation_time[MAX_PROC];
/*+ the time at witch the reactivation timer is post +*/
int reactivation_timer[MAX_PROC]; /*+ the recativation timer +*/
struct cap_queue *queue; /* pointer to the spare capacity queue */
int flags; /*+ the init flags... +*/
bandwidth_t U; /*+ the used bandwidth by the server +*/
int idle; /* the idle flag... */
struct timespec start_idle; /*gives the start time of the last idle period */
LEVEL scheduling_level;
} CBS_FT_level_des;
/* insert a capacity in the queue capacity ordering by deadline */
static int c_insert(struct timespec dead, int cap, struct cap_queue **que,
PID p)
{
struct cap_queue *prev, *n, *new;
prev = NULL;
n = *que;
while ((n != NULL) &&
!TIMESPEC_A_LT_B(&dead, &n->dead)) {
prev = n;
n = n->next;
}
new = (struct cap_queue *)kern_alloc(sizeof(struct cap_queue));
if (new == NULL) {
kern_printf("\nNew cash_queue element failed\n");
kern_raise(XINVALID_TASK, p);
return -1;
}
new->next = NULL;
new->cap = cap;
new->dead = dead;
if (prev != NULL)
prev->next = new;
else
*que = new;
if (n != NULL)
new->next = n;
return 0;
}
/* extract the first element from the capacity queue */
int c_extractfirst(struct cap_queue **que)
{
struct cap_queue *p = *que;
if (*que == NULL) return(-1);
*que = (*que)->next;
kern_free(p, sizeof(struct cap_queue));
return(1);
}
/* read data of the first element from the capacity queue */
static void c_readfirst(struct timespec *d, int *c, struct cap_queue *que)
{
*d = que->dead;
*c = que->cap;
}
/* write data of the first element from the capacity queue */
static void c_writefirst(struct timespec dead, int cap, struct cap_queue *que)
{
que->dead = dead;
que->cap = cap;
}
static void CBS_FT_activation(CBS_FT_level_des *lev,
PID p,
struct timespec *acttime)
{
JOB_TASK_MODEL job;
int capacity;
/* This rule is used when we recharge the budget at initial task activation
and each time a new task instance must be activated */
if (TIMESPEC_A_GT_B(acttime, &lev->cbs_ft_dline[p])) {
/* we modify the deadline ... */
TIMESPEC_ASSIGN(&lev->cbs_ft_dline[p], acttime);
}
if (proc_table[p].avail_time > 0)
proc_table[p].avail_time = 0;
/* A spare capacity is inserted in the capacity queue!! */
ADDUSEC2TIMESPEC(lev->period[p], &lev->cbs_ft_dline[p]);
capacity = lev->maxcap[p] - proc_table[ lev->backup[p] ].wcet;
c_insert(lev->cbs_ft_dline[p], capacity, &lev->queue, p);
/* it exploits available capacities from the capacity queue */
while (proc_table[p].avail_time < proc_table[p].wcet &&
lev->queue != NULL) {
struct timespec dead;
int cap, delta;
delta = proc_table[p].wcet - proc_table[p].avail_time;
c_readfirst(&dead, &cap, lev->queue);
if (!TIMESPEC_A_GT_B(&dead, &lev->cbs_ft_dline[p])) {
if (cap > delta) {
proc_table[p].avail_time += delta;
c_writefirst(dead, cap - delta, lev->queue);
}
else {
proc_table[p].avail_time += cap;
c_extractfirst(&lev->queue);
}
}
else
break;
}
/* If the budget is still less than 0, an exception is raised */
if (proc_table[p].avail_time <= 0) {
kern_printf("\nnegative value for the budget!\n");
kern_raise(XINVALID_TASK, p);
return;
}
/*if (p==6)
kern_printf("(act_time:%d dead:%d av_time:%d)\n",
acttime->tv_sec*1000000+
acttime->tv_nsec/1000,
lev->cbs_ft_dline[p].tv_sec*1000000+
lev->cbs_ft_dline[p].tv_nsec/1000,
proc_table[p].avail_time); */
#ifdef TESTG
if (starttime && p == 3) {
oldx = x;
x = ((lev->cbs_ft_dline[p].tv_sec*1000000+lev->cbs_ft_dline[p].tv_nsec/1000)/5000 - starttime) + 20;
// kern_printf("(a%d)",lev->cbs_ft_dline[p].tv_sec*1000000+lev->cbs_ft_dline[p].tv_nsec/1000);
if (oldx > x) sys_end();
if (x<640)
grx_plot(x, 15, 8);
}
#endif
/* and, finally, we reinsert the task in the master level */
job_task_default_model(job, lev->cbs_ft_dline[p]);
job_task_def_yesexc(job);
level_table[ lev->scheduling_level ]->
private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job);
}
/* this is the periodic reactivation of the task... */
static void CBS_FT_timer_reactivate(void *par)
{
PID p = (PID) par;
CBS_FT_level_des *lev;
struct timespec t;
lev = (CBS_FT_level_des *)level_table[proc_table[p].task_level];
if (proc_table[p].status == CBS_FT_IDLE) {
/* the task has finished the current activation and must be
reactivated */
/* request_time represents the time of the last instance release!! */
TIMESPEC_ASSIGN(&t, &lev->reactivation_time[p]);
/* If idle=1, then we have to discharge the capacities stored in
the capacity queue up to the length of the idle interval */
if (lev->idle == 1) {
TIME interval;
struct timespec delta;
lev->idle = 0;
SUBTIMESPEC(&t, &lev->start_idle, &delta);
/* length of the idle interval expressed in usec! */
interval = TIMESPEC2NANOSEC(&delta) / 1000;
/* it discharges the available capacities from the capacity queue */
while (interval > 0 && lev->queue != NULL) {
struct timespec dead;
int cap;
c_readfirst(&dead, &cap, lev->queue);
if (cap > interval) {
c_writefirst(dead, cap - interval, lev->queue);
interval = 0;
}
else {
interval -= cap;
c_extractfirst(&lev->queue);
}
}
}
CBS_FT_activation(lev,p,&lev->reactivation_time[p]);
/* Set the reactivation timer */
TIMESPEC_ASSIGN(&lev->reactivation_time[p], &lev->cbs_ft_dline[p]);
lev->reactivation_timer[p] = kern_event_post(&lev->reactivation_time[p],
CBS_FT_timer_reactivate,
(void *)p);
event_need_reschedule();
}
else {
/* this situation cannot occur */
kern_printf("\nTrying to reactivate a primary task which is not IDLE!\n");
kern_raise(XINVALID_TASK,p);
}
}
static void CBS_FT_avail_time_check(CBS_FT_level_des *lev, PID p)
{
/*+ if the capacity became negative the remaining computation time
is diminuished.... +*/
/* if (p==4)
kern_printf("(old dead:%d av_time:%d)\n",
lev->cbs_ft_dline[p].tv_sec*1000000+
lev->cbs_ft_dline[p].tv_nsec/1000,
proc_table[p].avail_time); */
int newcap = proc_table[p].wcet / 100 * 30;
if (newcap <= 0)
newcap = proc_table[p].wcet;
/* it exploits available capacities from the capacity queue */
while (proc_table[p].avail_time < newcap
&& lev->queue != NULL) {
struct timespec dead;
int cap, delta;
delta = newcap - proc_table[p].avail_time;
c_readfirst(&dead, &cap, lev->queue);
if (!TIMESPEC_A_GT_B(&dead, &lev->cbs_ft_dline[p])) {
if (cap > delta) {
proc_table[p].avail_time += delta;
c_writefirst(dead, cap - delta, lev->queue);
}
else {
proc_table[p].avail_time += cap;
c_extractfirst(&lev->queue);
}
}
else
break;
}
/*if (p==6)
kern_printf("(ATC dead:%d av_time:%d)\n",
lev->cbs_ft_dline[p].tv_sec*1000000+
lev->cbs_ft_dline[p].tv_nsec/1000,
proc_table[p].avail_time); */
/* if the budget is still empty, the backup task must be woken up.
Remind that a short chunk of primary will go ahead executing
before the task switch occurs */
if (proc_table[p].avail_time <= 0) {
lev->CP[p] = 1;
proc_table[p].avail_time += proc_table[ lev->backup[p] ].wcet;
}
/*if (p==6)
kern_printf("(ATC1 dead:%d av_time:%d)\n",
lev->cbs_ft_dline[p].tv_sec*1000000+
lev->cbs_ft_dline[p].tv_nsec/1000,
proc_table[p].avail_time); */
}
/*+ this function is called when a killed or ended task reach the
period end +*/
static void CBS_FT_timer_zombie(void *par)
{
PID p = (PID) par;
CBS_FT_level_des *lev;
lev = (CBS_FT_level_des *)level_table[proc_table[p].task_level];
/* we finally put the task in the FREE status */
proc_table[p].status = FREE;
iq_insertfirst(p,&freedesc);
/* and free the allocated bandwidth */
lev->U -= (MAX_BANDWIDTH / lev->period[p]) * (TIME)lev->maxcap[p];
}
static PID CBS_FT_public_scheduler(LEVEL l)
{
CBS_FT_level_des *lev = (CBS_FT_level_des *)(level_table[l]);
/* it stores the actual time and set the IDLE flag in order to handle
the capacity queue discharging!!! */
lev->idle = 1;
kern_gettime(&lev->start_idle);
/* the CBS_FT don't schedule anything...
it's an EDF level or similar that do it! */
return NIL;
}
/* The on-line guarantee is enabled only if the appropriate flag is set... */
static int CBS_FT_public_guarantee(LEVEL l, bandwidth_t *freebandwidth)
{
CBS_FT_level_des *lev = (CBS_FT_level_des *)(level_table[l]);
if (lev->flags & CBS_FT_FAILED_GUARANTEE) {
*freebandwidth = 0;
kern_printf("guarantee :garanzia fallita!!!!!!\n");
return 0;
}
else if (*freebandwidth >= lev->U) {
*freebandwidth -= lev->U;
return 1;
}
else {
kern_printf("guarantee :garanzia fallita per mancanza di banda!!!!!!\n");
kern_printf("freeband: %d request band: %d", *freebandwidth, lev->U);
return 0;
}
}
static int CBS_FT_public_create(LEVEL l, PID p, TASK_MODEL *m)
{
CBS_FT_level_des *lev = (CBS_FT_level_des *)(level_table[l]);
FT_TASK_MODEL *s;
if (m->pclass != FT_PCLASS) return -1;
if (m->level != 0 && m->level != l) return -1;
s = (FT_TASK_MODEL *) m;
//kern_printf("accept :FAULT TOLERANT TASK found!!!!!!\n"); */
if (!(s->type == PRIMARY && s->execP > 0 && s->budget < (int)s->period
&& s->backup != NIL)) return -1;
if (!(s->type == BACKUP && s->wcetB > 0))
return -1;
/* now we know that m is a valid model */
/* Enable budget check */
proc_table[p].control |= CONTROL_CAP;
proc_table[p].avail_time = 0;
NULL_TIMESPEC(&lev->cbs_ft_dline[p]);
if (s->type == PRIMARY) {
proc_table[p].wcet = (int)s->execP;
lev->period[p] = s->period;
lev->maxcap[p] = s->budget;
lev->backup[p] = s->backup;
lev->CP[p] = 0;
lev->P_or_B[p] = PRIMARY;
/* update the bandwidth... */
if (lev->flags & CBS_FT_ENABLE_GUARANTEE) {
bandwidth_t b;
b = (MAX_BANDWIDTH / lev->period[p]) * (TIME)lev->maxcap[p];
/* really update lev->U, checking an overflow... */
if (MAX_BANDWIDTH - lev->U > b)
lev->U += b;
else
/* The task can NOT be guaranteed (U>MAX_BANDWIDTH)...
(see EDF.c) */
lev->flags |= CBS_FT_FAILED_GUARANTEE;
}
}
else {
proc_table[p].wcet = (int)s->wcetB;
lev->P_or_B[p] = BACKUP;
/* Backup tasks are unkillable tasks! */
proc_table[p].control |= NO_KILL;
}
return 0; /* OK, also if the task cannot be guaranteed... */
}
static void CBS_FT_public_detach(LEVEL l, PID p)
{
/* the CBS_FT level doesn't introduce any dynamic allocated new field.
we have only to reset the NO_GUARANTEE FIELD and decrement the allocated
bandwidth */
CBS_FT_level_des *lev = (CBS_FT_level_des *)(level_table[l]);
if (lev->flags & CBS_FT_FAILED_GUARANTEE)
lev->flags &= ~CBS_FT_FAILED_GUARANTEE;
else
lev->U -= (MAX_BANDWIDTH / lev->period[p]) * (TIME)lev->maxcap[p];
}
static void CBS_FT_public_dispatch(LEVEL l, PID p, int nostop)
{
CBS_FT_level_des *lev = (CBS_FT_level_des *)(level_table[l]);
level_table[ lev->scheduling_level ]->
private_dispatch(lev->scheduling_level,p,nostop);
}
static void CBS_FT_public_epilogue(LEVEL l, PID p)
{
CBS_FT_level_des *lev = (CBS_FT_level_des *)(level_table[l]);
/* check if the budget is finished... */
if (proc_table[p].avail_time <= 0) {
/* A backup task cannot ever exhaust its budget! */
if (lev->P_or_B[p] == BACKUP) {
kern_printf("\nBACKUP wcet violation!\n");
kern_raise(XWCET_VIOLATION,p);
/* we kill the current activation */
level_table[ lev->scheduling_level ]->
private_extract(lev->scheduling_level, p);
return;
}
/* we try to recharge the budget */
CBS_FT_avail_time_check(lev, p);
/* The budget must be greater than 0! */
if (proc_table[p].avail_time <= 0) {
kern_printf("\nBackup task starting with exhausted budget\n");
kern_raise(XINVALID_TASK, p);
lev->CP[p] = 0;
/* we kill the current activation */
level_table[ lev->scheduling_level ]->
private_extract(lev->scheduling_level, p);
return;
}
}
/* the task returns into the ready queue by
calling the guest_epilogue... */
level_table[ lev->scheduling_level ]->
private_epilogue(lev->scheduling_level,p);
}
static void CBS_FT_public_activate(LEVEL l, PID p)
{
CBS_FT_level_des *lev = (CBS_FT_level_des *)(level_table[l]);
struct timespec t;
kern_gettime(&t);
if (lev->P_or_B[p] == BACKUP) {
kern_printf("\nTrying to activate a BACKUP task!\n");
kern_raise(XINVALID_TASK, p);
}
else {
/* If idle=1, then we have to discharge the capacities stored in
the capacity queue up to the length of the idle interval */
if (lev->idle == 1) {
TIME interval;
struct timespec delta;
lev->idle = 0;
SUBTIMESPEC(&t, &lev->start_idle, &delta);
/* length of the idle interval expressed in usec! */
interval = TIMESPEC2NANOSEC(&delta) / 1000;
/* it discharge the available capacities from the capacity queue */
while (interval > 0 && lev->queue != NULL) {
struct timespec dead;
int cap;
c_readfirst(&dead, &cap, lev->queue);
if (cap > interval) {
c_writefirst(dead, cap - interval, lev->queue);
interval = 0;
}
else {
interval -= cap;
c_extractfirst(&lev->queue);
}
}
}
CBS_FT_activation(lev, p, &t);
/* Set the reactivation timer */
TIMESPEC_ASSIGN(&lev->reactivation_time[p], &lev->cbs_ft_dline[p]);
lev->reactivation_timer[p] = kern_event_post(&lev->reactivation_time[p],
CBS_FT_timer_reactivate,
(void *)p);
// kern_printf("act : %d %d |",lev->cbs_ft_dline[p].tv_nsec/1000,p);
}
}
static int CBS_FT_public_message(LEVEL l, PID p, void *m)
{
CBS_FT_level_des *lev = (CBS_FT_level_des *)(level_table[l]);
level_table[ lev->scheduling_level ]->
private_extract(lev->scheduling_level,p);
proc_table[p].status = CBS_FT_IDLE;
if (lev->P_or_B[p] == PRIMARY) {
if (lev->CP[p]) {
JOB_TASK_MODEL job;
/* We have to start the backup task */
TIMESPEC_ASSIGN(&lev->cbs_ft_dline[ lev->backup[p] ],
&lev->cbs_ft_dline[p]);
proc_table[ lev->backup[p] ].avail_time = proc_table[p].avail_time;
lev->CP[p] = 0;
/* and, finally, we insert the backup task in the master level */
job_task_default_model(job, lev->cbs_ft_dline[p]);
job_task_def_yesexc(job);
level_table[ lev->scheduling_level ]->
private_insert(lev->scheduling_level, lev->backup[p],
(TASK_MODEL *)&job);
}
else {
/* A spare capacity is inserted in the capacity queue!! */
proc_table[p].avail_time += proc_table[ lev->backup[p] ].wcet;
if (proc_table[p].avail_time > 0) {
c_insert(lev->cbs_ft_dline[p], proc_table[p].avail_time,
&lev->queue, p);
proc_table[p].avail_time = 0;
}
}
}
else {
/* this branch is for backup tasks:
A spare capacity is inserted in the capacity queue!! */
if (proc_table[p].avail_time > 0) {
c_insert(lev->cbs_ft_dline[p], proc_table[p].avail_time,
&lev->queue, p);
proc_table[p].avail_time = 0;
}
}
jet_update_endcycle(); /* Update the Jet data... */
return 0;
}
static void CBS_FT_public_end(LEVEL l, PID p)
{
CBS_FT_level_des *lev = (CBS_FT_level_des *)(level_table[l]);
/* A backup task cannot be killed, this behaviour can be modified
in a new release */
if (lev->P_or_B[p] == BACKUP) {
kern_printf("\nKilling a BACKUP task!\n");
kern_raise(XINVALID_TASK, p);
return;
}
/* check if the capacity becomes negative... */
/* there is a while because if the wcet is << than the system tick
we need to postpone the deadline many times */
while (proc_table[p].avail_time < 0) {
/* the CBS_FT rule for recharging the capacity */
proc_table[p].avail_time += lev->maxcap[p];
ADDUSEC2TIMESPEC(lev->period[p], &lev->cbs_ft_dline[p]);
}
level_table[ lev->scheduling_level ]->
private_extract(lev->scheduling_level,p);
/* we delete the reactivation timer */
kern_event_delete(lev->reactivation_timer[p]);
lev->reactivation_timer[p] = -1;
/* Finally, we post the zombie event. when the end period is reached,
the task descriptor and banwidth are freed */
proc_table[p].status = CBS_FT_ZOMBIE;
lev->reactivation_timer[p] = kern_event_post(&lev->cbs_ft_dline[p],
CBS_FT_timer_zombie,
(void *)p);
}
/* Registration functions */
/*+ Registration function:
int flags the init flags ... see CBS.h +*/
LEVEL CBS_FT_register_level(int flags, LEVEL master)
{
LEVEL l; /* the level that we register */
CBS_FT_level_des *lev; /* for readableness only */
PID i; /* a counter */
printk("CBS_FT_register_level\n");
/* request an entry in the level_table */
l = level_alloc_descriptor(sizeof(CBS_FT_level_des));
lev = (CBS_FT_level_des *)level_table[l];
printk(" lev=%d\n",(int)lev);
/* fill the standard descriptor */
lev->l.public_scheduler = CBS_FT_public_scheduler;
if (flags & CBS_FT_ENABLE_GUARANTEE)
lev->l.public_guarantee = CBS_FT_public_guarantee;
else
lev->l.public_guarantee = NULL;
lev->l.public_create = CBS_FT_public_create;
lev->l.public_detach = CBS_FT_public_detach;
lev->l.public_end = CBS_FT_public_end;
lev->l.public_dispatch = CBS_FT_public_dispatch;
lev->l.public_epilogue = CBS_FT_public_epilogue;
lev->l.public_activate = CBS_FT_public_activate;
lev->l.public_message = CBS_FT_public_message;
/* fill the CBS_FT descriptor part */
for (i=0; i<MAX_PROC; i++) {
NULL_TIMESPEC(&lev->cbs_ft_dline[i]);
lev->period[i] = 0;
NULL_TIMESPEC(&lev->reactivation_time[i]);
lev->reactivation_timer[i] = -1;
lev->maxcap[i] = 0;
lev->backup[i] = NIL;
lev->CP[i] = 0;
lev->P_or_B[i] = PRIMARY;
}
lev->U = 0;
lev->idle = 0;
lev->queue = NULL;
lev->scheduling_level = master;
lev->flags = flags & 0x07;
return l;
}
bandwidth_t CBS_FT_usedbandwidth(LEVEL l)
{
CBS_FT_level_des *lev = (CBS_FT_level_des *)(level_table[l]);
return lev->U;
}
void CBS_FT_Primary_Abort()
{
PID p;
CBS_FT_level_des *lev;
kern_cli();
p = exec_shadow;
lev = (CBS_FT_level_des *)level_table[proc_table[p].task_level];
lev->CP[p] = 1;
kern_sti();
}
char CBS_FT_Checkpoint()
{
char f;
PID p;
CBS_FT_level_des *lev;
kern_cli();
p = exec_shadow;
lev = (CBS_FT_level_des *)level_table[proc_table[p].task_level];
f = lev->CP[p];
kern_sti();
return f;
}