Page Replacement Algorithms in Operating System (OS)

Page Replacement Algorithms in OS

On the paging page we saw the mapping of virtual memory to physical memory and how MMU does the paging process. But, what should happen when a new page comes is in scenerio. Which of the existing pages should be replaced and how to decide which one to replace.

On this page we will discuss all page replacement algorithms in operating system.

Page Replacement algorithms in operating system are different operational logics to decide which page should be replaced when a new page comes in the system.

Types of Page Replacement Algorithms PrepInsta

Types of Page Replacement Algorithms

  1. FIFO – First in First Out
  2. LRU – Least Recently Used
  3. Optimal Page Replacement Algorithm
  4. LFU – Least Frequently Used
  5. MFU – Most Frequently Used

Page Fault – A page that is available (mapped) in the Logical Memory is not available (loaded) in the physical memory causes an interrupt service to be called by hardware.

In page replacement algorithms basically we will be looking for page faults, its okay if you don’t understand it now. With examples given for each algorithm you will be able to understand what a page fault is.

First In First Out:-   A FIFO replacement algorithm associates with each page the time when that page was brought into memory.When a page must be replaced, the oldest page is chosen i.e. the page which was loaded first goes out thus, justifying its name FIFO.

Track is kept in a FIFO table of the following –

  • Current pages in memory
  • Recent Arrival coming in
  • Oldest page in the memory

The idea is obvious from the name –

It might be a confusing theory, lets look with an example –

Incoming page Steam – 7, 0, 1, 2, 0 , 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

Page Size/ Frame Size = 3

Table will look like(Explanation after the table)

Incoming Page Stream ->70120304230321
Existing at position 177722244400
Existing at position 20003332221
Existing at position 3111000333
Page Faultxxxxxxxxxxx

Explanation –

  • Step n [Incoming Stream] – Current Stack [x,y,z]
  • Current Oldest – In Red
  • After Replacing – In Green

Goes as

  • Step 1 [7] – Current Stack [nil,nil,nil] (Page Fault Occurs)
    • Result – [7,nil,nil]
  • Step 2 [0] – Current Stack [x,y,z]
    • Result – [7,0,nil] (Page Fault Occurs)
  • Step 3 [1] – Current Stack [x,y,z]
    • Result – [7,0,1] (Page Fault Occurs)
  • Step 4 [2] – Current Stack -[7,0,1]
    • Result – [2,0,1] (Page Fault Occurs)
  • Step 5 [0] – Current Stack [2,0,1]
    • Result – [2,0,1] as 0 is already Present
  • Step 6 [3] – Current Stack [2,0,1]
    • Result – [2,3,1]
  • Step 7 [0] – Current Stack [2,3,1]
    • Result – [2,3,0] (Page Fault Occurs)
  • Step 8 [4] – Current Stack [2,3,0]
    • Result – [4,3,0]
  • Step 9 [2] – Current Stack [4,3,0]
    • Result – [4,2,0] (Page Fault Occurs)
  • Step 10 [3] – Current Stack [4,2,0]
    • Result – [4,2,3] (Page Fault Occurs)
  • Step 11 [0] – Current Stack [4,2,3]
    • Result – [0,2,3] (Page Fault Occurs)
  • Step 12 [3] – Current Stack [0,2,3]
    • Result – [0,2,3] (3 already there)
  • Step 13 [Incoming Stream] – Current Stack [0,2,3]
    • Result – [0,2,3] (2 already there
  • Step 14 [1] – Current Stack [0,2,3]
    • Result – [0,1,3] (Page Fault Occurs)

If you have any questions ask in the comments section, we will help.

Now page fault occurs 11 times out of 14.

So page fault ratio is 11/14.

Think – Now, one should think that increase the page size(frame size as page size = frame size) will lead to less page fault, right!! since more chances of element to be present in the queue.

But, thats not the case always. Some times by increasing the page size page fault rather increases, this type of anomaly is called belady’s Anomaly.(asked in AMCAT, CoCubes, Oracle)

Example consider the following(solve yourself for practice)

  • 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4
    • Using 3 slots gives 9 page faults
    • Using 4 slots gives 10 page faults

Least Recently Used –

In this algorithm for any incoming page stream unit say X, we replace the element which is the current least recently used element in current stack.

That is, when we look to the left of the table, that we have created we choose the further most page to get replaced.

Example –

Let’s say d is incoming page and current stack is [a,b,c].

Lets assume we are at 10th iteration

  • a was last entered in current stack at 4th iteration.
  • b was entered at 2nd iteration
  • c was entered at 7th iteration

In this case d will replace b as b is the least recently used.

But, What if !!!

b was entered at 2nd iteration and replaced by some other page on 5th and then entered current stack again at 8th iteration??

In this case b will not be least recently used but a will be and thus a will be replaced.

Trick is to look for first occurance of page towards the left of the table and whichever is the furthermost. Incoming page should replace that.

Page Reference Stream: 

12321521625631361243
11113215216256613612
2232152162563136124
321521625631361243
***********

LRU

Total 11 Page Faults

Optimal Page Replacement:- 

In LRU we looked for the left further most page to replace.

In optimal we do opposite and look for right further most. Now, this is done so that there are lesser page faults as the element will  not used for the longest duration of time in the future. 

  • The result of the discovery of Belady’s Anamoly
  • Lowest page fault rate of all algorithm’s and will never suffer from belady’s Anamoly.
  • Simply it replaces the pages that won’t be used for longest period of time.
  • Optimal page replacement is perfect, but not possible in practice as 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.

The image below shows the implementation of Optimal page replacement Algorithm.

 

This algorithm is not for placement course.

But basically in current stack at any iteration we choose that element for replacement which has smallest count in the incoming page stream.

This algorithm is not for placement course.

But basically in current stack at any iteration we choose that element for replacement which has highest count in the incoming page stream.

Please Login/Signup to comment