Deadline Miss Rate Scheduling in DAG Considering Probabilistic Execution Time
Open Access
- 5 September 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. PP, 1
Abstract
Autonomous driving systems have been extensively researched for safety. To ensure safety, a strict deadline is enforced before sensor data influences vehicle control. A common approach to this issue is Directed Acyclic Graph (DAG) scheduling. However, existing studies use fixed values, typically using Worst-case Execution Time (WCET). During actual vehicle operation, the task execution time varies due to factors such as input size (e.g., surrounding vehicles), and the actual execution time often takes on a value smaller than the WCET. The execution time variation causes the actual results of DAG scheduling to deviate from the intended strategy. To address this problem, this paper proposes a DAG scheduling algorithm that considers probabilistic execution time to reduce the number of deadline misses. For consecutive timer-driven nodes, a waiting time may occur, during which executing higher priority nodes does not affect end-to-end deadline misses. The proposed scheduling algorithm calculates this waiting time and executes high deadline miss rate nodes outside the end-to-end path during this time. In DAGs with high utilization, the evaluation results of the proposed scheduling algorithm demonstrate that the number of deadline misses decreases compared to existing methods. Specifically, our evaluation results indicate an approximate 8.3% improvement in deadline achievement rate compared to existing methods in high utilization scenarios.Keywords
Funding Information
- Japan Science and Technology Agency (JPMJPR21P1)