A response-time analysis for non-preemptive job sets under global scheduling

Mitra Nasri, Geoffrey Nelissen, Björn B. Brandenburg

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)


An effective way to increase the timing predictability of multicore platforms is to use nonpreemptive scheduling. It reduces preemption and job migration overheads, avoids intra-core cache interference, and improves the accuracy of worst-case execution time (WCET) estimates. However, existing schedulability tests for global non-preemptive multiprocessor scheduling are pessimistic, especially when applied to periodic workloads. This paper reduces this pessimism by introducing a new type of sufficient schedulability analysis that is based on an exploration of the space of possible schedules using concise abstractions and state-pruning techniques. Specifically, we analyze the schedulability of non-preemptive job sets (with bounded release jitter and execution time variation) scheduled by a global job-level fixed-priority (JLFP) scheduling algorithm upon an identical multicore platform. The analysis yields a lower bound on the best-case response-time (BCRT) and an upper bound on the worst-case response time (WCRT) of the jobs. In an empirical evaluation with randomly generated workloads, we show that the method scales to 30 tasks, a hundred thousand jobs (per hyperperiod), and up to 9 cores.

Original languageEnglish
Title of host publication30th Euromicro Conference on Real-Time Systems, ECRTS 2018
EditorsSebastian Altmeyer
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)9783959770750
Publication statusPublished - 1 Jun 2018
Externally publishedYes
Event30th Euromicro Conference on Real-Time Systems, ECRTS 2018 - Barcelona, Spain
Duration: 3 Jun 20186 Jun 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference30th Euromicro Conference on Real-Time Systems, ECRTS 2018


  • Best-case response time
  • Global multiprocessor scheduling
  • Non-preemptive tasks
  • Schedulability analysis
  • Worst-case response time


Dive into the research topics of 'A response-time analysis for non-preemptive job sets under global scheduling'. Together they form a unique fingerprint.

Cite this