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.8
URN: urn:nbn:de:0030-drops-89965
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8996/
Go to the corresponding LIPIcs Volume Portal

Chen, Jian-Jia ; von der Brüggen, Georg ; Ueter, Niklas

Push Forward: Global Fixed-Priority Scheduling of Arbitrary-Deadline Sporadic Task Systems

pdf-format:
LIPIcs-ECRTS-2018-8.pdf (0.7 MB)

Abstract

The sporadic task model is often used to analyze recurrent execution of tasks in real-time systems. A sporadic task defines an infinite sequence of task instances, also called jobs, that arrive under the minimum inter-arrival time constraint. To ensure the system safety, timeliness has to be guaranteed in addition to functional correctness, i.e., all jobs of all tasks have to be finished before the job deadlines. We focus on analyzing arbitrary-deadline task sets on a homogeneous (identical) multiprocessor system under any given global fixed-priority scheduling approach and provide a series of schedulability tests with different tradeoffs between their time complexity and their accuracy. Under the arbitrary-deadline setting, the relative deadline of a task can be longer than the minimum inter-arrival time of the jobs of the task. We show that global deadline-monotonic (DM) scheduling has a speedup bound of 3-1/M against any optimal scheduling algorithms, where M is the number of identical processors, and prove that this bound is asymptotically tight.

BibTeX - Entry

@InProceedings{chen_et_al:LIPIcs:2018:8996,
  author =	{Jian-Jia Chen and Georg von der Br{\"u}ggen and Niklas Ueter},
  title =	{{Push Forward: Global Fixed-Priority Scheduling of Arbitrary-Deadline Sporadic Task Systems}},
  booktitle =	{30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
  pages =	{8:1--8:24},
  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/8996},
  URN =		{urn:nbn:de:0030-drops-89965},
  doi =		{10.4230/LIPIcs.ECRTS.2018.8},
  annote =	{Keywords: global fixed-priority scheduling, schedulability analyses, speedup bounds}
}

Keywords: global fixed-priority scheduling, schedulability analyses, speedup bounds
Collection: 30th Euromicro Conference on Real-Time Systems (ECRTS 2018)
Issue Date: 2018
Date of publication: 22.06.2018
Supplementary Material: ECRTS Artifact Evaluation approved artifact available at https://dx.doi.org/10.4230/DARTS.4.2.6

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