Name
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. schedulablability 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), which since it matches a recently published upper bound gives the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive fixed priority scheduling dominates the other, i.e., 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 upper and lower bounds on the speed-up factor required to guarantee FP-P feasibility of any FP-NP feasible task set. Empirical evidence suggests that the lower bound may be tight, and hence equate to the exact speed-up factor in this case. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/RTSS.2015.17 | Real-Time Systems Symposium |
Keywords | Field | DocType |
real-time, uniprocessor, resource augmentation, speedup factor, sub-optimality, non-preemptive scheduling, preemptive scheduling, EDF, fixed priority | Fixed-priority pre-emptive scheduling,Uniprocessor system,Upper and lower bounds,Computer science,Scheduling (computing),Deadline-monotonic scheduling,Real-time computing,Rate-monotonic scheduling,Dynamic priority scheduling,Earliest deadline first scheduling,Distributed computing | Conference |
ISSN | ISBN | Citations |
1052-8725 | 978-1-4673-9507-6 | 5 |
PageRank | References | Authors |
0.39 | 27 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert I. Davis | 1 | 1824 | 93.74 |
| abhilash thekkilakattil | 2 | 43 | 6.07 |
| Oliver Gettings | 3 | 23 | 1.68 |
| Radu Dobrin | 4 | 169 | 22.41 |
| Sasikumar Punnekkat | 5 | 414 | 50.49 |