Two level preemptive global fixed priority DAG recursive scheduling for multi-core platforms

For real-time application scheduling, directed acyclic graph (DAG) is used to set up a set of parallel and recursive tasks on multi-core platforms to obtain sub-tasks (i.e. nodes) with priority constraints (i.e. directed edges) and to ensure that all the sub-tasks are executed before a specified deadline. Each task may generate an unlimited number of instances, in which the publication of successive instances is separated by some minimum arrival time. At the same time, each sub-task of the DAG task is assigned a fixed priority. A two-level preemptive global fixed priority scheduling (GFP) strategy is proposed. The task-level scheduler first determines the highest priority ready task, and then the sub-task-level scheduler selects its highest priority sub-task to execute. The sub task level scheduler then selects its highest priority sub task to perform. Then, a schedulability test is derived for the proposed two-level GFP scheduler, which guarantees that all tasks meet their deadlines under GFP. Finally, through experimental analysis, the performance advantage of the proposed algorithm on acceptance rate index is verified.