CONCEPTS - PAGE REPLACEMENT

Simulation Graphs


Page Replacement Algorithm

The page replacement algorithm decides which memory page is to be replaced. The process of replacement is sometimes called swap out or write to disk. Page replacement is done when the requested page is not found in the main memory (page fault).

When a page fault occurs, the operating system has to choose a page to remove from memory to make room for the page that has to be brought in. The page replacement is done by swapping the required pages from backup storage to main memory and vice-versa. If the page to be removed has been modified while in memory, it must be rewritten to the disk to bring the disk copy up to date. If, however, the page has not been changed (e.g., it contains program text), the disk copy is already up to date, so no rewrite is needed. The page to be read in just overwrites the page being evicted. A page replacement algorithm is evaluated by running the particular algorithm on a string of memory references and compute the page faults.Referenced string is a sequence of pages being referenced. Page fault is not an error. Contrary to what their name might suggest, page faults are not errors and are common and necessary to increase the amount of memory available to programs in any operating system that utilizes virtual memory, including Microsoft Windows, Mac OS X, Linux and Unix.

Each operating system uses different page replacement algorithms. To select the particular algorithm, the algorithm with lowest page fault rate is considered.
1.First-In First-Out page replacement (FIFO)
2.Least recently used page replacement (LRU)
3.Optimal page replacement algorithm

First In First Out (FIFO)

This is the simplest page replacement algorithm. In this algorithm, the operating system keeps track of all pages in the memory in a queue, the oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal.

>> Example : Consider page reference string 1, 3, 0, 3, 5, 6 with 3 page frames. Find number of page faults.



  • Initially all slots are empty, so when 1, 3, 0 came they are allocated to the empty slots —> 3 Page Faults.
  • When 3 comes, it is already in memory so —> 0 Page Faults.
  • Then 5 comes, it is not available in memory so it replaces the oldest page slot i.e 1. —>1 Page Fault.
  • 6 comes, it is also not available in memory so it replaces the oldest page slot i.e 3 —>1 Page Fault.
  • Finally when 3 come it is not avilable so it replaces 0 1 page fault.

    • Least Recently Used (LRU)

    In the Least Recently Used (LRU) page replacement policy, the page that is used least recently will be replaced.

    >> Example : Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 with 4 page frames.Find number of page faults.



  • Initially all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4 Page faults.
  • 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.
  • 4 will takes place of 1 —> 1 Page Fault.
  • Now for the further page reference string —> 0 Page fault because they are already available in the memory.

    • Optimal (OPT)

    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, with 4 page frame. Find number of page fault.



  • Initially all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4 Page faults.
  • 0 is already their so —> 0 Page fault.
  • 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.
  • 0 is already there so —> 0 Page fault.
  • 4 will takes place of 1 —> 1 Page Fault.
  • Now for the further page reference string —> 0 Page fault because they are already available in the memory.


    • NOTE : Optimal page replacement is perfect, but not possible in practice as the operating system cannot know future requests. The use of Optimal Page replacement is to set up a benchmark so that other replacement algorithms can be analyzed against it.

    Belady's Anomaly

    Belady’s Anomaly is the phenomenon of increasing the number of page faults on increasing the number of frames in main memory.


    Reason Behind Belady’s Anomaly :

  • An algorithm suffers from Belady’s Anomaly if and only if it does not follow stack property.
  • Algorithms that follow stack property are called as stack based algorithms.
  • Stack based algorithms do not suffer from Belady’s Anomaly.
  • This is because these algorithms assign priority to a page for replacement that is independent of the number of frames in the main memory.

    • LRU Page Replacement Algorithm and Optimal Page Replacement Algorithm are stack based algorithms. Hence, they do not suffer from Belady’s Anomaly.


    Stack Property :

  • Consider - Initially, we had ‘m’ number of frames in the main memory.
  • Now, the number of frames in the main memory is increased to ‘m+1’.
  • According to stack property, At each stage, the set of pages that were present in the main memory when number of frames is ‘m’ will be compulsorily present in the corresponding stages in main memory when the number of frames is increased to ‘m+1’.


    • >> Example : For Optimal Page Replacement Algorithm, Consider the reference string 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4.


    Case-1 : When frame size = 3

    Number of page faults = 7


    Case-2 : When frame size = 4

    Number of page faults = 6


    From here, we can observe :

  • At all the stages in case-2, main memory compulsorily contains the set of pages that are present in the corresponding stages in case-1.
  • Thus, optimal page replacement algorithm follows the stack property.
  • Hence, it does not suffer from Belady’s Anomaly.
  • As a proof, number of page faults decrease when the number of frames is increased from 3 to 4.


    • So, from this above example you understood that Optimal Page Replacement Algorithm doesn't suffer Belady's Anomaly Algorithm.


    >> Example : For LRU Page Replacement Algorithm, Consider the reference string 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4.


    Case-1 : When frame size = 3

    Number of page faults = 10


    Case-2 : When frame size = 4

    Number of page faults = 8


    From here, we can observe :

  • At all the stages in case-2, main memory compulsorily contains the set of pages that are present in the corresponding stages in case-1.
  • Thus, LRU page replacement algorithm follows the stack property.
  • Hence, it does not suffer from Belady’s Anomaly.
  • As a proof, number of page faults decrease when the number of frames is increased from 3 to 4.


    • So, from this above example you understood that LRU Page Replacement Algorithm doesn't suffer Belady's Anomaly Algorithm.


    >> Example : For FIFO Page Replacement Algorithm, Consider the reference string 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4.


    Case-1 : When frame size = 3

    Number of page faults = 9


    Case-2 : When frame size = 4

    Number of page faults = 10


    From here, we can observe :

  • At stage-7 and stage-8 in case-2, main memory does not contain the set of pages that are present in the corresponding stages in case-1.
  • Thus, FIFO page replacement algorithm does not follow the stack property.
  • Hence, it suffers from Belady’s Anomaly.
  • As a proof, number of page faults increase when the number of frames is increased from 3 to 4.


    • Note:

  • In the above example,FIFO Page Replacement Algorithm suffers from Belady’s Anomaly.
  • It would be wrong to say that “FIFO Page Replacement Algorithm always suffer from Belady’s Anomaly”.