20,11 → 20,11 |
|
/** |
------------ |
CVS : $Id: edf.c,v 1.3 2002-11-11 08:32:06 pj Exp $ |
CVS : $Id: edf.c,v 1.4 2003-01-07 17:07:50 pj Exp $ |
|
File: $File$ |
Revision: $Revision: 1.3 $ |
Last update: $Date: 2002-11-11 08:32:06 $ |
Revision: $Revision: 1.4 $ |
Last update: $Date: 2003-01-07 17:07:50 $ |
------------ |
|
This file contains the scheduling module EDF (Earliest Deadline First) |
34,7 → 34,7 |
**/ |
|
/* |
* Copyright (C) 2000 Paolo Gai |
* Copyright (C) 2000,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 |
62,8 → 62,8 |
#include <kernel/func.h> |
#include <kernel/trace.h> |
|
//#define edf_printf kern_printf |
#define edf_printf printk |
//#define EDFDEBUG |
#define edf_printf kern_printf |
|
/*+ Status used in the level +*/ |
#define EDF_READY MODULE_STATUS_BASE /*+ - Ready status +*/ |
98,21 → 98,6 |
} EDF_level_des; |
|
|
static char *EDF_status_to_a(WORD status) |
{ |
if (status < MODULE_STATUS_BASE) |
return status_to_a(status); |
|
switch (status) { |
case EDF_READY : return "EDF_Ready"; |
case EDF_WCET_VIOLATED: return "EDF_Wcet_Violated"; |
case EDF_WAIT : return "EDF_Sporadic_Wait"; |
case EDF_IDLE : return "EDF_Idle"; |
case EDF_ZOMBIE : return "EDF_Zombie"; |
default : return "EDF_Unknown"; |
} |
} |
|
static void EDF_timer_deadline(void *par) |
{ |
PID p = (PID) par; |
119,7 → 104,9 |
EDF_level_des *lev; |
struct timespec *temp; |
|
#ifdef EDFDEBUG |
edf_printf("$"); |
#endif |
|
lev = (EDF_level_des *)level_table[proc_table[p].task_level]; |
|
137,8 → 124,6 |
trc_logevent(TRC_INTACTIVATION,&p); |
/* similar to EDF_task_activate */ |
temp = iq_query_timespec(p,&lev->ready); |
TIMESPEC_ASSIGN(&proc_table[p].request_time, |
temp); |
ADDUSEC2TIMESPEC(lev->period[p], temp); |
proc_table[p].status = EDF_READY; |
iq_timespec_insert(p,&lev->ready); |
145,10 → 130,10 |
lev->deadline_timer[p] = kern_event_post(temp, |
EDF_timer_deadline, |
(void *)p); |
#ifdef EDFDEBUG |
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 ); |
#endif |
event_need_reschedule(); |
printk("el%d|",p); |
break; |
|
case EDF_WAIT: |
158,8 → 143,10 |
|
default: |
/* else, a deadline miss occurred!!! */ |
#ifdef EDFDEBUG |
edf_printf("\nstatus %d\n", (int)proc_table[p].status); |
edf_printf("timer_deadline:AAARRRGGGHHH!!!"); |
#endif |
kern_raise(XDEADLINE_MISS,p); |
} |
} |
168,99 → 155,26 |
{ |
PID p = (PID) par; |
|
#ifdef EDFDEBUG |
edf_printf("AAARRRGGGHHH!!!"); |
#endif |
kern_raise(XDEADLINE_MISS,p); |
} |
|
static int EDF_level_accept_task_model(LEVEL l, TASK_MODEL *m) |
/* The scheduler only gets the first task in the queue */ |
static PID EDF_public_scheduler(LEVEL l) |
{ |
if (m->pclass == HARD_PCLASS || m->pclass == (HARD_PCLASS | l)) { |
HARD_TASK_MODEL *h = (HARD_TASK_MODEL *)m; |
|
if (h->wcet && h->mit) |
return 0; |
} |
|
return -1; |
} |
|
static int EDF_level_accept_guest_model(LEVEL l, TASK_MODEL *m) |
{ |
if (m->pclass == JOB_PCLASS || m->pclass == (JOB_PCLASS | l)) |
return 0; |
else |
return -1; |
} |
|
|
static char *onoff(int i) |
{ |
if (i) |
return "On "; |
else |
return "Off"; |
} |
|
static void EDF_level_status(LEVEL l) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
PID p = iq_query_first(&lev->ready); |
|
kern_printf("Wcet Check : %s\n", |
onoff(lev->flags & EDF_ENABLE_WCET_CHECK)); |
kern_printf("On-line guarantee : %s\n", |
onoff(lev->flags & EDF_ENABLE_GUARANTEE)); |
kern_printf("Used Bandwidth : %u/%u\n", |
lev->U, MAX_BANDWIDTH); |
#ifdef EDFDEBUG |
edf_printf("(s%d)", iq_query_first(&lev->ready)); |
#endif |
|
while (p != NIL) { |
if ((proc_table[p].pclass) == JOB_PCLASS) |
kern_printf("Pid: %2d (GUEST)\n", p); |
else |
kern_printf("Pid: %2d Name: %10s %s: %9ld Dline: %9ld.%6ld Stat: %s\n", |
p, |
proc_table[p].name, |
lev->flag[p] & EDF_FLAG_SPORADIC ? "MinITime" : "Period ", |
lev->period[p], |
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 = iq_query_next(p, &lev->ready); |
} |
|
for (p=0; p<MAX_PROC; p++) |
if (proc_table[p].task_level == l && proc_table[p].status != EDF_READY |
&& proc_table[p].status != FREE ) |
kern_printf("Pid: %2d Name: %10s %s: %9ld Dline: %9ld.%6ld Stat: %s\n", |
p, |
proc_table[p].name, |
lev->flag[p] & EDF_FLAG_SPORADIC ? "MinITime" : "Period ", |
lev->period[p], |
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)); |
} |
|
/* The scheduler only gets the first task in the queue */ |
static PID EDF_level_scheduler(LEVEL l) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
/* { // print 4 dbg the ready queue |
PID p= lev->ready; |
kern_printf("(s"); |
while (p != NIL) { |
kern_printf("%d ",p); |
p = proc_table[p].next; |
} |
kern_printf(") "); |
} |
*/ |
return iq_query_first(&lev->ready); |
} |
|
/* The on-line guarantee is enabled only if the appropriate flag is set... */ |
static int EDF_level_guarantee(LEVEL l, bandwidth_t *freebandwidth) |
static int EDF_public_guarantee(LEVEL l, bandwidth_t *freebandwidth) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
278,14 → 192,20 |
|
} |
|
static int EDF_task_create(LEVEL l, PID p, TASK_MODEL *m) |
static int EDF_public_create(LEVEL l, PID p, TASK_MODEL *m) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
HARD_TASK_MODEL *h; |
|
/* if the EDF_task_create is called, then the pclass must be a |
valid pclass. */ |
if (m->pclass != HARD_PCLASS) return -1; |
if (m->level != 0 && m->level != l) return -1; |
h = (HARD_TASK_MODEL *)m; |
if (!h->wcet || !h->mit) return -1; |
/* now we know that m is a valid model */ |
|
HARD_TASK_MODEL *h = (HARD_TASK_MODEL *)m; |
#ifdef EDFDEBUG |
edf_printf("(cr%d)", p); |
#endif |
|
lev->period[p] = h->mit; |
|
329,7 → 249,7 |
return 0; /* OK, also if the task cannot be guaranteed... */ |
} |
|
static void EDF_task_detach(LEVEL l, PID p) |
static void EDF_public_detach(LEVEL l, PID p) |
{ |
/* the EDF level doesn't introduce any dinamic allocated new field. |
we have only to reset the NO_GUARANTEE FIELD and decrement the allocated |
337,6 → 257,10 |
|
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
#ifdef EDFDEBUG |
edf_printf("(det%d)", p); |
#endif |
|
if (lev->flags & EDF_FAILED_GUARANTEE) |
lev->flags &= ~EDF_FAILED_GUARANTEE; |
else |
343,16 → 267,13 |
lev->U -= (MAX_BANDWIDTH / lev->period[p]) * proc_table[p].wcet; |
} |
|
static int EDF_task_eligible(LEVEL l, PID p) |
static void EDF_public_dispatch(LEVEL l, PID p, int nostop) |
{ |
return 0; /* if the task p is chosen, it is always eligible */ |
} |
|
static void EDF_task_dispatch(LEVEL l, PID p, int nostop) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
#ifdef EDFDEBUG |
edf_printf("(disp p%d %d.%d)",(int)p,(int)schedule_time.tv_sec,(int)schedule_time.tv_nsec/1000); |
#endif |
|
/* the task state is set EXE by the scheduler() |
we extract the task from the ready queue |
360,11 → 281,13 |
iq_extract(p, &lev->ready); |
} |
|
static void EDF_task_epilogue(LEVEL l, PID p) |
static void EDF_public_epilogue(LEVEL l, PID p) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
#ifdef EDFDEBUG |
edf_printf("(epil p%d %d.%d)",p,(int)schedule_time.tv_sec,(int)schedule_time.tv_nsec/1000); |
#endif |
|
/* check if the wcet is finished... */ |
if ((lev->flags & EDF_ENABLE_WCET_CHECK) && proc_table[p].avail_time <= 0) { |
379,11 → 302,15 |
} |
} |
|
static void EDF_task_activate(LEVEL l, PID p) |
static void EDF_public_activate(LEVEL l, PID p) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
struct timespec *temp; |
|
#ifdef EDFDEBUG |
edf_printf("(act%d)", p); |
#endif |
|
if (proc_table[p].status == EDF_WAIT) { |
kern_raise(XACTIVATION,p); |
return; |
397,10 → 324,8 |
|
|
/* see also EDF_timer_deadline */ |
ll_gettime(TIME_EXACT, &proc_table[p].request_time); |
|
temp = iq_query_timespec(p, &lev->ready); |
TIMESPEC_ASSIGN(temp, &proc_table[p].request_time); |
kern_gettime(temp); |
ADDUSEC2TIMESPEC(lev->period[p], temp); |
|
/* Insert task in the correct position */ |
411,15 → 336,17 |
lev->deadline_timer[p] = kern_event_post(temp, |
EDF_timer_deadline, |
(void *)p); |
#ifdef EDFDEBUG |
edf_printf("(dline p%d ev%d %d.%d)",p,(int)lev->deadline_timer[p],(int)temp->tv_sec,(int)temp->tv_nsec/1000); |
#endif |
} |
|
static void EDF_task_insert(LEVEL l, PID p) |
static void EDF_public_unblock(LEVEL l, PID p) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
/* Similar to EDF_task_activate, but we don't check in what state |
the task is and we don't set the request_time*/ |
/* Similar to EDF_task_activate, |
but we don't check in what state the task is */ |
|
/* Insert task in the coEDFect position */ |
proc_table[p].status = EDF_READY; |
426,7 → 353,7 |
iq_timespec_insert(p,&lev->ready); |
} |
|
static void EDF_task_extract(LEVEL l, PID p) |
static void EDF_public_block(LEVEL l, PID p) |
{ |
/* Extract the running task from the level |
. we have already extract it from the ready queue at the dispatch time. |
439,30 → 366,35 |
*/ |
} |
|
static void EDF_task_endcycle(LEVEL l, PID p) |
static int EDF_public_message(LEVEL l, PID p, void *m) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
#ifdef EDFDEBUG |
edf_printf("(ecyc p%d %d.%d)",p,(int)schedule_time.tv_sec,(int)schedule_time.tv_nsec/1000); |
#endif |
|
/* the task has terminated his job before it consume the wcet. All OK! */ |
if (lev->flag[p] & EDF_FLAG_SPORADIC) |
if (!lev->flag[p] & EDF_FLAG_SPORADIC) |
proc_table[p].status = EDF_IDLE; |
else |
proc_table[p].status = EDF_WAIT; |
else /* pclass = sporadic_pclass */ |
proc_table[p].status = EDF_IDLE; |
|
/* we reset the capacity counters... */ |
if (lev->flags & EDF_ENABLE_WCET_CHECK) |
proc_table[p].avail_time = proc_table[p].wcet; |
|
jet_update_endcycle(); /* Update the Jet data... */ |
trc_logevent(TRC_ENDCYCLE,&exec_shadow); /* tracer stuff */ |
|
/* when the deadline timer fire, it recognize the situation and set |
correctly all the stuffs (like reactivation, request_time, etc... ) */ |
correctly all the stuffs (like reactivation, sleep, etc... ) */ |
|
return 0; |
} |
|
static void EDF_task_end(LEVEL l, PID p) |
static void EDF_public_end(LEVEL l, PID p) |
{ |
// EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
proc_table[p].status = EDF_ZOMBIE; |
|
/* When the deadline timer fire, it put the task descriptor in |
469,60 → 401,40 |
the free queue, and free the allocated bandwidth... */ |
} |
|
static void EDF_task_sleep(LEVEL l, PID p) |
static void EDF_private_insert(LEVEL l, PID p, TASK_MODEL *m) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
JOB_TASK_MODEL *job; |
|
/* the task has terminated his job before it consume the wcet. All OK! */ |
proc_table[p].status = EDF_WAIT; |
if (m->pclass != JOB_PCLASS || (m->level != 0 && m->level != l) ) { |
kern_raise(XINVALID_TASK, p); |
return; |
} |
|
/* we reset the capacity counters... */ |
if (lev->flags & EDF_ENABLE_WCET_CHECK) |
proc_table[p].avail_time = proc_table[p].wcet; |
job = (JOB_TASK_MODEL *)m; |
|
/* when the deadline timer fire, it recognize the situation and set |
correctly the task state to sleep... */ |
} |
|
|
/* Guest Functions |
These functions manages a JOB_TASK_MODEL, that is used to put |
a guest task in the EDF ready queue. */ |
|
static int EDF_guest_create(LEVEL l, PID p, TASK_MODEL *m) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
JOB_TASK_MODEL *job = (JOB_TASK_MODEL *)m; |
|
/* if the EDF_guest_create is called, then the pclass must be a |
valid pclass. */ |
|
/* Insert task in the correct position */ |
*iq_query_timespec(p, &lev->ready) = job->deadline; |
iq_timespec_insert(p,&lev->ready); |
proc_table[p].status = EDF_READY; |
|
lev->deadline_timer[p] = -1; |
|
if (job->noraiseexc) |
lev->period[p] = job->period; |
|
/* Set the deadline timer */ |
if (!(job->noraiseexc)) |
lev->flag[p] = EDF_FLAG_NORAISEEXC; |
else |
else { |
lev->flag[p] = 0; |
|
lev->period[p] = job->period; |
|
/* there is no bandwidth guarantee at this level, it is performed |
by the level that inserts guest tasks... */ |
|
return 0; /* OK, also if the task cannot be guaranteed... */ |
lev->deadline_timer[p] = kern_event_post(iq_query_timespec(p, &lev->ready), |
EDF_timer_guest_deadline, |
(void *)p); |
} |
} |
|
static void EDF_guest_detach(LEVEL l, PID p) |
static void EDF_private_dispatch(LEVEL l, PID p, int nostop) |
{ |
/* the EDF level doesn't introduce any dinamic allocated new field. |
No guarantee is performed on guest tasks... so we don't have to reset |
the NO_GUARANTEE FIELD */ |
} |
|
static void EDF_guest_dispatch(LEVEL l, PID p, int nostop) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
/* the task state is set to EXE by the scheduler() |
531,7 → 443,7 |
iq_extract(p, &lev->ready); |
} |
|
static void EDF_guest_epilogue(LEVEL l, PID p) |
static void EDF_private_epilogue(LEVEL l, PID p) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
540,75 → 452,30 |
proc_table[p].status = EDF_READY; |
} |
|
static void EDF_guest_activate(LEVEL l, PID p) |
static void EDF_private_extract(LEVEL l, PID p) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
/* Insert task in the correct position */ |
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(iq_query_timespec(p, &lev->ready), |
EDF_timer_guest_deadline, |
(void *)p); |
|
} |
|
static void EDF_guest_insert(LEVEL l, PID p) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
/* Insert task in the correct position */ |
iq_timespec_insert(p,&lev->ready); |
proc_table[p].status = EDF_READY; |
} |
|
static void EDF_guest_extract(LEVEL l, PID p) |
{ |
/* Extract the running task from the level |
. we have already extract it from the ready queue at the dispatch time. |
. the state of the task is set by the calling function |
. the deadline must remain... |
|
So, we do nothing!!! |
*/ |
} |
|
static void EDF_guest_endcycle(LEVEL l, PID p) |
{ kern_raise(XINVALID_GUEST,exec_shadow); } |
|
static void EDF_guest_end(LEVEL l, PID p) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
|
//kern_printf("EDF_guest_end: dline timer %d\n",lev->deadline_timer[p]); |
#ifdef EDFDEBUG |
edf_printf("EDF_guest_end: dline timer %d\n",lev->deadline_timer[p]); |
#endif |
if (proc_table[p].status == EDF_READY) |
{ |
iq_extract(p, &lev->ready); |
//kern_printf("(g_end rdy extr)"); |
} |
|
/* we remove the deadline timer, because the slice is finished */ |
if (lev->deadline_timer[p] != NIL) { |
// kern_printf("EDF_guest_end: dline timer %d\n",lev->deadline_timer[p]); |
event_delete(lev->deadline_timer[p]); |
kern_event_delete(lev->deadline_timer[p]); |
lev->deadline_timer[p] = NIL; |
} |
|
} |
|
static void EDF_guest_sleep(LEVEL l, PID p) |
{ kern_raise(XINVALID_GUEST,exec_shadow); } |
|
|
|
/* Registration functions */ |
|
/*+ Registration function: |
int flags the init flags ... see edf.h +*/ |
void EDF_register_level(int flags) |
LEVEL EDF_register_level(int flags) |
{ |
LEVEL l; /* the level that we register */ |
EDF_level_des *lev; /* for readableness only */ |
617,56 → 484,34 |
printk("EDF_register_level\n"); |
|
/* request an entry in the level_table */ |
l = level_alloc_descriptor(); |
l = level_alloc_descriptor(sizeof(EDF_level_des)); |
|
printk(" alloco descrittore %d %d\n",l,(int)sizeof(EDF_level_des)); |
lev = (EDF_level_des *)level_table[l]; |
|
/* alloc the space needed for the EDF_level_des */ |
lev = (EDF_level_des *)kern_alloc(sizeof(EDF_level_des)); |
|
printk(" lev=%d\n",(int)lev); |
|
/* update the level_table with the new entry */ |
level_table[l] = (level_des *)lev; |
|
/* fill the standard descriptor */ |
strncpy(lev->l.level_name, EDF_LEVELNAME, MAX_LEVELNAME); |
lev->l.level_code = EDF_LEVEL_CODE; |
lev->l.level_version = EDF_LEVEL_VERSION; |
lev->l.private_insert = EDF_private_insert; |
lev->l.private_extract = EDF_private_extract; |
lev->l.private_dispatch = EDF_private_dispatch; |
lev->l.private_epilogue = EDF_private_epilogue; |
|
lev->l.level_accept_task_model = EDF_level_accept_task_model; |
lev->l.level_accept_guest_model = EDF_level_accept_guest_model; |
lev->l.level_status = EDF_level_status; |
lev->l.level_scheduler = EDF_level_scheduler; |
|
lev->l.public_scheduler = EDF_public_scheduler; |
if (flags & EDF_ENABLE_GUARANTEE) |
lev->l.level_guarantee = EDF_level_guarantee; |
lev->l.public_guarantee = EDF_public_guarantee; |
else |
lev->l.level_guarantee = NULL; |
lev->l.public_guarantee = NULL; |
|
lev->l.task_create = EDF_task_create; |
lev->l.task_detach = EDF_task_detach; |
lev->l.task_eligible = EDF_task_eligible; |
lev->l.task_dispatch = EDF_task_dispatch; |
lev->l.task_epilogue = EDF_task_epilogue; |
lev->l.task_activate = EDF_task_activate; |
lev->l.task_insert = EDF_task_insert; |
lev->l.task_extract = EDF_task_extract; |
lev->l.task_endcycle = EDF_task_endcycle; |
lev->l.task_end = EDF_task_end; |
lev->l.task_sleep = EDF_task_sleep; |
lev->l.public_create = EDF_public_create; |
lev->l.public_detach = EDF_public_detach; |
lev->l.public_end = EDF_public_end; |
lev->l.public_dispatch = EDF_public_dispatch; |
lev->l.public_epilogue = EDF_public_epilogue; |
lev->l.public_activate = EDF_public_activate; |
lev->l.public_unblock = EDF_public_unblock; |
lev->l.public_block = EDF_public_block; |
lev->l.public_message = EDF_public_message; |
|
lev->l.guest_create = EDF_guest_create; |
lev->l.guest_detach = EDF_guest_detach; |
lev->l.guest_dispatch = EDF_guest_dispatch; |
lev->l.guest_epilogue = EDF_guest_epilogue; |
lev->l.guest_activate = EDF_guest_activate; |
lev->l.guest_insert = EDF_guest_insert; |
lev->l.guest_extract = EDF_guest_extract; |
lev->l.guest_endcycle = EDF_guest_endcycle; |
lev->l.guest_end = EDF_guest_end; |
lev->l.guest_sleep = EDF_guest_sleep; |
|
/* fill the EDF descriptor part */ |
for(i=0; i<MAX_PROC; i++) { |
lev->period[i] = 0; |
677,15 → 522,14 |
iq_init(&lev->ready, &freedesc, 0); |
lev->flags = flags & 0x07; |
lev->U = 0; |
|
return l; |
} |
|
bandwidth_t EDF_usedbandwidth(LEVEL l) |
{ |
EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
if (lev->l.level_code == EDF_LEVEL_CODE && |
lev->l.level_version == EDF_LEVEL_VERSION) |
return lev->U; |
else |
return 0; |
|
return lev->U; |
} |
|