Real‐time task scheduling with overheads considered

Christian L. Cesar and Peter G. Jessel

Naval Research Logistics (NRL), 1992, vol. 39, issue 2, 247-264

Abstract: n periodic tasks are to be processed by a single machine, where each task i has a maximum request rate or periodicity Fi, a processing time Ei, a deadline Di, relative to each request of task i, a task‐request interrupt overhead Ii, 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.

Date: 1992
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199203)39:23.0.CO;2-S

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:39:y:1992:i:2:p:247-264

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().