Parametric dispatching of hard real-time tasks
Richard A. Gerber, William White Tison Pugh, Manas C. Saksena · IEEE Transactions on Computers · 1995
In many real-time systems relative timing constraints are imposed on a set of tasks. Generating a correct ordering for the tasks and deriving their proper start-time assignments is an NP-hard problem; it subsumes the non-preemptive scheduling problem. Even when the application imposes a total order on the tasks, generating proper start-times is still nontrivial if execution times may range between upper and lower bounds. We present the technique of parametric dispatching to enforce such timing constraints. During an off-line component, we check if the constraints can be guaranteed. If so, a calendar is produced that allows our on-line algorithm to generate upper and lower bounds on the start time of each task, based on the start times and execution times of previous tasks. A suitable start time for the task may then be selected taking into account the presence of other non-critical tasks in the system.>