## 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.

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.

Original language | English |
---|---|

Title of host publication | Real-Time Systems Symposium (RTSS) |

Publication status | Accepted/In press - Dec 2015 |

## Keywords

- EDF
- fixed priority
- uniprocessor
- resource augmentation
- real-time
- speedup factor
- sub-optimality
- non-preemptive scheduling
- preemptive scheduling