Advertisement
Published in:
2006 | OriginalPaper | Chapter
Online Sorting Buffers on Line
Authors : Rohit Khandekar, Vinayaka Pandit
Published in: STACS 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider the online scheduling problem for sorting buffers on a line metric, motivated by an application to disc scheduling. Input is an online sequence of requests. Each request is a block of data to be written on a specified track of the disc. To write a block on a particular track, the scheduler has to bring the disc head to that track. The cost of moving the disc head from a track to another is the distance between those tracks. A sorting buffer that can store at most
k
requests at a time is available to the scheduler. This buffer can be used to rearrange the input sequence. The objective is to minimize the total cost of head movement while serving the requests. On a disc with
n
uniformly-spaced tracks, we give a randomized online algorithm with a competitive ratio of
O
(log
2
n
) in expectation against an oblivious adversary. We show that any deterministic strategy which makes scheduling decisions based only on the contents of the buffer has a competitive ratio of Ω(
k
) or Ω(log
n
/loglog
n
).