Adaptive Replacement Algorithm Templates and EELRU - Advanced Operating Systems and Kernel Applications - page 273

importantly, when EELRU does not yield fewer
misses than LRU, its adaptive mechanism, in
practice, yields at worst approximately a 16%
increase in misses over LRU. That is, EELRU
commonly improves upon LRU, and when it
cannot, it does little to no harm.
First, we examine the how much of the po-
tential improvement over LRU that EELRU
obtains. This table shows the percentage of that
potential improvement for each of a group of
benchmark applications over a wide range of
memory sizes. (We filtered out memory sizes for
which few misses occur, since differences may
seem disproportionately large. We do not show

memory sizes for which the program suffers few
faults. In particular, we present statistics for all
memory sizes m, at which LRU incurs at least
m misses.)
For example, consider a program and a memory
size where, under the optimal policy, OPT, the
system would incur 100 main memory misses,
while under LRU, it would incur 200 misses. If
EELRU incurred 200 misses, then it would obtain
0% of the potential improvement. At 175 misses,
EELRU would obtain 25% of the potential im-
provement. Finally, at 225 misses, EELRU would
obtain -25% of that possible improvement.
On one hand, Table 1 shows that there are

Table 2.

Program name Increase in number of misses

acrord32 9.45%

applu 5.42%

cc1 9.96%

compress95 0.99%

espresso 4.57%

gcc-2.7.2 8.26%

gnuplot 3.55%

go 3.85%

grobner 3.80%

gs3.33 10.89%

ijpeg 5.68%

lindsay 2.74%

m88ksim 1.66%

murphi 4.13%

netscape 11.23%

p2c 1.57%

perl-etch -3.46%

perl-wisconsin 7.52%

photoshp 14.87%

powerpnt 16.38%

trygtsl -1.41%

vortex 4.27%

wave5 -8.86%

winword 9.10%