License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECRTS.2018.9
URN: urn:nbn:de:0030-drops-89941
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8994/
Go to the corresponding LIPIcs Volume Portal

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

A Response-Time Analysis for Non-Preemptive Job Sets under Global Scheduling

pdf-format:
LIPIcs-ECRTS-2018-9.pdf (2 MB)

Abstract

An effective way to increase the timing predictability of multicore platforms is to use non-preemptive 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.

BibTeX - Entry

@InProceedings{nasri_et_al:LIPIcs:2018:8994,
  author =	{Mitra Nasri and Geoffrey Nelissen and Bj{\"o}rn B. Brandenburg},
  title =	{{A Response-Time Analysis for Non-Preemptive Job Sets under Global Scheduling}},
  booktitle =	{30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
  pages =	{9:1--9:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-075-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{106},
  editor =	{Sebastian Altmeyer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8994},
  URN =		{urn:nbn:de:0030-drops-89941},
  doi =		{10.4230/LIPIcs.ECRTS.2018.9},
  annote =	{Keywords: global multiprocessor scheduling, schedulability analysis, non-preemptive tasks, worst-case response time, best-case response time}
}

Keywords: global multiprocessor scheduling, schedulability analysis, non-preemptive tasks, worst-case response time, best-case response time
Collection: 30th Euromicro Conference on Real-Time Systems (ECRTS 2018)
Issue Date: 2018
Date of publication: 22.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI