A Note on the Suboptimality of Nonpreemptive Real-time Scheduling

Fathi Abugchem, Michael Short, Donglai Xu

Research output: Contribution to journalArticlepeer-review

209 Downloads (Pure)


In this paper, processor speedup analysis is used to strengthen recent results regarding the sub-optimality of uniprocessor non-preemptive Earliest Deadline First (npEDF) scheduling. The sub-optimality of npEDF is defined as the minimum amount of increase in the processor speed that is needed to guarantee the npEDF schedulability of any feasible task set. We show that any preemptively schedulable task set that is not schedulable by npEDF will become schedulable on a processor speeded up by a factor of not more than one plus the value of the largest execution requirement divided by the shortest relative deadline of any task. This reduces the pessimism compared to the best previous bound by factor of at least two. In addition, for the case of non-preemptive Fixed Priority scheduling, we also show that twice this speedup bound is enough to guarantee the schedulability of any feasible task set.
Original languageEnglish
Pages (from-to)69-72
JournalIEEE Embedded Systems Letters
Issue number3
Publication statusPublished - 27 Apr 2015


Dive into the research topics of 'A Note on the Suboptimality of Nonpreemptive Real-time Scheduling'. Together they form a unique fingerprint.

Cite this