20,11 → 20,11 |
|
/* |
------------ |
CVS : $Id: cbsstar.c,v 1.5 2003-06-18 08:13:01 trimarchi Exp $ |
CVS : $Id: cbsstar.c,v 1.6 2003-08-01 13:20:38 trimarchi Exp $ |
|
File: $File$ |
Revision: $Revision: 1.5 $ |
Last update: $Date: 2003-06-18 08:13:01 $ |
Revision: $Revision: 1.6 $ |
Last update: $Date: 2003-08-01 13:20:38 $ |
------------ |
|
Read CBSSTAR.h for general details. |
70,13 → 70,20 |
#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 |
*/ |
|
#ifdef CBSSTAR_DEBUG_OLD |
//#define CBSSTAR_DEBUG |
int event_monitor; |
#ifdef CBSSTAR_DEBUG |
|
|
static __inline__ void fake_printf(char *fmt, ...) {} |
|
//#define cbsstar_printf kern_printf |
87,8 → 94,8 |
#define cbsstar_printf2 fake_printf |
#define cbsstar_printf3 fake_printf |
|
#if 0 |
void cbsstar_printq(IQUEUE *q) |
#if 0 |
void cbsstar_printq(QQUEUE *q) |
{ |
PID p; |
kern_printf("["); |
104,7 → 111,7 |
static __inline__ void cbsstar_printq(QQUEUE *q) {} |
#endif |
|
#if 0 |
#if 0 |
static __inline__ void cbsstar_printblob(int x) { if (x) cputc('±'); else cputc('Û'); } |
#else |
static __inline__ void cbsstar_printblob(int x) {} |
115,19 → 122,22 |
/* |
* 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 */ |
}; |
142,14 → 152,80 |
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) |
156,7 → 232,6 |
{ |
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... */ |
|
172,22 → 247,17 |
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) ) { |
/* if (TIMESPEC_A_LT_B(&lev->cbs_dline[p], acttime) ) |
kern_printf("$"); |
else |
kern_printf("(Ûdline%d.%d act%d.%d wcet%d per%d avail%dÛ)", |
lev->cbs_dline[p].tv_sec,lev->cbs_dline[p].tv_nsec/1000, |
acttime->tv_sec, acttime->tv_nsec/1000, |
proc_table[p].wcet, lev->period[p], proc_table[p].avail_time); |
*/ /* we modify the deadline ... */ |
TIMESPEC_ASSIGN(&b->dline, acttime); |
ADDUSEC2TIMESPEC(b->T, &b->dline); |
|
/* and the capacity */ |
} |
|
/* and the capacity */ |
if (b->flags==INIT) { |
b->avail = b->Q; |
b->flags=ACTIVE; |
} |
|
|
#ifdef CBSSTAR_DEBUG |
194,28 → 264,43 |
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 |
cbsstar_printf("(C:iact p%d %ld.%ld av=%d)",p,b->dline.tv_sec,b->dline.tv_nsec/1000, b->avail); |
#endif |
//kern_printf("Pid %d, Act %d, Dd %d", p,acttime->tv_nsec/1000,(b->dline).tv_nsec/1000); |
//#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; |
223,6 → 308,25 |
#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); |
} |
|
|
} |
|
|
243,6 → 347,15 |
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]); |
250,7 → 363,7 |
JOB_TASK_MODEL job; |
|
#ifdef CBSSTAR_DEBUG |
cbsstar_printf("(C:eli %d",p); |
//kern_printf("(C:eli %d",p); |
#endif |
|
/* we have to check if the deadline and the wcet are correct... |
259,32 → 372,45 |
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 ( TIMESPEC_A_LT_B(&b->dline, &schedule_time) ) { |
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 ... */ |
/* 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; |
|
#ifdef CBSSTAR_DEBUG |
cbsstar_printf2(" %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 |
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 |
292,7 → 418,6 |
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 |
315,7 → 440,7 |
|
lev->tb[p] = budget->b; |
|
if (lev->b[budget->b].current == NIL) { |
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; |
326,10 → 451,10 |
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 |
cbsstar_printf(" ilast"); |
cbsstar_printq(&lev->b[budget->b].tasks); |
#endif |
//#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(")"); |
340,18 → 465,19 |
{ |
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]); |
|
#ifdef CBSSTAR_DEBUG |
cbsstar_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 |
//#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!) */ |
CBSSTAR_account_capacity(lev,p); |
|
/* 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); |
365,7 → 491,7 |
/* the buffer has no tasks! */ |
lev->b[lev->tb[p]].current = NIL; |
} |
else { |
else if (lev->b[lev->tb[p]].flags) { |
/* if so, insert the new task into the master module */ |
PID n; |
struct timespec t; |
372,33 → 498,29 |
|
kern_gettime(&t); |
n = iq_getfirst(&lev->b[lev->tb[p]].tasks); |
#ifdef CBSSTAR_DEBUG |
cbsstar_printf("{p%d n%d}",p,n); |
#endif |
//#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 |
else { |
iq_extract(p, &lev->b[lev->tb[p]].tasks); |
} |
} |
|
static void capacity_handler() |
{ |
//kern_printf("!"); |
event_need_reschedule(); |
|
} |
|
|
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 |
cbsstar_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 |
//#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 |
413,8 → 535,9 |
if (!nostop) { |
TIMESPEC_ASSIGN(&ty, &schedule_time); |
ADDUSEC2TIMESPEC(lev->b[lev->tb[p]].avail,&ty); |
lev->cap_lev = kern_event_post(&ty, capacity_handler, NULL); |
lev->cap_lev = kern_event_post(&ty,capacity_handler, lev); |
} |
|
} |
|
static void CBSSTAR_private_epilogue(LEVEL l, PID p) |
422,65 → 545,47 |
CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]); |
struct budget_struct *b = &lev->b[lev->tb[p]]; |
|
#ifdef CBSSTAR_DEBUG |
cbsstar_printf("(C:gepi %d",p); |
#endif |
|
CBSSTAR_account_capacity(lev,p); |
//#ifdef CBSSTAR_DEBUG |
//kern_printf("(C:gepi %d %d",p, b->current); |
//#endif |
|
if (lev->cap_lev!=NIL) |
kern_event_delete(lev->cap_lev); |
lev->cap_lev=NIL; |
if (p==b->current) { |
|
CBSSTAR_account_capacity(lev,p); |
|
/* we have to check if the capacity is still available */ |
if (b->avail > 0) { |
/* 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 |
cbsstar_printf(" *av=%d", b->avail); |
#endif |
} else { |
|
/* The capacity is exausted; the deadline have to be postponed and |
the task have to be reinserted in the master module */ |
JOB_TASK_MODEL job; |
|
/* we kill the current activation */ |
level_table[ lev->scheduling_level ]-> |
private_extract(lev->scheduling_level, p); |
|
/* 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 */ |
while (b->avail <= 0) { |
ADDUSEC2TIMESPEC(b->T, &b->dline); |
b->avail += b->Q; |
#ifdef CBSSTAR_DEBUG |
cbsstar_printf("±%d±",b->avail); |
#endif |
// 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 |
kern_printf(" %ld.%ld av=%d",b->dline.tv_sec,b->dline.tv_nsec/1000, b->avail); |
#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); |
} |
#ifdef CBSSTAR_DEBUG |
cbsstar_printf(")"); |
cbsstar_printf(")"); |
#endif |
|
} |
|
} |
|
/* Registration functions }*/ |
|
/* Registration functions */ |
|
/*+ Registration function: |
int flags the init flags ... see CBSSTAR.h +*/ |
LEVEL CBSSTAR_register_level(int n, LEVEL master) |
516,14 → 621,16 |
lev->b[i].Q = 0; |
lev->b[i].T = 0; |
NULL_TIMESPEC(&lev->b[i].dline); |
lev->b[i].dline_timer = 0; |
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; |
|
530,6 → 637,7 |
lev->U = 0; |
lev->cap_lev=NIL; |
lev->scheduling_level = master; |
lev->on_shadow=NIL; |
|
return l; |
} |