Question

Consider the virtual page reference string

1, 2, 3, 2, 4, 1, 3, 2, 4, 1

on a demand paged virtual memory system running on a computer system that has main memory size of 3 page frames which are initially empty. Let LRU, FIFO and OPTIMAL denote the number of page faults under the corresponding page replacement policy. Then

1. OPTIMAL < LRU < FIFO
2. OPTIMAL < FIFO < LRU
3. OPTIMAL = LRU
4. OPTIMAL = FIFO

Answer 1

Correct Answer - Option 2 : OPTIMAL < FIFO < LRU

The correct answer is Option 2.

Concept:

First In First Out (FIFO):

In this algorithm, the operating system keeps track of all pages in the memory in a queue. The oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal.

Optimal Page replacement:
In this algorithm, pages are replaced which would not be used for the longest duration of time in the future.

Least Recently Used :
In this algorithm, the page will be replaced which is least recently used.

Solution: 

First In First Out (FIFO):

The given virtual page reference string is 1, 2, 3, 2, 4, 1, 3, 2, 4, 1 and the main memory size is 3-page frames.

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
F	F	F	H	F	F	H	F	H	H

Total number of page faults= 6

Optimal Page replacement:

1	1	1	1	1	1	1	1	1	1
	2	2	2	4	4	4	4	4	4
		3	3	3	3	3	2	2	2
F	F	F	H	F	H	H	F	H	H

Total number of page faults= 5

Least Recently Used :

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
F	F	F	H	F	F	F	F	F	F

Total number of page faults= 9

The number of page faults with OPTIMAL, FIFO, LRU (5,6,9) is OPTIMAL < FIFO < LRU.