CREATE OWN LIBRARY

Second Chance page replacement algorithm

Before seeing this chapter please follows FIFO policy: 

FIFO page replacement algorithm

Second chance algorithm is a modified version of the FIFO page replacement algorithm.

IF you follow FIFO policy chapter, you can see how FIFO policy can be implemented by queue using a linked list.

Let understand the need of second change algorithm using a Gate question:

Q. GATE 1994

A memory page containing a heavily used variable that was initialized very early and is in constant use is removed then

A. LRU page replacement algorithm is used

B. FIFO page replacement algorithm is used

C. LFU page replacement algorithm is used

D. None of the above

Solution:

To answer this question, first, we have to understand this question. 

Heavily used means frequently used i.e. page is requested frequently.

Very early means it come at memory very long back i.e. oldest page.

Constant use means recently requested this page.

(A) is not correct because this page is recently used, we do not replace the recently used page in LRU (Least Recently Used). 

(C) is not correct because this page is frequently used, so, we do not replace frequently used pages in LFU (Least Frequently Used).

(B) is correct.  The only way to replace the oldest page even it is recently and frequently used is FIFO.

So, from this question it is clear that FIFO has a disadvantage that even a page is frequently and recently used so that it is a very important page, still, FIFO replaces this page because it came early. 

To overcome this disadvantage of FIFO, it modified to second chance algorithm. 

Second chance algorithm: 

A simple modification to FIFO that avoids the problem of replacing out a heavily used page is to inspect the R (Reference bit) bit of the oldest page.

Reference (R) Bit: We know every page has a reference bit that identifies this page is recently used or not. If R = 1 then it is recently used and if R = 0 then it is not recently used.

If it is R = 0, the page is both old and unused, so it is replaced immediately. 

If the R = 1 i.e. recently used, give this page to second chance. Make the bit is cleared (R = 0) and the page is put onto the end of the linked list of pages, and its load time is updated as though it had just arrived in memory. 

Example:

Case1:

Page references: 1, 4, 2, 3, 7 and number of frame 4.

Now page 7 is requested so, we have to replace the oldest page 1 as per FIFO but here we also check reference bit (R bit). Here R = 0 for page 1 means not recently used. So, we can replace page 1 and loaded new page 7 at end of the list.

Case2:

Page references: 1, 4, 2, 3, 7 and number of frame 4.

Now page 7 is requested so, we have to replace the oldest page 1 as per FIFO but here we also check reference bit (R bit). Here R = 1 for page 1 which means page 1 is recently used. Then as per second chance algorithm, we give a second chance to page 1. 

Cleared the reference bit of page 1 and put it to the end of the linked list and continue searching for the next oldest page.

Now, the next oldest page is 4 and reference bit of 0 (R = 0) so, it is no recent use and we can replace page 4 and loaded new page 7 at the end of the linked list.