The Optimal Replacement Policy

Explore the optimal replacement policy developed by Belady to understand how virtual memory management can minimize cache misses. This lesson explains the theory behind selecting pages to evict by predicting future usage, compares it with practical policies, and illustrates its role as a benchmark for evaluating real-world algorithms. Gain insights into cache miss types and how this policy leads to the fewest cache misses overall.

We'll cover the following...

- About the policy
- Example

About the policy

To better understand how a particular replacement policy works, it would be nice to compare it to the best possible replacement policy. As it turns out, such an optimal policy was developed by Belady many years ago (he originally called it MIN)“A Study of Replacement Algorithms for Virtual-Storage Computer” by Laszlo A. Belady. IBM Systems Journal 5(2): 78-101, 1966. The paper that introduces the simple way to compute the optimal behavior of a policy (the MIN algorithm).. The optimal replacement policy leads to the fewest number of misses overall. Belady showed that a simple (but, unfortunately, difficult to implement!) approach that replaces the page that will be accessed furthest in the future is the optimal policy, resulting in the fewest-possible cache misses.

TIP: COMPARING AGAINST OPTIMAL IS USEFUL

Although optimal is not very practical as a real policy, it is incredibly useful as a comparison point in simulation or other studies. Saying that your fancy new algorithm has an 80% hit rate isn’t meaningful in isolation; saying that optimal achieves an 82% hit rate (and thus your new approach is quite close to optimal) makes the result more meaningful and gives it context. ...