Page Replacement Algorithms

When physical memory is full and a Page Fault occurs, the operating system must select a "victim" page to evict from RAM and write to the disk. The goal of a page-replacement algorithm is to minimize the total number of page faults.

A bad algorithm will evict a page that the CPU needs immediately in the very next instruction, causing another expensive page fault.

1. FIFO (First-In, First-Out)

The simplest page-replacement algorithm is FIFO.

• Mechanism: The OS maintains a queue of all pages in memory. When a page must be replaced, the oldest page (the one at the front of the queue) is chosen.
• Pros: Incredibly simple to implement.
• Cons: Its performance is generally poor. The oldest page might be a critical initialization module that is constantly being executed. If it's evicted, it will cause an immediate page fault.

Belady's Anomaly

Intuitively, you would expect that giving an algorithm more physical RAM frames would decrease the number of page faults. FIFO suffers from Belady's Anomaly: for some access patterns, increasing the number of page frames actually increases the number of page faults.

2. Optimal Page Replacement (OPT)

The Optimal algorithm has the lowest possible page-fault rate of all algorithms and will never suffer from Belady's anomaly.

• Mechanism: Replace the page that will not be used for the longest period of time in the future.
• Pros: Perfect efficiency. Used as a benchmark to compare other algorithms against.
• Cons: It requires future knowledge! The OS cannot look into the future to see which pages the program will request. Therefore, OPT is purely theoretical and impossible to implement in a real operating system.

3. LRU (Least Recently Used)

Since we cannot predict the future (OPT), we can look at the past. LRU assumes that pages that have been used heavily in the recent past will likely be used heavily in the near future.

• Mechanism: Replace the page that has not been used for the longest period of time.
• Pros: Excellent performance. It is the gold standard for page replacement and does not suffer from Belady's anomaly.
• Cons: Difficult and expensive to implement in hardware. Every single time memory is accessed, the hardware must update a clock register or a stack pointer to track exactly when the page was last used.

4. LRU-Approximation (Clock / Second-Chance Algorithm)

Because true LRU is too slow to execute on every single memory access, modern operating systems use approximations.

Most computer hardware provides a single Reference Bit for each page table entry. The bit starts at 0. Whenever a page is read or written to, the hardware automatically sets its reference bit to 1.

The Clock Algorithm:

• The OS keeps all pages in a circular queue (like the face of a clock). A "hand" points to the oldest page.
• When a page needs to be replaced, the OS looks at the page the hand is pointing to.
  • If its reference bit is 0 (it hasn't been used recently), it is evicted.
  • If its reference bit is 1 (it has been used recently), the OS gives it a "second chance", sets the bit to 0, and moves the hand to the next page.
• This provides an excellent, incredibly fast approximation of LRU.