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.

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

Biondi, Alessandro;
2018

Abstract

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.
File in questo prodotto:
File Dimensione Formato  
main.pdf

accesso aperto

Licenza: Licenza non conosciuta
406.54 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11382/521569
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
social impact