Proceedings of the ACM Sigmetrics Conference 1994, pp. 241251.
Scheduling Algorithms for Modern Disk Drives
Bruce L. Worthington, Gregory R. Ganger, Yale N. Patt
Department of Electrical Engineering
and Computer Science
Disk subsystem performance can be dramatically improved by dynamically ordering, or scheduling, pending requests. Via strongly validated simulation, we examine the impact of complex logicaltophysical 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 seekreducing algorithms. (2) Algorithms which effectively utilize prefetching disk caches provide significant performance improvements for workloads with read sequentiality. The cyclical scan algorithm (CLOOK), which always schedules requests in ascending logical order, achieves the highest performance among seekreducing algorithms for such workloads. (3) Algorithms that reduce overall positioning delays produce the highest performance provided that they recognize and exploit a prefetching cache.