Improved Schedulability Test for Non-Preemptive Fixed-Priority Scheduling on Multiprocessors

Hyeongboo Baek, Jinkyu Lee

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Non-preemptive scheduling is essential to tasks that inherently disallow any preemption and useful for tasks that exhibit extremely large preemption/migration overhead; however, studies of non-preemptive scheduling have not matured for real-time tasks subject to timing constraints. In this letter, we propose an improved schedulability test for non-preemptive fixed-priority scheduling (NP-FP), which offers timing guarantees for a set of real-time tasks executed on a multiprocessor platform. To this end, we first carefully investigate the NP-FP properties, and present an observation why the existing technique is pessimistic in calculating interference from higher-priority tasks. We then develop a new technique that tightly upper bounds the amount of the interference, and show how to incorporate the technique into the existing schedulability test. Via simulations, we demonstrate that our proposed test improves schedulability performance of NP-FP up to 18%, compared with the state-of-the-art existing tests.

Original languageEnglish
Article number8959310
Pages (from-to)129-132
Number of pages4
JournalIEEE Embedded Systems Letters
Issue number4
StatePublished - Dec 2020


  • Non-preemptive fixed-priority scheduling (NP-FP)
  • real-time embedded systems
  • real-time tasks
  • schedulability analysis


Dive into the research topics of 'Improved Schedulability Test for Non-Preemptive Fixed-Priority Scheduling on Multiprocessors'. Together they form a unique fingerprint.

Cite this