Exact speedup factors and sub-optimality for non-preemptive scheduling |
| |
Authors: | Robert I. Davis,Abhilash Thekkilakattil,Oliver Gettings,Radu Dobrin,Sasikumar Punnekkat,Jian-Jia Chen author-information" > |
| |
Affiliation: | 1.Department of Computer Science,University of York,York,UK;2.AtlasCopco Industrial Tools and Solutions,Nacka,Sweden;3.M?lardalen Real-Time Research Center,M?lardalen University,V?ster?s,Sweden;4.Technische Universit?t Dortmund,Dortmund,Germany |
| |
Abstract: | Fixed priority scheduling is used in many real-time systems; however, both preemptive and non-preemptive variants (FP-P and FP-NP) are known to be sub-optimal when compared to an optimal uniprocessor scheduling algorithm such as preemptive earliest deadline first (EDF-P). In this paper, we investigate the sub-optimality of fixed priority non-preemptive scheduling. Specifically, we derive the exact processor speed-up factor required to guarantee the feasibility under FP-NP (i.e. schedulability assuming an optimal priority assignment) of any task set that is feasible under EDF-P. As a consequence of this work, we also derive a lower bound on the sub-optimality of non-preemptive EDF (EDF-NP). As this lower bound matches a recently published upper bound for the same quantity, it closes the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive fixed priority scheduling dominates the other, in other words, there are task sets that are feasible on a processor of unit speed under FP-P that are not feasible under FP-NP and vice-versa. Hence comparing these two algorithms, there are non-trivial speedup factors in both directions. We derive the exact speed-up factor required to guarantee the FP-NP feasibility of any FP-P feasible task set. Further, we derive the exact speed-up factor required to guarantee FP-P feasibility of any constrained-deadline FP-NP feasible task set. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|