New schedulability test conditions for non-preemptive scheduling on multiprocessor platforms

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

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

47 Citations (Scopus)


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 [1] (referred to as [BAREDFnp]) 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 the work in [2] 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 timecomplexity for Non-preemptive Earliest Deadline First scheduling (EDF np) and Non-preemptive Fixed Priority scheduling (FPnp) 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-EDFnp].

Original languageEnglish
Title of host publicationProceedings - 2008 Real-Time Systems Symposium, RTSS 2008
Number of pages10
Publication statusPublished - 1 Dec 2008
Externally publishedYes
Event2008 Real-Time Systems Symposium, RTSS 2008 - Barcelona, Spain
Duration: 30 Nov 20083 Dec 2008

Publication series

NameProceedings - Real-Time Systems Symposium
ISSN (Print)1052-8725


Conference2008 Real-Time Systems Symposium, RTSS 2008

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this