Multiprocessor Real-Time Scheduling with Hierarchical Processor Affinities
Authors:
- Vincenzo BonifaciVBVincenzo Bonifaci
- Gianlorenzo D'AngeloGDGianlorenzo D'Angelo
- 1 September 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 237-247
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+m2) per task departure, where mis the number of processors and n is the number of tasks, thus improving on the previous bounds of O(m2) and O(mn). The improved runtime algorithms allowed us to implement support for strong hierarchical processor affinities in LITMUSRT. We benchmarked this implementation on a 24-core platform and observed nonnegligible, 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.Keywords
This publication has 21 references indexed in Scilit:
- Linux's Processor Affinity API, Refined: Shifting Real-Time Tasks Towards Higher Schedulability2014
- Scaling global scheduling with message passing2014
- A semi-partitioned approach for parallel real-time scheduling2012
- Strict fibonacci heaps2012
- A survey of hard real-time scheduling for multiprocessor systemsACM Computing Surveys, 2011
- Partitioned EDF scheduling for multiprocessors using a C=D task splitting schemeReal-Time Systems, 2011
- A Hybrid Real-Time Scheduling Approach for Large-Scale Multicore Platforms2007
- Optimal Time-Critical Scheduling via Resource AugmentationAlgorithmica, 2002
- The effectiveness of affinity-based scheduling in multiprocessor network protocol processing (extended version)IEEE/ACM Transactions on Networking, 1996
- Using processor affinity in loop scheduling on shared-memory multiprocessorsIEEE Transactions on Parallel and Distributed Systems, 1994