Quantifying Competitiveness in Paging with Locality of Reference

The classical paging problem is to maintain a two-level memory system so that a sequence of requests to memory pages can be served with a small number of faults. Standard competitive analysis gives overly pessimistic results as it ignores the fact that real-world input sequences exhibit locality of reference. In this paper we study the paging problem using an intuitive and simple locality model that records inter-request distances in the input. A characteristic vector

$$\mathcal{C}$$

C

defines a class of request sequences that satisfy certain properties on these distances. The concept was introduced by Panagiotou and Souza [

19

].

As a main contribution we develop new and improved bounds on the performance of important paging algorithms. A strength and novelty of the results is that they express algorithm performance in terms of locality parameters. In a first step we develop a new lower bound on the number of page faults incurred by an optimal offline algorithm

opt

. The bound is tight up to a small additive constant. Based on these expressions for

opt

’s cost, we obtain nearly tight upper and lower bounds on

lru

’s competitiveness, given any characteristic vector

$$\mathcal{C}$$

C

. The resulting ratios range between 1 and

$$k$$

k

, depending on

$$\mathcal{C}$$

C

. Furthermore, we compare

lru

to

fifo

and

fwf

. For the first time we show bounds that quantify the difference between

lru

’s performance and that of the other two strategies. The results imply that

lru

is strictly superior on inputs with a high degree of locality of reference. In particular, there exist general input families for which

lru

achieves constant competitive ratios whereas the guarantees of

fifo

and

fwf

tend to

$$k$$

k

, the size of the fast memory. Finally, we report on an experimental study that demonstrates that our theoretical bounds are very close to the experimentally observed ones. Hence we believe that our contributions bring competitive paging again closer to practice.