New Algorithms for Disk Scheduling |
| |
Authors: | Andrews Bender and Zhang |
| |
Affiliation: | (1) Bell Laboratories, Murray Hill, NJ 07974, USA. \{andrews,ylz\}@research.bell-labs.com., US;(2) Department of Computer Science, State University of New York at Stony Brook, Stony Brook, NY 11794-4400, USA. bender@cs.sunysb.edu. Supported in part by HRL Laboratories and the ISX Corporation., US |
| |
Abstract: | Abstract. Processor speed and memory capacity are increasing several times faster than disk speed. This disparity suggests that disk
I/ O performance could become an important bottleneck. Methods are needed for using disks more efficiently. Past analysis of
disk scheduling algorithms has largely been experimental and little attempt has been made to develop algorithms with provable
performance 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 fast 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 an optimal polynomial-time solution.
The disk scheduling problem is related to the special case of the Asymmetric Traveling Salesman Problem with the triangle
inequality (ATSP-Δ ) in which all distances are either 0 or some constant α . We show how to find the optimal tour in polynomial time and describe how this gives another approximation 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-Δ . |
| |
Keywords: | , Disk scheduling, Approximation algorithms, Asymmetric Traveling Salesman Problem, |
本文献已被 SpringerLink 等数据库收录! |
|