Real-Time DAG Task Allocation Strategy for Multiprocessor by Optimistic Parallelism

In modern real-time operating systems, complex task loads are often modeled as directed acyclic graphs (DAG) and executed in parallel on multiprocessor systems. The topological constraints present in DAG tasks prevent the DAG task allocation strategy from fully leveraging the parallel advantage of multiprocessor platforms. We analyze the parallelism of DAG tasks and propose a method to limit the number of processors that can be executed by DAG tasks. This method provides more idle processors and processor time for high parallelism DAG tasks by limiting the number of processors that can be executed by low parallelism DAG tasks. In addition, we develope optimistic parallelism scheduling algorithm (OPSA) based on the remaining utilization with low complexity. The experimental results show that our DAG task allocation strategy fully utilizes processor resources, reduces interference between DAG tasks, and achieves better worst case response time (WCRT) analysis results and shorter actual task’s WCRT on real-time multiprocessor system.