Page Replacement Algorithm

Whenever a process requests data from a page which is not in the memory then the system uses a page replacement algorithm to swap out an existing page to make space for the new page.

In demand paging only a subset of pages are in the memory at any time. When a process needs some data then that page is brought into the memory on demand. Since the memory is limited so every process gets a limited number of frames. Generally, the number of pages of the process is more than the frames available to the process. Hence, when the process request for a page and no free frame is available the system will replace one of the pages in the memory with the new one. Now, which page to select for replacement?

There are three page replacement algorithms:

  • First In First Out (FIFO)
  • Least Recently Used First (LRU)
  • Optimal Page Replacement
First In First Out (FIFO)

In First In First Out (FIFO) algorithm the system keeps track of the time when each page gets into the memory.
Hence, for page replacement, the page which entered first into the memory is selected for replacement.

Drawback of FIFO:
This technique suffers from Beladay’s Anomaly. In general, with an increase in the number of frames, the number of page faults decreases. But for some certain scenario, the number of page faults increases with an increase in number of frames. This is called Beladay’s Anomaly.

Least Recently Used First (LRU)

LRU page replacement algorithm associates with each page the time of that page’s last use.
When a page must be replaced, LRU chooses the page that has not been used for the longest period of time

Optimal Page Replacement

This strategy is opposite to LRU. Optimal page replacement looks in future requests. Optimal page replacement algorithm replaces the page that will not be used for the longest period of time(in future).

Note: This is only a theoretical approach as it is not possible to look into the future to check with page will be requested in future.

The PPT and the video below explains all the three algorithms with an example.

PPT on Page Replacement Algorithms

Note: Clicking on the “next” slide button will not display any animation. Hence, Click within the slide area for animations.

Video

page replacement algorithms

Practice Question

[UGC-June2014] Consider a program that consists of 8 pages (from 0 to 7) and we have 4 page frames in the physical memory for the pages. The page reference string is :
1 2 3 2 5 6 3 4 6 3 7 3 1 5 3 6 3 4 2 4 3 4 5 1
The number of page faults in LRU and optimal page replacement algorithms are respectively (without including initial page faults to fill available page frames with pages) :
(A) 9 and 6 (B) 10 and 7
(C) 9 and 7 (D) 10 and 6

Previous

Virtual memory

8 thoughts on “Page Replacement Algorithm

Leave a Reply

Your email address will not be published. Required fields are marked *