A Fluid Scheduling Algorithm for DAG Tasks With Constrained or Arbitrary Deadlines

doi:10.1109/TC.2021.3111512

A Fluid Scheduling Algorithm for DAG Tasks With Constrained or Arbitrary Deadlines

2021-01-01

6

PRE

AI

DOI：10.1109/TC.2021.3111512

Original

Original request for help

Save

Abstract

En 中文

A number of scheduling algorithms have been proposed for real-time parallel tasks modeled as Directed Acyclic Graphs (DAGs). Many of them focus on scheduling DAG tasks with implicit deadlines. Fewer studies have considered DAG tasks with constrained deadlines or arbitrary deadlines. In this study, we propose a scheduling strategy based on fluid scheduling theory and we target DAG tasks with constrained or arbitrary deadlines. We prove that the proposed algorithm has a capacity augmentation bound of 1/2(1 + beta root(1 +beta)(2) - 4/m) when scheduling multiple DAG tasks with constrained deadlines, in which m is the number of processors and beta is the maximum ratio of task period to deadline. This value is lower than the current best result beta + 2 root(beta + - 1/m) 1 - 1/m). We also prove that a capacity augmentation bound of 1/2 (1 + root 2 + root(1 + root 2)(2) - 4 root 2/m) is guaranteed by our algorithm in the case of scheduling multiple DAG tasks with deadlines greater than periods. To the best of our knowledge, this is the first capacity augmentation bound that has been proven for scheduling multiple DAG tasks with deadlines greater than periods. Our experiments show that our algorithm outperforms the state of the art scheduling algorithms in the percentage of schedulable task sets.

Keywords:

Real-time scheduling

multi-processor system

parallel task

A Fluid Scheduling Algorithm for DAG Tasks With Constrained or Arbitrary Deadlines

Abstract

Journal

Organization