Mitigating Priority Inversion in Non-Preemptive Rigid Gang Scheduling Beyond Work-Conserving

Rigid gang scheduling, which enables multiple threads of real-time tasks to execute concurrently on a fixed number of different processors, has recently gained attention. Compared to preemptive rigid gang scheduling, non-preemptive rigid gang (NPRG) scheduling improves predictability by requiring fewer context switches. However, NPRG scheduling is vulnerable to 2D-blocking, where lower-priority tasks can block a higher-priority task multiple times, leading to severe priority inversion at runtime and pessimism in schedulability analysis. The root cause is the work-conserving execution behavior, in which tasks are immediately executed whenever the required processors are idle, regardless of priority and the potential blocking of subsequent tasks. This paper focuses on the global fixed-priority NPRG scheduling and introduces the NPRG-SS scheduler. NPRG-SS leverages a selective stalling (SS) mechanism that selectively stalls lower-priority jobs whenever their execution could delay the start time of a higher-priority job in the ready queue. This non-work-conserving approach inherently mitigates multiple blocking. Additionally, we present the first schedulability analysis for NPRG scheduling with SS and propose a novel heuristic priority assignment technique, Iterative Priority Refinement (IPR). Experimental results show that NPRG-SS with IPR effectively mitigates priority inversion, accepts up to 42% more task sets than the baselines at runtime, while our proposed schedulability test accepts up to 80% more task sets than the baselines in worst-case scenarios.