Question 43

Reference string: 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6
Number of frames = 3 (initially empty).

1. Page 1: Page Fault $\implies [1]$ (Fault 1)
2. Page 2: Page Fault $\implies [1, 2]$ (Fault 2)
3. Page 3: Page Fault $\implies [1, 2, 3]$ (Fault 3)
4. Page 4: Page Fault. Frames contain $\{1, 2, 3\}$. Future references: 2 (at pos 5), 1 (at pos 6), 3 (at pos 8). Page 3 is referenced farthest in future, so replace 3 with 4 $\implies [1, 2, 4]$ (Fault 4)
5. Page 2: Hit $\implies [1, 2, 4]$
6. Page 1: Hit $\implies [1, 2, 4]$
7. Page 5: Page Fault. Frames contain $\{1, 2, 4\}$. Future references: 3 (pos 8), 2 (pos 9), 4 (pos 10), 6 (pos 11). Page 1 is never referenced again, so replace 1 with 5 $\implies [5, 2, 4]$ (Fault 5)
8. Page 3: Page Fault. Frames contain $\{5, 2, 4\}$. Future references: 2 (pos 9), 4 (pos 10), 6 (pos 11). Page 5 is never referenced again, so replace 5 with 3 $\implies [3, 2, 4]$ (Fault 6)
9. Page 2: Hit $\implies [3, 2, 4]$
10. Page 4: Hit $\implies [3, 2, 4]$
11. Page 6: Page Fault. Frames contain $\{3, 2, 4\}$. No future references remain, replace any frame (e.g., 3) $\implies [6, 2, 4]$ (Fault 7)

Total number of page faults = 7.