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 p_i ≥ p_j 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.