Definition
Page Replacement Policy
A page replacement policy is the algorithm used by the operating system to decide which page currently in physical memory (RAM) should be replaced when a new page must be loaded and no free frames are available.
The goal of a replacement policy is to minimize the number of page faults by selecting the page that is least likely to be needed in the near future.
Replacement Scope
The OS can apply replacement policies at different scopes:
- Local Replacement: The candidate page for replacement is chosen only from the frames currently allocated to the process that triggered the page fault.
- Global Replacement: The candidate page can be chosen from any frame in physical memory, potentially taking a frame away from another process.
Common Algorithms
Optimal
Replaces the page that will not be used for the longest period of time.
- Pros: Guaranteed minimum page fault rate.
- Cons: Impossible to implement in real time as it requires future knowledge of memory references. It serves as a benchmark for other algorithms.
Least Recently Used
Replaces the page that has not been accessed for the longest time.
- Logic: Based on the principle of locality—if a page hasn’t been used for a long time, it is unlikely to be needed soon.
- Overhead: High, as the system must track access times for every page.
3. First-In-First-Out
Replaces the page that has been in memory the longest.
- Pros: Simple to implement using a queue.
- Cons: Performs poorly as it may replace a heavily used page just because it was loaded early.
4. Clock Policy
A more efficient approximation of LRU. It uses a circular buffer of frames and a use bit for each frame.
- Mechanism:
- When a page is accessed, its use bit is set to 1.
- A pointer (the “hand”) rotates through the frames.
- If the hand finds a bit at 1, it sets it to 0 and moves on.
- if the hand finds a bit at 0, that page is replaced.
Comparison
The performance of LRU and Clock is usually near-optimal, while FIFO is generally avoided in high-performance systems.