Page Replacement Algorithms - aryanjoshi0823/5143-Operating-System GitHub Wiki

Page replacement algorithms are techniques used to manage memory effectively in operating systems when the virtual memory is full. These algorithms decide which page to replace in physical memory when a new page needs to be loaded, and there is no free memory available.

When is Page Replacement Performed?

When a page fault occurs and no free page frame is available in memory:

  1. The virtual memory manager performs a page replacement operation.
  2. It uses a page replacement algorithm to select an existing page for removal.
  3. The selected page's page table entry is updated to mark it as "not present" in memory.
  4. If the page has been modified (indicated by the dirty bit), it is written back to disk (page-out operation).
  5. The new page is then brought into memory and its page table entry is updated.

1. First In First Out (FIFO)

  • The operating system keeps track of pages in memory using a queue. The oldest page in the queue is selected for replacement.

Example:
Reference string: 1, 3, 0, 3, 5, 6, 3 with 3 page frames.
Steps:

  1. Initially, all slots are empty: 1, 3, 0 → 3 Page Faults.
  2. 3 is already in memory → 0 Page Faults.
  3. 5 replaces the oldest page (1): 1 Page Fault.
  4. 6 replaces the next oldest page (3): 1 Page Fault.
  5. 3 replaces the oldest page (0): 1 Page Fault.

Total Page Faults: 6.

What is Belady’s Anomaly?

  • Definition:
    Belady’s anomaly demonstrates that increasing the number of page frames can sometimes lead to more page faults when using the FIFO algorithm.
  • Example:
    Reference string: 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4.
    • With 3 slots → 9 page faults.
    • With 4 slots → 10 page faults.

2.Least Recently Used

In this algorithm, page will be replaced which is least recently used.

Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4 page frames.

  1. Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4 Page faults
  2. 0 is already their so —> 0 Page fault. when 3 came it will take the place of 7 because it is least recently used —> 1 Page fault
  3. 0 is already in memory so —> 0 Page fault .
  4. 4 will takes place of 1 —> 1 Page Fault
  5. Now for the further page reference string —> 0 Page fault because they are already available in the memory.

3.Optimal Page Replacement

  • In this algorithm, pages are replaced which would not be used for the longest duration of time in the future.

  • Example: Consider the page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4 page frame.

Find number of page fault using Optimal Page Replacement Algorithm.

  1. Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4 Page faults
  2. 0 is already there so —> 0 Page fault.
  3. when 3 came it will take the place of 7 because it is not used for the longest duration of time in the future.—> 1 Page fault.
  4. 0 is already there so —> 0 Page fault. 4 will takes place of 1 —> 1 Page Fault.

4.Clock (Second-Chance) Page Replacement Algorithm

The Clock algorithm, also known as the Second-Chance algorithm, is a page replacement strategy designed to manage memory more efficiently by giving pages a "second chance" before replacing them. It is a practical and efficient approximation of the Least Recently Used (LRU) algorithm.

Key Features of the Clock Algorithm

  1. Second Chance Mechanism:

    • Pages are given an additional chance to stay in memory if they are accessed again before being replaced.
    • This avoids prematurely replacing frequently used pages.

  2. Uses a Circular Queue:

    • Memory frames are arranged in a circular queue resembling a clock.
    • A "hand" (pointer) rotates around the circle to select pages for replacement.

  3. Reference Bit:

    • Each page has a reference bit (R) associated with it.
    • R = 1: The page was recently accessed.
    • R = 0: The page has not been accessed recently.

Algorithm Steps

  1. Page Reference and Initial Setup:

    • When a page is referenced, its reference bit (R) is set to 1.
    • Initially, all reference bits are set to 0.

  2. Page Fault Handling:

    • If a page fault occurs and a new page needs to be loaded into memory:
      1. The "clock hand" scans pages in the circular queue.
      2. For each page:
        • If R = 0, the page is replaced.
        • If R = 1, the reference bit is cleared (R = 0), and the hand moves to the next page.

  3. Repeat Process:

    • The process continues until a page with R = 0 is found and replaced.
⚠️ **GitHub.com Fallback** ⚠️