*Edith Cohen **
Haim Kaplan
Uri Zwick *AT&T Labs-Research
School of Computer Science
180 Park Avenue
Tel-Aviv University
Florham Park, NJ 07932 USA
Tel Aviv 69978, Israel
` {edith}@research.att.com`
` {haimk,zwick}@post.tau.ac.il`

**April 22, 2001**

We present a competitive analysis of the LRFU paging
algorithm, a hybrid of the LRU (Least Recently Used) and
LFU (Least Frequently Used) paging algorithms. We show
that the competitive ratio of LRFU is
,
where
is the decay parameter used
by the LRFU algorithm, and *k* is the size of the cache.
This supplies, in particular, the first natural paging
algorithms that are competitive but are not optimally
competitive, answering a question of Borodin and
El-Yaniv. Although LRFU, as it turns out, is not
optimally competitive, it is expected to behave well in
practice, as it combines
the benefits of both LRU and LFU.

- 1.
- Each page
*p*currently in the cache has a value*v*(*p*) associated with it. - 2.
- Upon a request for a page
*q*, the following operations are performed:- (a)
- If a page has to be evicted to make room for
*q*, then the page with the smallest value is evicted. (Ties are broken arbitrarily.) The new page*q*is temporarily given the value . - (b)
- The values of the pages in the cache are updated as follows:

It follows that if a page *p* is in the cache at time *t* and if
the hits to this page, since it last entered the cache, were at times
,
then its value at time *t* is
.
Note that the value *v*(*p*) of a page
is always *smaller* than
.
In particular, if
,
then LRFU
behaves just like LRU, since the most recent request time dominates the
value of the page (that is,
*v*(*p*_{1})<*v*(*p*_{2}) if and only if the most recent
request to *p*_{1} occured before the most recent request to *p*_{2}).
If ,
then LRFU
behaves just
like LFU. It is well known that LRU has an optimal competitive
ratio of *k*, while LFU is not competitive. We show that as
increases from
to 1, the competitive ratio of LRFU
increases from *k* to
and assumes all possible integral
values in this range.

**Proof:**As in the classical analysis of LRU (see [#!BoEl98!#],
Chapter 3), we break the sequence of requests into *k**-phases*.
A *k*-phase is a maximal contiguous block of requests in which at
most *k* different pages are requested. The first *k*-phase starts
at the beginning of the sequence and ends just before the (*k*+1)-st
distinct page is referenced. The second block begins immediately
after the first block and so on. It is easy to see that any caching
policy must incur, on average, at least one miss for each
*k*-phase. (More precisely, any caching policy must incur at least
one miss on each *shifted **k**-phase*, where a shifted
*k*-phase is a sequence of requests that begins with the second
request of an ordinary *k*-phase and ends with the first request of
the next ordinary *k*-phase.) To show that LRFU
is
-competitive, we show that LRFU
incurs at most
misses on each *k*-phase.
We first claim that under the LRFU
policy, a page *p* that enters
the cache *after* the first
requests of a *k*-phase stays
in the cache until the end of the phase. This follows from the
interpretation of
given after the statement of
Theorem . When *p* enters the cache, and is assigned the
value 1, the value *v*(*q*) of a page *q* that is currently in the
cache, but was not referenced yet in the current *k*-phase, must satisfy
*v*(*q*)<1. If a miss occurs in the *k*-phase after *p* enters the
cache, then there is at least one page *q* in the cache that was not
referenced yet in the *k*-phase. (If all *k* pages in the cache were
referenced in the current phase then a subsequent miss would end
the phase.) As *v*(*q*)<*v*(*p*), *p* will not be evicted.
It follows, therefore, that at most
misses occur in the first
requests of each *k*-phase (at most one miss per request),
and at most *k* misses occur in the rest of the *k*-phase (at most
one miss per each page that enters the cache after the -th
request). (See Figure .) This completes the proof of
the lemma.

Note that if
then
(i.e.,
if and
only if *p* is the last page referenced), and Lemma states
that the competitive ratio of LRFU_{1/2}= LRU
is *k*. Lemma is therefore an extension of the classical
competitive analysis of the LRU policy.
An easy extension of Lemma is the following:

**Proof:**Follows from the fact any algorithm that uses a cache of size *h* must
incur at least *k*-*h*+1 misses on each shifted *k*-phase.

**Proof:**For every
and
,
we construct an
infinite sequence of requests such that the ratio between the number
of misses incurred by LRFU
and the minimum possible number of
misses needed to serve the sequence approaches .
As in the
classical case of LRU, only *k*+1 distinct pages are needed for
this purpose.
Our sequences are again partitioned into *k*-phases. The state of
the cache at the end of each *k*-phase is isomorphic to the state of
the cache at the beginning of the phase. (This is explained below in
more detail.) We show that LRFU
incurs
misses in each
phase. As there is a total of only *k*+1 pages, the sequence of
requests can be served with only one miss per *k*-phase. (At the first
miss of a phase, the optimal algorithm evicts the page that
is not going to be referenced in that phase.) The claim
of the lemma would thus follow.
Let *L* (for Large) be a sufficiently large number such that after *L*
consecutive requests to a page *p* we have
and
*v*(*q*)<1 for any page *q* such that .
Such
a number exists as by the definition of
we have
.
The first initializing *k*-phase is composed of the following page
requests:

where

where the parentheses around the indices indicate that they should be interpreted modulo

Now, the state of cache at the end of the second phase is similar to its state at the end of the first phase. One page, namely , has value larger than , while all other pages have values that are less than 1. We can therefore use a sequence of requests similar to the one used in the second state, and again create a

This document was generated using the
**LaTeX**2`HTML` translator Version 98.1p1 release (March 2nd, 1998)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:

**latex2html** `-split 1 -no_navigation -show_section_numbers lrfu-html`.

The translation was initiated by Edith Cohen on 2001-08-27