Page Replacement Algorithms in 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.

Page Replacement Algorithm

Page Fault – In simple terms, if an incoming stream item (page) is not available in any of the frames. Then page fault occurs.

Page Replacement Algorithm In OS

FIFO-First In First Out

A FIFO replacement algorithm associates with each page the time when that page was brought into memory.

This is how FIFO works –

  • If an incoming page is not available in any of the frames. Replacement shall be done.
  • Page replaced is according to FIFO (First in First Out)
  • The page that entered first must be swapped out first
  • In other words, the oldest frame must be swapped out
Page Replacement Algorithm In OS FIFO Example

Example

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
  • Page Size/ Frame Size = 3

Table will look like(Explanation after the table)

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 [7, nil, nil]
    • Result – [7,0,nil] (Page Fault Occurs)
  • Step 3 [1] – Current Stack [7, 0, nil]
    • 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, and we will help.

Now page fault occurs 11 times out of 14.

So page fault ratio is 11/14.

Belady’s Anomaly

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, that’s not the case always. Sometimes by increasing the page size page fault rather increases, this type of anomaly is called belady’s Anomaly.(asked in AMCAT, CoCubes, Oracle)

For 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, we replace the element which is the current least recently used element in the 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.

Page Replacement Algorithm In OS LRU Example
Page Replacement Algorithm LRU Example detailed

Optimal Page Replacement

In LRU we looked for the left furthermost page to replace. In optimal we do the opposite and look for right furthermost.

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. 

Optimal Page Replacement Quick Facts

  • 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 the Optimal page replacement Algorithm.

Page Replacement Algorithm Optimal

Least Frequently Used

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.

Most Frequently Used

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.