Page replacement is a way to swap a page that is not being used out of the memory and swap in the page that is requested by the program in the memory. Several algorithms are used to solve this and I have written about two of these algorithms in a previous post which you can find here in Day 62. In this post I will be writing about one other algorithm that is also used for Page Replacemnt in the VM.
In Day 62, we learned about FIFO (First In, First Out) and POR (Page Optimal Replacement) Page Replacement algorithms and now we will be learning about Least Recently Used (LRU) algorithm.
Least Recently Used (LRU)
Least Recently Used (LRU) is a page replcement algorithm that replaces the page whose time since the last reference is greater than any other page in the memory. This requires a timestamp recording for each page when it is loaded into the memory. The page that is then the oldest in the memory is swapped out of it to make space for some other page which is requested to be loaded. The overhead in such a system is that of a maintaining all the timestamps which is generally a linked list and the time it takes to find the oldest value.
In the example below, the system produces 10 page faults. When the page fault for page 4 ocurs the algorithm decides that tha page 2 is the oldest in the memory and swaps it out and swaps the page 4 in. But next fault is for page 2 and this time the page 3 is the oldest so it is swapped out and so on.
|7|0|1|2|0|3|0|4|2|3|0|3|2|1|
--- Frames ---
|7|7|7|2| |2| |4|4|4|0| | |1|
|-|0|0|0| |0| |0|0|3|3| | |3|
|-|-|1|1| |3| |3|2|2|2| | |2|
In addition to LRU, there are LRU Approximation Algorithms that use a refernce bit associated with each entry of the page table. Initially the bit is set to zero when the but when the page is accessed (read or write) its bit is chaged to 1. Later when we access this page again we can see if the page was accessed since the last check.
There are three LRU approximation algorithms:
- Additional-Reference Bits Algorithm
- Second Chance-Algorithm
- Enhanced Second-Chance Algorithm
We will look into may some next time.
zainsci