Nearly insensitive bounds on SMART scheduling
Nearly insensitive bounds on SMART scheduling
复制标题
SMART 调度的界限几乎不敏感
DOI：
10.1145/1064212.1064236
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
T. Osogami
中科院分区：
文献类型：
--
作者：
A. Wierman;Mor Harchol;T. Osogami
我们定义了智能调度策略类别。这些政策偏向剩余服务时间较小的工作，原始规模较小的工作，或两者兼而有之，以最大程度地减少平均响应时间和/或平均速度放缓的动机。智能策略的示例包括PSJF，SRPT和混合政策，例如RS（根据剩余规模和工作规模的产物偏见）。对于智能类中的许多政策，平均响应时间和平均速度放缓是未知的或具有涉及多个嵌套积分的复杂表示，使评估变得困难。在这项工作中，我们证明了三个主要结果。首先，对于智能类中的所有策略，我们在平均响应时间上证明了简单的上限和下限。其次，我们表明，智能班级中的所有政策都具有非常相似的平均响应时间。第三，我们表明，智能策略的响应时间在很大程度上对工作规模分布的变异性不敏感。特别是，我们专注于SRPT和PSJF政策，并在这些情况下证明了不敏感的界限。
We define the class of SMART scheduling policies. These are policies that bias towards jobs with small remaining service times, jobs with small original sizes, or both, with the motivation of minimizing mean response time and/or mean slowdown. Examples of SMART policies include PSJF, SRPT, and hybrid policies such as RS (which biases according to the product of the remaining size and the original size of a job).For many policies in the SMART class, the mean response time and mean slowdown are not known or have complex representations involving multiple nested integrals, making evaluation difficult. In this work, we prove three main results. First, for all policies in the SMART class, we prove simple upper and lower bounds on mean response time. Second, we show that all policies in the SMART class, surprisingly, have very similar mean response times. Third, we show that the response times of SMART policies are largely insensitive to the variability of the job size distribution. In particular, we focus on the SRPT and PSJF policies and prove insensitive bounds in these cases.