An Improved Speedup Factor for Sporadic Tasks with Constrained Deadlines Under Dynamic Priority Scheduling
An Improved Speedup Factor for Sporadic Tasks with Constrained Deadlines Under Dynamic Priority Scheduling
复制标题
动态优先级调度下时限有限的零星任务的改进加速因子
DOI：
10.1109/rtss.2018.00058
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Liu, Xingwu
中科院分区：
文献类型：
--
作者：
Han, Xin;Zhao, Liang;Guo, Zhishan;Liu, Xingwu
可调度性是实时调度中的一个基本问题，但由于其固有的计算困难，必须对其进行近似。作为多进程平台上最流行的决定可调度性的算法，分区EDF的加速因子分析具有挑战性，而且远未确定。Partitioned-EDF最早由Barush和Fisher在2005年提出[1]，并且被证明具有最多3-1/m的加速因子，这意味着如果零星任务的输入在速度为1的m个处理器上是可行的，则Partitioned-EDF将始终在速度为3-1/m的m个处理器上成功。在2011年，Chen和Chakraborty [2]将这个上限改进为2.6322-1/m，此后没有出现更多的改进。在本文中，我们开发了一种新的方法来离散化和正则化零星任务，这使我们能够提高，在有约束的最后期限的情况下，分区EDF的加速因子为2.5556-1/m，非常接近[2]中的渐近下限2.5。
Schedulability is a fundamental problem in real-time scheduling, but it has to be approximated due to the intrinsic computational hardness. As the most popular algorithm for deciding schedulability on multiprocess platforms, the speedup factor of partitioned-EDF is challenging to analyze and is far from being determined. Partitioned-EDF was first proposed in 2005 by Barush and Fisher [1], and was shown to have a speedup factor at most 3-1/m, meaning that if the input of sporadic tasks is feasible on m processors with speed one, partitioned-EDF will always succeed on m processors with speed 3-1/m. In 2011, this upper bound was improved to 2.6322-1/m by Chen and Chakraborty [2], and no more improvements have appeared ever since then. In this paper, we develop a novel method to discretize and regularize sporadic tasks, which enables us to improve, in the case of constrained deadlines, the speedup factor of partitioned-EDF to 2.5556-1/m, very close to the asymptotic lower bound 2.5 in [2].
登录
查看更多内容
非抢占式调度的精确加速因子和次优性
影响因子：
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