Minimizing stall time in single and parallel disk systems

We study integrated prefetching and caching problems following the work of Cao ct al. [1995] and Kimbrel and Karlin [1996]. Cao ct al. and Kimbrel and Karlin gave approximation algorithms for minimizing the total elapsed time in single and parallel disk settings. The total elapsed rime is the sum of the processor stall times and the length of the request sequence to be ser ved. We show that an optimum prefetching/caching schedule for a single disk prob lem can be computed in polynomial time, thereby settling an open question b y Kimbrel and Karlin. For the parallel disk problem, we give an approximati on algorithm for minimizing stall time. The solution uses a few extra memor y blocks in cache. Stall time is an important and harder to approximate mea sure for this problem. All of our algorithms are based on a new approach wh ich involves formulating the prefetching/caching problems as linear program s.