Analysis of methods for scheduling low priority disk drive tasks
- 1 June 2002
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 30 (1) , 55-65
- https://doi.org/10.1145/511334.511342
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.Keywords
This publication has 8 references indexed in Scilit:
- Fast, on-line failure recovery in redundant disk arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Asymptotic distribution for the cost of linear probing hashingRandom Structures & Algorithms, 2001
- Analysis of SRPT schedulingPublished by Association for Computing Machinery (ACM) ,2001
- An analytical model of reconstruction time in mirrored disksPerformance Evaluation, 1994
- An introduction to disk drive modelingComputer, 1994
- The design and implementation of a log-structured file systemPublished by Association for Computing Machinery (ACM) ,1991
- A case for redundant arrays of inexpensive disks (RAID)Published by Association for Computing Machinery (ACM) ,1988
- Linear probing: The probable largest search time grows logarithmically with the number of recordsJournal of Algorithms, 1987