PSBS: Practical Size-Based Scheduling
PSBS: Practical Size-Based Scheduling
复制标题
DOI：
10.1109/tc.2015.2468225
复制
发表时间：
2014-10
影响因子：
3.7
通讯作者：
Matteo Dell'Amico;D. Carra;Pietro Michiardi
中科院分区：
文献类型：
--
作者：
Matteo Dell'Amico;D. Carra;Pietro Michiardi
基于大小的调度器具有非常理想的性能特性：最优或接近最优的响应时间可以与很强的公平性相结合。然而，尽管如此，这样的系统很少在实际环境中实施，因为它们需要先验地知道完成作业所需的工作量：这一假设在具体系统中很难满足。它肯定更有可能通知系统一个工作规模的估计，但现有的研究指出，如果基于规模的政策使用不准确的工作规模估计，结果有些悲观。我们的目标是设计明确处理不精确作业大小的调度策略。首先，我们证明了在没有错误的情况下，通过设计一种基于大小的调度策略来改进任何调度策略总是可能的：在新的调度策略中，没有任何作业会比原始调度策略更晚完成。不幸的是，当作业大小严重倾斜时，基于大小的调度程序可能会在作业大小信息不准确的情况下表现不佳；我们表明，这个问题以及文献中显示的悲观结果是由于低估大型作业时的问题行为造成的。一旦发现问题，就可以修改基于大小的调度程序来解决问题。我们推广了FSP-一种公平有效的基于大小的调度策略-来解决上面突出显示的问题；此外，我们的解决方案处理了不同的作业权重(可以独立于作业的大小分配给作业)。我们提供了所得到的协议的有效实现，我们称之为实用的基于大小的调度器(PSB)。通过对合成和实际工作负载的模拟评估，我们证明了PSB在各种尺寸信息不准确的情况下具有接近最优的性能，它的性能是公平的，并且它正确地处理了作业权重。我们相信，这项工作表明PSB确实是实用的，我们认为它可以启发大量现实世界用例中的调度器设计。
Size-based schedulers have very desirable performance properties: optimal or near-optimal response time can be coupled with strong fairness. Despite this, however, such systems are rarely implemented in practical settings, because they require knowing a priori the amount of work needed to complete jobs: this assumption is difficult to satisfy in concrete systems. It is definitely more likely to inform the system with an estimate of the job sizes, but existing studies point to somewhat pessimistic results if size-based policies use imprecise job size estimations. We take the goal of designing scheduling policies that explicitly deal with inexact job sizes. First, we prove that, in the absence of errors, it is always possible to improve any scheduling policy by designing a size-based one that dominates it: in the new policy, no jobs will complete later than in the original one. Unfortunately, size-based schedulers can perform badly with inexact job size information when job sizes are heavily skewed; we show that this issue, and the pessimistic results shown in the literature, are due to problematic behavior when large jobs are underestimated. Once the problem is identified, it is possible to amend size-based schedulers to solve the issue. We generalize FSP-a fair and efficient size-based scheduling policy-to solve the problem highlighted above; in addition, our solution deals with different job weights (that can be assigned to a job independently from its size). We provide an efficient implementation of the resulting protocol, which we call Practical Size-Based Scheduler (PSBS). Through simulations evaluated on synthetic and real workloads, we show that PSBS has near-optimal performance in a large variety of cases with inaccurate size information, that it performs fairly and that it handles job weights correctly. We believe that this work shows that PSBS is indeed pratical, and we maintain that it could inspire the design of schedulers in a wide array of real-world use cases.