Explain the page replacement policies. Implement LRU, OPT, FIFO for a sequence. Also calculate hits and faults.

66views

written 3.0 years ago by

binitamayekar ★ 6.6k

First In First Out (FIFO) Page Replacement Algorithm

This algorithm works on the principle of “First in First out“.
It replaces the oldest page that has been present in the main memory for the longest time.
It is implemented by keeping track of all the pages in a queue.
The page which resides at the rare end of the queue will be replaced on every page fault.

This algorithm works on the principle of “Last in First out“.
It replaces the newest page that arrived at last in the main memory.
It replaces the page that has not been referred by the CPU for the longest time.
It is implemented by keeping track of all the pages in a stack.

This algorithm replaces the page that will not be referred to by the CPU in the future for the longest time.
It is practically impossible to implement this algorithm.
This is because the pages that will not be used in the future for the longest time can not be predicted.
However, it is the best-known algorithm and gives the least number of page faults.
Hence, it is used as a performance measure criterion for other algorithms.

Given String = 0, 1, 2, 4, 3, 7, 1, 4, 2, 3

Frame Size = 3

FIFO:

String	0	1	2	4	3	7	1	4	2	3
Frame 3			2	2	2	7	7	7	2	2
Frame 2		1	1	1	3	3	3	4	4	4
Frame 1	0	0	0	4	4	4	1	1	1	3
Miss/Hit	M	M	M	M	M	M	M	M	M	M

Page Faults = 10 and Page Hit = 0

LRU:

String	0	1	2	4	3	7	1	4	2	3
Frame 3			2	2	2	7	7	7	2	2
Frame 2		1	1	1	3	3	3	4	4	4
Frame 1	0	0	0	4	4	4	1	1	1	3
Miss/Hit	M	M	M	M	M	M	M	M	M	M

Page Faults = 10 and Page Hit = 0

OPTIMAL:

String	0	1	2	4	3	7	1	4	2	3
Frame 3			2	2	3	7			7	7
Frame 2		1	1	1	1	1			1	1
Frame 1	0	0	0	4	4	4			2	3
Miss/Hit	M	M	M	M	M	M	H	H	M	M

Page Faults = 8 and Page Hit = 2

ADD COMMENT EDIT