Narrowing the speedup factor gap of partitioned EDF
Narrowing the speedup factor gap of partitioned EDF
复制标题
缩小分区 EDF 的加速因子差距
DOI：
10.1016/j.ic.2021.104743
复制
发表时间：
2021
影响因子：
1
通讯作者：
Guo, Zhishan
中科院分区：
文献类型：
--
作者：
Liu, Xingwu;Han, Xin;Zhao, Liang;Guo, Zhishan
可调度性是实时系统分析中的一个基本问题，但由于固有的计算难度，通常必须对其进行近似处理。分区最早截止日期优先（EDF）是多处理器平台上最流行的多项式时间和实用调度程序之一，其加速因子最多为2.6322−1/m。本文进一步将约束时限和任意时限的系数提高到2.5556−1/m，非常接近已知的（非紧）下界2.5−1/m。关键思想是我们开发了一种新的方法来离散和正则化在单处理器上可调度的零星任务集，我们发现在任意截止日期情况下，近似需求界值与机器容量的比值（ρ）上界为1.5556，这对估计分区EDF的速度因子起着重要作用。
Schedulability is a fundamental problem in analyzing real-time systems, but it often has to be approximated because of the intrinsic computational hardness. Partitioned earliest deadline first (EDF) is one of the most popular polynomial-time and practical scheduler on multiprocessor platforms, and it was shown to have a speedup factor of at most 2.6322− 1/m. This paper further improves the factor to 2.5556− 1/m for both the constrained-deadline case and the arbitrary-deadline case, and it is very close to the known (non-tight) lower bound of 2.5− 1/m. The key ideas are that we develop a novel method to discretize and regularize sporadic task sets that are schedulable on uniprocessors, and we find that the ratio (ρ) of the approximate demand bound value to the machine capacity is upper-bounded by 1.5556 for the arbitrary-deadline case, which plays an important role in estimating the speed factor of partitioned EDF.
登录
查看更多内容
非抢占式调度的精确加速因子和次优性
影响因子：
1.3
作者：
Robert I. Davis;Abhilash Thekkilakattil;Oliver Gettings;R. Dobrin;S. Punnekkat;Jian
通讯作者：
Jian
关于混合临界可调度性测试的加速界限的最优性
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
Zhishan Guo
通讯作者：
Zhishan Guo
通过利用率和响应时间权衡将零星任务转变为离线调度。
DOI：
--
发表时间：
2011
期刊：
影响因子：
--
作者：
J. Theis;G. Fohler
通讯作者：
G. Fohler
影响因子：
3.7
作者：
Kunal Agrawal;Sanjoy Baruah
通讯作者：
Sanjoy Baruah
同步周期性任务系统的 EDF 可调度性是共难点
DOI：
--
发表时间：
2010
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
F. Eisenbrand;T. Rothvoss
通讯作者：
T. Rothvoss