计算机科学
有向无环图
调度(生产过程)
上下界
算法
动态优先级调度
最早截止时间优先安排
作业车间调度
公平份额计划
单调速率调度
固定优先级先发制人调度
并行计算
数学优化
数学
服务质量
地铁列车时刻表
计算机网络
操作系统
数学分析
作者
Fengying Guan,Long Peng,Jiaqing Qiao
标识
DOI:10.1109/tc.2021.3111512
摘要
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++((1+) 24/m)) when scheduling multiple DAG tasks with constrained deadlines, in which m is the number of processors and is the maximum ratio of task period to deadline. This value is lower than the current best result +2((1+-1/m)(1-1/m)). We also prove that a capacity augmentation bound of 1/2(1+2+((1+2)242/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.
科研通智能强力驱动
Strongly Powered by AbleSci AI