In: Computer Science
Consider the following page reference string:
0, 1, 2, 3, 1, 0, 4, 5, 1, 0, 1, 2, 6, 5, 2, 1, 0, 1, 2, 5
How many page faults would occur for the following replacement algorithms, assuming one, three, five, and seven frames? Remember that all frames are initially empty, so your first unique pages will cost one fault each.
One frame:
Optimal replacement:
string:
No of page faults = 20
LRU replacement :
string:
No of page faults = 20
CLOCK replacement
string:
No of page faults = 20
FIFO replacement
string:
No of page faults = 20
Three frames:
Optimal replacement:
string: 0, 1, 2, 3, 1, 0, 4, 5, 1, 0, 1, 2, 6, 5, 2, 1, 0, 1, 2, 5
0 0 0 0 2 2 2 2 2
1 1 1 1 1 6 1 1 1
2 3 4 5 5 5 5 0 5
No of page faults =11
LRU replacement :
string: 0, 1, 2, 3, 1, 0, 4, 5, 1, 0, 1, 2, 6, 5, 2, 1, 0, 1, 2, 5
0 3 3 4 4 4 0 0 6 6 1 1 1
1 1 1 1 5 5 5 2 2 2 2 2 2
2 2 0 0 0 1 1 1 1 5 5 0 5
No of page faults = 15
CLOCK replacement :
string: 0, 1, 2, 3, 1, 0, 4, 5, 1, 0, 1, 2, 6, 5, 2, 1, 0, 1, 2, 5
0 3 3 4 4 4 0 0 6 6 6 1 1 1
1 1 1 1 5 5 5 2 2 5 5 5 0 5
2 2 0 0 0 1 1 1 1 1 2 2 2 2
No of page faults = 16
FIFO replacement
string: 0, 1, 2, 3, 1, 0, 4, 5, 1, 0, 1, 2, 6, 5, 2, 1, 0, 1, 2, 5
0 3 3 3 5 5 5 2 2 2 1 1 1 5
1 1 0 0 0 1 1 1 6 6 6 0 0 0
2 2 2 4 4 4 0 0 0 5 5 5 2 2
No of page faults = 16
Five frames:
Optimal replacement:
string: 0, 1, 2, 3, 1, 0, 4, 5, 1, 0, 1, 2, 6, 5, 2, 1, 0, 1, 2, 5
0 0 0
1 1 1
2 2 2
3 5 5
4 4 6
No of page faults = 7
LRU replacement :
string: 0, 1, 2, 3, 1, 0, 4, 5, 1, 0, 1, 2, 6, 5, 2, 1, 0, 1, 2, 5
0 0 0 0
1 1 1 1
2 5 5 5
3 3 2 2
4 4 4 6
No of page faults = 8
CLOCK replacement :
string: 0, 1, 2, 3, 1, 0, 4, 5, 1, 0, 1, 2, 6, 5, 2, 1, 0, 1, 2, 5
0 0 0 0
1 1 1 1
2 5 5 5
3 3 2 2
4 4 4 6
No of page faults = 8
FIFO replacement
string: 0, 1, 2, 3, 1, 0, 4, 5, 1, 0, 1, 2, 6, 5, 2, 1, 0, 1, 2, 5
0 5 5 5 5 5
1 1 0 0 0 0
2 2 2 1 1 1
3 3 3 3 2 2
4 4 4 4 4 6
No of page faults = 10
Seven frames:
Optimal replacement:
string: 0, 1, 2, 3, 1, 0, 4, 5, 1, 0, 1, 2, 6, 5, 2, 1, 0, 1, 2, 5
0
1
2
3
4
5
6
No of page faults = 7
LRU replacement :
string: 0, 1, 2, 3, 1, 0, 4, 5, 1, 0, 1, 2, 6, 5, 2, 1, 0, 1, 2, 5
0
1
2
3
4
5
6
No of page faults = 7
CLOCK replacement :
string: 0, 1, 2, 3, 1, 0, 4, 5, 1, 0, 1, 2, 6, 5, 2, 1, 0, 1, 2, 5
0
1
2
3
4
5
6
No of page faults = 7
FIFO replacement
string : 0, 1, 2, 3, 1, 0, 4, 5, 1, 0, 1, 2, 6, 5, 2, 1, 0, 1, 2, 5
0
1
2
3
4
5
6
No of page faults = 7