Proceedings of the ACM Sigmetrics Conference 1994, pp. 241­251.

Scheduling Algorithms for Modern Disk Drives

Bruce L. Worthington, Gregory R. Ganger, Yale N. Patt

Department of Electrical Engineering and Computer Science
University of Michigan
Ann Arbor, MI 48109­2122

Abstract

Disk subsystem performance can be dramatically improved by dynamically ordering, or scheduling, pending requests. Via strongly validated simulation, we examine the impact of complex logical­to­physical mappings and large prefetching caches on scheduling effectiveness. Using both synthetic workloads and traces captured from six different user environments, we arrive at three main conclusions: (1) Incorporating complex mapping information into the scheduler provides only a marginal (less than 2%) decrease in response times for seek­reducing algorithms. (2) Algorithms which effectively utilize prefetching disk caches provide significant performance improvements for workloads with read sequentiality. The cyclical scan algorithm (C­LOOK), which always schedules requests in ascending logical order, achieves the highest performance among seek­reducing algorithms for such workloads. (3) Algorithms that reduce overall positioning delays produce the highest performance provided that they recognize and exploit a prefetching cache.

Available Online