Motivated by an apparent contradiction regarding whether certain scheduling policies are sustainable, we revisit the topic of sustainability in real-time scheduling and argue that the existing definitions of sustainability should be further clarified and generalized. After proposing a formal, generic sustainability theory, we relax the existing notion of (strongly) sustainable scheduling policy to provide a new classification called weak sustainability. Proving weak sustainability properties allows reducing the number of variables that must be considered in the search of a worst-case schedule, and hence enables more efficient schedulability analyses and testing regimes even for policies that are not (strongly) sustainable. As a proof of concept, and to better understand a model for which many mistakes were found in the literature, we study weak sustainability in the context of dynamic self-suspending tasks, where we formalize a generic suspension model using the Coq proof assistant and provide a machine-checked proof that any JLFP scheduling policy is weakly sustainable with respect to job costs and variable suspension times.

Motivated by a string of recent errata, the paper argues that mechanized, yet readable schedulability proofs are desirable, feasible to create with current tools and with reasonable effort, and beneficial beyond the increase in confidence. To facilitate such mechanized analyses, PROSA, a new open-source foundation for formally proven schedulability analyses that prioritizes readability, is presented. The approach is demonstrated with a case study that mechanizes multiprocessor response-time analysis, including new variants for parallel jobs and release jitter.

Global real-time schedulers have earned the reputation of scaling poorly due to the high runtime overheads involved in global state management. In this paper, two mature implementations, one using fine-grained locking (SCHED DEADLINE) and one using coarse-grained locking (LITMUSRT's G-EDF plugin), are evaluated and it is shown that, regardless of locking granularity, indeed neither scales well w.r.t. worst-case overheads due to excessive lock contention. To demonstrate that this is not an inherent limitation of global scheduling, the design of G-EDF-MP is presented, a global scheduler that uses message passing to avoid lock contention and cache-line sharing. It is shown to offer up to a 23- to 36-fold reduction in worst-case scheduling overhead on a 64-core platform, which translates into much improved schedulability (in some cases, more than 120 additional tasks can be supported).

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 and Linux-like systems currently offer, without violating the original affinity restrictions? To answer this question, we explore the similarities between priority-based scheduling with processor affinities and the assignment 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.

Contemporary multiprocessor real-time operating systems, such as VxWorks, LynxOS, QNX, and real-time variants of Linux, allow a process to have an arbitrary processor affinity, that is, a process may be pinned to an arbitrary subset of the processors in the system. Placing such a hard constraint on process migrations can help to improve cache performance of specific multi-threaded applications, achieve isolation among components, and aid in load-balancing. However, to date, the lack of schedulability analysis for such systems prevents the use of arbitrary processor affinities in predictable hard real-time applications. In this paper, it is shown that job-level fixed-priority scheduling with arbitrary processor affinities is strictly more general than global, clustered, and partitioned job-level fixed-priority scheduling. The Linux push and pull scheduler is studied as a reference implementation and techniques for the schedulability analysis of hard real-time tasks with arbitrary processor affinity masks are presented. The proposed tests work by reducing the scheduling problem to ``global-like'' sub-problems to which existing global schedulability tests can be applied. Schedulability experiments show the proposed techniques to be effective.