Multiprocessor Real-Time Scheduling with Hierarchical Processor Affinities - Archive ouverte HAL Access content directly
Conference Papers Year : 2016

Multiprocessor Real-Time Scheduling with Hierarchical Processor Affinities

(1) , (2) , (3) , (4, 5)


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.
Fichier principal
Vignette du fichier
bonifaci2016.pdf (368.61 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01397807 , version 1 (16-11-2016)



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⟩


119 View
201 Download



Gmail Facebook Twitter LinkedIn More