Subversion Repositories shark

Compare Revisions

Ignore whitespace Rev 241 → Rev 253

/shark/trunk/ports/first/modules/grubstar.c
37,29 → 37,10
*
*/
 
#include "cbsstar.h"
#include "grubstar.h"
 
/*
* DEBUG stuffs begin
*/
//#define CBSSTAR_DEBUG
#ifdef CBSSTAR_DEBUG
#define GRUBSTAR_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
 
#endif
/*
* DEBUG stuffs end
*/
 
/* this structure contains the status for a single budget */
struct budget_struct {
TIME Q; /* budget */
70,7 → 51,7
int vtimer;
int avail; /* current budget */
LEVEL l; /* Current CBSSTAR level */
LEVEL l; /* Current GRUBSTAR level */
int loc_sched_id; /* Local scheduler id */
LEVEL loc_sched_level; /* Local scheduler level */
82,9 → 63,9
 
};
 
#define CBSSTAR_NOACTIVE 0
#define CBSSTAR_ACTIVE 1
#define CBSSTAR_RECLAIMING 2
#define GRUBSTAR_NOACTIVE 0
#define GRUBSTAR_ACTIVE 1
#define GRUBSTAR_RECLAIMING 2
 
typedef struct {
level_des l; /* the standard level descriptor */
102,42 → 83,47
 
LEVEL scheduling_level;
 
} CBSSTAR_level_des;
} GRUBSTAR_level_des;
 
 
static void CBSSTAR_deadline_timer_hardreservation(void *a)
static void GRUBSTAR_deadline_timer_hardreservation(void *a)
{
struct budget_struct *b = a;
PID p;
#ifdef CBSSTAR_DEBUG
cbsstar_printf("(CS:HrdRes:");
GRUBSTAR_level_des *lev;
lev = (GRUBSTAR_level_des *)(level_table[b->l]);
 
#ifdef GRUBSTAR_DEBUG
kern_printf("(GS:HrdRes:");
#endif
 
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 */
b->avail += b->Q;
if (b->avail > b->Q) b->avail = b->Q;
if (b->avail > 0) b->flags = CBSSTAR_ACTIVE;
if (b->flags==GRUBSTAR_RECLAIMING && b->avail>0) {
bandwidth_t bw;
bw = (MAX_BANDWIDTH / b->T) * b->Q;
 
/* 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 */
lev->Uf += bw;
 
#ifdef GRUBSTAR_DEBUG
kern_printf("BW=%ld, U=%u, Uf=%u",(long)bw, lev->U, lev->Uf);
#endif
}
 
if (b->avail > 0) b->flags = GRUBSTAR_ACTIVE;
 
if (b->current == NIL && b->flags) {
if (iq_query_first(&(b->tasks)) != NIL) {
CBSSTAR_level_des *lev;
JOB_TASK_MODEL job;
p = iq_getfirst(&b->tasks);
#ifdef CBSSTAR_DEBUG
cbsstar_printf("%d",p);
#ifdef GRUBSTAR_DEBUG
kern_printf("%d",p);
#endif
 
kern_gettime(&b->dline);
145,7 → 131,6
 
b->current = p;
 
lev = (CBSSTAR_level_des *)(level_table[b->l]);
job_task_default_model(job, b->dline);
job_task_def_noexc(job);
157,26 → 142,26
}
}
if (b->flags == CBSSTAR_NOACTIVE) {
if (b->flags == GRUBSTAR_NOACTIVE) {
kern_gettime(&b->dline);
ADDUSEC2TIMESPEC(b->T, &b->dline);
b->dline_timer=kern_event_post(&b->dline, CBSSTAR_deadline_timer_hardreservation, b);
b->dline_timer=kern_event_post(&b->dline, GRUBSTAR_deadline_timer_hardreservation, b);
}
 
#ifdef CBSSTAR_DEBUG
cbsstar_printf(")");
#ifdef GRUBSTAR_DEBUG
kern_printf(")");
#endif
 
}
 
void CBSSTAR_ANC(void *arg)
void GRUBSTAR_ANC(void *arg)
{
struct budget_struct *b = arg;
CBSSTAR_level_des *lev=(CBSSTAR_level_des *)level_table[b->l];
GRUBSTAR_level_des *lev=(GRUBSTAR_level_des *)level_table[b->l];
#ifdef CBSSTAR_DEBUG
cbsstar_printf("(CS:Rec:");
#ifdef GRUBSTAR_DEBUG
kern_printf("(GS:Rec:");
#endif
 
b->vtimer = NIL;
183,56 → 168,46
if (b->current != NIL && iq_query_first(&(b->tasks)) != NIL) {
bandwidth_t bw;
 
b->flags=CBSSTAR_RECLAIMING;
b->flags=GRUBSTAR_RECLAIMING;
 
bw = (MAX_BANDWIDTH / b->T) * b->Q;
 
lev->Uf -= bw;
#ifdef CBSSTAR_DEBUG
cbsstar_printf("%ld",(long)bw);
#ifdef GRUBSTAR_DEBUG
kern_printf("bw=%ld, U=%u, Uf=%u",(long)bw, lev->U, lev->Uf);
#endif
 
}
 
#ifdef CBSSTAR_DEBUG
cbsstar_printf(")");
#ifdef GRUBSTAR_DEBUG
kern_printf(")");
#endif
 
 
}
 
static void CBSSTAR_activation(CBSSTAR_level_des *lev,
static void GRUBSTAR_activation(GRUBSTAR_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... */
TIME t;
struct timespec t2,t3;
 
/* we have to check if the deadline and the wcet are correct before
* activating a new task or an old task... */
t = (b->T * b->avail) / b->Q;
t3.tv_sec = t / 1000000;
t3.tv_nsec = (t % 1000000) * 1000;
 
/* 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) ||
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);
b->avail=b->Q;
if (b->flags==CBSSTAR_RECLAIMING) {
if (b->flags==GRUBSTAR_RECLAIMING) {
bandwidth_t bw;
bw = (MAX_BANDWIDTH / b->T) * b->Q;
239,21 → 214,22
 
lev->Uf += bw;
#ifdef CBSSTAR_DEBUG
cbsstar_printf("BW=%ld",(long)bw);
#ifdef grubSTAR_DEBUG
kern_printf("BW=%ld, U=%u, Uf=%u",(long)bw, lev->U, lev->Uf);
#endif
}
 
 
b->flags=CBSSTAR_ACTIVE;
b->flags=GRUBSTAR_ACTIVE;
 
}
else {
SUBTIMESPEC(&b->dline, &t3, &t2);
b->vtimer = kern_event_post(&t2, CBSSTAR_ANC, (void *)&b);
}
 
SUBTIMESPEC(&b->dline, &t3, &t2);
if (b->vtimer!=NIL) kern_event_delete(b->vtimer);
b->vtimer=NIL;
b->vtimer = kern_event_post(&t2, GRUBSTAR_ANC, b);
 
 
/* record the current task inserted in the master module */
b->current = p;
 
264,7 → 240,7
 
}
 
static void CBSSTAR_account_capacity(CBSSTAR_level_des *lev, PID p)
static void GRUBSTAR_account_capacity(GRUBSTAR_level_des *lev, PID p)
{
struct timespec ty;
TIME tx;
277,13 → 253,13
 
SUBTIMESPEC(&schedule_time, &cap_lasttime, &ty);
tx = TIMESPEC2USEC(&ty);
b->avail -= tx;
b->avail -= (int)((long long)tx * (long long)lev->Uf / (int)lev->U);
 
#ifdef CBSSTAR_DEBUG
kern_printf("(CS:Cap p%d av=%d)", p, b->avail);
#ifdef GRUBSTAR_DEBUG
kern_printf("(GS:Cap p%d av=%d Uf=%u U=%u)", p, b->avail,lev->Uf, lev->U);
#endif
 
if (b->avail <= 0) b->flags = CBSSTAR_NOACTIVE;
if (b->avail <= 0) b->flags = GRUBSTAR_NOACTIVE;
 
if (TIMESPEC_A_LT_B(&b->dline, &schedule_time)) {
/* we modify the deadline ... */
291,8 → 267,8
ADDUSEC2TIMESPEC(b->T, &b->dline);
}
 
if (b->flags == CBSSTAR_NOACTIVE && b->dline_timer == NIL) {
b->dline_timer=kern_event_post(&b->dline, CBSSTAR_deadline_timer_hardreservation, b);
if (b->flags == GRUBSTAR_NOACTIVE && b->dline_timer == NIL) {
b->dline_timer=kern_event_post(&b->dline, GRUBSTAR_deadline_timer_hardreservation, b);
}
}
299,12 → 275,12
 
 
/* The on-line guarantee is enabled only if the appropriate flag is set... */
static int CBSSTAR_public_guarantee(LEVEL l, bandwidth_t *freebandwidth)
static int GRUBSTAR_public_guarantee(LEVEL l, bandwidth_t *freebandwidth)
{
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
 
#ifdef CBSSTAR_DEBUG
cbsstar_printf("(CS:Gua)");
#ifdef GRUBSTAR_DEBUG
kern_printf("(GS:Gua)");
#endif
 
if (*freebandwidth >= lev->U) {
318,24 → 294,18
static void capacity_handler(void *l)
{
CBSSTAR_level_des *lev = l;
GRUBSTAR_level_des *lev = l;
lev->cap_lev = NIL;
event_need_reschedule();
}
 
static int CBSSTAR_private_eligible(LEVEL l, PID p)
static int GRUBSTAR_private_eligible(LEVEL l, PID p)
{
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
struct budget_struct *b = &lev->b[lev->tb[p]];
JOB_TASK_MODEL job;
 
/* 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) {
352,7 → 322,7
 
/* and the capacity */
b->avail = b->Q;
b->flags = CBSSTAR_ACTIVE;
b->flags = GRUBSTAR_ACTIVE;
 
if (b->dline_timer!=NIL) {
kern_event_delete(b->dline_timer);
374,13 → 344,9
 
}
 
static void CBSSTAR_private_insert(LEVEL l, PID p, TASK_MODEL *m)
static void GRUBSTAR_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]);
GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
BUDGET_TASK_MODEL *budget;
 
if (m->pclass != BUDGET_PCLASS ||
390,8 → 356,8
}
budget = (BUDGET_TASK_MODEL *)m;
 
#ifdef CBSSTAR_DEBUG
cbsstar_printf("(CS:PriIns:%d:%d", p, budget->b);
#ifdef GRUBSTAR_DEBUG
kern_printf("(GS:PriIns:%d:%d", p, budget->b);
#endif
if (budget->b == -1)
404,7 → 370,7
the task have to be inserted into the master module */
struct timespec t;
kern_gettime(&t);
CBSSTAR_activation(lev,p,&t);
GRUBSTAR_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
412,18 → 378,18
iq_insertlast(p,&lev->b[budget->b].tasks);
}
 
#ifdef CBSSTAR_DEBUG
cbsstar_printf(")");
#ifdef GRUBSTAR_DEBUG
kern_printf(")");
#endif
 
}
 
static void CBSSTAR_private_extract(LEVEL l, PID p)
static void GRUBSTAR_private_extract(LEVEL l, PID p)
{
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
 
#ifdef CBSSTAR_DEBUG
kern_printf("(CS:Ext:%d)", p);
#ifdef GRUBSTAR_DEBUG
kern_printf("(GS:Ext:%d)", p);
#endif
 
/* a task is removed from execution for some reasons. It must be
433,7 → 399,7
/* remove the task from execution (or from the ready queue) */
if (lev->b[lev->tb[p]].current == p) {
 
CBSSTAR_account_capacity(lev,p);
GRUBSTAR_account_capacity(lev,p);
/* remove the task from the master module */
level_table[ lev->scheduling_level ]->
private_extract(lev->scheduling_level, p);
450,7 → 416,7
kern_gettime(&t);
n = iq_getfirst(&lev->b[lev->tb[p]].tasks);
CBSSTAR_activation(lev,n,&t); // it modifies b[lev->tb[p]].current
GRUBSTAR_activation(lev,n,&t); // it modifies b[lev->tb[p]].current
}
else
lev->b[lev->tb[p]].current=NIL;
461,13 → 427,13
}
}
 
static void CBSSTAR_private_dispatch(LEVEL l, PID p, int nostop)
static void GRUBSTAR_private_dispatch(LEVEL l, PID p, int nostop)
{
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
struct timespec ty;
 
#ifdef CBSSTAR_DEBUG
kern_printf("(CS:Dsp:%d)", p);
#ifdef GRUBSTAR_DEBUG
kern_printf("(GS:Dsp:%d)", p);
#endif
 
/* the current task (that is the only one inserted in the master module
488,18 → 454,18
}
 
static void CBSSTAR_private_epilogue(LEVEL l, PID p)
static void GRUBSTAR_private_epilogue(LEVEL l, PID p)
{
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
struct budget_struct *b = &lev->b[lev->tb[p]];
 
#ifdef CBSSTAR_DEBUG
#ifdef GRUBSTAR_DEBUG
kern_printf("(CS:Epi:%d)",p);
#endif
 
if (p==b->current) {
CBSSTAR_account_capacity(lev,p);
GRUBSTAR_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 */
525,31 → 491,28
 
/* Registration functions }*/
 
/*+ Registration function:
int flags the init flags ... see CBSSTAR.h +*/
LEVEL CBSSTAR_register_level(int n, LEVEL master)
LEVEL GRUBSTAR_register_level(int n, LEVEL master)
{
LEVEL l; /* the level that we register */
CBSSTAR_level_des *lev; /* for readableness only */
GRUBSTAR_level_des *lev; /* for readableness only */
PID i; /* a counter */
 
kern_printf("CBSSTAR_register_level\n");
printk("GRUBSTAR_register_level\n");
 
/* request an entry in the level_table */
l = level_alloc_descriptor(sizeof(CBSSTAR_level_des));
l = level_alloc_descriptor(sizeof(GRUBSTAR_level_des));
 
lev = (CBSSTAR_level_des *)level_table[l];
lev = (GRUBSTAR_level_des *)level_table[l];
 
/* 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.private_insert = GRUBSTAR_private_insert;
lev->l.private_extract = GRUBSTAR_private_extract;
lev->l.private_eligible = GRUBSTAR_private_eligible;
lev->l.private_dispatch = GRUBSTAR_private_dispatch;
lev->l.private_epilogue = GRUBSTAR_private_epilogue;
 
lev->l.public_guarantee = CBSSTAR_public_guarantee;
lev->l.public_guarantee = GRUBSTAR_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++) {
557,11 → 520,12
lev->b[i].T = 0;
NULL_TIMESPEC(&lev->b[i].dline);
lev->b[i].dline_timer = NIL;
lev->b[i].vtimer=NIL;
lev->b[i].avail = 0;
lev->b[i].current = -1;
lev->b[i].flags = CBSSTAR_ACTIVE;
lev->b[i].flags = GRUBSTAR_ACTIVE;
lev->b[i].l=l;
iq_init(&lev->b[i].tasks, /* &freedesc */NULL, 0);
iq_init(&lev->b[i].tasks, NULL, 0);
}
 
lev->n = n;
579,13 → 543,13
 
}
 
int CBSSTAR_setbudget(LEVEL l, TIME Q, TIME T, LEVEL local_scheduler_level, int scheduler_id)
int GRUBSTAR_setbudget(LEVEL l, TIME Q, TIME T, LEVEL local_scheduler_level, int scheduler_id)
{
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
int r;
 
#ifdef CBSSTAR_DEBUG
cbsstar_printf("(CS:SetBud)");
#ifdef GRUBSTAR_DEBUG
kern_printf("(GS:SetBud)");
#endif
 
for (r = 0; r < lev->n; r++)
605,7 → 569,7
lev->b[r].Q = Q;
lev->b[r].T = T;
lev->b[r].avail = Q;
lev->b[r].flags = CBSSTAR_ACTIVE;
lev->b[r].flags = GRUBSTAR_ACTIVE;
lev->b[r].loc_sched_id = scheduler_id;
lev->b[r].loc_sched_level = local_scheduler_level;
618,10 → 582,10
return -1;
}
 
int CBSSTAR_removebudget(LEVEL l, int budget)
int GRUBSTAR_removebudget(LEVEL l, int budget)
{
 
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
 
bandwidth_t b;
635,16 → 599,16
lev->b[budget].dline_timer = NIL;
lev->b[budget].avail = 0;
lev->b[budget].current = -1;
lev->b[budget].flags = CBSSTAR_ACTIVE;
lev->b[budget].flags = GRUBSTAR_ACTIVE;
 
return 0;
 
}
 
int CBSSTAR_adjust_budget(LEVEL l, TIME Q, TIME T, int budget)
int GRUBSTAR_adjust_budget(LEVEL l, TIME Q, TIME T, int budget)
{
 
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
 
lev->b[budget].Q = Q;
lev->b[budget].T = T;
653,10 → 617,10
 
}
 
int CBSSTAR_getbudgetinfo(LEVEL l, TIME *Q, TIME *T, int budget)
int GRUBSTAR_getbudgetinfo(LEVEL l, TIME *Q, TIME *T, int budget)
{
 
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
*Q = lev->b[budget].Q;
*T = lev->b[budget].T;
665,41 → 629,41
 
}
 
int CBSSTAR_is_active(LEVEL l, int budget)
int GRUBSTAR_is_active(LEVEL l, int budget)
{
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
 
return lev->b[budget].flags;
 
}
 
int CBSSTAR_get_local_scheduler_level_from_budget(LEVEL l, int budget)
int GRUBSTAR_get_local_scheduler_level_from_budget(LEVEL l, int budget)
{
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
 
return lev->b[budget].loc_sched_level;
 
}
 
int CBSSTAR_get_local_scheduler_level_from_pid(LEVEL l, PID p)
int GRUBSTAR_get_local_scheduler_level_from_pid(LEVEL l, PID p)
{
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
 
return lev->b[lev->tb[p]].loc_sched_level;
 
}
 
int CBSSTAR_get_local_scheduler_id_from_budget(LEVEL l, int budget)
int GRUBSTAR_get_local_scheduler_id_from_budget(LEVEL l, int budget)
{
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
 
return lev->b[budget].loc_sched_id;
 
}
 
int CBSSTAR_get_local_scheduler_id_from_pid(LEVEL l, PID p)
int GRUBSTAR_get_local_scheduler_id_from_pid(LEVEL l, PID p)
{
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
GRUBSTAR_level_des *lev = (GRUBSTAR_level_des *)(level_table[l]);
 
return lev->b[lev->tb[p]].loc_sched_id;