Implementing Historical Algorithms
Explore how to implement historical page replacement algorithms such as Least Recently Used (LRU) in virtual memory. Understand the challenges of updating page usage data on every access and discover hardware-assisted methods to balance accuracy and performance. This lesson helps you grasp how approximations to perfect algorithms provide practical and efficient memory management solutions.
We'll cover the following...
As you can see, an algorithm such as LRU can generally do a better job than simpler policies like FIFO or Random, which may throw out important pages. Unfortunately, historical policies present us with a new challenge: how do we implement them?
Requirements for implementation
Let’s take, for example, LRU. To implement it perfectly, we need to do a lot of work. Specifically, upon each page access (i.e., each memory access, whether an ...