Contention-Free Scheduling for Single Preemption Multiprocessor Platforms

Abstract

The Contention-Free (CF) policy has been extensively researched in the realm of real-time multi-processor scheduling due to its wide applicability and the performance enhancement benefits it provides to existing scheduling algorithms. The CF policy improves the feasibility of executing other real-time tasks by assigning the lowest priority to a task at a moment when it is guaranteed not to miss its deadline during the remaining execution time. Despite its effectiveness, existing studies on the CF policy are largely confined to preemptive scheduling, leaving the efficiency and applicability of limited preemption scheduling unexplored. Limited preemption scheduling permits a job to execute to completion with a limited number of preemptions, setting it apart from preemptive scheduling. This type of scheduling is crucial when preemption or migration overheads are either excessively large or unpredictable. In this paper, we introduce SP-CF, a single preemption scheduling approach that incorporates the CF policy. SP-CF allows a preemption only once during each job’s execution, following a priority demotion under the CF policy. We also propose a new schedulability analysis method for SP-CF to determine whether each task is executed in a timely manner and without missing its deadline. Through simulation experiments, we demonstrate that SP-CF can significantly enhance the schedulability of the traditional rate-monotonic algorithm and the earliest deadline first algorithm.

Keywords

• real-time multi-processor scheduling
• contention-free policy
• limited preemption scheduling