The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+35 votes
5.8k 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
asked in Operating System by Veteran (106k points)
edited by | 5.8k views
+1
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 ?
+1

For other readers please read @Shreya Roy's comment for getting difference between LIFO and MRU.

+1
How  many Page fault will occur?
0

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)

0
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 ?

please confirm.

5 Answers

+38 votes
Best answer

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.

answered by Active (2.1k points)
edited by
0
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
+12
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 ..
0
thanx. but again we have to assume that 100-120 are invalid frames otherwise we wont get the hits.
+1
yes that we have assumed..
0
Your answer is correct and you should answer this question as a separate answer not as a reply to an answer.
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

@arjun sir please confirm
+8 votes

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.

answered by Loyal (8.6k points)
0
Thank you for this short and nice explanation! :)
+6 votes

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)

answered by (203 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 :(
0
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????
+2
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.
+4 votes

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.)

answered by (75 points)
+2 votes
Here the options are wrong no option will be matched.
answered by (321 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
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,599 questions
48,601 answers
155,674 comments
63,741 users