On the ineffectiveness of 1/m-based interference bounds in the analysis of global EDF and FIFO scheduling

Alessandro Biondi, Youcheng Sun

Research output: Contribution to journalArticlepeer-review


Enormous efforts have been spent in the derivation of sufficient schedulability tests for popular global schedulers such as global fixed-priority (G-FP) and global earliest-deadline first (G-EDF). Among all the proposals, response-time analysis techniques are established as the most popular ones and have been widely adopted by several authors in subsequent researches. Such tests are based on interference bounds that have been derived by exploiting the work-conserving property of such schedulers, and are typically expressed with a 1 / m multiplier in the interference equation (with m being the number of available processors). This paper shows that the popular response-time analysis for G-EDF is ineffective with respect to partitioned EDF (P-EDF) scheduling. That is, it is proven that every task set that is deemed schedulable by such an analysis is also schedulable under P-EDF by adopting a trivial partitioning algorithm. Furthermore, an analogous result is proven for global first-in first-out (G-FIFO) scheduling when analyzed with a 1 / m-based interference bound. Finally, experimental results are presented to compare sufficient tests for G-EDF and G-FIFO with the corresponding partitioned schemes under a vast collection of partitioning heuristics. The results show that the considered tests for global scheduling are always outperformed by those for partitioned scheduling exhibiting a significant performance gap.

Original languageEnglish
Pages (from-to)515-536
Number of pages22
JournalReal-Time Systems
Issue number3
Publication statusPublished - 1 Jul 2018


Dive into the research topics of 'On the ineffectiveness of 1/m-based interference bounds in the analysis of global EDF and FIFO scheduling'. Together they form a unique fingerprint.

Cite this