Dynamic Dispatching of Cyclic Real-Time Tasks with Relative Constraints

dc.contributor.authorChoi, Seonhoen_US
dc.contributor.authorAgrawala, Ashok K.en_US
dc.description.abstractIn 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-300en_US
dc.format.extent701631 bytes
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3770en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-97-300en_US
dc.titleDynamic Dispatching of Cyclic Real-Time Tasks with Relative Constraintsen_US
dc.typeTechnical Reporten_US


Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
685.19 KB
Postscript Files
Thumbnail Image
380.28 KB
Adobe Portable Document Format
Auto-generated copy of CS-TR-3770.ps