Asymptotically Optimal Multiprocessor Real-Time Locking for non-JLFP Scheduling

In prior work, a number of asymptotically optimal suspension-based real-time locking protocols have been presented for job-level fixed priority (JLFP) schedulers, where job priorities do not change. However, the optimality proofs for these locking protocols break down under non-JLFP scheduling, where job priorities can vary. In fact, the problem of designing an asymptotically optimal real-time locking protocol for general non-JLFP scheduling has remained open. This paper closes this problem by presenting the non-JLFP locking protocol (NJLP), the first asymptotically optimal suspension-based real-time locking protocol for non-JLFP schedulers.