Reducing preemptions and migrations in real-time multiprocessor scheduling algorithms by releasing the fairness

Geoffrey Nelissen, Vandy Berten, Joël Goossens, Dragomir Milojevic

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

12 Citations (Scopus)

Abstract

Over the past two decades, numerous optimal scheduling algorithms for real-time systems on multiprocessor platforms have been proposed for the Liu & Layland task model. However, recent studies showed that even if optimal algorithms can theoretically schedule any feasible task set, suboptimal algorithms usually perform better when executed on real computation platforms. This can be explained by the runtime overheads that such optimal algorithms induce. We have observed that all current optimal online multiprocessor real-time scheduling algorithms are (completely or partially) based on the notion of fairness. The respect of this fairness can be the cause of numerous preemptions and migrations. We therefore propose a new algorithm -named U-EDF- which releases the property of fairness and instead use an EDFlike scheduling policy. The simulation results are really encouraging since they show that, in average, U-EDF produces less than one preemption and one migration per job released during the schedule. Furthermore, we strongly believe in the optimality of our algorithm since all tested task sets were correctly scheduled under U-EDF.

Original languageEnglish
Title of host publicationProceedings - 17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2011
Pages15-24
Number of pages10
DOIs
Publication statusPublished - 1 Dec 2011
Externally publishedYes
Event17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2011 - Toyama, Japan
Duration: 28 Aug 201131 Aug 2011

Publication series

NameProceedings - 17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2011
Volume1

Conference

Conference17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2011
CountryJapan
CityToyama
Period28/08/1131/08/11

Fingerprint Dive into the research topics of 'Reducing preemptions and migrations in real-time multiprocessor scheduling algorithms by releasing the fairness'. Together they form a unique fingerprint.

  • Cite this

    Nelissen, G., Berten, V., Goossens, J., & Milojevic, D. (2011). Reducing preemptions and migrations in real-time multiprocessor scheduling algorithms by releasing the fairness. In Proceedings - 17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2011 (pp. 15-24). [6029825] (Proceedings - 17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2011; Vol. 1). https://doi.org/10.1109/RTCSA.2011.57