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.2019.14
URN: urn:nbn:de:0030-drops-107519
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10751/
Go to the corresponding LIPIcs Volume Portal

Ekberg, Pontus

Dual Priority Scheduling is Not Optimal

pdf-format:
LIPIcs-ECRTS-2019-14.pdf (0.4 MB)

Abstract

In dual priority scheduling, periodic tasks are executed in a fixed-priority manner, but each job has two phases with different priorities. The second phase is entered after a fixed amount of time has passed since the release of the job, at which point the job changes its priority. Dual priority scheduling was introduced by Burns and Wellings in 1993 and was shown to successfully schedule many task sets that are not schedulable with ordinary (single) fixed-priority scheduling. Burns and Wellings conjectured that dual priority scheduling is an optimal scheduling algorithm for synchronous periodic tasks with implicit deadlines on preemptive uniprocessors. We demonstrate the falsity of this conjecture, as well as of some related conjectures that have since been stated. This is achieved by means of computer-verified counterexamples.

BibTeX - Entry

@InProceedings{ekberg:LIPIcs:2019:10751,
  author =	{Pontus Ekberg},
  title =	{{Dual Priority Scheduling is Not Optimal}},
  booktitle =	{31st Euromicro Conference on Real-Time Systems (ECRTS 2019)},
  pages =	{14:1--14:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-110-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{133},
  editor =	{Sophie Quinton},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10751},
  URN =		{urn:nbn:de:0030-drops-107519},
  doi =		{10.4230/LIPIcs.ECRTS.2019.14},
  annote =	{Keywords: Scheduling, real time systems, dual priority}
}

Keywords: Scheduling, real time systems, dual priority
Collection: 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)
Issue Date: 2019
Date of publication: 02.07.2019
Supplementary Material: ECRTS 2019 Artifact Evaluation approved artifact available at https://dx.doi.org/10.4230/DARTS.5.1.1; The source code for a C program that verifies the correctness of the counterexamples in this paper can be found at https://github.com/pontusekberg/dualpriotest/.

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