Consider the following page reference string: 4,3,2,1,4,3,5,4,3,2,1,5. How many page faults would occur for the following page replacement algorithms assuming three frames? Initially all frames are empty.
FIFO
LRU
Optimal
Answers
Answer:
Consider the following page reference string:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6.
How many page faults occur for the following page replacement algorithms assuming one, three, four, five, six, or seven frames? Assume that all pages are initially used by pages left over from another process, so your first unique pages will all cost one fault each. Your answer to parts a) - c) should include a sketch showing pages resident in memory and those replaced over time, the number of page faults, and any interesting observations
LRU replacement
FIFO replacement
Optimal replacement
Do any of your examples exhibit Belady's anomaly? Explain.
Which page replacement policy would your recommend? Why?
LRU:
3 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 4 5 1 7 2 -
Frame 2: 2 - 6 3 - -
Frame 3: 3 1 2 - 6 1 6
15 faults
4 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - - 6 -
Frame 2: 2 - - - - -
Frame 3: 3 5 3 - -
Frame 4: 4 6 7 1
10 faults
5 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - - -
Frame 2: 2 - - - - -
Frame 3: 3 6 - -
Frame 4: 4 3 - -
Frame 5: 5 7
8 faults
6 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - - -
Frame 2: 2 - - - - -
Frame 3: 3 - - -
Frame 4: 4
Frame 5: 5 7
Frame 6: 6 - -
7 faults, which is the fewest we can have with 7 pages
FIFO:
3 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 4 6 3 - 2 - 6
Frame 2: 2 - 1 2 - 7 1
Frame 3: 3 5 1 6 3
16 faults
4 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - 5 3 - 1
Frame 2: 2 - 6 7 3
Frame 3: 3 2 - 6 -
Frame 4: 4 1 2 -
14 faults
5 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - 6 - -
Frame 2: 2 - - 1 -
Frame 3: 3 2 - -
Frame 4: 4 3 - -
Frame 5: 5 7
10 faults
6 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - - 7
Frame 2: 2 - - - - 1
Frame 3: 3 - - 2
Frame 4: 4 3
Frame 5: 5
Frame 6: 6 - -
10 faults
Optimal:
3 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - - 3 - -
Frame 2: 2 - - - 7 2 -
Frame 3: 3 4 5 6 - 1 6
11 faults
4 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - - 7 1
Frame 2: 2 - - - - -
Frame 3: 3 - - -
Frame 4: 4 5 6 - -
8 faults
5 frames:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
Frame 1: 1 - - - -
Frame 2: 2 - - - - -
Frame 3: 3 - - -
Frame 4: 4 7
Frame 5: 5 6 - -
7 faults, which is the best we can do