1.6k views

A process, has been allocated $3$ page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): $1, 2, 1, 3, 7, 4, 5, 6, 3, 1$

Least Recently Used (LRU) page replacement policy is a practical approximation to optimal page replacement. For the above reference string, how many more page faults occur with LRU than with the optimal page replacement policy?

1. $0$
2. $1$
3. $2$
4. $3$

edited | 1.6k views
+1
In full length test it is showing option b as a correct answer. So, please correct it.

Using $LRU = 9$ Page Fault

Using Optimal$= 7$ Page Fault

So, LRU-OPTIMAL $=2$

Option (C).

by Boss (38.7k points)
edited by
+3
option C).
Optimal replacement policy

1     1      1     1     1

2      7      4     5     6

3      3      3     3     3

For Pages 1 2 3 6 4 5  6, page faults occur

LRU replacement policy

9 page faults occur page fault occurs for pages 1 2 3 7 4 5 6 3 1

So 2 more page faults than optimal algorithm

So the answer is $(C)$
by Boss (31.4k points)
edited

Solution to the above problem.

Tip: In question asking no. of page fault always calculate no. of  page hit as its count will be less so keeping a track on its count will be easy.

No. of Page fault =Total length of reference string - No. of Page Hit

by (215 points)