Processor speed and memory capacity are increasing several times faster tha
n disk speed. This disparity suggests that disk I/O performance could becom
e an important bottleneck. Methods are needed for using disks more efficien
tly, Past analysis of disk scheduling algorithms has largely been experimen
tal and little attempt has been made to develop algorithms with provable pe
rformance guarantees.
We consider the following disk scheduling problem. Given a set of requests
on a computer disk and a convex reachability function that determines how f
ast the disk head travels between tracks, our goal is to schedule the disk
head so that it services all the requests in the shortest time possible. We
present a 3/2-approximation algorithm (with a constant additive term). For
the special case in which the reachability function is linear we present a
n optimal polynomial-time solution.
The disk scheduling problem is related to the special case of the Asymmetri
c Traveling Salesman Problem with the triangle inequality (ATSP-Delta) in w
hich all distances are either 0 or some constant alpha. We show how to find
the optimal tour in polynomial time and describe how this gives another ap
proximation algorithm for the disk scheduling problem. Finally we consider
the on-line version of the problem in which uniformly distributed requests
arrive over time, We present an algorithm related to the above ATSP-Delta.