/*
* 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: edf.c,v 1.15 2004-05-26 15:36:23 anton Exp $
File: $File$
Revision: $Revision: 1.15 $
Last update: $Date: 2004-05-26 15:36:23 $
------------
This file contains the scheduling module EDF (Earliest Deadline First)
Read edf.h for further details.
**/
/*
* 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
* 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 <modules/edf.h>
#include <ll/stdio.h>
#include <ll/string.h>
#include <kernel/model.h>
#include <kernel/descr.h>
#include <kernel/var.h>
#include <kernel/func.h>
#include <tracer.h>
//#define EDF_DEBUG
#define edf_printf kern_printf
#ifdef EDF_DEBUG
char *pnow
() {
static char buf
[40];
struct timespec t
;
sys_gettime
(&t
);
sprintf(buf
, "%ld.%06ld", t.
tv_sec, t.
tv_nsec/1000);
return buf
;
}
char *ptime1
(struct timespec
*t
) {
static char buf
[40];
sprintf(buf
, "%ld.%06ld", t
->tv_sec
, t
->tv_nsec
/1000);
return buf
;
}
char *ptime2
(struct timespec
*t
) {
static char buf
[40];
sprintf(buf
, "%ld.%06ld", t
->tv_sec
, t
->tv_nsec
/1000);
return buf
;
}
#endif
/* statuses used in the level */
#define EDF_READY MODULE_STATUS_BASE /* ready */
#define EDF_IDLE MODULE_STATUS_BASE+1 /* idle, waiting for offset/eop */
#define EDF_WAIT MODULE_STATUS_BASE+2 /* to sleep, waiting for eop */
#define EDF_ZOMBIE MODULE_STATUS_BASE+3 /* zombie, waiting for eop */
/* task flags */
#define EDF_FLAG_SPORADIC 1 /* the task is sporadic */
#define EDF_FLAG_SPOR_LATE 2 /* sporadic task with period overrun */
/* the level redefinition for the Earliest Deadline First level */
typedef struct {
level_des l
; /* standard level descriptor */
IQUEUE ready
; /* the ready queue */
int flags
; /* level flags */
bandwidth_t U
; /* used bandwidth */
int taskflags
[MAX_PROC
]; /* task flags */
TIME period
[MAX_PROC
]; /* task period */
TIME rdeadline
[MAX_PROC
]; /* task relative deadlines */
TIME offset
[MAX_PROC
]; /* task release offsets */
struct timespec release
[MAX_PROC
]; /* release time of the task */
struct timespec adeadline
[MAX_PROC
]; /* latest assigned deadline
(needed to correctly assign deadlines to queued activations) */
int dl_timer
[MAX_PROC
]; /* deadline overrun timer */
int eop_timer
[MAX_PROC
]; /* end of period timer */
int dl_miss
[MAX_PROC
]; /* deadline miss counter */
int wcet_miss
[MAX_PROC
]; /* WCET miss counter */
int nact
[MAX_PROC
]; /* number of pending periodic jobs */
int nskip
[MAX_PROC
]; /* number of skipped sporadic jobs */
} EDF_level_des
;
static void EDF_timer_endperiod
(void *par
);
/* This function is called when a task misses its deadline */
static void EDF_timer_deadline
(void *par
)
{
PID p
= (PID
) par
;
EDF_level_des
*lev
;
lev
= (EDF_level_des
*)level_table
[proc_table
[p
].
task_level];
TRACER_LOGEVENT
(FTrace_EVT_task_deadline_miss
,(unsigned short int)proc_table
[p
].
context,0);
if (lev
->flags
& EDF_ENABLE_DL_EXCEPTION
) {
kern_raise
(XDEADLINE_MISS
,p
);
} else {
lev
->dl_miss
[p
]++;
}
}
/* Release (or queue) task, post deadline and endperiod timers.
The release time is stored in lev->release[p]. */
static void EDF_intern_release
(PID p
, EDF_level_des
*lev
)
{
struct timespec temp
;
/* post deadline timer */
if (lev
->flags
& EDF_ENABLE_DL_CHECK
) {
temp
= lev
->release
[p
];
ADDUSEC2TIMESPEC
(lev
->rdeadline
[p
], &temp
);
lev
->dl_timer
[p
] = kern_event_post
(&temp
,EDF_timer_deadline
,(void *)p
);
}
/* release or queue next job */
if (proc_table
[p
].
status == EDF_IDLE
) {
/* assign deadline, insert task in the ready queue */
proc_table
[p
].
status = EDF_READY
;
*iq_query_timespec
(p
,&lev
->ready
) = lev
->adeadline
[p
];
iq_timespec_insert
(p
,&lev
->ready
);
#ifdef EDF_DEBUG
edf_printf
("At %s: releasing %s with deadline %s\n", pnow
(),
proc_table
[p
].
name, ptime1
(&lev
->adeadline
[p
]));
#endif
/* increase assigned deadline */
ADDUSEC2TIMESPEC
(lev
->period
[p
], &lev
->adeadline
[p
]);
/* reschedule */
event_need_reschedule
();
} else {
/* queue */
lev
->nact
[p
]++;
}
/* increase release time */
ADDUSEC2TIMESPEC
(lev
->period
[p
],&lev
->release
[p
]);
/* post end of period timer */
lev
->eop_timer
[p
] = kern_event_post
(&lev
->release
[p
],
EDF_timer_endperiod
,(void *)p
);
TRACER_LOGEVENT
(FTrace_EVT_task_timer
,(unsigned short int)proc_table
[p
].
context,(unsigned int)proc_table
[p
].
task_level);
}
/* Release after an offset */
static void EDF_timer_offset
(void *par
)
{
PID p
= (PID
) par
;
EDF_level_des
*lev
;
lev
= (EDF_level_des
*)level_table
[proc_table
[p
].
task_level];
EDF_intern_release
(p
, lev
);
}
/* This function is called at the end of the period */
static void EDF_timer_endperiod
(void *par
)
{
PID p
= (PID
) par
;
EDF_level_des
*lev
;
lev
= (EDF_level_des
*)level_table
[proc_table
[p
].
task_level];
lev
->eop_timer
[p
] = -1;
if (proc_table
[p
].
status == EDF_ZOMBIE
) {
/* put the task in the FREE state */
proc_table
[p
].
status = FREE
;
iq_insertfirst
(p
,&freedesc
);
/* free the allocated bandwidth */
lev
->U
-= (MAX_BANDWIDTH
/lev
->rdeadline
[p
]) * proc_table
[p
].
wcet;
return;
}
if (proc_table
[p
].
status == EDF_WAIT
) {
proc_table
[p
].
status = SLEEP
;
return;
}
if (!(lev
->taskflags
[p
] & EDF_FLAG_SPORADIC
)) {
/* if the task is periodic, rerelease it (now or later) */
EDF_intern_release
(p
, lev
);
} else {
/* the sporadic task is still busy. mark it as late */
lev
->taskflags
[p
] |= EDF_FLAG_SPOR_LATE
;
}
}
/* This function is called when a guest task misses its deadline */
static void EDF_timer_guest_deadline
(void *par
)
{
PID p
= (PID
) par
;
TRACER_LOGEVENT
(FTrace_EVT_task_deadline_miss
,(unsigned short int)proc_table
[p
].
context,0);
kern_raise
(XDEADLINE_MISS
,p
);
}
/* The scheduler only gets the first task in the queue */
static PID EDF_public_scheduler
(LEVEL l
)
{
EDF_level_des
*lev
= (EDF_level_des
*)(level_table
[l
]);
return iq_query_first
(&lev
->ready
);
}
/* The on-line guarantee is enabled only if the appropriate flag is set... */
static int EDF_public_guarantee
(LEVEL l
, bandwidth_t
*freebandwidth
)
{
EDF_level_des
*lev
= (EDF_level_des
*)(level_table
[l
]);
if (*freebandwidth
>= lev
->U
) {
*freebandwidth
-= lev
->U
;
return 1;
}
else
return 0;
}
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 (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;
if (h
->drel
> h
->mit
) return -1; /* only D <= T supported */
if (!h
->drel
) {
lev
->rdeadline
[p
] = h
->mit
;
} else {
lev
->rdeadline
[p
] = h
->drel
;
}
/* check the free bandwidth... */
if (lev
->flags
& EDF_ENABLE_GUARANTEE
) {
bandwidth_t b
;
b
= (MAX_BANDWIDTH
/ lev
->rdeadline
[p
]) * h
->wcet
;
/* really update lev->U, checking an overflow... */
if (MAX_BANDWIDTH
- lev
->U
> b
) {
lev
->U
+= b
;
} else {
return -1;
}
}
if (lev
->flags
& EDF_ENABLE_WCET_EXCEPTION
) {
lev
->flags
|= EDF_ENABLE_WCET_CHECK
;
}
if (lev
->flags
& EDF_ENABLE_DL_EXCEPTION
) {
lev
->flags
|= EDF_ENABLE_DL_CHECK
;
}
lev
->period
[p
] = h
->mit
;
if (lev
->rdeadline
[p
] == lev
->period
[p
]) {
/* Ensure that D <= T-eps to make dl_timer trigger before rel_timer */
lev
->rdeadline
[p
] = lev
->period
[p
] - 1;
}
lev
->taskflags
[p
] = 0;
if (h
->periodicity
== APERIODIC
)
lev
->taskflags
[p
] |= EDF_FLAG_SPORADIC
;
lev
->dl_timer
[p
] = -1;
lev
->eop_timer
[p
] = -1;
/* Enable wcet check */
if (lev
->flags
& EDF_ENABLE_WCET_CHECK
) {
proc_table
[p
].
avail_time = h
->wcet
;
proc_table
[p
].
wcet = h
->wcet
;
proc_table
[p
].
control |= CONTROL_CAP
; /* turn on measurement */
}
lev
->offset
[p
] = h
->offset
;
NULL_TIMESPEC
(&lev
->release
[p
]);
return 0; /* OK, also if the task cannot be guaranteed... */
}
static void EDF_public_detach
(LEVEL l
, PID p
)
{
EDF_level_des
*lev
= (EDF_level_des
*)(level_table
[l
]);
if (lev
->flags
& EDF_ENABLE_GUARANTEE
) {
lev
->U
-= (MAX_BANDWIDTH
/ lev
->rdeadline
[p
]) * proc_table
[p
].
wcet;
}
}
static void EDF_public_dispatch
(LEVEL l
, PID p
, int nostop
)
{
EDF_level_des
*lev
= (EDF_level_des
*)(level_table
[l
]);
iq_extract
(p
, &lev
->ready
);
}
static void EDF_public_epilogue
(LEVEL l
, PID p
)
{
EDF_level_des
*lev
= (EDF_level_des
*)(level_table
[l
]);
/* check if the wcet is finished... */
if (lev
->flags
& EDF_ENABLE_WCET_CHECK
) {
if (proc_table
[p
].
avail_time <= 0) {
TRACER_LOGEVENT
(FTrace_EVT_task_wcet_violation
,(unsigned short int)proc_table
[p
].
context,0);
if (lev
->flags
& EDF_ENABLE_WCET_EXCEPTION
) {
kern_raise
(XWCET_VIOLATION
,p
);
} else {
proc_table
[p
].
control &= ~CONTROL_CAP
;
lev
->wcet_miss
[p
]++;
}
}
}
/* the task returns to the ready queue */
iq_timespec_insert
(p
,&lev
->ready
);
proc_table
[p
].
status = EDF_READY
;
}
static void EDF_public_activate
(LEVEL l
, PID p
, struct timespec
*t
)
{
struct timespec clocktime
;
EDF_level_des
*lev
= (EDF_level_des
*)(level_table
[l
]);
kern_gettime
(&clocktime
);
/* check if we are not in the SLEEP state */
if (proc_table
[p
].
status != SLEEP
) {
if (lev
->flags
& EDF_ENABLE_ACT_EXCEPTION
) {
/* too frequent or wrongful activation: raise exception */
kern_raise
(XACTIVATION
,p
);
} else {
/* skip the sporadic job, but increase a counter */
#ifdef EDF_DEBUG
edf_printf
("At %s: activation of %s skipped\n", pnow
(), proc_table
[p
].
name);
#endif
lev
->nskip
[p
]++;
}
return;
}
/* set the release time to the activation time + offset */
lev
->release
[p
] = *t
;
ADDUSEC2TIMESPEC
(lev
->offset
[p
], &lev
->release
[p
]);
/* set the absolute deadline to the activation time + offset + rdeadline */
lev
->adeadline
[p
] = lev
->release
[p
];
ADDUSEC2TIMESPEC
(lev
->rdeadline
[p
], &lev
->adeadline
[p
]);
/* Check if release > clocktime. If so, release it later,
otherwise release it now. */
proc_table
[p
].
status = EDF_IDLE
;
if (TIMESPEC_A_GT_B
(&lev
->release
[p
], &clocktime
)) {
/* release later */
kern_event_post
(&lev
->release
[p
],EDF_timer_offset
,(void *)p
);
} else {
/* release now */
EDF_intern_release
(p
, lev
);
}
}
static void EDF_public_unblock
(LEVEL l
, PID p
)
{
EDF_level_des
*lev
= (EDF_level_des
*)(level_table
[l
]);
/* Insert task in the correct position */
proc_table
[p
].
status = EDF_READY
;
iq_timespec_insert
(p
,&lev
->ready
);
}
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.
. the capacity event have to be removed by the generic kernel
. the wcet don't need modification...
. the state of the task is set by the calling function
. the deadline must remain...
So, we do nothing!!!
*/
}
static int EDF_public_message
(LEVEL l
, PID p
, void *m
)
{
EDF_level_des
*lev
= (EDF_level_des
*)(level_table
[l
]);
switch((long)(m
)) {
/* task_endcycle() */
case 0:
/* if there are no pending jobs */
if (lev
->nact
[p
] == 0) {
/* remove deadline timer, if any */
if (lev
->dl_timer
[p
] != -1) {
kern_event_delete
(lev
->dl_timer
[p
]);
lev
->dl_timer
[p
] = -1;
}
if (lev
->taskflags
[p
] & EDF_FLAG_SPORADIC
) {
/* sporadic task */
if (!(lev
->taskflags
[p
] & EDF_FLAG_SPOR_LATE
)) {
proc_table
[p
].
status = EDF_WAIT
;
} else {
/* it's late, move it directly to SLEEP */
proc_table
[p
].
status = SLEEP
;
lev
->taskflags
[p
] &= ~EDF_FLAG_SPOR_LATE
;
}
} else {
/* periodic task */
proc_table
[p
].
status = EDF_IDLE
;
}
} else {
/* we are late / there are pending jobs */
lev
->nact
[p
]--;
/* compute and assign absolute deadline */
*iq_query_timespec
(p
,&lev
->ready
) = lev
->adeadline
[p
];
iq_timespec_insert
(p
,&lev
->ready
);
/* increase assigned deadline */
ADDUSEC2TIMESPEC
(lev
->period
[p
], &lev
->adeadline
[p
]);
#ifdef EDF_DEBUG
edf_printf
("(Late) At %s: releasing %s with deadline %s\n",
pnow
(),proc_table
[p
].
name,ptime1
(&lev
->adeadline
[p
]));
#endif
}
break;
/* task_sleep() */
case 1:
/* remove deadline timer, if any */
if (lev
->dl_timer
[p
] != -1) {
kern_event_delete
(lev
->dl_timer
[p
]);
lev
->dl_timer
[p
] = -1;
}
if (lev
->taskflags
[p
] & EDF_FLAG_SPORADIC
) {
/* sporadic task */
if (!(lev
->taskflags
[p
] & EDF_FLAG_SPOR_LATE
)) {
proc_table
[p
].
status = EDF_WAIT
;
} else {
/* it's late, move it directly to SLEEP */
proc_table
[p
].
status = SLEEP
;
lev
->taskflags
[p
] &= ~EDF_FLAG_SPOR_LATE
;
}
} else {
/* periodic task */
if (!(lev
->nact
[p
] > 0)) {
/* we are on time. go to the EDF_WAIT state */
proc_table
[p
].
status = EDF_WAIT
;
} else {
/* we are late. delete pending activations and go to SLEEP */
lev
->nact
[p
] = 0;
proc_table
[p
].
status = SLEEP
;
/* remove end of period timer */
if (lev
->eop_timer
[p
] != -1) {
kern_event_delete
(lev
->eop_timer
[p
]);
lev
->eop_timer
[p
] = -1;
}
}
}
break;
}
if (lev
->flags
& EDF_ENABLE_WCET_CHECK
) {
proc_table
[p
].
control |= CONTROL_CAP
;
}
jet_update_endcycle
(); /* Update the Jet data... */
proc_table
[p
].
avail_time = proc_table
[p
].
wcet;
TRACER_LOGEVENT
(FTrace_EVT_task_end_cycle
,(unsigned short int)proc_table
[p
].
context,(unsigned int)l
);
return 0;
}
static void EDF_public_end
(LEVEL l
, PID p
)
{
EDF_level_des
*lev
= (EDF_level_des
*)(level_table
[l
]);
if (!(lev
->taskflags
[p
] & EDF_FLAG_SPOR_LATE
)) {
/* remove the deadline timer (if any) */
if (lev
->dl_timer
[p
] != -1) {
kern_event_delete
(lev
->dl_timer
[p
]);
lev
->dl_timer
[p
] = -1;
}
proc_table
[p
].
status = EDF_ZOMBIE
;
} else {
/* no endperiod timer will be fired, free the task now! */
proc_table
[p
].
status = FREE
;
iq_insertfirst
(p
,&freedesc
);
/* free the allocated bandwidth */
lev
->U
-= (MAX_BANDWIDTH
/lev
->rdeadline
[p
]) * proc_table
[p
].
wcet;
}
}
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
;
if (m
->pclass
!= JOB_PCLASS
|| (m
->level
!= 0 && m
->level
!= l
) ) {
kern_raise
(XINVALID_TASK
, p
);
return;
}
job
= (JOB_TASK_MODEL
*)m
;
/* 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
->dl_timer
[p
] = -1;
lev
->period
[p
] = job
->period
;
if (!job
->noraiseexc
) {
lev
->dl_timer
[p
] = kern_event_post
(iq_query_timespec
(p
, &lev
->ready
),
EDF_timer_guest_deadline
,(void *)p
);
}
}
static void EDF_private_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()
we extract the task from the ready queue
NB: we can't assume that p is the first task in the queue!!! */
iq_extract
(p
, &lev
->ready
);
}
static void EDF_private_epilogue
(LEVEL l
, PID p
)
{
EDF_level_des
*lev
= (EDF_level_des
*)(level_table
[l
]);
/* the task has been preempted. it returns into the ready queue... */
iq_timespec_insert
(p
,&lev
->ready
);
proc_table
[p
].
status = EDF_READY
;
}
static void EDF_private_extract
(LEVEL l
, PID p
)
{
EDF_level_des
*lev
= (EDF_level_des
*)(level_table
[l
]);
if (proc_table
[p
].
status == EDF_READY
)
iq_extract
(p
, &lev
->ready
);
/* we remove the deadline timer, because the slice is finished */
if (lev
->dl_timer
[p
] != -1) {
kern_event_delete
(lev
->dl_timer
[p
]);
lev
->dl_timer
[p
] = -1;
}
}
/* Registration function:
int flags the init flags ... see edf.h */
LEVEL EDF_register_level
(int flags
)
{
LEVEL l
; /* the level that we register */
EDF_level_des
*lev
; /* for readableness only */
PID i
; /* a counter */
printk
("EDF_register_level\n");
/* request an entry in the level_table */
l
= level_alloc_descriptor
(sizeof(EDF_level_des
));
lev
= (EDF_level_des
*)level_table
[l
];
/* fill the standard descriptor */
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.
public_scheduler = EDF_public_scheduler
;
if (flags
& EDF_ENABLE_GUARANTEE
)
lev
->l.
public_guarantee = EDF_public_guarantee
;
else
lev
->l.
public_guarantee = NULL
;
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
;
/* fill the EDF descriptor part */
for(i
=0; i
<MAX_PROC
; i
++) {
lev
->period
[i
] = 0;
lev
->dl_timer
[i
] = -1;
lev
->eop_timer
[i
] = -1;
lev
->taskflags
[i
] = 0;
lev
->dl_miss
[i
] = 0;
lev
->wcet_miss
[i
] = 0;
lev
->nact
[i
] = 0;
lev
->nskip
[i
] = 0;
}
iq_init
(&lev
->ready
, &freedesc
, 0);
lev
->flags
= flags
;
lev
->U
= 0;
return l
;
}
bandwidth_t EDF_usedbandwidth
(LEVEL l
)
{
EDF_level_des
*lev
= (EDF_level_des
*)(level_table
[l
]);
return lev
->U
;
}
int EDF_get_nact
(PID p
)
{
LEVEL l
= proc_table
[p
].
task_level;
EDF_level_des
*lev
= (EDF_level_des
*)(level_table
[l
]);
return lev
->nact
[p
];
}
int EDF_get_dl_miss
(PID p
)
{
LEVEL l
= proc_table
[p
].
task_level;
EDF_level_des
*lev
= (EDF_level_des
*)(level_table
[l
]);
return lev
->dl_miss
[p
];
}
int EDF_get_wcet_miss
(PID p
)
{
LEVEL l
= proc_table
[p
].
task_level;
EDF_level_des
*lev
= (EDF_level_des
*)(level_table
[l
]);
return lev
->wcet_miss
[p
];
}
int EDF_get_nskip
(PID p
)
{
LEVEL l
= proc_table
[p
].
task_level;
EDF_level_des
*lev
= (EDF_level_des
*)(level_table
[l
]);
return lev
->nskip
[p
];
}