Scheduling for Modern Disk Drives and
Non-Random Workloads

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

Department of Electrical Engineering and Computer Science
The University of Michigan, Ann Arbor 48109-2122

March 1, 1994

Abstract

Disk subsystem performance can be dramatically improved by dynamically ordering, or scheduling, pending requests. Modern disk drives have several features, such as complex logical-to-physical mappings and large prefetching caches, that can influence scheduling effectiveness. Via strongly validated simulation, we examine the impact of these features on various scheduling algorithms. 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 a prefetching disk cache 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 (five of the six examined). (3) Algorithms that reduce overall positioning delays produce the highest performance provided that they recognize and exploit a prefetching cache.

This postscript version of this report has been broken into three files for on-line access:

• Cover sheet
• Part 1
• Part 2
• pdf