On a novel property of the earliest deadline first algorithm

Hongya Wang, Jin Jie Jin, Wang Zhijun Wang, Lih-Chyun Shu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Citations (Scopus)

Abstract

Real-time scheduling theory plays a key role in many time critical control systems or applications. In this paper, an interesting property of the Earliest Deadline First (EDF) algorithm, which has never been discussed before, is examined. To be specific, we conjecture that if a task set is schedulable under EDF, then for any task pair (Τi, Τj) such that pi ≥ pj in this task set, there must be at least one whole execution of j occurring between the release time and deadline of any Τi's job. Although this property is not hard to describe, its proof is far more difficult than expected. To prove this property, we first show the correctness of the conjecture for task sets consisting of only two real-time tasks. In view of the hardness in extending the proof to task sets having more than 2 members, extensive simulation experiments are conducted to support our intuition for general cases. The conjecture holds under a substantial number of parameter settings we have tried.

Original languageEnglish
Title of host publicationProceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011
Pages197-201
Number of pages5
DOIs
Publication statusPublished - 2011 Oct 6
Event2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011, Jointly with the 2011 7th International Conference on Natural Computation, ICNC'11 - Shanghai, China
Duration: 2011 Jul 262011 Jul 28

Publication series

NameProceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011
Volume1

Other

Other2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011, Jointly with the 2011 7th International Conference on Natural Computation, ICNC'11
CountryChina
CityShanghai
Period11-07-2611-07-28

Fingerprint

Earliest Deadline First
Hardness
Scheduling
Control systems
Experiments
Scheduling Theory
Real-time
Release Time
Deadline
Pi
Simulation Experiment
Correctness
Control System

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Computer Science Applications
  • Applied Mathematics

Cite this

Wang, H., Jie Jin, J., Zhijun Wang, W., & Shu, L-C. (2011). On a novel property of the earliest deadline first algorithm. In Proceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011 (pp. 197-201). [6019496] (Proceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011; Vol. 1). https://doi.org/10.1109/FSKD.2011.6019496
Wang, Hongya ; Jie Jin, Jin ; Zhijun Wang, Wang ; Shu, Lih-Chyun. / On a novel property of the earliest deadline first algorithm. Proceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011. 2011. pp. 197-201 (Proceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011).
@inproceedings{46a40f844eaa47f1869add13f7f288b3,
title = "On a novel property of the earliest deadline first algorithm",
abstract = "Real-time scheduling theory plays a key role in many time critical control systems or applications. In this paper, an interesting property of the Earliest Deadline First (EDF) algorithm, which has never been discussed before, is examined. To be specific, we conjecture that if a task set is schedulable under EDF, then for any task pair (Τi, Τj) such that pi ≥ pj in this task set, there must be at least one whole execution of j occurring between the release time and deadline of any Τi's job. Although this property is not hard to describe, its proof is far more difficult than expected. To prove this property, we first show the correctness of the conjecture for task sets consisting of only two real-time tasks. In view of the hardness in extending the proof to task sets having more than 2 members, extensive simulation experiments are conducted to support our intuition for general cases. The conjecture holds under a substantial number of parameter settings we have tried.",
author = "Hongya Wang and {Jie Jin}, Jin and {Zhijun Wang}, Wang and Lih-Chyun Shu",
year = "2011",
month = "10",
day = "6",
doi = "10.1109/FSKD.2011.6019496",
language = "English",
isbn = "9781612841816",
series = "Proceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011",
pages = "197--201",
booktitle = "Proceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011",

}

Wang, H, Jie Jin, J, Zhijun Wang, W & Shu, L-C 2011, On a novel property of the earliest deadline first algorithm. in Proceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011., 6019496, Proceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011, vol. 1, pp. 197-201, 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011, Jointly with the 2011 7th International Conference on Natural Computation, ICNC'11, Shanghai, China, 11-07-26. https://doi.org/10.1109/FSKD.2011.6019496

On a novel property of the earliest deadline first algorithm. / Wang, Hongya; Jie Jin, Jin; Zhijun Wang, Wang; Shu, Lih-Chyun.

Proceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011. 2011. p. 197-201 6019496 (Proceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011; Vol. 1).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - On a novel property of the earliest deadline first algorithm

AU - Wang, Hongya

AU - Jie Jin, Jin

AU - Zhijun Wang, Wang

AU - Shu, Lih-Chyun

PY - 2011/10/6

Y1 - 2011/10/6

N2 - Real-time scheduling theory plays a key role in many time critical control systems or applications. In this paper, an interesting property of the Earliest Deadline First (EDF) algorithm, which has never been discussed before, is examined. To be specific, we conjecture that if a task set is schedulable under EDF, then for any task pair (Τi, Τj) such that pi ≥ pj in this task set, there must be at least one whole execution of j occurring between the release time and deadline of any Τi's job. Although this property is not hard to describe, its proof is far more difficult than expected. To prove this property, we first show the correctness of the conjecture for task sets consisting of only two real-time tasks. In view of the hardness in extending the proof to task sets having more than 2 members, extensive simulation experiments are conducted to support our intuition for general cases. The conjecture holds under a substantial number of parameter settings we have tried.

AB - Real-time scheduling theory plays a key role in many time critical control systems or applications. In this paper, an interesting property of the Earliest Deadline First (EDF) algorithm, which has never been discussed before, is examined. To be specific, we conjecture that if a task set is schedulable under EDF, then for any task pair (Τi, Τj) such that pi ≥ pj in this task set, there must be at least one whole execution of j occurring between the release time and deadline of any Τi's job. Although this property is not hard to describe, its proof is far more difficult than expected. To prove this property, we first show the correctness of the conjecture for task sets consisting of only two real-time tasks. In view of the hardness in extending the proof to task sets having more than 2 members, extensive simulation experiments are conducted to support our intuition for general cases. The conjecture holds under a substantial number of parameter settings we have tried.

UR - http://www.scopus.com/inward/record.url?scp=80053417043&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80053417043&partnerID=8YFLogxK

U2 - 10.1109/FSKD.2011.6019496

DO - 10.1109/FSKD.2011.6019496

M3 - Conference contribution

SN - 9781612841816

T3 - Proceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011

SP - 197

EP - 201

BT - Proceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011

ER -

Wang H, Jie Jin J, Zhijun Wang W, Shu L-C. On a novel property of the earliest deadline first algorithm. In Proceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011. 2011. p. 197-201. 6019496. (Proceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011). https://doi.org/10.1109/FSKD.2011.6019496