一种用于优化尾延迟的Gittins策略

《Proceedings of the ACM on Measurement and Analysis of Computing Systems》：A Gittins Policy for Optimizing Tail Latency

在轻尾M/G/1队列中，当工作负载大小未知时，本文提出一种基于改进Gittins策略的调度算法，通过引入负折扣率实现强尾最优性，该方案扩展了γ-Boost的性能边界，并适用于部分已知工作负载的系统。

　　

摘要

我们研究了在M/G/1排队系统中，如何在未知作业大小的情况下安排任务以最小化渐进尾延迟的问题。当作业大小分布具有重尾特性时，已知有许多不需要作业大小信息的调度策略（例如处理器共享、最小服务时间策略）具有很强的尾部分优性，这意味着它们的响应时间尾部具有最快的渐进衰减速度。相比之下，对于轻尾分布的作业大小，直到最近几年才出现了性能优于简单先来先服务（FCFS）的调度策略。其中最新的一种是γ-Boost，在轻尾环境下实现了强尾部分优性。然而，到目前为止，所有在轻尾环境下性能优于FCFS的策略（包括γ-Boost）都需要已知作业大小。在本文中，我们设计了一种新的调度策略，该策略能够在未知作业大小的轻尾M/G/1系统中实现强尾部分优性。令人惊讶的是，最优策略实际上是Gittins策略的一个变体，但它具有一个新颖且不寻常的特点：它使用了一个负折扣率。我们的研究也适用于对作业大小只有部分信息的系统，在作业大小完全已知的情况下，γ-Boost可以被视为一个极端情况。

可用格式

您可以通过以下格式查看完整内容：

PDF