License
When quoting this document, please refer to the following
DOI: 10.4230/DARTS.5.1.1
URN: urn:nbn:de:0030-drops-107293
URL: http://drops.dagstuhl.de/opus/volltexte/2019/10729/
Go back to Dagstuhl Artifacts Series


Ekberg, Pontus

Dual Priority Scheduling is Not Optimal (Artifact)

pdf-format:
DARTS-5-1-1.pdf (0.3 MB)
artifact-format:
DARTS-5-1-1-artifact-7b582798bcdb3bbce0502bd31ecb95df.tgz (0.01 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. The related article presents counterexamples to this conjecture, and to some related conjectures that have since been stated. This artifact verifies the counterexamples by means of exhaustive simulations of vast numbers of configurations.

BibTeX - Entry

@Article{ekberg:DARTS:2019:10729,
  author =	{Pontus Ekberg},
  title =	{{Dual Priority Scheduling is Not Optimal (Artifact)}},
  pages =	{1:1--1:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2019},
  volume =	{5},
  number =	{1},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10729},
  URN =		{urn:nbn:de:0030-drops-107293},
  doi =		{10.4230/DARTS.5.1.1},
  annote =	{Keywords: Scheduling, real time systems, dual priority}
}

Keywords: Scheduling, real time systems, dual priority
Seminar: Special Issue of the 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)
Related Scholarly Article: https://dx.doi.org/10.4230/LIPIcs.ECRTS.2019.14
Issue Date: 2019
Date of publication: 08.07.2019


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