Question

Consider the following page reference string: 1, 0, 3, 2, 6, 4, 5, 0, 1, 7, 7, 6, 4, 3, 5, 2, 1, 3, 2, 7 Assuming demand paging with three frames, how many page faults would occur for the following replacement algorithms? Show your work.

(a) LRU replacement

(b) FIFO replacement

(c) Optimal replacement

Answer 1

the frames at the reference are shown as follows:
LRU
3 page fault 1
3 0        page fault 2
3 0 1   page fault 3
2 3 0        page fault 4
6 2 3        page fault 5
4 6 2       page fault 6
5 4 6       page fault 7
0 5 4       page fault 8
1 0 5        page fault 9
7 1 0       page fault 10
6 7 1       page fault 11
4 6 7       page fault 12
3 4 6       page fault 13
5 3 4       page fault 14
2 5 3       page fault 15
1 2 5       page fault 16
3 1 2       page fault 17
7 3 2       page fault 18

Total no of page fault 18

FIFO
3 page fault 1
3 0        page fault 2
3 0 1   page fault 3
2 3 0        page fault 4
6 2 3        page fault 5
4 6 2       page fault 6
5 4 6       page fault 7
0 5 4       page fault 8
1 0 5        page fault 9
7 1 0       page fault 10
6 7 1       page fault 11
4 6 7       page fault 12
3 4 6       page fault 13
5 3 4       page fault 14
2 5 3       page fault 15
1 2 5       page fault 16
3 1 2       page fault 17
7 3 1       page fault 18

Total no of page fault 18

Optimal replacement
3 page fault 1
3 0        page fault 2
3 0 1   page fault 3
6 0 1        page fault 4
4 0 1        page fault 5
5 0 1       page fault 6
5 7 1        page fault 7
5 6 1       page fault 8
5 4 1        page fault 9
5 3 1       page fault 10
2 3 1       page fault 11
2 3 7       page fault 12

Total no of page fault 12