Dynamic Dispatching of Cyclic Real-Time Tasks with Relative Constraints
Dynamic Dispatching of Cyclic Real-Time Tasks with Relative Constraints
Files
Publication or External Link
Date
1998-10-15
Authors
Choi, Seonho
Agrawala, Ashok K.
Advisor
Citation
DRUM DOI
Abstract
In some hard real-time systems, relative timing constraints may be imposed
on task executions, in addition to the release time and deadline
constraints. A periodic task may have jitter constraints between the
start or finish times of any two consecutive executions. Relative
constraints such as separation or relative deadline constraints may be
given between start or finish times of tasks (4).
One approach is to find a total order on a set of n jobs in a scheduling
window, and cyclically use this order at run time to execute the jobs.
However, in the presence of the relative constraints, if the job execution
times are nondeterminiistic with defined lower and upper bound, it is not
always possible to statically assign start times at pre-runtime without
sacrificing the schedulability(4).
We develop a technique called dynamic cyclic dispatching to enforce
relative constraints along with release time and deadline constraints. An
ordered set of N jobs is assumed to be given within a scheduling window
and this schedule (ordering) is cyclically repeated at runtime. An
off-line algorithm is presented to check the schedulability of the job
set and to obtain parametric lower and upper bounds on the start times of
jobs, if the job set is schedulable. Then, these parametric bounds are
evaluated at runtime to obtain a valid time intervals during which jobs
can be started. The complexity of this off-line component is shown to be
O(n2N3) where n is the number of jobs in a scheduling window that have
relative constraints with jobs in the next scheduling window. An online
algorithm can evaluate these bounds in O(N3+n5) computation time.
Unlike static approached which assign fixed start times to jobs in the
scheduling window, our approach not only allows us to flexibly manage the
slack times with the schedulability of a task set not affected, but also
yields a guaranteed schedulability in the sense that, if other dispatching
mechanism can schedule the job sequences satisfying all given constraints,
then our mechanism can also schedule them.
(Also cross-referenced as UMIACS-TR-97-300