Approximating the Optimal Replacement Algorithm

摘要

LRU is the de facto standard page replacement strategy.It is well-known,however,that there are many situations where LRU behaves far from optimal.We present a replacement policy that approximates the optimal algorithm OPT more closely by predicting the time each page will be referenced again and by evicting the page that has the largest predicted time of next reference.Experiments using several bench- marks from the SPEC 2000 benchmark suite show that our algorithm is superior to LRU,in some cases by as much as 25%-30%and in one case by more than 100%.