TY - JOUR
T1 - The relative worst order ratio applied to paging
AU - Boyar, Joan
AU - Favrholdt, Lene Monrad
AU - Larsen, Kim Skak
PY - 2007/8/1
Y1 - 2007/8/1
N2 - The relative worst order ratio, a new measure for the quality of on-line algorithms, was recently defined and applied to two bin packing problems. Here, we apply it to the paging problem and obtain the following results: We devise a new deterministic paging algorithm, Retrospective-LRU, and show that it performs better than LRU. This is supported by experimental results, but contrasts with the competitive ratio. All deterministic marking algorithms have the same competitive ratio, but here we find that LRU is better than FWF. According to the relative worst order ratio, no deterministic marking algorithm can be significantly better than LRU, but the randomized algorithm MARK is better than LRU. Finally, look-ahead is shown to be a significant advantage, in contrast to the competitive ratio, which does not reflect that look-ahead can be helpful.
AB - The relative worst order ratio, a new measure for the quality of on-line algorithms, was recently defined and applied to two bin packing problems. Here, we apply it to the paging problem and obtain the following results: We devise a new deterministic paging algorithm, Retrospective-LRU, and show that it performs better than LRU. This is supported by experimental results, but contrasts with the competitive ratio. All deterministic marking algorithms have the same competitive ratio, but here we find that LRU is better than FWF. According to the relative worst order ratio, no deterministic marking algorithm can be significantly better than LRU, but the randomized algorithm MARK is better than LRU. Finally, look-ahead is shown to be a significant advantage, in contrast to the competitive ratio, which does not reflect that look-ahead can be helpful.
KW - On-line algorithms
KW - Relative worst-order ratio
KW - Paging
KW - LRU
KW - RLRU
KW - Look-ahead
U2 - 10.1016/j.jcss.2007.03.001
DO - 10.1016/j.jcss.2007.03.001
M3 - Journal article
SN - 0022-0000
VL - 73
SP - 818
EP - 843
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
IS - 5
ER -