The replacement problem, and why every answer is an approximation

Why is every replacement policy an approximation of an optimal policy that needs the future?

When the pool is full and a new page is needed, the pool must pick a victim to evict. The optimal policy is known exactly: Belady's MIN (1966) evicts the page whose next reference is furthest in the future. It is provably optimal. It also requires the future, so it cannot be computed online. Its only practical use is as a ceiling in trace-driven evaluation (you replay a recorded access log and compute what MIN would have achieved). That use is valuable: it tells you whether a 60% hit rate is a policy failure or a capacity failure.

Everything that ships is an approximation of MIN, and the approximation ladder has two rungs:

1. MIN needs the future, so approximate the future by the past. Which statistic of the past? Recency (LRU), frequency (LFU), or reference rate (LRU-K).
2. That statistic is too expensive to maintain on the hit path, so approximate the statistic. Clock approximates LRU. 2Q approximates LRU-2.

Two stacked approximations of one intractable test, and the second rung is imposed by concurrency, not by information. It is the cleanest example of "a conservative approximation of an intractable test" across the platform, and the first where the approximation is forced twice for two unrelated reasons.

An aside: Belady's anomaly

Adding frames can increase the number of faults. This anomaly afflicts FIFO but not LRU, because LRU is a stack algorithm: the contents with c frames are always a subset of the contents with c+1 frames. That is the one guarantee LRU offers that cheap policies do not. It is why "we gave it more memory and it got slower" is a real and confusing incident report on FIFO-like policies.

One-line compression: MIN needs the future, so policies approximate it by a statistic of the past. Then concurrency forces a second approximation of that statistic.