Tighter Bounds of Speedup Factor of Partitioned EDF for Constrained-Deadline Sporadic Tasks
Tighter Bounds of Speedup Factor of Partitioned EDF for Constrained-Deadline Sporadic Tasks
复制标题
针对期限有限的零星任务的分区 EDF 加速因子的更严格界限
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Zhishan Guo
中科院分区：
文献类型：
--
作者：
Xingwu Liu;Zizhao Chen;Xin Han;Zhenyu Sun;Zhishan Guo
尽管最早截止日期优先 (EDF) 在单处理器可调度性方面是最佳的，但精确验证截止日期受限任务集的单处理器可调度性却是共 NP 困难的。在多项式时间内解决此问题的最有效方法是通过需求约束函数的部分线性近似。这种近似导致使用加速因子 ρ 进行简单的单处理器可调度性测试。这样的结果进一步导致多处理器上的 Deadline-Monotonic Partitioned-EDF 加速因子为 1+rho -1m（其中 m 是处理器的数量）。当前最先进的结果表明 ρ 在 [1.5,14/9] 范围内。特别是，推测ρ=1.5。本文将ρ的范围改进为(1.5026,1.5380)。改进后的下界反驳了下界1.5的猜想。一种新技术是构造一个辅助函数，该函数大于近似需求约束函数，但保持上界 ρ 不变。 %提出了一种新技术来扩大近似需求界限函数，但保持上限（限制，ρ）不变。它解决了打破下限 1.5 需要极大的任务集，而大的任务集又使得检查可调度性变得困难的困境。这项技术不仅使我们能够通过仅包含 8 个任务的任务集来反驳 1.5，而且还为未来在传输/缩小任务集以及为各种工作负载抽象模型（例如 DAG 任务）派生基于利用率界限的测试方面的工作提供了启示。
Even though earliest-deadline-first (EDF) is optimal in terms of uniprocessor schedulability, it is co-NP-hard to precisely verify uniprocessor schedulability for constrained-deadline task sets. The most efficient way to solve this problem in polynomial time is via a partially linear approximation of the demand bound function. Such approximation leads to a simple uniprocessor schedulability testing with speedup factor ρ. Such a result further leads to Deadline-Monotonic Partitioned-EDF on multi-processors with speedup factor of 1+rho -1m (where m is the number of processors). The current state of the art results indicate that ρ is within the range [1.5,14/9]. Especially, it has been a conjecture that ρ=1.5. This paper improves the range of ρ to (1.5026, 1.5380). The improved lower bound disproves the conjecture of lower bound 1.5. A novel technique is to construct an auxiliary function that is larger than the approximate demand bound function but keeps the supremum ρ unchanged. %A novel technique is proposed to enlarge the approximate demand bound function but keeps the upper bound (limit, ρ) unchanged. It solves the dilemma that beating the lower bound 1.5 requires extremely large task sets, while the large size makes it difficult to check the schedulability. This technique not only enables us to disprove 1.5 by a task set of only eight tasks, but also sheds light on future work in transferring/downsizing task sets and deriving utilization bound based tests for various workload abstraction models, such as DAG tasks.
缩小分区 EDF 的加速因子差距
影响因子：
1
作者：
Liu, Xingwu;Han, Xin;Zhao, Liang;Guo, Zhishan
通讯作者：
Guo, Zhishan
动态优先级调度下时限有限的零星任务的改进加速因子
DOI：
10.1109/rtss.2018.00058
发表时间：
2018
期刊：
Proceedings of IEEE Real-Time Systems Symposium (RTSS
影响因子：
--
作者：
Han, Xin;Zhao, Liang;Guo, Zhishan;Liu, Xingwu
通讯作者：
Liu, Xingwu