Analysis of methods for scheduling low priority disk drive tasks

ABSTRACT

This paper analyzes various algorithms for scheduling low priority disk drive tasks. The derived closed form solution is applicable to class of greedy algorithms that include a variety of background disk scanning applications. By paying close attention to many characteristics of modern disk drives, the analytical solutions achieve very high accuracy---the difference between the predicted response times and the measurements on two different disks is only 3% for all but one examined workload. This paper also proves a theorem which shows that background tasks implemented by greedy algorithms can be accomplished with very little seek penalty. Using greedy algorithm gives a 10% shorter response time for the foreground application requests and up to a 20% decrease in total background task run time compared to results from previously published techniques.

REFERENCES

• 1: Nikhil Bansal , Mor Harchol-Balter, Analysis of SRPT scheduling: investigating unfairness, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.279-290, June 2001, Cambridge, Massachusetts, United States
• 2: O. J. Boxma and J. W. Cohen. The M/G/1 queue with permanent customers. Journal of Selected Areas in Communications,9:(2)179-184, February 1991.
• 3: Peter M Chen , David A. Patterson, Maximizing Performance in a Striped Disk Array, University of California at Berkeley, Berkeley, CA, 1990
• 4: Mark Holland, Garth A. Gibson, and Daniel P. Siewiorek. Fast, on-line failure recovery in redundant disk arrays. 23rd International Symposium on Fault-Tolerant Compter Systems (Toulouse, France, 22-24 June 1993), pages 422-431. IEEE Computing Services, August 1993.
• 5: Svante Janson, Asymptotic distribution for the cost of linear probing hashing, Random Structures & Algorithms, v.19 n.3-4, p.438-471, October-December 2001 [doi>10.1002/rsa.10009]
• 6: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 7: Christopher R. Lumb, Jiri Schindler, Gregory R. Ganger, David F. Nagle, and Erik Riedel. Towards higher disk head utilization: extracting free bandwidth from busy disk drives. Symposium on Operating Systems Design and Implementation (San Diego, CA, 23-25 October 2000), pages 87-102. USENIX Association, 2000.
• 8: Arif Merchant , Philip S. Yu, An analytical model of reconstruction time in mirrored disks, Performance Evaluation, v.20 n.1-3, p.115-129, May 1994
• 9: Richard R. Muntz , John C. S. Lui, Performance analysis of disk arrays under failure, Proceedings of the sixteenth international conference on Very large databases, p.162-173, September 1990, Brisbane, Australia
• 10: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States
• 11: Yuri Pavlov. The asymptotic distribution of maximum tree size in a random forest. Theory of probability and applications,22:509-520, 1977.
• 12: B. Pittel, Linear probing: the probable largest search time grows logarithmically with the number of records, Journal of Algorithms, v.8 n.2, p.236-249, June 1987 [doi>10.1016/0196-6774(87)90040-X]
• 13: Quantum Corporation. Quantum Atlas 10K II 9.2/18.4/36.7/73.4 GB Ultra 160/m S product manual, Document number 81-122517-04, June 2000.
• 14: Erik Riedel, Christos Faloutsos, Greg Ganger, and David Nagle. Data mining on an OLTP system (nearly) for free. Technical report CMU-CS-99-151. Carnegie-Mellon University, Pittsburgh, PA, June 1999.
• 15: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.1-15, October 13-16, 1991, Pacific Grove, California, United States
• 16: Chris Ruemmler , John Wilkes, An introduction to disk drive modeling, Computer, v.27 n.3, p.17-28, March 1994 [doi>10.1109/2.268881]
• 17: Jiri Schindler and Gregory R. Ganger. Automated disk drive characterization. Technical report CMU-CS-99-176. Carnegie-Mellon University, Pittsburgh, PA, December 1999.
• 18: Jiri Schindler , John Linwood Griffin , Christopher R. Lumb , Gregory R. Ganger, Track-Aligned Extents: Matching Access Patterns to Disk Drive Characteristics, Proceedings of the Conference on File and Storage Technologies, p.259-274, January 28-30, 2002
• 19: Seagate. Seagate Cheetah X15 FC disk drive ST318451FC/FCV product manual, volume 1, Document number 83329486, June 2000.
• 20: Hideaki Takagi. Queueing Analysis Volume 1: Vacations and Priority Systems. North-Holland, 1991.
• 21: Alexander Thomasian , Asser N. Tantawi, Approximate solutions for M/G/1 fork/join synchronization, Proceedings of the 26th conference on Winter simulation, p.361-368, December 11-14, 1994, Orlando, Florida, United States
• 22: Alexander Thomasian , Jai Menon, Performance Analysis of RAID5 Disk Arrays with a Vacationing Server Model for Rebuild Mode Operation, Proceedings of the Tenth International Conference on Data Engineering, p.111-119, February 14-18, 1994