Worst-Case Response Time Analysis of Multitype DAG Tasks Based on Reconstruction

Abstract

With the wide application of heterogeneous multi-core processor real-time systems, the existing analysis methods of worst-case response time (WCRT) overestimate the blocking information among tasks, resulting in a rather pessimistic estimation. To improve the accuracy of the WCRT, we propose a reconstruction-based WCRT analysis method for multi-type directed acyclic graph (DAG) tasks scheduling algorithm(RMDS). The RMDS algorithm comprises the following steps: First, we unitize all task nodes in the multi-type DAG task; Then, we use key factors as task priorities to schedule tasks and reconstruct the DAG task model into a parallel node segment model; Finally, we estimate the WCRT of multi-type DAG tasks according to the parallel node segment model to assess task schedulability. To verify the performance of our algorithm, we compared it with traditional algorithms. RDMS showed an acceptance rate 6.13% higher and its overall performance increased by 25.95% in comparison with traditional algorithms.

Keywords

• Worst-case response time
• reconstruction
• task scheduling
• RMDS
• multitype DAG tasks