Carnegie Mellon School of Computer Science Technical Report CMU-CS-03-116. February 2003. Superceded by Proceedings of the Ninth Workshop on Hot Topics in Operating systems, USENIX Association, May 2003.
Craig A.N. Soules, Gregory R. Ganger
Electrical and Computer Engineering
Carnegie Mellon University
Pittsburgh, PA 15213
http://www.pdl.cmu.edu
This paper analyzes various algorithms for scheduling low priority disk drive tasks. The derived closed form solution is applicable to a class of greedy algorithms that includes 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: semantic, context, file system, search, attribute-based naming
FULL PAPER, TR VERSION: pdf
FULL PAPER, CONFERENCE VERSION: pdf