On a novel property of the earliest deadline first algorithm

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

研究成果: Conference contribution

11 引文 斯高帕斯(Scopus)

摘要

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.

原文English
主出版物標題Proceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011
頁面197-201
頁數5
DOIs
出版狀態Published - 2011 10月 6
事件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
持續時間: 2011 7月 262011 7月 28

出版系列

名字Proceedings - 2011 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2011
1

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
國家/地區China
城市Shanghai
期間11-07-2611-07-28

All Science Journal Classification (ASJC) codes

  • 計算機理論與數學
  • 電腦科學應用
  • 應用數學

指紋

深入研究「On a novel property of the earliest deadline first algorithm」主題。共同形成了獨特的指紋。

引用此