Attacking the bottlenecks of backfilling schedulers
Attacking the bottlenecks of backfilling schedulers
复制标题
解决回填调度程序的瓶颈
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Dejan Perkovic
中科院分区：
文献类型：
--
作者：
P. Keleher;D. Zotkin;Dejan Perkovic
回填是一种简单而有效的提高共享空间建筑物利用率的方法。简单的先到先得的方法是无效的，因为大型作业可能会分散可用资源。回填调度器通过允许作业在队列中向前移动来解决这个问题，前提是它们不会延迟后续作业。以前的研究表明，对执行时间的不准确估计可以导致更好的时间表。在本研究的第一部分中，我们描述了这种影响的几个工作负载，并表明，平均减速可以有效地减少系统延长估计的执行时间。此外，我们还表明，可以通过增加执行时间对作业进行排序来直接解决平均作业放缓指标。最后，我们修改我们的排序调度程序，以确保传入的作业可以得到硬保证。由此产生的调度器保证避免饥饿，并执行显着优于以前的调度器。在本研究的第二部分，我们将展示队列随机化以及队列随机化和按作业长度排序的组合如何提高性能。我们表明，这些改进是更好的队列排序的作业长度单独在模拟与实际估计的作业运行时间。我们调查了这些估计的真实的特征，并显示了大范围的高估。为了利用更多的随机化和队列排序，我们消除了保证从EQUIPMENT算法，并显示出显着的改进。最后，我们展示了有限的有用性，这些保证，并表明，队列排序标准可以修改，以防止饥饿的修改后的RISK算法。
Backfilling is a simple and effective way of improving the utilization of space‐sharing schedulers. Simple first‐come‐first‐served approaches are ineffective because large jobs can fragment the available resources. Backfilling schedulers address this problem by allowing jobs to move ahead in the queue, provided that they will not delay subsequent jobs. Previous research has shown that inaccurate estimates of execution times can lead to better backfilling schedules. In the first part of this study, we characterize this effect on several workloads, and show that average slowdowns can be effectively reduced by systematically lengthening estimated execution times. Further, we show that the average job slowdown metric can be addressed directly by sorting jobs by increasing execution time. Finally, we modify our sorting scheduler to ensure that incoming jobs can be given hard guarantees. The resulting scheduler guarantees to avoid starvation, and performs significantly better than previous backfilling schedulers. In the second part of this study, we show how queue randomization and even more a combination of queue randomization and sorting by job length can improve performance. We show that these improvements are better than with queue sorting by job length alone in the simulation with actual estimates of job running times. We investigate the real characteristics of these estimates, and show the wide range of overestimation. To exploit even more randomization and queue sorting, we eliminate guarantees from backfilling algorithm, and show significant improvements. Finally, we show a limited usefulness of these guarantees, and show that queue sorting criteria can be modified to prevent starvation in the modified backfilling algorithm.