Linux’s Processor Affinity API, Refined: Shifting Real-Time Tasks towards Higher Schedulability

Abstract—Virtually all major real-time operating systems such as QNX, VxWorks, LynxOS, and most real-time variants of Linux, expose processor affinity APIs to restrict task migrations. Initially motivated by throughput and isolation reasons, the ability to flexibly control migrations on a per-task basis has also proved to be useful from a schedulability perspective. However, as the motivation to use processor affinities is highly application-specific, the two interests can conflict, i.e., the fixed, user-specified processor affinities chosen for non-schedulability reasons can actually limit any possible gains in schedulability. This paper specifically addresses the scenario where processor affinities are given as input, and investigates the following question: while maintaining API compatibility (i.e., without changing the interface exposed to the programmer), is it possible to improve schedulability beyond what Linux currently offers, without violating the original affinity restrictions? To answer this question, we explore the similarities between priority-based scheduling with processor affinities and the as-signment problem with seniority and job priority constraints, studied previously by Caron et al. in an operations-research context, to derive a more generic model of migrations. Based on vertex-weighted bipartite matchings, the proposed model exploits the idea of shifting high-priority tasks among processors in their affinity set, in order to accommodate lower-priority tasks that have more constrained processor affinities. The proposed approach is analyzed with a novel shifting-aware schedulability analysis based on linear programming. An empirical evaluation in terms of schedulability shows shifting to be effective, although performance naturally degrades if migration overheads are high. I