Assume that there are 3 page frames which are initially empty. If the page…

Key idea: The optimal replacement policy evicts the page whose next use is farthest in the future (or not used again).

Reference string: 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6

1. Reference 1: page fault (frames: 1 _ _). Total faults = 1

2. Reference 2: page fault (frames: 1 2 _). Total faults = 2

3. Reference 3: page fault (frames: 1 2 3). Total faults = 3

4. Reference 4: page fault. Next uses after this point: 2 appears soon, 1 appears soon, 3 appears much later, so evict 3. Frames become 1 2 4. Total faults = 4

5. Reference 2: hit (frames unchanged 1 2 4). Total faults = 4

6. Reference 1: hit (frames unchanged 1 2 4). Total faults = 4

7. Reference 5: page fault. Look ahead: 1 is not used again, 2 and 4 are used later, so evict 1. Frames become 5 2 4. Total faults = 5

8. Reference 3: page fault. Looking ahead, 5 is not used again while 2 and 4 are used later, so evict 5. Frames become 3 2 4. Total faults = 6

9. Reference 2: hit (frames 3 2 4). Total faults = 6

10. Reference 4: hit (frames 3 2 4). Total faults = 6

11. Reference 6: page fault. None of 3, 2, 4 are used again after this point, so evict any; total faults = 7

Total number of page faults = 7