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-01-01
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 | Dimensione | Formato | |
---|---|---|---|
main.pdf
accesso aperto
Tipologia:
Documento in Pre-print/Submitted manuscript
Licenza:
Licenza non conosciuta
Dimensione
406.54 kB
Formato
Adobe PDF
|
406.54 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.