New Schedulability Test Conditions for Non-preemptive Scheduling on Multiprocessor Platforms
Citations Over TimeTop 10% of 2008 papers
Abstract
We study the schedulability analysis problem for nonpreemptive scheduling algorithms on multiprocessors. To our best knowledge, the only known work on this problem is the test condition proposed by Baruah for non-preemptive EDF scheduling, which will reject a task set with arbitrarily low utilization if it contains a task whose execution time is equal or greater than the minimal relative deadline among all tasks. In this paper, we firstly derive a linear-time test condition which avoids the problem mentioned above, by building upon previous work for preemptive multiprocessor scheduling. This test condition works on not only non-preemptive EDF, but also any other work-conserving non-preemptive scheduling algorithms. Then we improve the analysis and present test conditions of pseudo-polynomial time-complexity for Non-preemptive Earliest Deadline First scheduling and Non-preemptive Fixed Priority scheduling respectively. Experiments with randomly generated task sets show that our proposed test conditions, especially the improved test conditions, have significant performance improvements compared with [BAR-EDF <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">np ].
Related Papers
- → Scheduling fixed-priority tasks with preemption threshold(2003)270 cited
- Limited Preemptive Scheduling in Real-time Systems(2016)
- → On-line Scheduling in Real-Time Multiprocessor Systems(2008)
- Off-Line Optimization of Fixed Priority Scheduling in Hard Real-Time Environment(2008)
- Task Scheduling in Multiprocessor Real-Time Systems(2001)