A short proof of optimality for the MIN cache replacement al

A Short Proof of Optimality for

the MIN Cache Replacement Algorithm

Benjamin Van Roy

Stanford University

November 10,2006

Abstract

The MIN algorithm is an of?ine strategy for deciding which item to replace when writing a new item to a cache.Its optimality was ?rst established by Mattson,Gecsei,Slutz,and Traiger [2]through a lengthy analysis.We provide a short and elementary proof based on a dynamic programming argument.

Keywords:analysis of algorithms,on-line algorithms,caching,paging 1The MIN Algorithm

Consider the management of a cache over T time periods given advance knowl-edge of requests ω0,ω1,...,ωT ?1from a set ?of items stored in slower memory.Let S t ??denote the set of items stored in the cache just before ωt is requested.If ωt ∈S t then S t +1=S t .Otherwise,a decision must be made to evict one item from the cache,which is replaced by ωt .The objective is to maximize the number of hits:P T

?1t =01(ωt ∈S t ).

The MIN algorithm chooses to evict an item in the cache whose next request occurs furthest in the future.If there are multiple items that will never again be requested one of them is chosen arbitrarily.Mattson,Gecsei,Slutz,and Traiger [2]establish that this algorithm is optimal.1However,their proof is somewhat long and complicated.The textbook Randomized Algorithms [3]offers an excellent ac-count of several cache replacement algorithms and their analyses.In the case of the MIN algorithm,the authors cite the optimality result of [2]without providing the proof,which they mention to be “nontrivial.”Here we offer a short and elementary proof based on a dynamic programming argument.

1In

[2],this algorithm is referred to as the OPT algorithm.In that work,the term MIN identi?es another algorithm originally proposed in [1].1

2Proof of Optimality

Let J t(S t)denote the maximum possible number of hits to occur starting with the t th request.The dynamic programming recursion takes the form

J t(S t)=1(ωt∈S t)+max

S t+1∈U t(S t)

J t+1(S t+1),for t

U t(S t)={S?S t∪ωt:ωt∈S,|S|=|S t|},

is the set of possible successive states.The state S t+1∈U t(S t)is an optimal choice if and only if it attains the maximum in the above equation.

Denote the time of an item’s next request byτt(ω)=min{t≤z

d t(S,S )=min

h∈matchings ??

?{ω∈S|τt(ω)>τt(h(ω))}

??

?.

This is the minimum among matchings of the number of items in S requested after matched items in S .

The MIN algorithm evicts the item to be requested furthest in the future. Hence,if S t+1is chosen by the MIN algorithm and Z∈U t(S t)is some other feasible choice then d t+1(S t+1,S )≤d t+1(Z,S )for any cache state S .In

other words,S t+1∈argmin Z∈U

t(S t)d t+1(Z,S )for all S .

The following lemma shows how d t can be used to bound differences among values of cache states.

Lemma1.J t(S )?J t(S)≤d t(S,S )for all t≤T and S,S ??with |S|=|S |.

Proof:Since J T(S)=J T(S )=0and d T(S,S )=0,the result holds for t=T.We proceed by weak induction.Fix t

Let S t=S and S t=S .Let S t+1∈U t(S t)be chosen by an optimal strategy.Let S t+1∈U t(S t)be chosen by the MIN algorithm,and note that this

implies S t+1∈argmin Z∈U

t(S t)d t+1(Z,S t+1).We study the relationship be-

tween d t(S t,S t)and d t+1(S t+1,S t+1)in four cases:

Case1:Both S t and S t are hit byωt.Neither cache state changes,so d t+1(S t+1,S t+1)= d t(S t,S t).

Case2:Neither S t nor S t are hit byωt.If S t evicts an item,S t can evict the same item.It follows that d t+1(S t+1,S t+1)≤d t(S t,S t).

Case3:Only S t is hit byωt.S t evicts an item and at best this improves its relative standing by1;that is,d t+1(S t+1,S t+1)≤d t(S t,S t)+1.

Case4:Only S t is hit byωt.S t was previously disadvantaged relative to S t by

not holdingωt but now by replacing the item to be requested furthest in the future

withωt,this disadvantage vanishes.Hence,d t+1(S t+1,S t+1)≤d t(S t,S t)?1. These four relations together imply that

d t+1(S t+1,S t+1)≤d t(S t,S t)+1(ωt∈S t)?1(ωt∈S t).

2

Using this relation,the dynamic programming recursion,and our inductive hy-pothesis,we obtain

J t(S t)=1(ωt∈S t)+J t+1(S t+1)

≤1(ωt∈S t)+d t+1(S t+1,S t+1)+J t+1(S t+1)

≤1(ωt∈S t)+d t(S t,S t)+J t+1(S t+1)

J t+1(Z)+d t(S t,S t)

≤1(ωt∈S t)+max

Z∈U t(S t)

=J t(S t)+d t(S t,S t).

2 Given S t,let S t+1be a successive cache state selected by the MIN algo-rithm and let S t+1be a successive cache state selected by an optimal strategy. Since S t+1minimizes d t+1(S t+1,S t+1)over the set U t(S t)which contains S t+1, d t+1(S t+1,S t+1)=0.By the optimality of S t+1and Lemma1,

0≤J t+1(S t+1)?J t+1(S t+1)≤d t+1(S t+1,S t+1).

It follows that J t+1(S t+1)=J t+1(S t+1),and therefore,a decision made by the MIN algorithm is optimal.

Acknowledgments

Balaji Prabhakar introduced the author to the MIN algorithm,its history,and the interest in obtaining a simpler proof of optimality.

References

[1]L.A.Belady.A study of replacement algorithms for virtual storage computers.

IBM Systems Journal,5(2):78–101,1966.

[2]R.L.Mattson,J.Gecsei,D.R.Slutz,and I.L.Traiger.Evaluation techniques

for storage hierarchies.IBM Systems Journal,9(2):78–117,1970.

[3]R.Motwani and P.Raghavan.Randomized Algorithms.Cambridge University

Press,1995.

3

本文来源：https://www.bwwdw.com/article/ldqq.html