Question

Page Replacement Algorithms. Consider the following page reference stream and 3 page frames: 0 1 2 3 2 4 3 1 1 5 2 4 6 3 3 4 6 3 4 7.
For the MIN, FIFO, and LRU algorithms, show the contents of the page frame after each reference, and then compute the total number of page faults, divided in to cold misses and other misses.

Answer 1

min algorithm or optimal page replacement ;-

y-> yes

n-> no

total page fault ->9

string	0	1	2	3	2	4	3	1	1	5	2	4	6	3	3	4	6	3	4	7
frame 1	0	0	0	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	7
frame 2		1	1	1	1	1	1	1	1	5	2	2	6	6	6	6	6	6	6	6
frame 3			2	2	2	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4
page fault ?	y	y	y	y	n	y	n	n	n	y	y	n	y	n	n	n	n	n	n	y

fifo

total page fault -> 12

string	0	1	2	3	2	4	3	1	1	5	2	4	6	3	3	4	6	3	4	7
frame 1	0	0	0	3	3	3	3	3	3	5	5	5	6	6	6	6	6	6	6	6
frame 2		1	1	1	1	4	4	4	4	4	2	2	2	3	3	3	3	3	3	3
frame 3			2	2	2	2	2	1	1	1	1	4	4	4	4	4	4	4	4	7
page fault ?	y	y	y	y	n	y	n	y	n	y	y	y	y	y	n	n	n	n	n	y

c) lru algorithm

total page fault 12

string	0	1	2	3	2	4	3	1	1	5	2	4	6	3	3	4	6	3	4	7
frame 1	0	0	0	3	3	3	3	3	3	3	2	2	2	3	3	3	3	3	3	3
frame 2		1	1	1	1	4	4	4	4	5	5	5	6	6	6	6	6	6	6	7
frame 3			2	2	2	2	2	1	1	1	1	4	4	4	4	4	4	4	4	4
page fault ?	y	y	y	y	n	y	n	y	n	y	y	y	y	y	n	n	n	n	n	y