Question

Consider the virtual page reference string 1, 2, 3, 2, 4, 1, 3, 2, 4, 1

Let a computer system has main memory size of 3 page frames which are initially empty and it is running on demand paged virtual memory system. The number of page faults under LRU and FIFO page replacement policy are respectively:

1. 9, 6
2. 6, 3
3. 6, 9
4. 3 , 6

Answer 1

Correct Answer - Option 1 : 9, 6

Concept:

LRU Page Replacement Policy:

LRU (Least recently used) page replacement algorithm is based on the assumption that the page that has been used in the last few instructions will be referenced in the next few instructions. It replaces the page that has not been referenced for the longest time.

Explanation:

Reference string: 1, 2, 3, 2, 4, 1, 3, 2, 4, 1

Number of frames = 3

	1	1	1	1	4	4	4	2	2	2
		2	2	2	2	2	3	3	3	1
			3	3	3	1	1	1	4	4
Page Fault	1	1	1	0	1	1	1	1	1	1

Here, total page faults = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1= 9

FIFO Page Replacement Policy:

It is based on the principle of first in first out. The page which is accessed first in the sequence is replaced first. Also, we can say that during the page fault, the page that has been in memory the longest is replaced.

Explanation:

Reference string: 1, 2, 3, 2, 4, 1, 3, 2, 4, 1

Total frames allocated are 3

	1	1	1	1	4	4	4	4	4	4
		2	2	2	2	1	1	1	1	1
			3	3	3	3	3	2	2	2
Page Fault	1	1	1	0	1	1	0	1	0	0

Here, total page faults = 1 + 1 + 1 + 0 + 1 + 0 + 1 + 0 + 0= 6