Skip to Main content Skip to Navigation
Conference papers

Multiprocessor Real-Time Scheduling with Hierarchical Processor Affinities

Abstract : Many multiprocessor real-time operating systems offer the possibility to restrict the migrations of any task to a specified subset of processors by setting affinity masks. A notion of " strong arbitrary processor affinity scheduling " (strong APA scheduling) has been proposed; this notion avoids schedulability losses due to overly simple implementations of processor affinities. Due to potential overheads, strong APA has not been implemented so far in a real-time operating system. We show that, in the special but highly relevant case of hierarchical processor affinities (HPA), strong APA scheduling can be implemented with a vastly improved runtime complexity. In particular, we present a strong HPA scheduler with a runtime complexity of O(m) per task arrival and O(log n+m 2) per task departure, where m is the number of processors and n is the number of tasks, thus improving on the previous bounds of O(m 2) and O(mn). The improved runtime algorithms allowed us to implement support for strong hierarchical processor affinities in LITMUS RT. We benchmarked this implementation on a 24-core platform and observed non-negligible, but still viable runtime overheads. Additionally, in the case of a bilevel affinity hierarchy and when job priorities are based on deadlines, we argue that the performance of our strong HPA scheduler, HPA-EDF, can be related to system optimality in the following way: any collection of jobs that is schedulable (under any policy) on m unit-speed processors subject to hierarchical affinity constraints is correctly scheduled by HPA-EDF on m processors of speed 2.415.
Document type :
Conference papers
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download
Contributor : Marie-France Sagot Connect in order to contact the contributor
Submitted on : Wednesday, November 16, 2016 - 12:27:07 PM
Last modification on : Wednesday, November 3, 2021 - 2:21:10 PM
Long-term archiving on: : Thursday, March 16, 2017 - 5:03:52 PM


Files produced by the author(s)




Vincenzo Bonifaci, Björn Brandenburg, Gianlorenzo d'Angelo, Alberto Marchetti-Spaccamela. Multiprocessor Real-Time Scheduling with Hierarchical Processor Affinities. 28th Euromicro Conference on Real-Time Systems, ECRTS 2016, Jul 2016, Toulouse, France. pp.237-247, ⟨10.1109/ECRTS.2016.24⟩. ⟨hal-01397807⟩



Record views


Files downloads