Reducing Worst-Case Deadline Failure Probability for EDF Scheduling

As modern real-time systems become more complex, traditional deterministic analysis techniques often cannot accurately capture the system characteristics and offer meaningful design guidance. In contrast, probabilistic analysis is usually more practical and provides superior design insight while ensuring timing correctness with the required level of confidence. Earliest Deadline First (EDF) is one of the most widely used real-time scheduling algorithms. Although previous research has proposed a worst-case deadline failure probability (WCDFP) analysis for EDF, such an analysis tends to be overly pessimistic. Meanwhile, we observe that any analytical approach has inherent limitations, indicating that further reductions in WCDFP cannot be achieved solely through improved the analysis. In response to the first issue, this paper proposes a new technique to improve the accuracy of the WCDFP analysis. For the second issue, we enhance EDF by incorporating an active-dropping policy to reduce the analytical deadline failure probability. Empirical experiments demonstrate that our techniques lower the job failure probability in most tested scenarios, with especially significant improvements for task sets with high utilization.