20,11 → 20,11 |
|
/** |
------------ |
CVS : $Id: edf.c,v 1.2 2002-10-28 07:55:54 pj Exp $ |
CVS : $Id: edf.c,v 1.3 2002-11-11 08:32:06 pj Exp $ |
|
File: $File$ |
Revision: $Revision: 1.2 $ |
Last update: $Date: 2002-10-28 07:55:54 $ |
Revision: $Revision: 1.3 $ |
Last update: $Date: 2002-11-11 08:32:06 $ |
------------ |
|
This file contains the scheduling module EDF (Earliest Deadline First) |
67,7 → 67,6 |
|
/*+ Status used in the level +*/ |
#define EDF_READY MODULE_STATUS_BASE /*+ - Ready status +*/ |
#define EDF_DELAY MODULE_STATUS_BASE+1 /*+ - Delay status +*/ |
#define EDF_WCET_VIOLATED MODULE_STATUS_BASE+2 /*+ when wcet is finished +*/ |
#define EDF_WAIT MODULE_STATUS_BASE+3 /*+ to wait the deadline +*/ |
#define EDF_IDLE MODULE_STATUS_BASE+4 /*+ to wait the deadline +*/ |
90,7 → 89,7 |
/*+ used to manage the JOB_TASK_MODEL and the |
periodicity +*/ |
|
QUEUE ready; /*+ the ready queue +*/ |
IQUEUE ready; /*+ the ready queue +*/ |
|
int flags; /*+ the init flags... +*/ |
|
106,7 → 105,6 |
|
switch (status) { |
case EDF_READY : return "EDF_Ready"; |
case EDF_DELAY : return "EDF_Delay"; |
case EDF_WCET_VIOLATED: return "EDF_Wcet_Violated"; |
case EDF_WAIT : return "EDF_Sporadic_Wait"; |
case EDF_IDLE : return "EDF_Idle"; |
119,6 → 117,7 |
{ |
PID p = (PID) par; |
EDF_level_des *lev; |
struct timespec *temp; |
|
edf_printf("$"); |
|
128,7 → 127,7 |
case EDF_ZOMBIE: |
/* we finally put the task in the ready queue */ |
proc_table[p].status = FREE; |
q_insertfirst(p,&freedesc); |
iq_insertfirst(p,&freedesc); |
/* and free the allocated bandwidth */ |
lev->U -= (MAX_BANDWIDTH/lev->period[p]) * proc_table[p].wcet; |
break; |
137,15 → 136,16 |
/* tracer stuff */ |
trc_logevent(TRC_INTACTIVATION,&p); |
/* similar to EDF_task_activate */ |
temp = iq_query_timespec(p,&lev->ready); |
TIMESPEC_ASSIGN(&proc_table[p].request_time, |
&proc_table[p].timespec_priority); |
ADDUSEC2TIMESPEC(lev->period[p], &proc_table[p].timespec_priority); |
temp); |
ADDUSEC2TIMESPEC(lev->period[p], temp); |
proc_table[p].status = EDF_READY; |
q_timespec_insert(p,&lev->ready); |
lev->deadline_timer[p] = kern_event_post(&proc_table[p].timespec_priority, |
iq_timespec_insert(p,&lev->ready); |
lev->deadline_timer[p] = kern_event_post(temp, |
EDF_timer_deadline, |
(void *)p); |
edf_printf("(dline p%d ev%d %d.%d)",(int)p,(int)lev->deadline_timer[p],(int)proc_table[p].timespec_priority.tv_sec,(int)proc_table[p].timespec_priority.tv_nsec/1000); |
edf_printf("(dline p%d ev%d %d.%d)",(int)p,(int)lev->deadline_timer[p],(int)temp->tv_sec,(int)temp->tv_nsec/1000); |
//printk("(d%d idle priority set to %d)",p,proc_table[p].priority ); |
event_need_reschedule(); |
printk("el%d|",p); |
172,23 → 172,6 |
kern_raise(XDEADLINE_MISS,p); |
} |
|
/*+ this function is called when a task finish his delay +*/ |
static void EDF_timer_delay(void *par) |
{ |
PID p = (PID) par; |
EDF_level_des *lev; |
|
lev = (EDF_level_des *)level_table[proc_table[p].task_level]; |
|
proc_table[p].status = EDF_READY; |
q_timespec_insert(p,&lev->ready); |
|
proc_table[p].delay_timer = NIL; /* Paranoia */ |
|
event_need_reschedule(); |
} |
|
|
static int EDF_level_accept_task_model(LEVEL l, TASK_MODEL *m) |
{ |
if (m->pclass == HARD_PCLASS || m->pclass == (HARD_PCLASS | l)) { |
221,7 → 204,7 |
static void EDF_level_status(LEVEL l) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
PID p = lev->ready; |
PID p = iq_query_first(&lev->ready); |
|
kern_printf("Wcet Check : %s\n", |
onoff(lev->flags & EDF_ENABLE_WCET_CHECK)); |
239,10 → 222,10 |
proc_table[p].name, |
lev->flag[p] & EDF_FLAG_SPORADIC ? "MinITime" : "Period ", |
lev->period[p], |
proc_table[p].timespec_priority.tv_sec, |
proc_table[p].timespec_priority.tv_nsec/1000, |
iq_query_timespec(p, &lev->ready)->tv_sec, |
iq_query_timespec(p, &lev->ready)->tv_nsec/1000, |
EDF_status_to_a(proc_table[p].status)); |
p = proc_table[p].next; |
p = iq_query_next(p, &lev->ready); |
} |
|
for (p=0; p<MAX_PROC; p++) |
253,8 → 236,8 |
proc_table[p].name, |
lev->flag[p] & EDF_FLAG_SPORADIC ? "MinITime" : "Period ", |
lev->period[p], |
proc_table[p].timespec_priority.tv_sec, |
proc_table[p].timespec_priority.tv_nsec/1000, |
iq_query_timespec(p, &lev->ready)->tv_sec, |
iq_query_timespec(p, &lev->ready)->tv_nsec/1000, |
EDF_status_to_a(proc_table[p].status)); |
} |
|
273,7 → 256,7 |
kern_printf(") "); |
} |
*/ |
return (PID)lev->ready; |
return iq_query_first(&lev->ready); |
} |
|
/* The on-line guarantee is enabled only if the appropriate flag is set... */ |
365,14 → 348,6 |
return 0; /* if the task p is chosen, it is always eligible */ |
} |
|
#ifdef __TEST1__ |
extern int testactive; |
extern struct timespec s_stime[]; |
extern TIME s_curr[]; |
extern TIME s_PID[]; |
extern int useds; |
#endif |
|
static void EDF_task_dispatch(LEVEL l, PID p, int nostop) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
382,18 → 357,8 |
/* the task state is set EXE by the scheduler() |
we extract the task from the ready queue |
NB: we can't assume that p is the first task in the queue!!! */ |
q_extract(p, &lev->ready); |
|
#ifdef __TEST1__ |
if (testactive) |
{ |
TIMESPEC_ASSIGN(&s_stime[useds], &schedule_time); |
s_curr[useds] = proc_table[p].avail_time; |
s_PID[useds] = p; |
useds++; |
iq_extract(p, &lev->ready); |
} |
#endif |
} |
|
static void EDF_task_epilogue(LEVEL l, PID p) |
{ |
409,7 → 374,7 |
} |
else { |
/* the task has been preempted. it returns into the ready queue... */ |
q_timespec_insert(p,&lev->ready); |
iq_timespec_insert(p,&lev->ready); |
proc_table[p].status = EDF_READY; |
} |
} |
417,6 → 382,7 |
static void EDF_task_activate(LEVEL l, PID p) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
struct timespec *temp; |
|
if (proc_table[p].status == EDF_WAIT) { |
kern_raise(XACTIVATION,p); |
433,19 → 399,19 |
/* see also EDF_timer_deadline */ |
ll_gettime(TIME_EXACT, &proc_table[p].request_time); |
|
TIMESPEC_ASSIGN(&proc_table[p].timespec_priority, |
&proc_table[p].request_time); |
ADDUSEC2TIMESPEC(lev->period[p], &proc_table[p].timespec_priority); |
temp = iq_query_timespec(p, &lev->ready); |
TIMESPEC_ASSIGN(temp, &proc_table[p].request_time); |
ADDUSEC2TIMESPEC(lev->period[p], temp); |
|
/* Insert task in the correct position */ |
proc_table[p].status = EDF_READY; |
q_timespec_insert(p,&lev->ready); |
iq_timespec_insert(p,&lev->ready); |
|
/* Set the deadline timer */ |
lev->deadline_timer[p] = kern_event_post(&proc_table[p].timespec_priority, |
lev->deadline_timer[p] = kern_event_post(temp, |
EDF_timer_deadline, |
(void *)p); |
edf_printf("(dline p%d ev%d %d.%d)",p,(int)lev->deadline_timer[p],(int)proc_table[p].timespec_priority.tv_sec,(int)proc_table[p].timespec_priority.tv_nsec/1000); |
edf_printf("(dline p%d ev%d %d.%d)",p,(int)lev->deadline_timer[p],(int)temp->tv_sec,(int)temp->tv_nsec/1000); |
} |
|
static void EDF_task_insert(LEVEL l, PID p) |
457,7 → 423,7 |
|
/* Insert task in the coEDFect position */ |
proc_table[p].status = EDF_READY; |
q_timespec_insert(p,&lev->ready); |
iq_timespec_insert(p,&lev->ready); |
} |
|
static void EDF_task_extract(LEVEL l, PID p) |
518,22 → 484,7 |
correctly the task state to sleep... */ |
} |
|
static void EDF_task_delay(LEVEL l, PID p, TIME usdelay) |
{ |
struct timespec wakeuptime; |
// EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
/* equal to EDF_task_endcycle */ |
proc_table[p].status = EDF_DELAY; |
|
/* we need to delete this event if we kill the task while it is sleeping */ |
ll_gettime(TIME_EXACT, &wakeuptime); |
ADDUSEC2TIMESPEC(usdelay, &wakeuptime); |
proc_table[p].delay_timer = kern_event_post(&wakeuptime, |
EDF_timer_delay, |
(void *)p); |
} |
|
/* Guest Functions |
These functions manages a JOB_TASK_MODEL, that is used to put |
a guest task in the EDF ready queue. */ |
546,7 → 497,7 |
/* if the EDF_guest_create is called, then the pclass must be a |
valid pclass. */ |
|
TIMESPEC_ASSIGN(&proc_table[p].timespec_priority, &job->deadline); |
*iq_query_timespec(p, &lev->ready) = job->deadline; |
|
lev->deadline_timer[p] = -1; |
|
577,7 → 528,7 |
/* the task state is set to EXE by the scheduler() |
we extract the task from the ready queue |
NB: we can't assume that p is the first task in the queue!!! */ |
q_extract(p, &lev->ready); |
iq_extract(p, &lev->ready); |
} |
|
static void EDF_guest_epilogue(LEVEL l, PID p) |
585,7 → 536,7 |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
/* the task has been preempted. it returns into the ready queue... */ |
q_timespec_insert(p,&lev->ready); |
iq_timespec_insert(p,&lev->ready); |
proc_table[p].status = EDF_READY; |
} |
|
594,12 → 545,12 |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
/* Insert task in the correct position */ |
q_timespec_insert(p,&lev->ready); |
iq_timespec_insert(p,&lev->ready); |
proc_table[p].status = EDF_READY; |
|
/* Set the deadline timer */ |
if (!(lev->flag[p] & EDF_FLAG_NORAISEEXC)) |
lev->deadline_timer[p] = kern_event_post(&proc_table[p].timespec_priority, |
lev->deadline_timer[p] = kern_event_post(iq_query_timespec(p, &lev->ready), |
EDF_timer_guest_deadline, |
(void *)p); |
|
610,7 → 561,7 |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
/* Insert task in the correct position */ |
q_timespec_insert(p,&lev->ready); |
iq_timespec_insert(p,&lev->ready); |
proc_table[p].status = EDF_READY; |
} |
|
635,13 → 586,9 |
//kern_printf("EDF_guest_end: dline timer %d\n",lev->deadline_timer[p]); |
if (proc_table[p].status == EDF_READY) |
{ |
q_extract(p, &lev->ready); |
iq_extract(p, &lev->ready); |
//kern_printf("(g_end rdy extr)"); |
} |
else if (proc_table[p].status == EDF_DELAY) { |
event_delete(proc_table[p].delay_timer); |
proc_table[p].delay_timer = NIL; /* paranoia */ |
} |
|
/* we remove the deadline timer, because the slice is finished */ |
if (lev->deadline_timer[p] != NIL) { |
655,25 → 602,8 |
static void EDF_guest_sleep(LEVEL l, PID p) |
{ kern_raise(XINVALID_GUEST,exec_shadow); } |
|
static void EDF_guest_delay(LEVEL l, PID p, TIME usdelay) |
{ |
struct timespec wakeuptime; |
// EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
/* equal to EDF_task_endcycle */ |
proc_table[p].status = EDF_DELAY; |
|
/* we need to delete this event if we kill the task while it is sleeping */ |
ll_gettime(TIME_EXACT, &wakeuptime); |
ADDUSEC2TIMESPEC(usdelay, &wakeuptime); |
proc_table[p].delay_timer = kern_event_post(&wakeuptime, |
EDF_timer_delay, |
(void *)p); |
} |
|
|
|
|
/* Registration functions */ |
|
/*+ Registration function: |
725,7 → 655,6 |
lev->l.task_endcycle = EDF_task_endcycle; |
lev->l.task_end = EDF_task_end; |
lev->l.task_sleep = EDF_task_sleep; |
lev->l.task_delay = EDF_task_delay; |
|
lev->l.guest_create = EDF_guest_create; |
lev->l.guest_detach = EDF_guest_detach; |
737,7 → 666,6 |
lev->l.guest_endcycle = EDF_guest_endcycle; |
lev->l.guest_end = EDF_guest_end; |
lev->l.guest_sleep = EDF_guest_sleep; |
lev->l.guest_delay = EDF_guest_delay; |
|
/* fill the EDF descriptor part */ |
for(i=0; i<MAX_PROC; i++) { |
746,7 → 674,7 |
lev->flag[i] = 0; |
} |
|
lev->ready = NIL; |
iq_init(&lev->ready, &freedesc, 0); |
lev->flags = flags & 0x07; |
lev->U = 0; |
} |