Non-work-conserving scheduling of non-preemptive hard real-time tasks based on fixed priorities
Mitra Nasri, Gerhard Fohler · 2015
In this paper, we consider scheduling of non-preemptive and independent periodic tasks with implicit deadlines on uniprocessor systems. We assume loose-harmonic task sets with periods being integer multiples of the smallest period. This problem is known to be NP-Hard. Recently, two online non-work-conserving scheduling algorithms called Precautious-RM (P-RM) and lazy P-RM (LP-RM) have been introduced to guarantee schedulability of special cases of harmonic task sets. In this paper, we provide new sufficient schedulability tests for P-RM and LP-RM. Then, by introducing a new algorithm called efficient Precautious-RM (EP-RM), we increase the number of schedulable loose-harmonic task sets in comparison with P-RM by letting the tasks share the priorities. We prove that the new test dominates the schedulability tests for P-RM. Moreover, we show that if the ratio of two consecutive periods is greater than or equal to 3, P-RM, LP-RM, and EP-RM are able to schedule any task set satisfying the necessary conditions of schedulability. We present results from a simulation study, showing the efficiency of the algorithm.