利用马尔可夫服务率策略改进多资源作业调度

《Proceedings of the ACM on Measurement and Analysis of Computing Systems》：Improving Multiresource Job Scheduling with Markovian Service Rate Policies

现代云计算中多资源任务调度需平衡资源利用与响应时间。本文提出Markovian Service Rate（MSR）调度政策，证明其吞吐量最优且可应用于不同抢占系统。通过推导响应时间紧加常数界，为系统参数选择提供理论依据。

　　

摘要

现代云计算工作负载由多资源作业组成，这些作业需要各种计算资源才能运行，例如CPU核心、内存、磁盘空间或硬件加速器。单个云服务器通常可以并行运行许多多资源作业，但前提是服务器具有足够的资源来满足每个作业的需求。因此，调度策略必须选择一组多资源作业进行并行运行，以最小化作业的平均响应时间——即从作业到达系统到完成作业的平均时间。不幸的是，通过选择能够充分利用可用服务器资源的作业集来实现低响应时间已被证明是一个难题。

在本文中，我们开发并分析了一类新的多资源作业调度策略，称为马尔可夫服务率（MSR）策略。虽然之前的多资源作业调度策略要么分析起来非常复杂，要么难以实现，但我们的MSR策略实现简单，并且适合进行响应时间分析。我们证明了MSR策略类是吞吐量最优的，因为只要可能，我们就可以使用MSR策略来稳定系统。我们还推导出了MSR算法下平均响应时间的界限，这些界限与一个加法常数相差很小。这些界限可以应用于具有不同抢占行为的系统，例如完全抢占式系统、非抢占式系统以及允许带有设置时间的抢占的系统。我们展示了如何根据系统到达率、作业服务需求、服务器的资源容量以及作业的资源需求来选择合适的MSR策略。