edited by
18,667 views
68 votes
68 votes
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 by

9 Answers

Best answer
77 votes
77 votes
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.
edited by
63 votes
63 votes

the answer is $31-30=1$

edited by
9 votes
9 votes

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 

8 votes
8 votes
Zero
Answer:

Related questions

85 votes
85 votes
18 answers
4
Sandeep Singh asked Feb 12, 2016
35,051 views
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight s...