8.9k views

A computer has twenty physical page frames which contain pages numbered $101$ through $120$. Now a program accesses the pages numbered $\text{1, 2, ..., 100}$ in that order, and repeats the access sequence THRICE. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program?

1. Least-recently-used
2. First-in-first-out
3. Last-in-first-out
4. Most-recently-used

edited | 8.9k views
+3
Why we can't consider Last In First Out ?

Each time it will replace the most recent frame only like MRU, so how option D is more appropriate than option C ?
+2

+1
How  many Page fault will occur?
+3

I think there would be

Optimal: 260-page fault

MRU: 260-page fault

LIFO: 262-page fault

NOTE (if reference string has 300-page request i.e 1 2 .... 100 1 2 .... 100 1 2 .... 100 and demand paging is used)

+2
I think in MRU  when 1st page is arrived then it  replace  101 or any of 101 .....120 .Then when the 2nd page comes then it will replace 1St page ,,isnt as it is used most recent.Then how optimal page replacement algorithm is same as MRU . I think no option is correct.correct me if i am wrong.
0
what if in in the second round access is reverse means 100 to 1

then the answer for the same question would  be FIFO or not ?

0
I have the same doubt!
0

@Arjun sir, here all the answers have made the assumption that for MRU the pages 101 to 120 will be swaped out. Can we make assumptions like this in exam? Because in this case Optimal will not behave exactly like MRU, and the reason is the twenty pages that were already loaded. Please note here I have taken the sequence as 1,2,3,.....99,100,1,2,3......99,100,1,2,3.....99,100.

Please correct me if I am wrong, according to my calculations, in Optimal we will get 40/300 page hit rate, and in MRU we will get 0/300 Page Hit Rate.

I know MRU and Optimal work exactly same when the sequence is in a loop but in this question, the twenty frames are already loaded and that is what is making the difference.

0

It will be (D) i.e Most-recently-used.

To be clear "repeats the access sequence THRICE" means totally the sequence of page numbers are accessed $4$ times though this is not important for the answer here.

If we go optimal page replacement algorithm it replaces the page which will be least used in near future.

Now we have frame size $20$ and reference string is

$$1, 2, \dots, 100,1, 2, \dots, 100,1, 2, \dots, 100, 1, 2, \dots, 100$$

First $20$ accesses will cause page faults - the initial pages are no longer used and hence optimal page replacement replaces them first. Now, for page $21$, according  to reference string page 1 will be used again after $100$ and similarly $2$ will be used after $1$ so, on and so the least likely to be used page in future is page $20$. So, for $21^{st}$ reference page $20$ will be replaced and then for $22^{nd}$ page reference, page 21 will be replaced and so on which is MOST RECENTLY USED page replacement policy.

PS: Even for Most Recently Used page replacement at first all empty (invalid) pages frames are replaced and then only most recently used ones are replaced.

by Active (2k points)
edited by
0
Can you please explain...after replacement of page 20 with page 21 ...what would be the most recently used reference....wouldn't it be 21 ...?That is why we will replace the page 22 with page page 19...?
0

after replacing 20 by 21

 FRAMES SHOWN BELOW 20---> replaced by 21 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

so now

 FRAMES SHOWN BELOW 21 (MOST RECENTLY USED) 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

so 21 will be replaced by 22

 FRAMES SHOWN BELOW 22 (MOST RECENTLY USED) 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
+1
But does the number of page faults for LIFO and MRU differ here?
0

@arjun sir this option is for confusion there no page replacement algorithm exist as LIFO
A nice trick played by GATE paper setters (I had same doubt on the first hand but then i searched this one and found No book has ever implemented LIFO Algo for page replacement

0
0

@Arjun Sir the link shared by you has a line "The victim page is the page that has been most recently inserted into memory"

so its the LIFO is not used its used as MRU (they are synonyms ) but to be correct its most recently used As genrally known

+5

They are not synonyms- "most recently inserted into memory" and "most recently referenced in memory" are not the same.

0

@ arjun sir thanx because of you  i got where i was going wrong
Replace till 100 from 1 to 19 no page faults ryt

 FRAMES SHOWN BELOW 100 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

now  till 20 will arrive  no page fault ......again 100 will be used in near future because of string coming in near future(ie 20 21 ......100 ,1,2......100) correct so in Optimal merge pattern 19 will be replaced instead of 100
i.e MOST recent was 19 but for LIFO 100 must be replaced...

 FRAMES SHOWN BELOW 100 19(most recently used ) 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
 FRAMES SHOWN BELOW 100 20(MOST RECENTLY USED) 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
0
@Arjun Sir now we got the correct reason and Solution :)
0
Why there will be no page faults from 1 to 19 and can you please explain briefly the solution....couldn't get it...
0
Its for the second time when string is referred after 1,2,3......100 again 1,2,3,4,......19,20,21.....100
there will be no page fault for these because we are not replacing 1 to 19 pages according to optimal Page replacement algorithm
0
thanks..
0
while using MRU why didn't we assumed that pages 101 to 120 will be there and anyone of them will be replaced????
0
101 to 120 will be there and anyone can be replaced. I guess its worth counting the page faults here.
+1
so i doubt sir

in gate we have to make assumptions if not getting the answer

like if TLB access time not given then take 0

or in this question , assume the 20 frames are empty (when testing MRU)

??

Sir how do u know when to take assumption

0

@lgau0522 we are counting them just not showen here keeping in mind the assumption that it is understandable
But this is ryt that 101 to 119 there will be no page faults as 1 ,2,3,....19 are allready avilable in frame

0
when i was solving this question i got 260 page fault for optimal

but when i tried for options (i.e MRU) i assumed frames will have 101 to 120

which will not give the answer

so here we have to assume those frames are empty to get 260 faults (from MRU)

am i thinking right??
0
yes its always the case we need to take frames as empty until and unless specified
0
i dont want to be annoying

but in this question they said frames are filled and asked which policy will experience same faults so i followed the question!!

but i get it now!
0
Yes here they have mentioned 101 to 120 are present but no occurring sequence is mentioned of them so you cannot say which is most recently used or which is not so just consider 1 fault for every 1 to 20 frame in every algo mentioned in the question (if the occurrence was clearly defined then accordingly we need to take miss and hits )
0
we wont get the answer if we consider 101 to 120 are present

assume they are present

now one of them will surely be the most recent used replace it (any one of it)

now if u continue the frame u replaced will be the one getting replaced not others and hence will get 300 faults
0
303 rt? Also, 120 pages are accessed and repeated thrice. So, it should be 480 page accesses. So, 4*101 = 404 page faults rt?
+2
@ arjun sir their wil be 262 page falut
since 101 to 120 is present now string reffered is 1,2.....,99,100,1,2,3.........99,100,1,2,........99,100

so 101 and 120 will never appear so first time 100 page fault next time 100-19(since we are not replacing these 19 )= 81 page fault ,next time 100-19(since we are not replacing 1 to 18 and 100th page from last time )=81 page fault
so,100+81+81=262 Page fault in both MRU and Optimal pag replacement
+2
i think there will be 300 faults

101 102 ..............................................119 120

now remove one of them say 120

now u can see that the frame containing 1 (which replaced 120) will always contain the Most recently used pages hence 300

ALL THE 300 PAGES WILL GO TO SAME FRAME
0

So, no option is correct?

What would be the number of page faults for these?
and repeats the access sequence ONCE.
and repeats the access sequence
TWICE.
and repeats the access sequence
THRICE.

0
100,200,300
0

and with no repetition of the access sequence?

0

@Arjun sir ,@lgau0522 if we see like that in real practical situations MRU is not that useful then becuase may be these reffered page ie. 101 to120 belong to some other process which is not in running state now so why we need to maintain them unnecessarily as they are also not refer'ed in the given sequence string as well
Consider this as a real life example
suppose we have some pages which were refer'ed by Cpu present in Main memory (RAM) now that prog terminates so new program req new set of pages arrives so RAM dose not clear automatically it is replaced by new set of Pages that is arriving reffered by new program (eg here 1 to 100 are belonging to new prog may be )
since nothing is mentioned regarding those 101 to 120 why we are considering them for MRU and Optimal search  unnecessarily
May be those where of some other process which has been blocked / terminated

#JUST A thought came to my mind

+2
i think all of the page replacement policies will give the same no. of page faults.

300

if i am wrong please provide valid reason.
+2
@kalpish Then they could have mentioned all pages are empty initially :)

@Tamojit-Chatterjee I agree. But it should be 400 and not 300 (repeated thrice should mean happened 4 times). And lets wait if someone can provide a better interpretation of the question.

@Suraj any help?
+1
all give same page faults which is 400 and optimal page replacement gives 100+(100-19)+(100-19)+(100-19) .=343.
+4
Actually in MRU non referenced frames are replaced first and then only MRU ones thus making it optimal here :)
0

sir

initially in 20 page frame 101 to 120 are present.

optimal says remove frame which referenced at last means which also present in page frame at present.

so 1 is push in any  place ans replace of 120 b/c numerically it come last .

now push 2 since 1 comes last

continue the same always remove 1st page frame.

Least-recently-used says which referenced  first

remove 101 first then push 1

remove 102 push 2.

like this work as first in first out.

last in first out works as stack remove which is pushed one step before.

Most-recently-used most recently insert 120 then remove it push 1.

remove 1 push 2....

do it untill we finish..

i got MRU and optimal same page fault with same frame no.

0
Q 2014 2_33  all give same page faults which is 400 and optimal page replacement gives 100+(100-19)+(100-19)+(100-19) .=343.  In first sequence from 1 to 19 and 100  why not considering 100 page as no page fault . ie why 19  why not 20
0
0
As per the question 20 physical frames contain pages from 101 to 120 .Thus in total 120pagess.How is that possible?It means one physical frame contain 6 pages of the program. But as far i know one physical frame is equal to one page.

if that the case in that why not pages numbered 1 to 100(100 pages) are accommodated in those 20 frames which can contain up to 120 pages.it can easily accommodate there:?
+3
why have we not considered them unnecessary in LIFO case?? I dont understand this assumption based questions. Why do they make only such questions. Cant they be bit clear with the question?? will it hurt them??,
0
@Arjun Sir, you said that non refrenced removed first in MRU. Is it the same case in LIFO or LIFO will have 400 faults???
+2
optimal page replacement and MRU will give 100+(100-20)+(100-20)+(100-20) .=340 misses  where as LIFO will give  100+(100-19)+(100-19)+(100-19) .=343 misses.
0
can u explain why?
+1
you must have assumed 101-120 initial frames as invalid then only 343 can come. well i think this question is a bit ambiguous. More of assumption
+42
1 2 3 ---19 20 now 20 gets popped out 21 ,21 gets popped out 22 so at the end of ist round we have 1 2 3 4 --19 100, now 1 to 19 hit ,20 will replace 19 not the hundred (here is the difference from LIFO),so upto 99 we get miss but at 100 again hit so total 20 hit in 2nd round . and frames present are 1 2 3 4........18 99 100, so in 3rd round upto 18 no miss now 19 will replace 18 so again will get a hit at the time of accessing 99 and 100 so again 20 hits ,similarly in 4th round 1 .....17 98 99 100present so 1 to 17 hit and again in 98 ,99,100 we will get hit.. So total 60 hits ..
+1
thanx. but again we have to assume that 100-120 are invalid frames otherwise we wont get the hits.
+3
yes that we have assumed..
+1
0

@Shreya Roy ji Thank You. :)

0

But does the number of page faults for LIFO and MRU differ here?

Arjun yes sir in Case of LIFO Page Fault is  343 (20+80+81+81+81). where as in case of Optimal and MRU its 340.

0
Lifo case :-

still the last in was 100 since it was last inserted, others (next 1 to 19) are just touched means accessed not inserted and lifo means last in first out

so i feel for the placement of 20 in second time element naming 100 will be choosen

+1

@sushmita

@Arjun

I believe MRU is not same as Optimal here. For MRU I am getting 400 pagefaults as at same place all pages are replaced. While in Optimal we get 343 pagefaults.

Please correct me, if i am wrong.
Should I assume 101-120 as invalid

0
Should I assume 101-120 as invalid

yes you have to assume that.
0
What difference LIFO makes ?? Plz explain
0

@Arjun sir,

Actually in MRU non referenced frames are replaced first and then only MRU ones thus making it optimal here

Any reference to this claim? I couldn't find anywhere.

Maybe the process started by using 101 to 120 pages and after that it accessed 1 to 100 repeatedly. Maybe pages 101 to 120 were pre-paged (pre-paging used instead of pure demand paging.)

I am not concerned about "which option to select" .. Only concerned about correct concept.

0

@Deepakk Poonia (Dee)

I think the statement made by @Arjun is incorrect. Non-referred frames will not be the recent ones used for sure and hence not replaced in MRU.

The optimal page replacement algorithm swaps out the page whose next use will occur farthest in the future. In the given question, the computer has 20 page frames and initially page frames are filled with pages numbered from 101 to 120. Then program accesses the pages numbered 1, 2, …, 100 in that order, and repeats the access sequence THRICE. The first 20 accesses to pages from 1 to 20 would definitely cause page fault. When 21st is accessed, there is another page fault. The page swapped out would be 20 because 20 is going to be accessed farthest in future. When 22nd is accessed, 21st is going to go out as it is going to be the farthest in future. The above optimal page replacement algorithm actually works as most recently used in this case. As a side note, the first 100 would cause 100 page faults, next 100 would cause 81 page faults (1 to 19 would never be removed), the last 100 would also cause 81 page faults.

by Loyal (9.9k points)
+1
Thank you for this short and nice explanation! :)
0

@Regina Phalange +2 likes for this short explanation.

+1

As a side note, the first 100 would cause 100 page faults, next 100 would cause 81 page faults (1 to 19 would never be removed), the last 100 would also cause 81 page faults.

First 100 would cause 100 page faults, and every next 100 would cause 80 page faults.

0

How come for the next 100 there will be 80-page faults? As the frame will contain 1,2,3..........19,100 after the first sequence and again for the sequence 1,2,3.......100 the first 19 will be a hit.

EDIT:- Sorry my fault I wasn't considering 100 to be a hit , so there will be 80-page faults. And one more question do we have to consider the sequence 3 times or 4 times? ( Even though it won't  make any difference in the answer)

0
How do we get 20 hits? we get 19 hits in the second round(from 1-19), then 20 will replace 100, 21 will replace 20 and so on again till 100. How is 100 considered a hit in this sequence. I can't figure this out. Please explain
0

@Rishav_Bhatt replying too late .... But i think you had also considered "repeat the access sequence thrice" means sequence of page numbers are accessed 4 times.

0

After the first round the sequence we will be having is 1,2,3,4.............19,100. 100 will be placed in the last frame as 20 will be replaced by 21, then 21 with 22 and so on till 100. Now when the second sequence starts till 1-19 there will be a hit now 20 will now be replaced with 19 as 19 is the will be not used for the longest time, similarly 20 by 21 till 99. Now when in the second sequence we come across 100 it will be a hit. Hence in the second sequence, we get 20 hits

The optimal algorithm gives 340 page faults(assuming 3 sequences from 1-100):

We have 20 frames containing 20 pages:  101, 102, 103, 104.....120. Since these pages are never referred again in future, we will replace them all. So, we now have 1, 2, 3, .... 17, 18, 19, 20 in the frames. 20 would not be used for the longest duration, so we remove 20 and load 21. Repeating this till we reach 100.

Now, we have 1, 2, 3,... 17, 18 , 19, 100. In second repetition we get 19 hits (for 1-19). Now 100 is needed in this repetition but 19 in next.

(1, 2, 3, 4, .... 19, 20,.... 99, 100  | 1, 2, 3,... 19, 20, 100)

So removing 19 and loading 20th page. At this instance main memory has

1, 2, 3, .... 20, ... 99, 100

20 is the best candidate to remove because it'd be needed later than the rest (like 1 , 2, 3...) in next iteration. So removing 20 and loading 21. Again to accommodate 22, 21 is best candidate to be removed. Repeating this process, we reach 100, which is already present in memory. So total hits become 20. Before the next repetition, main memory has

1, 2, 3, ...18, 99, 100

At the beginning, there would be total 18 hits. Since we need 99 and 100 in this iteration, 18 shall be removed, followed by 19, 20.... till 98. So at the end, again we have 20 hits. In the third iteration too, 17 shall be replaced, 98, 99, 100 already found in main memory, summing up the total hits to 20. So total page faults with optimal algorithm are 100+(100-20)+(100-20)+(100-20)=340

This clearly is MRU or most recently used where the latest referred page gets removed. For eg, in first iteration, since 19 was referred last, we removed it. But the frames were not empty at the beginning. Only optimal algorithm looks at the future demands and decides the best course, all the other algorithms make decisions based on previous entries. Hence neither MRU nor LIFO would eliminate all the 20 entries 101, 102, .... 120.

In fact MRU and LIFO in such circumstances would yield same results because they would keep replacing the last entry and perform worst. Thus to answer, we must assume the frames as empty, in which case MRU would better LIFO (because LIFO would remove the last entered page such as 100, thus reducing hits by 1.)

by (109 points)
0

FIFO=LRU=400 page faults

MRU=optimal=340 pf

LIFO=343 pf
+1
If there are 300 pages given(1 to 100, 1 to 100, 1 to 100)..then how page faults occur more than 340 ?

The page frame access sequence is

1,2,3.......19,20,21.....99,100,
1,2,3.......19,20,21.....99,100,
1,2,3.......19,20,21.....99,100,
1,2,3.......19,20,21.....99,100,

Using OPTIMAL replacement method from first 1....100 , first 20 page fault will take place as there are no common pages ,,from 21 to 100 again page fault will take place (these page fault will be equivalent to using MRU replacement method ). after these replacement the page frames will contain [1.....19,100] no pages .Considering the next sequence,no page fault from 1 to 19 and at the 20 page no ,19 will get replaced from the page frame and in the further sequence till 99 there will be page fault(these will be equivalent to using MRU ) and the resulting pages in frames will be 1...18 ,99,100 . going through the further sequence we will get the total page fault as 260 ......... replacing the pages using optimal method is equivalent to MRU replacement method thus answer (D)

by (187 points)
0

which contain pages numbered 101 through 120

Now for page access 1, one of the frame gets replaced and the most recently used frame becomes 1. So, during the next access to page numbered 2, shouldn't page 1 be replaced as per MRU policy?

0
hm yes sir ,i didnt consider that :(
+1
Actually yo are correct. Pages 101-120 are not referenced by the current process. So, they are replaced first even with MRU policy.
0
arjun sir i am getting the same no of page faults for LIFO also. LIFO will also behave as MRU after the frames 1-20 are present in the frames. please clear this huge doubt.

And as you are saying- " Pages 101-120 are not referenced by the current process. So, they are replaced first even with MRU policy." Isnt it the case for LIFO too????
+3
problem with LIFO is :

initially we had 101 ,102,....120 when we load frame no1 then last in was 120 and 1 replaced in 120 ,then when frame 2 come last used was frame 1 again frame 1 replaced, subsequently in the same page frame(i.e 10th frame) we have to replace all the 300 next pages. so number of miss will be 300. but in optimal we have 260 missed. as explained above by arjun sir.
0
Sir, how can MRU policy replace the pages that aren't in it's sequence? MRU derives which pages to remove only from it's own sequence.
Here the options are wrong no option will be matched.
by (385 points)
0
@spider 1896

@tamojeet Chatterjee i am agree with both of you

They shouldn't mention the pages 101 ...to 120 in the frames

If the frames would be remain empty then we can approach this

But for this question i am also getting 300 page faults for all options.

If any one says i am wrong provide me the reason
OPTIMAL will take 340 ( 100 +80+80+80 ) page faults.

FIFO will take 400( 100 +100+100+100 ) page faults.

LRU will take 400( 100 +100+100+100 ) page faults.

MRU will take 340( 100 +80+80+80 ) page faults.

LIFO will take 343 ( 100+81*3 ) page faults

by (371 points)

Correct Answer is MRU. Let's see how

we can convert this problem to 3 pages and 5 page accesses which is accessed 3 times (you can access any no. of times above 2 it does not matter) because ratio of page fault will be same.

Note- Whenever there is repeated sequence like 12345 12345 then optimal convert itself into MRU & whenever there is reverse sequence like12345 54321 then optimal convert itself into LRU.

by Active (4.3k points)
edited
0

@Nitesh Singh 2 Yes bro if we get this idea that "fault rate ratio will be similar",we can save lot of time in exam.But here given like initally 101 to 120 numbered pages are there,so doubt is which one to consider MRU page among them?If we consider like last page 120,then all the faults will occur at 120 for every page since we are not using any other page as per MRU.Then it boiled down to page replacement with no of frames=1.So it should have 300 faults right? Then how  will it be equal with optimal?

Optimal PRA(Page Replacement Algorithm) behaves like MRU PRA  when the sequence is repeated only in case, where the frames are empty.

Here, the frames are already initialized with 101 to 120. So, none of the given options are correct.

by (129 points)