Optimal read-once parallel disk scheduling
Mahesh Kallahalla, Peter Varman · 1999
We present a" optimal algorithm, LOPT, for prefetching and UO scheduling in parallel UO systems using a read-once model of block reference.The algorithm usesknowledge of the next L block references, L-block lookahead, to schedule UOs in a" on-line manner.It uses a dynamic priority assiwent scheme to decide when blocks should be prefetched, so as to minimize the total number of UOs.The parallel disk model of a" UO system is used tu study the perfonnancc of L-OPT.We show that L-OFT is comparable to the best on-line algorithm with the same amuun, of lookahead; the ratio of the length of its schedule to the length of the optimal schedule is within a constant factor of the best possible show that the competitive ratio of LOFT is 0( matches the lower bound on the competitive ratio of any prefetching algorithm with L-block lookahead.I" addition we show that when the lookahead consists of the entire reference string, LOFT perfmms the tibnmu possible number of UOs; hence L-OFT is the optimal &line algorithm.Finally, using synthetic traces we empirically study the perfonnancc characteristics of LOFT.