ABSTRACT

Proceedings of SIGMETRICS 2002 Conference, June 15-19, 2002, Marina Del Rey, California.

Analysis of Methods for Scheduling Low Priority Disk Drive Tasks

Jiri Schindler, Eitan Bachmat*

Dept. Electrical and Computer Engineering
Carnegie Mellon University
Pittsburgh, PA 15213

*Ben-Gurion University
Beer Sheva, Israel

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

FULL PAPER: pdf / postscript