Consider a page reference string as: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2. Assume that there are 3-page frames available. Calculate the total number of page faults for the above reference string if LRU policy is used for page replacement.
Step-by-step Solution:
Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
Number of frames = 3. We simulate LRU (least recently used): when a page is referenced, it becomes the most recently used; on a miss, evict the least recently used page.
| Step | Page | Frames (LRU → MRU) | Result |
|---|---|---|---|
| 1 | 7 | [7] | Fault |
| 2 | 0 | [7, 0] | Fault |
| 3 | 1 | [7, 0, 1] | Fault |
| 4 | 2 | [0, 1, 2] | Fault (evict 7) |
| 5 | 0 | [1, 2, 0] | Hit (0 becomes MRU) |
| 6 | 3 | [2, 0, 3] | Fault (evict 1) |
| 7 | 0 | [2, 3, 0] | Hit (0 becomes MRU) |
| 8 | 4 | [3, 0, 4] | Fault (evict 2) |
| 9 | 2 | [0, 4, 2] | Fault (evict 3) |
| 10 | 3 | [4, 2, 3] | Fault (evict 0) |
| 11 | 0 | [2, 3, 0] | Fault (evict 4) |
| 12 | 3 | [2, 0, 3] | Hit (3 becomes MRU) |
| 13 | 2 | [0, 3, 2] | Hit (2 becomes MRU) |
Total page faults = 9.
Answer: 9 page faults.