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.
Type de document :
Communication dans un congrès
28th Euromicro Conference on Real-Time Systems, ECRTS 2016, Jul 2016, Toulouse, France. pp.237-247, 2016, IEEE Computer Society. 〈10.1109/ECRTS.2016.24〉
Liste complète des métadonnées

Littérature citée [32 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01397807
Contributeur : Marie-France Sagot <>
Soumis le : mercredi 16 novembre 2016 - 12:27:07
Dernière modification le : mardi 21 août 2018 - 01:13:33
Document(s) archivé(s) le : jeudi 16 mars 2017 - 17:03:52

Fichier

bonifaci2016.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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, 2016, IEEE Computer Society. 〈10.1109/ECRTS.2016.24〉. 〈hal-01397807〉

Partager

Métriques

Consultations de la notice

123

Téléchargements de fichiers

108