Optimal online buffer scheduling for block devices
Optimal online buffer scheduling for block devices
复制标题
块设备的最佳在线缓冲区调度
DOI：
10.1145/2213977.2214031
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Adamaszek A
中科院分区：
文献类型：
--
作者：
Adamaszek A
我们介绍了一个在线设置块操作设备的缓冲区调度问题。我们考虑由块设备处理的不同类型的项目流。块设备可以在单个步骤中处理相同类型的所有项目。为了提高系统的性能，一个大小为kis的缓冲区用于存储项目，以减少所需的操作次数。每当缓冲区变满时，缓冲区调度策略必须选择一种类型，然后对当前在缓冲区中的具有该类型的所有元素执行块操作。我们的目标是设计一个调度策略，最大限度地减少所需的块操作的数量。在本文中，我们考虑这个问题的在线版本，缓冲区调度策略必须在不知道输入流中出现的未来项目的情况下做出决定。我们的主要结果是设计了一个O（log log k）-竞争的在线随机缓冲区调度策略。这个界是渐近紧的。作为我们的LP为基础的技术的副产品，我们获得了一个随机的离线算法，近似的块操作的最佳数量在一个恒定的因素。
We introduce a buffer scheduling problem for block operation devices in an online setting. We consider a stream of items of different types to be processed by a block device. The block device can process all items of the same type in a single step. To improve the performance of the system a buffer of sizekis used to store items in order to reduce the number of operations required. Whenever the buffer becomes full a buffer scheduling strategy has to select one type and then a block operation on all elements with this type that are currently in the buffer is performed. The goal is to design a scheduling strategy that minimizes the number of block operations required. In this paper we consider the online version of this problem, where the buffer scheduling strategy must make decisions without knowing the future items that appear in the input stream. Our main result is the design of an O(log log k)-competitive online randomized buffer scheduling strategy. The bound is asymptotically tight. As a byproduct of our LP-based techniques, we obtain a randomized offline algorithm that approximates the optimal number of block operations to within a constant factor.
在线度量上排序缓冲区问题的在线和离线算法
DOI：
10.1016/j.jda.2008.08.002
发表时间：
2010
期刊：
J. Discrete Algorithms
影响因子：
--
作者：
R. Khandekar;Vinayaka Pandit
通讯作者：
Vinayaka Pandit
重新排序缓冲区管理的几乎严格限制
DOI：
10.1145/1993636.1993717
发表时间：
2011
期刊：
--
影响因子：
--
作者：
Adamaszek A
通讯作者：
Adamaszek A
DOI：
10.1137/1.9781611973105.70
发表时间：
2012
期刊：
J. Discrete Algorithms
影响因子：
--
作者：
Noa Avigdor;Y. Rabani
通讯作者：
Y. Rabani