edited by
10,177 views
23 votes
23 votes

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 by

3 Answers

Best answer
9 votes
9 votes

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. 

selected by
19 votes
19 votes

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

Answer is (B).

edited by
Answer:

Related questions

47 votes
47 votes
6 answers
3
Arjun asked Sep 26, 2014
19,400 views
Consider the $3$ processes, $P1, P2$ and $P3$ shown in the table. $$\small \begin{array}{|c|c|c|} \hline \textbf{Process} & \textbf{Arrival Time} & \textbf{Time Units Req...
34 votes
34 votes
4 answers
4
gatecse asked Aug 5, 2014
12,796 views
A process executes the codefork(); fork(); fork();The total number of child processes created is$3$$4$$7$$8$