FOR FREE YEAR SOLVED

NET question on Second Chance algorithm

Consider the main memory with three page frames for the following page reference string:

5, 4, 3, 2, 1, 4, 3, 5, 4, 3, 4, 1, 4

Assuming that the execution of the process is initialized after loading page 5 in memory, the number of page faults in FIFO and second chance replacement respectively are

(A) 8 and 9

(B) 10 and 11

(C) 7 and 9

(D) 9 and 8

You should Know

Before seeing the solutions please follow this chapter: 

FIFO page replacement algorithm, Second Chance page replacement algorithm

Solution: 

In this question they as page fault for two page replacement algorithms FIFO and second chance. 

First, we calculate page fault using FIFO policy by shortcut method for more details please follow:

FIFO page replacement algorithm

FIFO:

Page references: 5, 4, 3, 2, 1, 4, 3, 5, 4, 3, 4, 1, 4 and number of frames are 3.

As you know the shortcut method number of page references working with 3 frames is treated as a page fault. Here page references working with 3 frames are 5, 4, 3, 2, 1, 4, 3, 5, 1, 4. So, 10 page references working with 3 frames but we do not consider page 5 because it is preloaded.

So, 9 page references are there, then page faults = 9.

Second chance:

This is a modified version of FIFO and here we do not replace the page as it came early, we also check the reference bit means how recently it is used. 

Step 1: If it is recently used we give a second chance to this page, and continue to search for the next oldest one.

For more details and concept please follow: 

Second Chance page replacement algorithm

Page references: 5, 4, 3, 2, 1, 4, 3, 5, 4, 3, 4, 1, 4 and number of frames are 3.

Step 2: Oldest page is 5 and it not recently used, so, we replace 5 and load new page 2.

Step 3: Here oldest page is 4, even not recently used. So, we can replace 4 and load new page 1.

Step 4: In this case, the oldest page is 3 and it is not recently used. So, we replace 3 and load new page 4.

Step5: Here oldest page is 2 and not recently used. So, we replace 2 and load new page 3.

Step 6: Oldest page is 1 and it is not recently used. So, we replace 1 and load new page 5.

Step 7: For the new request page 4 and 3 are already present in the frame so, no page fault.

Step 8: Again new request page 4 is already present at the frame, so, no page fault.

In the all above steps, it is working the same as FIFO. Now in Step 9, we will see the flavor of a second chance.

Step 9: In this case, the oldest page is 4 but 4 is recently use. So, we do not replace page 4 rather we give second chance to page 4. 

Now if we search for the next oldest page, it is page 3, but here page 3 is also recently used. Then we give a second chance to page 3 also. 

If we looking for the next oldest one is page 5, it is not recently used compare to 4 and 3. So, here we replace page 5 and load new page 1.

So, the number of page faults excluding preloaded page 5 = 8. 

So, option (D) is correct.