= LRU stack property
{c}
{title2=$R_k(t)\subseteq R_{k+1}(t)$}
For exact <LRU replacement>, let $R_k(t)$ be the <resident set> after the first $t$ accesses of a fixed <page-reference trace> with capacity $k$. With empty starts, identical access order, freely placeable <memory pages>, and all resident <memory pages> eligible for eviction,
$$
R_k(t)\subseteq R_{k+1}(t)\qquad\text{for every }t\geq0.
$$
Here $\subseteq$ means <subset>. At every time, form one capacity-independent ordered list of distinct <memory pages>, most recently accessed first. An access moves its <memory page> to the front, preserving the order of the others. Exact <LRU replacement> with $k$ <page frames> retains the first $k$ entries, or all entries if fewer than $k$ have appeared. The first $k$ entries are contained in the first $k+1$, proving the property. This recency list is not the push/pop interface of a <LIFO stack>.<Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others/Beyond Physical Memory: Policies>[Belady's Anomaly aside, p. 5: stack-property inclusion and its consequence for LRU; section 22.7, p. 11: exact recency must be updated on every access]{ref}
Apply inclusion immediately before an access: a hit with $k$ <page frames> must also hit with $k+1$. Thus cumulative misses with $k+1$ cannot exceed those with $k$, at any prefix of the same <page-reference trace>. On the displayed <sequence>, the counts decrease from ten to eight when capacity increases from three to four. Arbitrary initial contents, different access orders, protected victims, or clean-victim preference fall outside the proof. Nor does it prove monotonic <page writeback> costs, or apply automatically to <CLOCK page replacement> just because that policy approximates <LRU replacement>.
// Destination: computer-science.bigb
Back to article page
