Quantifying the Exact SubOptimality of NonPreemptive Scheduling
Rob Davis  RTS York Summer 2016 Talks
Fixed priority scheduling is used in many realtime systems; however, both preemptive and nonpreemptive variants (FPP and FPNP) are known to be suboptimal when compared to an optimal uniprocessor scheduling algorithm such as preemptive Earliest Deadline First (EDFP). In this paper, we investigate the suboptimality of fixed priority nonpreemptive scheduling. Specifically, we derive the exact processor speedup factor required to guarantee the feasibility under FPNP (i.e. schedulablability assuming an optimal priority assignment) of any task set that is feasible under EDFP. As a consequence of this work, we also derive a lower bound on the suboptimality of nonpreemptive EDF (EDFNP), which since it matches a recently published upper bound gives the exact suboptimality for EDFNP.
It is known that neither preemptive, nor nonpreemptive fixed priority scheduling dominates the other, i.e., there are task sets that are feasible on a processor of unit speed under FPP that are not feasible under FPNP and viceversa. Hence comparing these two algorithms, there are nontrivial speedup factors in both directions. We derive the exact speedup factor required to guarantee the FPNP feasibility of any FPP feasible task set. Further, we derive upper and lower bounds on the speedup factor required to guarantee FPP feasibility of any FPNP feasible task set. Empirical evidence suggests that the lower bound may be tight, and hence equate to the exact speedup factor in this case.
Details
Date and Time  20160425 12:30 

Place  CSE/082 
Slides 
Slides Not Available

Paper 
Paper Not Available
