Multiprocessor Hard Real-Time Systems Preemption Threshold Scheduling

The preemption plays a critical role in hard real-time systems. Preemptions are able to increase the schedulability of system. However, in multiprocessor platform, the large amount of preemptions may cause significant run-time cost due to context switch, running scheduler, job migration, etc. Besides quite amount of these preemptions are unnecessary regarding to schedulability. Limited preemption scheduling is the hybrid method between preemptive and non-preemptive scheduling, which can reduce unnecessary preemptions. In this paper, we extend the preemption threshold scheduling (PTS), one of the major methods of limited preemption scheduling, to multiprocessor hard real-time systems, which is firstly proposed for uniprocessor. The main focus of this paper is reducing preemptions. Based on DA-LC test, we derive the schedulability test for PTS. An efficient priority assignment algorithm OPA-MLL is proposed which is optimized for PTS from the combination of OPA and DA-LC. We also establish the threshold assignment algorithm aiming at reducing preemptions. The simulation result shows the PTS can reduce preemptions significantly for multiple priority assignment algorithms. At the meantime OPA-MLL has the largest percentage of schedulable task sets and most potential for reducing preemptions.