2k views

Consider the virtual page reference string

$$\text{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 $\text{LRU}$, $\text{FIFO}$ and $\text{OPTIMAL}$ denote the number of page faults under the corresponding page replacement policy. Then

1. $\text{OPTIMAL} < \text{LRU} < \text{FIFO}$
2. $\text{OPTIMAL} < \text{FIFO} < \text{LRU}$
3. $\text{OPTIMAL} = \text{LRU}$
4. $\text{OPTIMAL} = \text{FIFO}$
edited | 2k views

Page fault for LRU $=9$, FIFO $=6$, OPTIMAL $=5$

edited by
+1

Option :- B

Page reference string is $$1\quad 2 \quad 3\quad 2 \quad 4\quad 1 \quad 3\quad 2 \quad 4 \quad 1$$

$$\require {cancel}\underset{\text{FIFO}}{ \begin{array}{|c|c|c|}\hline \cancel{1} 4 \\ \hline \cancel{2} 1\\\hline \cancel{3} 2\\ \hline \end{array}}$$

In FIFO, when a new page comes and there is no space left, the oldest page which came in is replaced. So, we get $6$ page faults here as shown above.

$$\require {cancel}\underset{\text{LRU}}{ \begin{array}{|c|c|c|}\hline 1_\boxed{1} \\ \hline 2_\boxed{2}\\\hline3\boxed{3}\\ \hline \end{array} \underset{\text{2}}{\implies} \begin{array}{|c|c|c|}\hline1_\boxed{1} \\ \hline 2_\boxed{3}\\\hline 3_\boxed{2}\\ \hline \end{array}\underset{\text{4}}{\implies} \begin{array}{|c|c|c|}\hline \cancel{1} 4_\boxed{3} \\ \hline 2_\boxed{2}\\\hline3_\boxed{1}\\ \hline \end{array}\underset{\text{1}}{\implies} \begin{array}{|c|c|c|}\hline \cancel{1} 4_\boxed{2} \\ \hline 2_\boxed{1}\\\hline\cancel{3}1_\boxed{3}\\ \hline \end{array}\underset{\text{3}}{\implies} \begin{array}{|c|c|c|}\hline \cancel{1} 4_\boxed{1} \\ \hline \cancel{2}3_\boxed{3}\\\hline\cancel{3}1_\boxed{2}\\ \hline \end{array} \underset{\text{2}}{\implies} \begin{array}{|c|c|c|}\hline \cancel{1} \cancel{4}2_\boxed{3} \\ \hline \cancel{2}3_\boxed{2}\\\hline\cancel{3}1_\boxed{1}\\ \hline \end{array} \underset{\text{4}}{\implies} \begin{array}{|c|c|c|}\hline \cancel{1} \cancel{4}2_\boxed{2} \\ \hline \cancel{2}3_\boxed{1}\\\hline\cancel{3}\cancel{1}{4}_\boxed{3}\\ \hline \end{array} \underset{\text{1}}{\implies} \begin{array}{|c|c|c|}\hline \cancel{1} \cancel{4}2_\boxed{1} \\ \hline \cancel{2}\cancel{3}1_\boxed{3}\\\hline\cancel{3}\cancel{1}{4}_\boxed{2}\\ \hline \end{array}}$$

In LRU, when a page comes and there is no space left, the oldest referenced page (unlike the oldest incoming one as in FIFO) gets replaced. So, we get $9$ page replacements as shown above. (The boxed digits shows the LRU number with $1$ being the least recently used one followed by $2$ and so on)

$$\require {cancel}\underset{\text{OPTIMAL}}{ \begin{array}{|c|c|c|}\hline 1_\boxed{2} \\ \hline 2_\boxed{3}\\\hline3\boxed{1}\\ \hline \end{array} \underset{\text{2}}{\implies} \begin{array}{|c|c|c|}\hline1_\boxed{3} \\ \hline 2_\boxed{1}\\\hline 3_\boxed{2}\\ \hline \end{array}\underset{\text{4}}{\implies} \begin{array}{|c|c|c|}\hline 1_\boxed{3} \\ \hline \cancel{2}4_\boxed{1}\\\hline3_\boxed{2}\\ \hline \end{array}\underset{\text{1}}{\implies} \begin{array}{|c|c|c|}\hline 1_\boxed{1} \\ \hline \cancel{2}4_\boxed{2}\\\hline3_\boxed{3}\\ \hline \end{array} \underset{\text{3}}{\implies} \begin{array}{|c|c|c|}\hline 1_\boxed{2} \\ \hline \cancel{2}4_\boxed{3}\\\hline3_\boxed{1}\\ \hline \end{array} \underset{\text{2}}{\implies} \begin{array}{|c|c|c|}\hline 1_\boxed{2} \\ \hline \cancel{2}4_\boxed{3}\\\hline\cancel{3}2_\boxed{1}\\ \hline \end{array} \underset{\text{4}}{\implies} \begin{array}{|c|c|c|}\hline 1_\boxed{3} \\ \hline \cancel{2}4_\boxed{1}\\\hline\cancel{3}2_\boxed{2}\\ \hline \end{array} \underset{\text{1}}{\implies} \begin{array}{|c|c|c|}\hline 1_\boxed{3} \\ \hline \cancel{2}4_\boxed{2}\\\hline\cancel{3}2_\boxed{1}\\ \hline \end{array} }$$

In optimal page replacement when a new page comes and there is no space, the page which is going to be referenced the latest in future will be replaced. So, we get $5$ page replacements as shown above (In the last part of the page replacement, future references are simply assumed and the boxed digits shows the future replacement order with $1$ being the one to get replaced first).

So we get $$\text{OPTIMAL} < \text{FIFO}< \text{LRU}$$

Option B.

1
2