Anonymous user menu

Calculate number of page faults with modified FCFS

Demand paging uses a second chance page replacement policy (clock). It uses one use bit to give every page one more chance in FIFO replacement. Whenever a page is referenced its use bit set to 0. Whenever it is need to replace by other page first time its use bit is changed to 1 and next page will be searched for replacement. If already given the chance then it will be replaced. Assume system has 3 page frames. Consider the following page reference stream in the given order.

                        7, 0, 1, 2, 0, 3, 0, 4, 2, 3

How many page faults occur using clock algorithm?

My answer is 9.

when first 3 comes I replaced 0 with 3. But they replaced 1 with 3. I am not getting why?

As we use queue in FCFS 0 is at front when 3 arrives.

7Comments
Arul @innovwelt
25 Jan 2015 01:13 am

what was the answer given?

I get the answer '6' (3 compulsary initial faults + 3 replacements)

 

To your question, at the particular instant, when 3 arrives, 0's use bit will be 0 (i.e., first replacement request). so the algorithm will change the use bit of '0' as 1 & proceeds to check next location.

fortunately, 1 will have use bit as '1' (i.e., a chance has already been given during the previous replacement). so, it gets replaced.

Nishant Vijayvergiya @nishantv
25 Jan 2015 12:00 am

I m getting 8.

It is given it is second chance algo.here every frame gets a second chance.

so for 2:0 gets replaced

for 0:7 gets replaced

for 3:1 gets replaced

for 4:2 gets replaced

for 2:0 gets replaced.

In all 5 (replacements)+3(initial)=8

Arul @innovwelt
25 Jan 2015 12:39 am

I have a doubt in first step.

for 2: 0 gets replaced? why is it so?

I think, for 2 = 7 will get replaced

Nishant Vijayvergiya @nishantv
25 Jan 2015 12:45 am

"Whenever it is need to replace by other page first time its use bit is changed to 1 and next page will be searched for replacement. If already given the chance then it will be replaced."

Since its the first replacement request,so 7 is given the chance & 0 gets replaced

Arul @innovwelt
25 Jan 2015 12:59 am

even, it is the first replacement request for 0. so, the algorithm will change the 'use' bit of 0 to 1 & continue.

further, the 'use' bit of 1 also will be changed to 1.

then the algorithm will look at 7. and it's use bit is 1 (i.e., 7 has already been given a chance).

So, 7 will be replaced.

when all the 'use' bits are 0, this algorithm works like a pure FCFS algorithm.

Shreyas Dawkhare @shreyasdawkhare
25 Jan 2015 04:08 pm

This is what they did. I replaced 0 when 4 arrives because 0 came first than 2 and 3.

I am also getting 6 page faults

Arul @innovwelt
25 Jan 2015 04:27 pm

Itseems that, whenever a page is referenced (say '0'), it's use bit will be changed to '0' & it will queued again at the rear of Queue, as it is a new page.
 

In this logic, 2 will be replaced for 4 , instead of replacing 0.