论文标题
在流量繁忙的多种工具job模型中的最佳调度
Optimal Scheduling in the Multiserver-job Model under Heavy Traffic
论文作者
论文摘要
在许多服务器上工作需要并发服务的多功能job系统在实践中广泛发生。从本质上讲，关于多种工具job系统的所有理论工作都集中在最大化利用率上，几乎对平均响应时间一无所知。在更简单的设置中，例如各种已知大小的单人助理设置，最大程度地减少平均响应时间只是优先考虑小工作的问题。但是，对于多种工作员 - 工作系统，优先考虑小型作业是不够的，因为我们还必须确保服务器不会不必要地闲置。因此，最大程度地减少平均响应时间需要优先考虑小工作，同时使吞吐量最大化。我们的问题是如何实现这些共同目标。 我们设计了ServerFilling-SRPT调度策略，这是第一个在繁重的交通限制中最小化多级job模型中平均响应时间的策略。除了证明这种重型交通效果外，我们还提供了经验证据，表明服务器填充SRPT的表现优于所有负载的所有现有调度策略，并在较高的负载下通过数量级进行改进。 由于ServerFilling-SRPT需要了解工作尺寸，因此我们还定义了ServerFilling-Gittins策略，当大小未知或部分已知时，这是最佳的。
Multiserver-job systems, where jobs require concurrent service at many servers, occur widely in practice. Essentially all of the theoretical work on multiserver-job systems focuses on maximizing utilization, with almost nothing known about mean response time. In simpler settings, such as various known-size single-server-job settings, minimizing mean response time is merely a matter of prioritizing small jobs. However, for the multiserver-job system, prioritizing small jobs is not enough, because we must also ensure servers are not unnecessarily left idle. Thus, minimizing mean response time requires prioritizing small jobs while simultaneously maximizing throughput. Our question is how to achieve these joint objectives. We devise the ServerFilling-SRPT scheduling policy, which is the first policy to minimize mean response time in the multiserver-job model in the heavy traffic limit. In addition to proving this heavy-traffic result, we present empirical evidence that ServerFilling-SRPT outperforms all existing scheduling policies for all loads, with improvements by orders of magnitude at higher loads. Because ServerFilling-SRPT requires knowing job sizes, we also define the ServerFilling-Gittins policy, which is optimal when sizes are unknown or partially known.
