A Study of Replacement Algorithms for a Virtual-Storage Computer

Original paper: A study of replacement algorithms for a virtual-storage computer. L. A. Belady. 1966

The paper addresses a fundamental problem: when a computer's physical memory is full and a new page needs to be loaded, which existing page should be removed (replaced)?

MIN algorithm: The theoretically optimal strategy is to replace the page that won't be used for the longest time in the future
3 classes of replacement:
1. No history (RAND, FIFO)
2. Recent history (AR-1, LT (LRU))
3. Global Program State (ATLAS)
Smaller blocks reduce replacements, space savings by using medium sized blocks (TL;DR block size matters)

This paper does not present the formal proof that this algorithm is the theoretically optimal solution

Forward notes

According to this paper, AR-1 is the best, but over time due to hardware integration LRU is now the industry standard.

References

L. A. Belady. 1966. “A study of replacement algorithms for a virtual-storage computer.” http://ieeexplore.ieee.org/document/5388441/.