Dual Priority Scheduling is Not Optimal (Artifact)

Author Pontus Ekberg



PDF
Thumbnail PDF

Artifact Description

DARTS.5.1.1.pdf
  • Filesize: 339 kB
  • 2 pages

Document Identifiers

Author Details

Pontus Ekberg
  • Uppsala University, Sweden

Cite AsGet 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

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)
    0
    PDF Downloads

References

  1. 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.
  2. 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.
  3. 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.
  4. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail