Bruce L. Worthington
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.
- Denn67.P. J. Denning, "Effects of schedtfling on file memory operations", AFIPS Spriug Joint Computer Conference, April 1967, pp. 9-21.Google Scholar
- Gang93.G. Ganger, Y. Part, "The Process-Flow Model: Examining I/O Performance from the System's Point of View", SIGMETRICS, 1993, pp. 86-97. Google ScholarDigital Library
- Geis87.R. Geist, S. Daniel, "A Continuum of Disk Scheduling Algorithms", A CM Transactions on Computer Systems, February 1987, pp. 77-92. Google ScholarDigital Library
- HP92.Hewlett-Pack~d Company, "HP C2240 Series 3.5-inch SCSI-2 Disk Drive, Technical Reference Manual", Part Number 5960-8346, Edition 2, April 1992.Google Scholar
- Jaco91.D. Jacobson, J. Wilkes, "Disk Scheduling Algorithms Based on Rotational Position", Hewlett-Packard Technical Report, HPL-CSP-91-7, Feb. 26, 1991.Google Scholar
- McNu86.B. McNutt, "An Empirical Study of Variations in DASD Volume Activity", CMG, 1986, pp. 274-283.Google Scholar
- Mert70.A. G. Merten, "Some quantitative techniques for file organization", Ph.D. Thesis, Technical Report No. 15, U. of Wisconsin Comput. Center, 1970. Google ScholarDigital Library
- Rama92.K. Ramakrishnan, P. Biswas, R. Karedla, "Analysis of File I/O Traces in Commercial Computing Environments", A CM S{GMETR{CS, 1992, pp. 78-90. Google ScholarDigital Library
- Ruem93.C. Ruemmler, J. Wilkes, "UNIX Disk Access Patterns", Winter USENIX, 1993.Google Scholar
- Ruem94.C. Ruemmler, J. Wilkes, "Modelling Disks", IEEE Co mput e r, March 1994.Google Scholar
- Seam66.P. H. Seaman, R. A. Lind, T. L. Wilson "An analysis of auxillary-storage activity", IBM System Journal, Voi. 5, No. 3, 1966, pp. 158-170.Google ScholarDigital Library
- Selt90.M. Seltzer, P. Chen, J. Ousterhout, "Disk Scheduling Revisited", Wiuter USENIX, 1990, pp. 313-324.Google Scholar
- Teor72.T. Teorey, T. Pinkerton, "A Comparative Analysis of Disk Scheduling Policies", Communications of the A C21I, March 1972, pp. 177-184. Google ScholarDigital Library
- Wort94.B. Worthington, G. Ganger, Y. Putt, "Scheduling for Modern Disk Drives and Non-Random Worldoads", U. of Michigan, Technical Report CSE-TR-194-94, 1994.Google Scholar
Index Terms
- Scheduling algorithms for modern disk drives
Recommendations
Scheduling algorithms for modern disk drives
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 ...
Exploiting the performance gains of modern disk drives by enhancing data locality
Due to the widening performance gap between RAM and disk drives, a large number of I/O optimization methods have been proposed and designed to alleviate the impact of this gap. One of the most effective approaches of improving disk access performance is ...
Implementation and performance of integrated application-controlled file caching, prefetching, and disk scheduling
As the performance gap between disks and micropocessors continues to increase, effective utilization of the file cache becomes increasingly immportant. Application-controlled file caching and prefetching can apply application-specific knowledge to ...
Comments