6k views
Consider a computer system with ten physical page frames. The system is provided with an access sequence $(a_{1}, a_{2},....,a_{20}, a_{1}, a_{2},...a_{20})$, where each $a_{i}$ is a distinct virtual page number. The difference in the number of page faults between the last-in-first-out page replacement policy and the optimal page replacement policy is_________.

edited | 6k views
+9

@srestha @Arjun Sir
pls see the above  diagram for optimal solution .Is this ok ?

+1
yes correct
+1
how 31 for lifo ?
+21

Explanation: LIFO stands for last in, first out
a1 to a10 will result in page faults, So 10 page faults from a1 to a10.
Then a11 will replace a10(last in is a10), a12 will replace a11 and so on till a20, so 10 page faults from a11 to a20 and a20 will be top of stack and a9…a1 are remained as such.
Then a1 to a9 are already there. So 0 page faults from a1 to a9.
a10 will replace a20, a11 will replace a10 and so on. So 11 page faults from a10 to a20. So total faults will be 10+10+11 = 31. Optimal
a1 to a10 will result in page faults, So 10 page faults from a1 to a10.
Then a11 will replace a10 because among a1 to a10, a10 will be used later, a12 will replace a11 and so on. So 10 page faults from a11 to a20 and a20 will be top of stack and a9…a1 are remained as such.
Then a1 to a9 are already there. So 0 page faults from a1 to a9.
a10 will replace a1 because it will not be used afterwards and so on, a10 to a19 will have 10 page faults.
a20 is already there, so no page fault for a20.
Total faults 10+10+10 = 30.
Difference = 1

http://www.geeksforgeeks.org/gate-gate-cs-2016-set-1-question-59/

0

sunita24

thanks a lot

0
I think for secound time access of a10 we can replace any of the (a1 to a9) as further access is not given
+1
in LIFO order last inserted page will be replaced only, not last referred.
–1
0

Answer is $1$.

In LIFO first $20$ are page faults followed by next $9$ hits then next $11$ page faults. (After $a_{10}$, $a_{11}$ replaces $a_{10}, a_{12}$ replaces $a_{11}$ and so on)

In optimal first $20$ are page faults followed by next $9$ hits then next $10$ page faults followed by last page hit.
by (321 points)
edited by
+1
I have a doubt on this one, in LIFO after the first 20 page faults and 9 hits, then the 10th one will replace the 9th page i guess as it is last in first out?
+7
last in was 20th page. 9th was just a page hit
+1
But in FIFO when a hit occurs , we replace that page last.

So, why here we will not think which hit last replaces first?
0
@srestha sorry. did not get your question.
0
Sir I have answered it at last. R u getting it?

In LIFO last access page will be replaces first

In LIFO we replace Last access page  First . As here First put a1 , then a2.......then a10 . As here 10 frames. Now replaces a10 with a11 to a20.

Now we are getting a1 to a9 hit as those are already in first 9 frames. Next a10 will be replace a9 as it is last access frame. And others will replace a10 , a11 will replace a10...........So, a20 will be hit .

Same with optimal too

by Veteran (116k points)
–1
Means after hit a1 to a9 why a9 will not be replaced in LIFO?

Why a20 will be replaced in that place?
+9

Good. So, you just showed that Last Accessed page replacement is optimal here. But in LIFO, it is not the last accessed but the last IN, page that is being replaced first. Is it not?

0

But in FIFO it will not cause any problem . What is the difference in concept behind last access page and last in page

+6
it is similar to LRU and FIFO. LRU means after each use we update the priority for replacement.
+1
ok tnks :)
0
thankssss shrestha mam..!!
+2

@srestha mam

plz edit the LIFO definition and ans it may create wrong concept who will not see comment.

the answer is $31-30=1$

by (165 points)
edited
0
Good efforts !
Zero
by Junior (693 points)
0
ok i got 0 too.. but there were many other clarifications of 1 2 3 ..... and so on..

so plz if few others can comment if 0 is 100% correct or not
+6
0
can u explain sir ?
+2
Answer will be one because a20 will not replace in optimal page replacement algorithm...
0
Also when Optimal Algo fails then considered FIFO. Right.
YES as you see the que and start solving it you will get the illusion that answer is 0 but if solve question fully...answer will come 1.
by (153 points)
0
Absolutely right. In optimal one fault is less and that is becoz of a20.
a20 is hit in a optimal which is miss is LIFO.

LIFO Page Faults ==> 20 + 11 = 31

OPTIMAL Algo Page Faults ==> 20+10 = 30

Difference between {LIFO , OPTIMAL} Page Faults = 31-30 = 1.

Second Approach:

Difference Between Total Hits.

Hits in LIFO = 1.

Hits in OPTIMAL Algo = 1+1 = 2.

Difference between {LIFO , OPTIMAL} Page Faults = 2-1 = 1.

by Active (3.7k points)
+1 vote
zero is correct ans,
by (179 points)
edited
Just try a small example you will get general formula for page fault

For LIFO => ((n/2)-1)+2*(n-(n/2)+1) = 3(n/2)+1

For Optimal => ((n/2)-1)+(n-(n/2)+1) +(n-n/2) = 3(n/2).

In the given problem n = 20.
by Boss (12.9k points)

1
2