Premium
Real‐time task scheduling with overheads considered
Author(s) -
Cesar Christian L.,
Jessel Peter G.
Publication year - 1992
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199203)39:2<247::aid-nav3220390208>3.0.co;2-s
Subject(s) - computer science , preemption , interrupt , context switch , fixed priority pre emptive scheduling , scheduling (production processes) , distributed computing , parallel computing , schedule , earliest deadline first scheduling , task (project management) , dynamic priority scheduling , overhead (engineering) , counterexample , real time computing , rate monotonic scheduling , embedded system , mathematical optimization , operating system , mathematics , management , discrete mathematics , economics , microcontroller
n periodic tasks are to be processed by a single machine, where each task i has a maximum request rate or periodicity F i , a processing time E i , a deadline D i , relative to each request of task i , a task‐request interrupt overhead I i , and a task‐independent scheduling overhead S . Two scheduling strategies are considered for sequencing the execution of an arbitrary arrangement of task requests in time: the preemptive and the nonpreemptive earliest‐deadline algorithms. Necessary and sufficient conditions are derived for establishing whether a given set of tasks can be scheduled by each scheduling strategy. The conditions are given in the form of limited simulations of a small number of well‐defined task‐request arrangements. If all simulations succeed, the schedule is feasible for the given set of tasks. If any simulation fails, the schedule is infeasible. While interrupt handling and scheduling overheads can be handled by such simulations, context switching overhead resulting from preemption cannot. A counterexample illustrates how the simulations fail to uncover unschedulable task sets when context switching overhead is considered.