Multiprocessor Real-Time Scheduling with Hierarchical Processor Affinities

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