DARTS.5.1.1.pdf
- Filesize: 339 kB
- 2 pages
Document
Dual Priority Scheduling is Not Optimal (Artifact)
Author
-
Part of:
Issue:
Special Issue of the 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)
Volume: DARTS, Volume 5 (ECOOP 2019)
Conference: Euromicro Conference on Real-Time Systems (ECRTS)
Journal: Dagstuhl Artifacts Series (DARTS) - License:
Creative Commons Attribution 3.0 Germany license
- Publication Date: 2019-07-08
Artifact Description
Document Identifiers
Cite As Get BibTex
Pontus Ekberg. Dual Priority Scheduling is Not Optimal (Artifact). In Special Issue of the 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Dagstuhl Artifacts Series (DARTS), Volume 5, Issue 1, pp. 1:1-1:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/DARTS.5.1.1
Artifact
DARTS-5-1-1-artifact-7b582798bcdb3bbce0502bd31ecb95df.tgz
(Filesize: 6 kB)
MD5 Sum:
7b582798bcdb3bbce0502bd31ecb95df
(Get MD5 Sum)
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.
Subject Classification
ACM Subject Classification
- Computer systems organization → Real-time systems
- Software and its engineering → Scheduling
Keywords
- Scheduling
- real time systems
- dual priority
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- A. Burns and A.J. Wellings. DUAL PRIORITY ASSIGNMENT: A Practical Method for Increasing Processor Utilisation. In Proceedings of the 5th Euromicro Workshop on Real-Time Systems, pages 48-53, 1993. URL: http://dx.doi.org/10.1109/EMWRT.1993.639052.
- Alan Burns. Dual priority scheduling: Is the processor utilisation bound 100%? In Proceedings of the 1st International Real-Time Scheduling Open Problems Seminar (RTSOPS), 2010. URL: https://www.cs.york.ac.uk/ftpdir/reports/2010/YCS/455/YCS-2010-455.pdf#page=9.
- Tristan Fautrel, Laurent George, Joël Goossens, Damien Masson, and Paul Rodriguez. A Practical Sub-Optimal Solution for the Dual Priority Scheduling Problem. In Proceedings of the 13th International Symposium on Industrial Embedded Systems (SIES), June 2018. URL: http://dx.doi.org/10.1109/SIES.2018.8442075.
- Laurent George, Joël Goossens, and Damien Masson. Dual Priority and EDF: a closer look. In Proceedings of the Work-in-Progress Session of 35th Real-Time Systems Symposium (RTSS-WiP), December 2014. URL: https://hal.archives-ouvertes.fr/hal-01217433.