On a novel property of the earliest deadline first algorithm

摘要

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.