Multi-level contention-free policy for real-time multiprocessor scheduling

The contention-free policy has received attention in real-time multiprocessor scheduling owing to its wide applicability and significant improvement in offline schedulability guarantees. Utilizing the notion of contention-free slots in which the number of active jobs is smaller than or equal to the number of processors, the policy improves the schedulability by offloading executions in contending time slots to contention-free ones. In this paper, we propose the multi-level contention-free policy by exploiting a new, generalized notion of multi-level contention-free slots. In a case study, we present how the multi-level contention-free policy is applied to EDF (Earliest Deadline First) scheduling and develop a schedulability test for EDF that adopts the new policy. Our evaluation results demonstrate that the multi-level contention-free policy significantly improves the schedulability by up to 4188% and 127%, compared to vanilla EDF and EDF adopting the existing contention-free policy, respectively.