Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem

摘要

The paging algorithm LRU-2 was proposed for use in database disk buffering and shown experimentally to perform better than LRU [O'Neil, O'Neil, and Weikum, 1993]. We compare LRU-2 and LRU theoretically, using both the standard competitive analysis and the newer relative worst order analysis. The competitive ratio for LRU-2 is shown to be 2κ for cache size κ, which is worse than LRU's competitive ratio of κ. However, using relative worst order analysis, we show that LRU-2 and LRU are asymptotically comparable in LRU-2's favor, giving a theoretical justification for the experimental results.