Abstract
The paging algorithm Least Recently Used Second Last Request (LRU-2) was proposed for use in database disk buffering and shown experimentally to perform better than Least Recently Used (LRU). 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 2k for cache size k, which is worse than LRU’s competitive ratio of k. However, using relative worst order analysis, we show that LRU-2 and LRU are comparable in LRU-2’s favor, giving a theoretical justification for the experimental results. Many of our results for LRU-2 also apply to its generalization, Least Recently Used Kth Last Request.
Original language | English |
---|---|
Journal | Acta Informatica |
Volume | 47 |
Issue number | 7-8 |
Pages (from-to) | 359-374 |
Number of pages | 16 |
ISSN | 0001-5903 |
DOIs | |
Publication status | Published - 2010 |