Calculate the number of page faults for the reference string 3, 2, 4, 1, 3, 5,…

Concept

Least Recently Used (LRU) replaces the resident page whose most recent access is the farthest in the past.

A reference is a page fault when the page is absent from every frame; filling an empty frame and replacing a resident page both count as faults.

Application

1. Reference 3: it is absent, so load 3. Frames: [3]. Fault count = 1.

2. Reference 2: it is absent, so load 2. Frames: [3, 2]. Fault count = 2.

3. Reference 4: it is absent, so load 4. Frames: [3, 2, 4]. Fault count = 3.

4. Reference 1: it is absent, so load 1. Frames: [3, 2, 4, 1]. Fault count = 4.

5. Reference 3: page 3 is present, so this is a hit. The frames do not change. Fault count = 4.

6. Reference 5: page 5 is absent. Page 2 is least recently used, so replace 2 with 5. Frames: [3, 5, 4, 1]. Fault count = 5.

7. Reference 2: page 2 is absent. Page 4 is least recently used, so replace 4 with 2. Frames: [3, 5, 2, 1]. Fault count = 6.

8. Reference 1: page 1 is present, so this is a hit. The frames do not change. Fault count = 6.

9. Reference 7: page 7 is absent. Page 3 is least recently used, so replace 3 with 7. Frames: [7, 5, 2, 1]. Fault count = 7.

10. Reference 3: page 3 is absent. Page 5 is least recently used, so replace 5 with 3. Frames: [7, 3, 2, 1]. Fault count = 8.

11. Reference 0: page 0 is absent. Page 2 is least recently used, so replace 2 with 0. Frames: [7, 3, 0, 1]. Fault count = 9.

Cross-check

• The only hits are the second reference to page 3 and the second reference to page 1, so 11 total references minus 2 hits equals 9 faults.

• Counting a second way gives the same figure: 4 references fill the initially empty frames and 5 later references (5, 2, 7, 3 and 0) each find their page absent, and 4 + 5 = 9.

Under LRU with four frames, this reference string therefore produces 9 page faults.