Question

What is the number of page faults for the following memory reference sequence using LRU considering 3 frames per process?

1, 7, 2, 3, 2, 4, 5, 6, 1

• A. 5
• B. 6
• C. 7
• D. 8

Hint:

Only the repeated 2 is a hit. Count the rest as faults.

Answer 1

The Correct Option is D

Step 1: There are 3 frames and the LRU rule evicts the page that was used least recently. Start with empty frames.

Step 2: Walk through the sequence 1, 7, 2, 3, 2, 4, 5, 6, 1.
1: fault, frames [1].
7: fault, frames [1, 7].
2: fault, frames [1, 7, 2].
3: fault, evict 1 (least recent), frames [7, 2, 3].
2: hit, 2 becomes most recent.
4: fault, evict 7, frames [2, 3, 4].
5: fault, evict 3, frames [2, 4, 5].
6: fault, evict 2, frames [4, 5, 6].
1: fault, evict 4, frames [5, 6, 1].

Step 3: Count the faults: references 1, 7, 2, 3, 4, 5, 6, 1 caused faults, and the second 2 was a hit.

Step 4: That gives \(8\) page faults. The answer is (D) 8.