This article is published in the 3rd issue of 2025 in the journal “Integrated Circuits and Embedded Systems”.
Multi-DAG Real-Time Scheduling Algorithm for Embedded Testing Platforms
Tian Wentao, Li Xiaoming
(Zhejiang University of Science and Technology, School of Mechanical Engineering)
Abstract: In the development of embedded testing platforms, real-time performance is a crucial characteristic that enables the platform system to respond quickly to task events. In most cases, the platform operates with numerous tasks of varying types. Therefore, this paper proposes a Multi-DAG Real-Time Scheduling Algorithm (MDRTPS) to address the issue of prioritizing real-time tasks in the context of numerous tasks with diverse interdependencies. The algorithm is mainly divided into three steps: ① Real-time task separation from multiple DAGs, where the separated real-time task set and ordinary task set use different priority algorithms and resource allocation. ② Maintenance of three scheduling queues to coordinate the ordering of tasks between different DAGs. ③ The scheduler dispatches tasks to processor cores based on the earliest finish time. Experimental results show that the task span and response speed of real-time tasks using the MDRTPS algorithm outperform those of the HEFT and CPOP algorithms.
Highlights of this Article
In the field of embedded systems, real-time performance has always been one of the key indicators for measuring system performance. Especially in the development of embedded testing platforms, real-time performance is crucial. It enables the platform system to respond quickly to task events, ensuring the accuracy and efficiency of testing. However, as the complexity of testing tasks increases, achieving efficient real-time scheduling in a multi-task, multi-dependency environment has become an urgent problem to solve. Tian Wentao and Li Xiaoming from Zhejiang University of Science and Technology published their research results titled “Multi-DAG Real-Time Scheduling Algorithm for Embedded Testing Platforms” in the 3rd issue of 2025 in the journal “Integrated Circuits and Embedded Systems”, providing an innovative solution to this problem.
Task Scheduling Framework
1. Research Background and Challenges
In embedded testing platforms, the importance of real-time systems is self-evident. Unlike general operating systems, real-time systems emphasize completing tasks within specified time limits to ensure system reliability and accuracy. However, most current embedded testing platforms are based on Linux operating systems, which are inherently non-real-time and typically require kernel patches to become preemptive systems. Even so, as task complexity increases, selecting a suitable real-time scheduling algorithm for the system remains a challenge.
The task scheduling problem in heterogeneous multi-core environments has been proven to be NP-complete, meaning that finding an optimal solution is nearly impossible. Therefore, researchers often focus on finding approximate optimal solutions. In scheduling algorithms, Directed Acyclic Graphs (DAGs) are commonly used to represent tasks with dependencies. Existing algorithms such as HEFT and CPOP perform well in certain aspects, but in multi-DAG task environments, they often fail to guarantee the priority of real-time tasks, thus not meeting real-time requirements.
2. MDRTPS Algorithm: An Innovative Scheduling Strategy
To address the aforementioned issues, Tian Wentao and Li Xiaoming proposed a Multi-DAG Real-Time Priority Scheduling algorithm (MDRTPS). The core idea of this algorithm is to separate real-time tasks from multiple DAGs, using different priority algorithms and resource allocation strategies for the separated real-time task set and ordinary task set, thereby achieving prioritized scheduling of real-time tasks.
The MDRTPS algorithm is mainly divided into three steps. First, real-time task separation from multiple DAGs is performed. Using a recursive approach, real-time nodes and all their preceding path nodes are designated as critical nodes, and the dependencies between real-time tasks and ordinary tasks are removed. Second, three scheduling queues are maintained to store real-time tasks, ordinary tasks, and ready tasks, respectively. Finally, the scheduler dispatches tasks to processor cores based on the earliest finish time (EFT).
The advantage of this algorithm lies in its flexibility to apply different priority algorithms to handle real-time tasks and ordinary tasks. For example, real-time tasks can adopt a preemptive scheduling strategy, while ordinary tasks can use a time-slice round-robin scheduling strategy. In this way, the algorithm not only ensures the priority execution of real-time tasks but also effectively coordinates the scheduling order of different tasks in a multi-DAG environment.
3. Experimental Verification and Performance Comparison
To verify the performance of the MDRTPS algorithm, researchers conducted simulation experiments comparing the MDRTPS algorithm with existing HEFT and CPOP algorithms. The experimental results indicate that the MDRTPS algorithm outperforms both HEFT and CPOP algorithms in terms of task span (Makespan) and response speed of real-time tasks.
In terms of task span, the MDRTPS algorithm maintains a low Makespan regardless of the increase in the number of tasks or changes in the internal task connection structure of the DAG. This indicates that the MDRTPS algorithm has higher scheduling efficiency under high load and can effectively cope with varying task complexities and dependencies.
Regarding real-time task response, the MDRTPS algorithm also performs excellently. In scenarios with a single real-time task and multiple real-time tasks, the MDRTPS algorithm ensures that real-time tasks are scheduled before their deadlines. Even under limited resources, the MDRTPS algorithm can achieve timely completion of each real-time task by employing a reasonable scheduling order.
4. Research Significance and Outlook
The significance of this research lies in providing a new perspective and method for the real-time scheduling problem of embedded testing platforms. The MDRTPS algorithm effectively improves the scheduling efficiency and response speed of real-time tasks through innovative node separation and priority calculation strategies, which is of great practical significance for enhancing the performance and reliability of embedded testing platforms.
However, the researchers also pointed out some limitations of the MDRTPS algorithm. For instance, in cases with too many DAGs, resource contention may occur, leading to prolonged delays for some DAG tasks. Additionally, in highly dynamic and uncertain environments, the scheduling decisions of the algorithm may still fail to meet the real-time requirements of all tasks. Future research could further optimize resource allocation strategies to enhance the algorithm’s adaptability and responsiveness in dynamic environments.
This research injects new vitality into the field of real-time scheduling for embedded testing platforms. The introduction of the MDRTPS algorithm not only provides an effective solution to the multi-DAG task scheduling problem but also offers new research directions and ideas for related researchers. As embedded systems are widely applied across various fields, the study of real-time scheduling algorithms will continue to play an important role in promoting the ongoing development and innovation of embedded technology.
Reference format for this article: Tian Wentao, Li Xiaoming. Multi-DAG Real-Time Scheduling Algorithm for Embedded Testing Platforms [J]. Integrated Circuits and Embedded Systems, 2025, 25(3): 24-32. TIAN W T, LI X M. Multi-DAG real-time scheduling algorithm for embedded test platform [J]. Integrated Circuits and Embedded Systems, 2025, 25(3): 24-32 (in Chinese).
Previous IssuesIndex
