article

Analysis of methods for scheduling low priority disk drive tasks

Authors:

Jiri SchindlerAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 30, Issue 1

Pages 55 - 65

https://doi.org/10.1145/511399.511342

Published: 01 June 2002 Publication History

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 and Mor Harchol-Balter. Analysis of SRPT scheduling: investigating unfairness. ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems (Cambridge, MA), pages 279-290, June 2001.

Digital Library

[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 and David A. Patterson. Maximizing performance in a striped disk array. UCB/CSD 90/559. Computer Science Div., Department of Electrical Engineering and Computer Science, University of California at Berkeley, February 1990.

Digital Library

[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 and algorithms,19:438-471, 2001.

Digital Library

[6]

Leonard Kleinrock. Queueing systems volume I: theory. John Wiley and Sons, 1975.

Digital Library

[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.

Digital Library

[8]

A. Merchant and P. S. Yu. An analytical model of reconstruction time in mirrored disks. Performance Evaluation,20(1-3):115-129, May 1994.

Digital Library

[9]

Richard R. Muntz and John C. S. Lui. Performance analysis of disk arrays under failure. International Conference on Very Large Databases (Brisbane, Australia), pages 162-173, 13-16 August 1990.

Digital Library

[10]

David A. Patterson, Garth Gibson, and Randy H. Katz. A case for redundant arrays of inexpensive disks (RAID). ACM SIGMOD International Conference on Management of Data (Chicago, IL), pages 109-116, 1-3 June 1988.

Digital Library

[11]

Yuri Pavlov. The asymptotic distribution of maximum tree size in a random forest. Theory of probability and applications,22:509-520, 1977.

[12]

Boris Pittel. Linear probing: The probable largest search time grows logarithmically with the number of records. Journal of algorithms,8:236-249, 1987.

Digital Library

[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 and John K. Ousterhout. The design and implementation of a log-structured file system. ACM Symposium on Operating System Principles (Asilomar, Pacific Grove, CA). Published as Operating Systems Review,25(5):1-15, 13-16 October 1991.

Digital Library

[16]

Chris Ruemmler and John Wilkes. An introduction to disk drive modeling. IEEE Computer,27(3):17-28, March 1994.

Digital Library

[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 L. Griffin, Christopher R. Lumb, and Gregory R. Ganger. Track-aligned extents: matching access patterns to disk drive characteristics. Conference on File and Storage Technologies (Monterey, CA, 28-30 January 2002), pages 259-274. USENIX Association, 2002.

Digital Library

[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]

A. Thomasian and A. Tantawi. Approximate solutions for M/G/1 fork-join synchronization. Winter Simulation Conference, December 1994.

Digital Library

[22]

Alexander Thomasian and Jai Menon. Performance analysis of RAID5 disk arrays with a vacationing server model for rebuild mode operation. International Conference on Data Engineering (Houston, TX), pages 111-119, February 1994.

Digital Library

Cited By

Qin YHoffmann BWang YLilja D(2019)Exploring A Forecasting Structure for the Capacity Usage in Backup Storage Systems2019 IEEE 10th Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON)10.1109/UEMCON47517.2019.8992955(0126-0134)Online publication date: Oct-2019
https://doi.org/10.1109/UEMCON47517.2019.8992955
Huang SLiang SFu SShi WTiwari DChen H(2019)Characterizing Disk Health Degradation and Proactively Protecting Against Disk Failures for Reliable Storage Systems2019 IEEE International Conference on Autonomic Computing (ICAC)10.1109/ICAC.2019.00027(157-166)Online publication date: Jun-2019
https://doi.org/10.1109/ICAC.2019.00027
Qin YHoffmann BLilja D(2018)HyperProtect: Enhancing the Performance of a Dynamic Backup System Using Intelligent Scheduling2018 IEEE 37th International Performance Computing and Communications Conference (IPCCC)10.1109/PCCC.2018.8711182(1-8)Online publication date: Nov-2018
https://doi.org/10.1109/PCCC.2018.8711182
Show More Cited By

Recommendations

Analysis of methods for scheduling low priority disk drive tasks
SIGMETRICS '02: Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

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 ...
Survey and analysis of disk scheduling methods

Performance of many important computer applications depends on the performance of Hard Disk Drives (HDDs). Disk capacities and transfer rates have been increasing rapidly, but the improvement in disk access time is disappointingly slow. Caching and ...
Systems Support for Preemptive Disk Scheduling

Allowing higher-priority requests to preempt ongoing disk IOs is of particular benefit to delay-sensitive and real-time systems. In this paper, we present Semi-preemptible IO, which divides disk IO requests into small temporal units of disk commands to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 30, Issue 1

Measurement and modeling of computer systems

June 2002

286 pages

ISSN:0163-5999

DOI:10.1145/511399

Issue’s Table of Contents

SIGMETRICS '02: Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems
June 2002
299 pages
ISBN:1581135319
DOI:10.1145/511334
General Chair:
Richard Muntz
UCLA
,
Program Chairs:
Margaret Martonosi
Princeton University
,
Edmundo de Souza e Silva
UFRJ, Brazil

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2002

Published in SIGMETRICS Volume 30, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

77
Total Citations
View Citations
484
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Qin YHoffmann BWang YLilja D(2019)Exploring A Forecasting Structure for the Capacity Usage in Backup Storage Systems2019 IEEE 10th Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON)10.1109/UEMCON47517.2019.8992955(0126-0134)Online publication date: Oct-2019
https://doi.org/10.1109/UEMCON47517.2019.8992955
Huang SLiang SFu SShi WTiwari DChen H(2019)Characterizing Disk Health Degradation and Proactively Protecting Against Disk Failures for Reliable Storage Systems2019 IEEE International Conference on Autonomic Computing (ICAC)10.1109/ICAC.2019.00027(157-166)Online publication date: Jun-2019
https://doi.org/10.1109/ICAC.2019.00027
Qin YHoffmann BLilja D(2018)HyperProtect: Enhancing the Performance of a Dynamic Backup System Using Intelligent Scheduling2018 IEEE 37th International Performance Computing and Communications Conference (IPCCC)10.1109/PCCC.2018.8711182(1-8)Online publication date: Nov-2018
https://doi.org/10.1109/PCCC.2018.8711182
Thomasian A(2018)Mirrored and hybrid disk arrays and their reliabilityCluster Computing10.1007/s10586-018-2127-xOnline publication date: 3-Mar-2018
https://doi.org/10.1007/s10586-018-2127-x
Huang ZZhu T(2017)Distributed Real-Time Multimodal Data Forwarding in Unmanned Aerial Systems2017 14th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON)10.1109/SAHCN.2017.7964920(1-9)Online publication date: Jun-2017
https://doi.org/10.1109/SAHCN.2017.7964920
Yan FSmirni E(2016)Workload interleaving with performance guarantees in data centersNOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium10.1109/NOMS.2016.7502934(967-972)Online publication date: Apr-2016
https://doi.org/10.1109/NOMS.2016.7502934
Nijim MPatel PTakale N(2016)Towards high performance and energy efficient storage systems using hybrid heterogeneous computing devices2016 International Conference on Industrial Informatics and Computer Systems (CIICS)10.1109/ICCSII.2016.7462442(1-6)Online publication date: Mar-2016
https://doi.org/10.1109/ICCSII.2016.7462442
Wan JWang JYang QXie C(2010)S2-RAIDProceedings of the 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies (MSST)10.1109/MSST.2010.5496980(1-9)Online publication date: 3-May-2010
https://dl.acm.org/doi/10.1109/MSST.2010.5496980
Sivathanu SLing Liu Ungureanu C(2010)Modeling the performance and energy of storage arraysProceedings of the International Conference on Green Computing10.1109/GREENCOMP.2010.5598308(229-242)Online publication date: 15-Aug-2010
https://dl.acm.org/doi/10.1109/GREENCOMP.2010.5598308
Vicković LMudnić EGotovac S(2009)Parity information placement in the disk array modelCOMPEL - The international journal for computation and mathematics in electrical and electronic engineering10.1108/0332164091099199428:6(1428-1441)Online publication date: 13-Nov-2009
https://doi.org/10.1108/03321640910991994
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents