Abstract
Non-preemptive scheduling is usually considered inferior to preemptive scheduling for time critical systems, because the non-preemptive block would lead to poor task responsiveness. Although this is true in single-processor scheduling, we found by empirical simulation experiments that it is not necessarily the case in multiprocessor scheduling. Additionally, non-preemptive scheduling enjoys other benefits like lower implementation complexity and run-time overhead. So non-preemptive scheduling may be a better alternative compared to preemptive scheduling for a considerable part of real-time applications on multiprocessor/multi-core platforms. As the technical contribution, we study the schedulability analysis problem of global non-preemptive fixed-priority scheduling (NP-FP) on multiprocessors. We propose schedulability test conditions for NP-FP, building upon the "problem window analysis" by Baruah [8] for preemptive scheduling. We firstly derive a linear-time general schedulability test condition that works on not only NP-FP, but also any other work-conserving non-preemptive scheduling algorithm. Then we improve the analysis and present a test condition of quadratic time-complexity for NP-FP, which has significant performance improvement comparing to the first one. A notable advantage of our proposed test conditions is, while the test in [8] needs to enumerate for a large number of possible problem window sizes, our proposed test conditions only need to be conducted with a single problem window size, and thereby are significantly more efficient. Experiments with randomly generated task sets are conducted to evaluate the performance of the proposed test conditions.
Original language | English |
---|---|
Pages (from-to) | 536-546 |
Number of pages | 11 |
Journal | Journal of Systems Architecture |
Volume | 57 |
Issue number | 5 |
DOIs | |
Publication status | Published - 1 May 2011 |
Externally published | Yes |
Keywords
- Multiprocessor scheduling
- Non-preemptive scheduling
- Real-time systems
- Schedulability analysis
ASJC Scopus subject areas
- Software
- Hardware and Architecture