Page Replacement Algorithms

In a demand paging system, not all pages can be kept in physical memory simultaneously. When memory is full and a new page needs to be brought in, the operating system must decide which page to remove to make space. This decision is handled by Page Replacement Algorithms.

An efficient algorithm reduces the number of page faults, thereby improving overall system performance.

Why Page Replacement Matters

When a page fault occurs and all memory frames are full:

• One page must be replaced.
• Choosing the wrong page can lead to more page faults in the future.
• A good algorithm predicts which pages are least likely to be used soon.

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

• The oldest page in memory (the one that came first) is removed.
• Implemented using a queue.

Pros:

• Simple to implement.

Cons:

• Doesn’t consider how often or recently a page is used.
• Can lead to Belady’s anomaly (more frames can cause more faults).

2. LRU (Least Recently Used)

• Replaces the page that hasn’t been used for the longest time.
• Based on the idea that pages used recently are likely to be used again soon.

Pros:

• Generally performs well in practice.

Cons:

• Requires tracking usage history, which can be complex.
• Needs more hardware support or clever software approximations.

3. Optimal Replacement

• Replaces the page that will not be used for the longest time in the future.
• This is a theoretical benchmark to compare other algorithms.

Pros:

• Produces the lowest number of page faults.

Cons:

• Not implementable in practice (requires future knowledge).

4. Clock Algorithm

• A practical approximation of LRU.
• Uses a circular buffer (clock) and a use bit (reference bit).

How it works:

• Pages are arranged like a clock.
• The pointer moves in a circle, checking each page’s use bit:

• • If use bit = 0, replace the page.

  • If use bit = 1, set it to 0 and skip it.

Pros:

• More efficient than full LRU.
• Easy to implement.

Cons:

• Still an approximation of recent use.

5. Second-Chance Algorithm

• A variation of FIFO that gives pages a “second chance” if they’ve been used recently.
• Combines simplicity of FIFO with some logic of LRU.

How it works:

• Before replacing a page, check its reference bit.

• • If it’s 1: set to 0 and skip.

  • If it’s 0: replace the page.

Pros:

• Avoids replacing heavily used pages.

Cons:

• Still not as accurate as true LRU.