Vaidikalaya
Privious Next

Page Replacement Algorithms

A page replacement algorithm is a strategy used by the operating system to decide which memory page to remove from RAM when a new page needs to be loaded but the memory is already full. Its main goal is to minimize page faults and keep memory usage efficient.

  • When virtual memory is used, some program pages are in RAM and others are on disk.
  • If a page needed by the CPU is not in RAM → a page fault occurs.
  • The OS must bring that page from disk into RAM.
  • If RAM is already full → the OS must replace (remove) one of the existing pages in RAM.

The decision of which page to remove is made using Page Replacement Algorithms.

Types of Page Replacement Algorithms

Page replacement techniques are used in operating systems to reduce page faults by minimizing unnecessary swapping between RAM and disk, and to increase CPU utilization by ensuring that the most relevant pages remain in memory so the processor spends less time waiting for data.

Some of the common techniques used by the operating system include

  • First-In First-Out (FIFO),
  • Least Recently Used (LRU),
  • Optimal Page Replacement (OPT),
  • Least Frequently Used (LFU), 
  • Clock or Second-Chance algorithm.

First-In First-Out (FIFO)

This is the simplest page replacement algorithm. The operating system keeps track of all pages in memory using a queue. When a new page needs to be loaded and the memory is full, the page that has been in memory the longest (the one that entered first) is replaced first.

  • FIFO means: The page that entered RAM first will be replaced first when a new page needs to be loaded.
  • Works exactly like a queue (first come, first go).
How It Works
  1. Maintain the pages in a queue in the order they were loaded into memory.
  2. When a new page is needed:
    • If RAM has space → just add it.
    • If RAM is full → remove the oldest page (the one at the front of the queue).
    • Insert the new page at the back of the queue.

    Example: Consider page reference string 1, 3, 0, 3, 5, 6, 3 with 3-page frames. Find the number of page faults using FIFO Page Replacement Algorithm.

    1
    Miss
    3
    1
    Miss
    0
    3
    1
    Miss
    0
    3
    1
    Hit
    0
    3
    5
    Miss
    0
    6
    5
    Miss
    3
    6
    5
    Miss

    Total Page Faults = 6

    Advantages of FIFO
    • Very simple to implement.
    • Easy to understand (just like a queue).
    Disadvantages of FIFO
    • May replace frequently used pages just because they are old.
    • Can cause Belady’s Anomaly → sometimes increasing the number of frames leads to more page faults (unexpected behavior).

    OPT (Optimal Page Replacement)

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

    • OPT (Optimal Page Replacement) replaces the page that will not be used for the longest time in the future.
    • It gives the minimum possible number of page faults.
    • It is not practical in real systems (because the OS cannot predict the future).
    • It is mainly used for theoretical analysis and as a benchmark to compare other algorithms (like FIFO, LRU).
    How It Works

    When a page fault occurs and RAM is full:

    • Look at the future reference string.
    • Find which page in RAM will be used farthest in the future.
    • At the moment of a page fault, OPT looks at the entire future reference string (the upcoming page requests).
    • It checks all the pages currently sitting in RAM.
    • Among them, it finds:
      • The page that will never be used again in the future, OR
      • The page that will be used last (farthest in time).
    • That page is the best candidate to remove, because it won’t be needed soon.

    • Replace that page with the new one.

    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.

    7
    7
    Miss
    0
    0
    7
    Miss
    1
    1
    0
    7
    Miss
    2
    2
    1
    0
    7
    Miss
    0
    2
    1
    0
    7
    Hit
    3
    2
    1
    0
    3
    Miss
    0
    2
    1
    0
    3
    Hit
    4
    2
    4
    0
    3
    Miss
    2
    2
    4
    0
    3
    Hit
    3
    2
    4
    0
    3
    Hit
    0
    2
    4
    0
    3
    Hit
    3
    2
    4
    0
    3
    Hit
    2
    2
    4
    0
    3
    Hit
    3
    2
    4
    0
    3
    Hit

    Total Page Faults = 6

    Advantages of OPT
    • Produces the least number of page faults (best-case scenario).
    • Used as a benchmark to measure other algorithms.
    Disadvantages of OPT
    • Not possible in practice (OS cannot know the future page requests).
    • Only theoretical → used for analysis and comparison.

    Least Recently Used:

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

    • LRU replaces the page that was least recently used in the past.
    • It works on the idea of locality of reference → pages that were used recently are more likely to be used again soon, so don’t remove them.

    How it works

    • Keep track of the order of page usage (when each page was last accessed).
    • When a page fault occurs and RAM is full:
      • Remove the page that was least recently used (the “oldest” in terms of last access).
    • Insert the new page into memory.

    Example: Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4-page frames. Find number of page faults using LRU Page Replacement Algorithm.

    7
    7
    Miss
    0
    0
    7
    Miss
    1
    1
    0
    7
    Miss
    2
    2
    1
    0
    7
    Miss
    0
    2
    1
    0
    7
    Hit
    3
    2
    1
    0
    3
    Miss
    0
    2
    1
    0
    3
    Hit
    4
    2
    4
    0
    3
    Miss
    2
    2
    4
    0
    3
    Hit
    3
    2
    4
    0
    3
    Hit
    0
    2
    4
    0
    3
    Hit
    3
    2
    4
    0
    3
    Hit
    2
    2
    4
    0
    3
    Hit
    3
    0
    4
    0
    3
    Hit

    Total Page Faults = 6

    Advantages of LRU
    • Performs better than FIFO in most cases.
    • Approximates OPT (uses past instead of future).
    • Follows real program behavior (recently used pages are likely needed again).
    Disadvantages of LRU
    • Needs extra hardware or software to keep track of usage order (like counters, stacks, or reference bits).
    • Slightly more complex to implement compared to FIFO.
    Privious Next