Towards Practical Multiprocessor EDF with Affinities

A gap exists between the theory of EDF scheduling on identical multiprocessors with arbitrary processor affinities (APA) and practical EDF scheduling as embodied by the SCHED_DEADLINE (SD) scheduler in Linux. This is because the EDF variant proposed in theory for APA, called Strong APA EDF, introduces affinity-related complexities that are not applicable under global EDF, the original target of SD. SD instead treats affinities as a secondary concern. It is shown herein that this treatment comes at the price of causing SD to be fundamentally broken with regard to soft real-time (SRT)-optimality with APA. This result resolves a longstanding open question regarding this matter. It also suggests that Strong APA EDF, which has been proven to be SRT-optimal, is necessary for practical EDF scheduling with APA. However, non-preemptive sections are typically required in practice, and prior work on Strong APA EDF is limited to fully preemptive systems. In this paper, this prior work is extended for the first time to deal with non-preemptivity, which introduces non-trivial nuances with APA. As a byproduct of considering non-preemptivity, it is shown that the SRT-optimality of EDF in this context carries over to a significantly expanded class of schedulers.