Rev 1176 |
Go to most recent revision |
Blame |
Compare with Previous |
Last modification |
View Log
| RSS feed
/*
* 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: cbsstar.c,v 1.6 2003-08-01 13:20:38 trimarchi Exp $
File: $File$
Revision: $Revision: 1.6 $
Last update: $Date: 2003-08-01 13:20:38 $
------------
Read CBSSTAR.h for general details.
Basically, a budget can be in 2 states:
- Active -> the budget queue is not empty
- Idle -> the budget queue is empty
The fact that a task into a budget is inserted into the master module depends
on the value of the remaining time the tasks can spend in the period.
The module does handle only one oslib event, used to enforce the
temporal isolation between buffers. Note that all is implemented
without using the CONTROL_CAP field.
Basically, for each budget there can be at most one task inserted
into the master level. Its deadline is modified according to the
usage of its capacity, that is, when a budget is exausted its
deadline is postponed.
*/
/*
* Copyright (C) 2002 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 "cbsstar.h"
#include <ll/string.h>
#define ACTIVE 1
#define NOACTIVE 0
#define INIT 2
#define CBSSTAR_IDLE APER_STATUS_BASE
/*
* DEBUG stuffs begin
*/
//#define CBSSTAR_DEBUG
int event_monitor;
#ifdef CBSSTAR_DEBUG
static __inline__ void fake_printf(char *fmt, ...) {}
//#define cbsstar_printf kern_printf
//#define cbsstar_printf2 kern_printf
//#define cbsstar_printf3 kern_printf
#define cbsstar_printf fake_printf
#define cbsstar_printf2 fake_printf
#define cbsstar_printf3 fake_printf
#if 0
void cbsstar_printq(QQUEUE *q)
{
PID p;
kern_printf("[");
p = q->first;
kern_printf("->%d",p);
while (p != NIL) {
p = proc_table[p].next;
kern_printf("->%d",p);
}
kern_printf("]");
}
#else
static __inline__ void cbsstar_printq(QQUEUE *q) {}
#endif
#if 0
static __inline__ void cbsstar_printblob(int x) { if (x) cputc('±'); else cputc('Û'); }
#else
static __inline__ void cbsstar_printblob(int x) {}
#endif
#endif
/*
* DEBUG stuffs end
*/
/*+ Status used in the level +*/
#define CBSSTAR_WAIT APER_STATUS_BASE /*+ waiting the service +*/
/* this structure contains the status for a single budget */
struct budget_struct {
TIME Q; /* budget */
TIME T; /* period */
struct timespec dline; /* deadline */
int dline_timer; /* oslib event for budget reactivation*/
int avail; /* current budget */
PID current; /* the task currently put in execution */
int flags;
IQUEUE tasks; /* a FIFO queue for the tasks handled
using the budget */
};
typedef struct {
level_des l; /* the standard level descriptor */
struct budget_struct *b; /* the budgets! */
int n; /* the maximum index for the budgets */
int freebudgets; /* number of free budgets; starts from n */
int tb[MAX_PROC]; /* link task->budget (used in guest_end) */
bandwidth_t U; /*+ the used bandwidth by the server +*/
int cap_lev;
PID on_shadow;
LEVEL scheduling_level;
} CBSSTAR_level_des;
static void CBSSTAR_deadline_timer_hardreservation(void *a)
{
struct budget_struct *b = a;
struct timespec t;
//kern_printf("*********** %d", b->dline_timer);
b->dline_timer=NIL;
/* we modify the deadline according to rule 4 ... */
/* there is a while because if the wcet is << than the system tick
we need to postpone the deadline many times */
if (b->avail<=0) {
b->avail += b->Q;
if (b->avail>b->Q) b->avail=b->Q;
//kern_printf("budget recharge %d", b);
}
if (b->avail>0) b->flags=ACTIVE;
/* avail may be <0 because a task executed via a shadow fo many time
b->current == NIL only if the prec task was finished and there
was not any other task to be put in the ready queue
... we are now activating the next task */
if (b->current == NIL && b->flags) {
if (iq_query_first(&(b->tasks)) != NIL) {
//struct timespec t;
CBSSTAR_level_des *lev;
PID p;
JOB_TASK_MODEL job;
//kern_gettime(&t);
//TIMESPEC_ASSIGN(&b->dline, &schedule_time);
//ADDUSEC2TIMESPEC(b->T, &b->dline);
kern_gettime(&t);
TIMESPEC_ASSIGN(&b->dline, &t);
ADDUSEC2TIMESPEC(b->T, &b->dline);
p = iq_getfirst(&(b->tasks));
b->current=p;
lev = (CBSSTAR_level_des *)(level_table[proc_table[p].task_level]);
//kern_printf("reinsert task p = %d lev = %d ",p,proc_table[p].task_level);
/* and, finally, we reinsert the task in the master level */
job_task_default_model(job, b->dline);
job_task_def_noexc(job);
//kern_printf("(CR:iact p%d %ld.%ld av=%d)",p,b->dline.tv_sec,b->dline.tv_nsec/1000, b->avail);
//kern_printf("**");
level_table[ lev->scheduling_level ]->
private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job);
event_need_reschedule();
}
} else
if (b->current !=NIL && b->avail>0) {
kern_printf("(cap&nil ");
}
if (b->flags==NOACTIVE && b->dline_timer!=NIL){
kern_gettime(&t);
TIMESPEC_ASSIGN(&b->dline, &t);
ADDUSEC2TIMESPEC(b->T, &b->dline);
b->dline_timer=kern_event_post(&b->dline, CBSSTAR_deadline_timer_hardreservation, b);
event_monitor=b->dline_timer;
//kern_printf("(dline hard %ld.%ld ev %d)",b->dline.tv_sec,b->dline.tv_nsec/1000, b->dline_timer);
}
}
static void CBSSTAR_activation(CBSSTAR_level_des *lev,
PID p,
struct timespec *acttime)
{
JOB_TASK_MODEL job;
struct budget_struct *b = &lev->b[lev->tb[p]];
/* we have to check if the deadline and the wcet are correct before
activating a new task or an old task... */
/* check 1: if the deadline is before than the actual scheduling time */
/* check 2: if ( avail_time >= (cbs_dline - acttime)* (wcet/period) )
(rule 7 in the CBS article!) */
TIME t;
struct timespec t2,t3;
t = (b->T * b->avail) / b->Q;
t3.tv_sec = t / 1000000;
t3.tv_nsec = (t % 1000000) * 1000;
SUBTIMESPEC(&b->dline, acttime, &t2);
if (/* 1 */ TIMESPEC_A_LT_B(&b->dline, acttime) ||
/* 2 */ TIMESPEC_A_GT_B(&t3, &t2) ) {
TIMESPEC_ASSIGN(&b->dline, acttime);
ADDUSEC2TIMESPEC(b->T, &b->dline);
}
/* and the capacity */
if (b->flags==INIT) {
b->avail = b->Q;
b->flags=ACTIVE;
}
#ifdef CBSSTAR_DEBUG
cbsstar_printf3("±%d±",lev->tb[p]);
cbsstar_printblob(lev->tb[p]);
#endif
//}
//#endif
/* record the current task inserted in the master module */
b->current = p;
//#ifdef CBSSTAR_DEBUG
//kern_printf("(CA:iact p%d %ld.%ld av=%d at=%ld.%ld)",p,b->dline.tv_sec,b->dline.tv_nsec/1000, b->avail, acttime->tv_sec, acttime->tv_nsec/1000);
//#endif
/* and, finally, we reinsert the task in the master level */
job_task_default_model(job, b->dline);
job_task_def_noexc(job);
level_table[ lev->scheduling_level ]->
private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job);
//b->dline_timer=kern_event_post(&b->dline, CBSSTAR_deadline_timer_hardreservation, b);
}
static void CBSSTAR_account_capacity(CBSSTAR_level_des *lev, PID p)
{
struct timespec ty;
TIME tx;
struct budget_struct *b = &lev->b[lev->tb[p]];
TIME t;
struct timespec t2,t3, acttime;
if (lev->cap_lev!=NIL && b->current==p) {
kern_event_delete(lev->cap_lev);
lev->cap_lev=NIL;
}
kern_gettime(&acttime);
t = (b->T * b->avail) / b->Q;
t3.tv_sec = t / 1000000;
t3.tv_nsec = (t % 1000000) * 1000;
SUBTIMESPEC(&b->dline, &acttime, &t2);
SUBTIMESPEC(&schedule_time, &cap_lasttime, &ty);
tx = TIMESPEC2USEC(&ty);
lev->b[lev->tb[p]].avail -= tx;
#ifdef CBSSTAR_DEBUG
cbsstar_printf2("(C:cap p%d av=%d)", p, lev->b[lev->tb[p]].avail);
#endif
if (lev->b[lev->tb[p]].avail<=0 || TIMESPEC_A_GT_B(&t3, &t2)) lev->b[lev->tb[p]].flags=NOACTIVE;
if ( TIMESPEC_A_LT_B(&b->dline, &schedule_time) ) {
/* we modify the deadline ... */
TIMESPEC_ASSIGN(&b->dline, &schedule_time);
ADDUSEC2TIMESPEC(b->T, &b->dline);
}
//if (b->flags==NOACTIVE && b->dline_timer!=NIL)
// kern_printf("flags %d, dline_timer %d", b->flags, b->dline_timer);
if (b->flags==NOACTIVE && b->dline_timer==NIL) {
b->dline_timer=kern_event_post(&b->dline, CBSSTAR_deadline_timer_hardreservation, b);
event_monitor=b->dline_timer;
//kern_printf("(dline %ld.%ld ev %d)",b->dline.tv_sec,b->dline.tv_nsec/1000, b->dline_timer);
}
}
/* The on-line guarantee is enabled only if the appropriate flag is set... */
static int CBSSTAR_public_guarantee(LEVEL l, bandwidth_t *freebandwidth)
{
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
#ifdef CBSSTAR_DEBUG
cbsstar_printf("(C:gua)");
#endif
if (*freebandwidth >= lev->U) {
*freebandwidth -= lev->U;
return 1;
}
else
return 0;
}
static void capacity_handler(void *l)
{
//kern_printf("!");
CBSSTAR_level_des *lev =l;
lev->cap_lev=NIL;
event_need_reschedule();
}
static int CBSSTAR_private_eligible(LEVEL l, PID p)
{
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
struct budget_struct *b = &lev->b[lev->tb[p]];
JOB_TASK_MODEL job;
#ifdef CBSSTAR_DEBUG
//kern_printf("(C:eli %d",p);
#endif
/* we have to check if the deadline and the wcet are correct...
if the CBSSTAR level schedules in background with respect to others
levels, there can be the case in witch a task is scheduled by
schedule_time > CBSSTAR_deadline; in this case (not covered in the
article because if there is only the standard scheduling policy
this never apply) we reassign the deadline */
if (b->current==p) {
if ( TIMESPEC_A_LT_B(&b->dline, &schedule_time)) {
if (lev->cap_lev!=NIL) {
kern_event_delete(lev->cap_lev);
lev->cap_lev=NIL;
}
/* we kill the current activation */
level_table[ lev->scheduling_level ]->
private_extract(lev->scheduling_level, p);
/* we modify the deadline ... */
TIMESPEC_ASSIGN(&b->dline, &schedule_time);
ADDUSEC2TIMESPEC(b->T, &b->dline);
/* and the capacity */
b->avail = b->Q;
b->flags=ACTIVE;
if (b->dline_timer!=NIL) {
kern_event_delete(b->dline_timer);
b->dline_timer=NIL;
}
//#ifdef CBSSTAR_DEBUG
//kern_printf(" %ld.%ld av=%d)",b->dline.tv_sec,b->dline.tv_nsec/1000, b->Q);
//cbsstar_printf3("±%d±",lev->tb[p]);
//cbsstar_printblob(lev->tb[p]);
//#endif
/* and, finally, we reinsert the task in the master level */
job_task_default_model(job, b->dline);
job_task_def_noexc(job);
//kern_printf("(CE:iact p%d %ld.%ld av=%d)",p,b->dline.tv_sec,b->dline.tv_nsec/1000, b->avail);
level_table[ lev->scheduling_level ]->
private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job);
//kern_printf("task %d, avail %d", p, b->avail);
return -1;
}
}
#ifdef CBSSTAR_DEBUG
cbsstar_printf(")");
#endif
return 0;
}
static void CBSSTAR_private_insert(LEVEL l, PID p, TASK_MODEL *m)
{
/* A task has been activated for some reason. Basically, the task is
inserted in the queue if the queue is empty, otherwise the task is
inserted into the master module, and an oslib event is posted. */
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
BUDGET_TASK_MODEL *budget;
if (m->pclass != BUDGET_PCLASS ||
(m->level != 0 && m->level != l)) {
kern_raise(XINVALID_TASK, p);
return;
}
budget = (BUDGET_TASK_MODEL *)m;
#ifdef CBSSTAR_DEBUG
cbsstar_printf("(C:gcr %d b%d", p, budget->b);
#endif
lev->tb[p] = budget->b;
if (lev->b[budget->b].current == NIL && lev->b[budget->b].flags ) {
/* This is the first task in the budget,
the task have to be inserted into the master module */
struct timespec t;
kern_gettime(&t);
CBSSTAR_activation(lev,p,&t);
} else {
/* The budget is not empty, another task is already into the
master module, so the task is inserted at the end of the budget
queue */
iq_insertlast(p,&lev->b[budget->b].tasks);
//#ifdef CBSSTAR_DEBUG
//kern_printf(" ilast flag %d task %d",lev->b[budget->b].flags,lev->b[budget->b].current);
// cbsstar_printq(&lev->b[budget->b].tasks);
//#endif
}
#ifdef CBSSTAR_DEBUG
cbsstar_printf(")");
#endif
}
static void CBSSTAR_private_extract(LEVEL l, PID p)
{
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
//#ifdef CBSSTAR_DEBUG
//kern_printf("(C:gend p%d c%d av=%d)", p, lev->b[lev->tb[p]].current, lev->b[lev->tb[p]].avail);
//cbsstar_printq(&lev->b[lev->tb[p]].tasks);
//#endif
/* a task is removed from execution for some reasons. It must be
that it is the first in its budget queue (only the first task in
a budget queue is put into execution!) */
/* remove the task from execution (or from the ready queue) */
if (lev->b[lev->tb[p]].current == p) {
CBSSTAR_account_capacity(lev,p);
/* remove the task from the master module */
level_table[ lev->scheduling_level ]->
private_extract(lev->scheduling_level, p);
#ifdef CBSSTAR_DEBUG
cbsstar_printq(&lev->b[lev->tb[p]].tasks);
#endif
/* check if the buffer has someone else to schedule */
if (iq_query_first(&lev->b[lev->tb[p]].tasks) == NIL) {
/* the buffer has no tasks! */
lev->b[lev->tb[p]].current = NIL;
}
else if (lev->b[lev->tb[p]].flags) {
/* if so, insert the new task into the master module */
PID n;
struct timespec t;
kern_gettime(&t);
n = iq_getfirst(&lev->b[lev->tb[p]].tasks);
//#ifdef CBSSTAR_DEBUG
//kern_printf("{p%d n%d}",p,n);
//#endif
CBSSTAR_activation(lev,n,&t); // it modifies b[lev->tb[p]].current
}
else
lev->b[lev->tb[p]].current=NIL;
}
else {
iq_extract(p, &lev->b[lev->tb[p]].tasks);
}
}
static void CBSSTAR_private_dispatch(LEVEL l, PID p, int nostop)
{
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
struct timespec ty;
//#ifdef CBSSTAR_DEBUG
//kern_printf("(C:gdisp p%d c%d av=%d)", p, lev->b[lev->tb[p]].current, lev->b[lev->tb[p]].avail);
// cbsstar_printq(&lev->b[lev->tb[p]].tasks);
//#endif
/* the current task (that is the only one inserted in the master module
for the corresponding budget) is dispatched. Note that the current
task is not inserted in any FIFO queue, so the task does not have to
be extracted! */
/* ... then, we dispatch it to the master level */
level_table[ lev->scheduling_level ]->
private_dispatch(lev->scheduling_level,p,nostop);
/* ...and finally, we have to post a capacity event */
if (!nostop) {
TIMESPEC_ASSIGN(&ty, &schedule_time);
ADDUSEC2TIMESPEC(lev->b[lev->tb[p]].avail,&ty);
lev->cap_lev = kern_event_post(&ty,capacity_handler, lev);
}
}
static void CBSSTAR_private_epilogue(LEVEL l, PID p)
{
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
struct budget_struct *b = &lev->b[lev->tb[p]];
//#ifdef CBSSTAR_DEBUG
//kern_printf("(C:gepi %d %d",p, b->current);
//#endif
if (p==b->current) {
CBSSTAR_account_capacity(lev,p);
// L'evento di capacità va cancellato perchè sarà ripristinato nella successiva dispatch
/* we have to check if the capacity is still available */
if (b->flags) {
/* there is capacity available, maybe it is simply a preemption;
the task have to return to the ready queue */
level_table[ lev->scheduling_level ]->
private_epilogue(lev->scheduling_level,p);
#ifdef CBSSTAR_DEBUG
//kern_printf("(ep *av=%d", b->avail);
#endif
} else {
/* we kill the current activation */
level_table[ lev->scheduling_level ]->
private_extract(lev->scheduling_level, p);
//kern_printf("extract");
iq_insertfirst(p, &b->tasks);
proc_table[p].status = CBSSTAR_IDLE;
b->current = NIL;
//kern_printf("budget finish %d", b);
}
#ifdef CBSSTAR_DEBUG
cbsstar_printf(")");
#endif
}
}
/* Registration functions }*/
/*+ Registration function:
int flags the init flags ... see CBSSTAR.h +*/
LEVEL CBSSTAR_register_level(int n, LEVEL master)
{
LEVEL l; /* the level that we register */
CBSSTAR_level_des *lev; /* for readableness only */
PID i; /* a counter */
#ifdef CBSSTAR_DEBUG
cbsstar_printf("CBSSTAR_register_level\n");
#endif
/* request an entry in the level_table */
l = level_alloc_descriptor(sizeof(CBSSTAR_level_des));
lev = (CBSSTAR_level_des *)level_table[l];
printk(" lev=%d\n",(int)lev);
/* fill the standard descriptor */
lev->l.private_insert = CBSSTAR_private_insert;
lev->l.private_extract = CBSSTAR_private_extract;
lev->l.private_eligible = CBSSTAR_private_eligible;
lev->l.private_dispatch = CBSSTAR_private_dispatch;
lev->l.private_epilogue = CBSSTAR_private_epilogue;
lev->l.public_guarantee = CBSSTAR_public_guarantee;
/* fill the CBSSTAR descriptor part */
lev->b = (struct budget_struct *)kern_alloc(sizeof(struct budget_struct)*n);
for (i=0; i<n; i++) {
lev->b[i].Q = 0;
lev->b[i].T = 0;
NULL_TIMESPEC(&lev->b[i].dline);
lev->b[i].dline_timer = NIL;
lev->b[i].avail = 0;
lev->b[i].current = -1;
lev->b[i].flags=INIT;
iq_init(&lev->b[i].tasks, &freedesc, 0);
}
lev->n = n;
lev->freebudgets = 0;
for (i=0; i<MAX_PROC; i++)
lev->tb[i] = NIL;
lev->U = 0;
lev->cap_lev=NIL;
lev->scheduling_level = master;
lev->on_shadow=NIL;
return l;
}
int CBSSTAR_setbudget(LEVEL l, TIME Q, TIME T)
{
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
#ifdef CBSSTAR_DEBUG
cbsstar_printf("(C:sbud)");
#endif
if (lev->freebudgets != lev->n) {
bandwidth_t b;
b = (MAX_BANDWIDTH / T) * Q;
/* really update lev->U, checking an overflow... */
if (Q< T && MAX_BANDWIDTH - lev->U > b) {
int r = lev->freebudgets; // the return value
lev->U += b;
lev->freebudgets++;
lev->b[r].Q = Q;
lev->b[r].T = T;
return r;
}
else
return -2;
}
else
return -1;
}