License
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://drops.dagstuhl.de/opus/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
Seminar: 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)
Issue Date: 2019
Date of publication: 08.07.2019


DROPS-Home | Imprint | Privacy Published by LZI