GATE CSE 2007 | Question: 83

Question

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?

• A. $0$
• B. $1$
• C. $2$
• D. $3$

Comments

In full length test it is showing option b as a correct answer. So, please correct it.

---

Note that rest of the faults will we first acces fault (as in optimal), extra faults will be for reference to 1 and 3 at the end.

Answer 1

Using $LRU = 9$ Page Fault

Using Optimal$ = 7$ Page Fault

So, LRU-OPTIMAL $=2$

Option (C).

Comments

option C).

Answer 2

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

Answer 3

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

Answer 4

Optimal: 7 page faults. https://gateoverflow.in/1274/gate2007-82?show=334037#a334037

LRU: 9 page faults

1	2	1	3	7	4	5	6	3	1
			3	3	3	5	5	5	1
	2	2	2	7	7	7	6	6	6
1	1	1	1	1	4	4	4	3	3
F	F	$\times$	F	F	F	F	F	F	F

 $Ans: 9-7=2$