.png){kind=icon}
返回
A Fluid Scheduling Algorithm for DAG Tasks With Constrained or Arbitrary Deadlines
.png){kind=icon}
PRE
AI
DOI：10.1109/TC.2021.3111512.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
Real-time scheduling
multi-processor system
parallel task
期刊
IF:
3.8
论文数:
5.3K
被引数:
9.8K
机构
引用论文
Predicting STI Positivity in US Cisgender Women Using Electronic Resources利用电子资源预测美国顺性别女性中STI的阳性率
PREAI
分享收藏分享收藏Characterization of the quinones in purple sulfur bacterium Thermochromatium tepidum.png)
FEBS Letters
OAAI
FEBS LettersIF0
OAAI分享收藏
分享收藏
查看更多内容