Consider the following set of virtual page references in a demand-pages virtual memory system : 0 1 2 1 2 3 1 2 4 1 2 1 2 0 1 2 3 4. Note that there are five unique virtual pages reference. If the physical memory has only four frames, eventually a page fault will occur that will require a replacement policy to take a mapped frame away from a chosen virtual page and give it to the faulting page. The most recently used (MRU) replacement policy takes the frame from the most recent access page. The following example shows the mappings (virtual to physical) and page faults cause by using the MRU policy with this reference string:

Frames		Virtual Page
		0	1	2	1	2	3	1	2	4	1	2	1	2	0	1	2	3	4
0	page to frame mappings ------------------------->	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0
1			1	1	1	1	1	1	2	4	1	2	1	2	2	2	2	3	3
2				2	2	2	3	3	3	3	3	3	4	4	4	4	4	4	4
page faults --------->		x	x	x			x		x	x		x	x	x				x

The pink numbers show which virtual pages are mapped to each of the physical frames for each reference and the x' in the bottom row indicate when a page fault occurred. In this case, ten pages faults occurred and so the page fault rate is equal to 10/18=56%.

Show the mappings and page fault rate if each of the following replacement policies is used instead.

a. First-in, First-out replacement (FIFO)

b. Optimal replacement (OPT)

c. least recently used replacement (LRU)

(Please explain subquestions answers in detail )