Quantifying the Exact Sub-Optimality of Non-Preemptive Scheduling

Robert Ian Davis; Abhilash Thekkilakattil; Oliver Gettings; Radu Dobrin; Sasikumar Punnekkat

Quantifying the Exact Sub-Optimality of Non-Preemptive Scheduling

Robert Ian Davis, Abhilash Thekkilakattil, Oliver Gettings, Radu Dobrin, Sasikumar Punnekkat

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

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

Access to Document

Cite this

@inproceedings{ca3823c6cb2840c9b11d8c9c2a205da0,

title = "Quantifying the Exact Sub-Optimality of Non-Preemptive Scheduling",

abstract = "Fixed priority scheduling is used in many real-timesystems; however, both preemptive and non-preemptivevariants (FP-P and FP-NP) are known to be sub-optimal whencompared to an optimal uniprocessor scheduling algorithmsuch as preemptive Earliest Deadline First (EDF-P). In thispaper, we investigate the sub-optimality of fixed prioritynon-preemptive scheduling. Specifically, we derive the exactprocessor speed-up factor required to guarantee the feasibilityunder FP-NP (i.e. schedulablability assuming an optimalpriority assignment) of any task set that is feasible underEDF-P. As a consequence of this work, we also derive a lowerbound on the sub-optimality of non-preemptive EDF (EDF-NP),which since it matches a recently published upper bound givesthe exact sub-optimality for EDF-NP.It is known that neither preemptive, nor non-preemptivefixed priority scheduling dominates the other, i.e., there aretask sets that are feasible on a processor of unit speed underFP-P that are not feasible under FP-NP and vice-versa. Hencecomparing these two algorithms, there are non-trivial speedupfactors in both directions. We derive the exact speed-up factorrequired to guarantee the FP-NP feasibility of any FP-Pfeasible task set. Further, we derive upper and lower bounds onthe speed-up factor required to guarantee FP-P feasibility ofany FP-NP feasible task set. Empirical evidence suggests thatthe lower bound may be tight, and hence equate to the exactspeed-up factor in this case.",

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

author = "Davis, {Robert Ian} and Abhilash Thekkilakattil and Oliver Gettings and Radu Dobrin and Sasikumar Punnekkat",

year = "2015",

month = dec,

language = "English",

booktitle = "Real-Time Systems Symposium (RTSS)",

}

TY - GEN

T1 - Quantifying the Exact Sub-Optimality of Non-Preemptive Scheduling

AU - Davis, Robert Ian

AU - Thekkilakattil, Abhilash

AU - Gettings, Oliver

AU - Dobrin, Radu

AU - Punnekkat, Sasikumar

PY - 2015/12

Y1 - 2015/12

N2 - Fixed priority scheduling is used in many real-timesystems; however, both preemptive and non-preemptivevariants (FP-P and FP-NP) are known to be sub-optimal whencompared to an optimal uniprocessor scheduling algorithmsuch as preemptive Earliest Deadline First (EDF-P). In thispaper, we investigate the sub-optimality of fixed prioritynon-preemptive scheduling. Specifically, we derive the exactprocessor speed-up factor required to guarantee the feasibilityunder FP-NP (i.e. schedulablability assuming an optimalpriority assignment) of any task set that is feasible underEDF-P. As a consequence of this work, we also derive a lowerbound on the sub-optimality of non-preemptive EDF (EDF-NP),which since it matches a recently published upper bound givesthe exact sub-optimality for EDF-NP.It is known that neither preemptive, nor non-preemptivefixed priority scheduling dominates the other, i.e., there aretask sets that are feasible on a processor of unit speed underFP-P that are not feasible under FP-NP and vice-versa. Hencecomparing these two algorithms, there are non-trivial speedupfactors in both directions. We derive the exact speed-up factorrequired to guarantee the FP-NP feasibility of any FP-Pfeasible task set. Further, we derive upper and lower bounds onthe speed-up factor required to guarantee FP-P feasibility ofany FP-NP feasible task set. Empirical evidence suggests thatthe lower bound may be tight, and hence equate to the exactspeed-up factor in this case.

AB - Fixed priority scheduling is used in many real-timesystems; however, both preemptive and non-preemptivevariants (FP-P and FP-NP) are known to be sub-optimal whencompared to an optimal uniprocessor scheduling algorithmsuch as preemptive Earliest Deadline First (EDF-P). In thispaper, we investigate the sub-optimality of fixed prioritynon-preemptive scheduling. Specifically, we derive the exactprocessor speed-up factor required to guarantee the feasibilityunder FP-NP (i.e. schedulablability assuming an optimalpriority assignment) of any task set that is feasible underEDF-P. As a consequence of this work, we also derive a lowerbound on the sub-optimality of non-preemptive EDF (EDF-NP),which since it matches a recently published upper bound givesthe exact sub-optimality for EDF-NP.It is known that neither preemptive, nor non-preemptivefixed priority scheduling dominates the other, i.e., there aretask sets that are feasible on a processor of unit speed underFP-P that are not feasible under FP-NP and vice-versa. Hencecomparing these two algorithms, there are non-trivial speedupfactors in both directions. We derive the exact speed-up factorrequired to guarantee the FP-NP feasibility of any FP-Pfeasible task set. Further, we derive upper and lower bounds onthe speed-up factor required to guarantee FP-P feasibility ofany FP-NP feasible task set. Empirical evidence suggests thatthe lower bound may be tight, and hence equate to the exactspeed-up factor in this case.

KW - EDF

KW - fixed priority

KW - uniprocessor

KW - resource augmentation

KW - real-time

KW - speedup factor

KW - sub-optimality

KW - non-preemptive scheduling

KW - preemptive scheduling

M3 - Conference contribution

BT - Real-Time Systems Symposium (RTSS)

ER -