Page Replacement Algorithms determine which memory pages to swap out when a page fault occurs, allowing efficient management of virtual memory.
Here’s an explanation of commonly used page replacement algorithms:
- First-In, First-Out (FIFO)
- Clock (Second-Chance)
- Least Recently Used (LRU)
- Least Frequently Used (LFU)
- Optimal Page Replacement (OPT)
- Most Recently Used (MRU)
- Working Set Clock (WS-Clock)
1.) First-In, First-Out (FIFO):
FIFO is a straightforward algorithm where the page that entered memory first is the first to be removed. Pages are managed in a queue structure: the oldest page is at the front, and new pages are added at the back.
- It is simple to implement and understand.
- It is not always optimal since the oldest page might still be needed. This can lead to the “Belady’s Anomaly,” where adding more frames increases the number of page faults.
2.) Clock (Second-Chance):
Second Chance is a modification of FIFO that gives each page a “second chance” before replacement. Pages have a reference bit that indicates recent use.
- If the page at the front of the queue has a reference bit set (indicating recent access), it is moved to the back of the queue, and its reference bit is reset. If the reference bit is not set, it is replaced.
- It reduces the chance of unnecessary replacement by allowing recently accessed pages to remain in memory.
3.) Least Recently Used (LRU):
LRU replaces the page that has not been used for the longest period, based on the assumption that pages that haven’t been used recently are less likely to be used soon.
4.) Least Frequently Used (LFU):
LFU replaces the page that has been used the least frequently over time, based on the assumption that less frequently used pages are less likely to be used again.
5.) Optimal Page Replacement (OPT):
The Optimal Page Replacement algorithm replaces the page that will not be used for the longest period in the future. This requires knowing future page accesses, which is often unrealistic in practice.
- Minimizes the number of page faults, providing the best possible performance.
6.) Most Recently Used (MRU):
The Most Recently Used (MRU) algorithm is the opposite of Least Recently Used (LRU). It replaces the page that was accessed most recently, under the assumption that this page is the least likely to be needed in the near future.
7.) Working Set Clock (WS-Clock):
WS-Clock combines the Clock algorithm with the concept of a “working set.” It keeps a circular list of pages and checks each page’s reference bit and its age (i.e., how long it has been in memory).
- If a page is not referenced recently and is older than a specified age (indicating it’s outside the working set), it’s replaced. Otherwise, the clock continues its cycle.
- It is more adaptive to changing working sets, helping balance performance and resource usage.
