edited by
18,669 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

5 votes
5 votes
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.
3 votes
3 votes

Correct Answer : 1.

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.

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

So final answer is 1.

In the given problem n = 20.
Answer:

Related questions

85 votes
85 votes
18 answers
4
Sandeep Singh asked Feb 12, 2016
35,081 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...