LRU Is Better than FIFO |
| |
Authors: | M Chrobak J Noga |
| |
Affiliation: | (1) Department of Computer Science, University of California, Riverside, CA 92521, USA. marek@cs.ucr.edu., US;(2) Department of Mathematics, University of California, Riverside, CA 92521, USA. jnoga@cs.ucr.edu., US |
| |
Abstract: | In the paging problem we have to manage a two-level memory system, in which the first level has short access time but can
hold only up to k pages, while the second level is very large but slow. We use competitive analysis to study the relative performance of the
two best known algorithms for paging, LRU and FIFO. Sleator and Tarjan proved that the competitive ratio of LRU and FIFO is
k . In practice, however, LRU is known to perform much better than FIFO. It is believed that the superiority of LRU can be
attributed to locality of reference exhibited in request sequences. In order to study this phenomenon, Borodin et al. 2]
refined the competitive approach by introducing the concept of access graphs. They conjectured that the competitive ratio
of LRU on each access graph is less than or equal to the competitive ratio of FIFO. We prove this conjecture in this paper.
Received June 2, 1997; revised January 28, 1998. |
| |
Keywords: | , Paging, Caching, On-line algorithms, Competitive analysis, |
本文献已被 SpringerLink 等数据库收录! |
|