Consider a demand paging system with three frames, and the following page reference string: 1 2 3 4 5 4 1 6 4 5 1 3 2. The contents of the frames are as follows initially and after each reference (from left to right):
| initially | after | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| - | 1* | 2* | 3* | 4* | 5* | 4 | 1 | 6* | 4 | 5 | 1* | 3* | 2* |
| - | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 6 | 6 | 6 | 6 | 6 | 2 |
| - | - | 2 | 2 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 1 | 1 | 1 |
| - | - | - | 3 | 3 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 3 | 3 |
The *-marked references cause page replacements.
Which one or more of the following could be the page replacement policy/policies in use?
Answer
(D)
Explanation
The table replaces page 2 at the 4th reference, 3 at the 5th, 1 at the 8th, and then 4, 5 and 6 at the last three.
- Optimal fits. At the 4th reference the frames hold 1, 2, 3, next used at references 7, 13 and 12, so 2, needed farthest ahead, goes. Likewise 3 goes at the 5th reference and 1 at the 8th. At the last three faults no page in memory is used again, so any victim is optimal.
- LRU fails: at the 4th reference it would evict 1, the least recently used page.
- LFU fails: at the 8th reference page 5 has one use and pages 1 and 4 have two, so it would evict 5.
- MFU fails: at the 4th reference pages 1, 2 and 3 have one use each, and a first-in or least-recently-used tie-break evicts 1, not 2.
Answer: D