Schedulability analysis for non-preemptive fixed-priority multiprocessor scheduling

Nan Guan, Wang Yi, Qingxu Deng, Zonghua Gu, Ge Yu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

33 Citations (Scopus)

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 languageEnglish
Pages (from-to)536-546
Number of pages11
JournalJournal of Systems Architecture
Volume57
Issue number5
DOIs
Publication statusPublished - 1 May 2011
Externally publishedYes

Keywords

  • Multiprocessor scheduling
  • Non-preemptive scheduling
  • Real-time systems
  • Schedulability analysis

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture

Cite this