ALCOMFT-TR-03-32

Joan Boyar, Lene M. Favrholdt and Kim S. Larsen
The Relative Worst Order Ratio Applied to Paging
Århus. Work package 4. September 2003.

Abstract: The relative worst order ratio, a new measure for the quality of on-line algorithms, was previously defined by Boyar and Favrholdt. The first studies of this new measure considered two bin packing problems. Here, we apply it to the paging problem.

A new deterministic paging algorithm, Retrospective-LRU, is shown to perform better than LRU according to the relative worst order ratio. This algorithm is neither conservative nor a marking algorithm. LRU is also compared to other algorithms and found to be better than FWF and PERM(pi), which have the same competitive ratio as LRU, but to have the same performance as all conservative algorithms.

Finally, look-ahead is considered and shown to be a significant advantage according to the relative worst order ratio. This is in contrast to the competitive ratio which does not reflect that look-ahead can be helpful.

Postscript file: ALCOMFT-TR-03-32.ps.gz (124 kb).