The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+15 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}$
asked in Operating System by Veteran (385k points)
edited by | 1.9k views

3 Answers

+14 votes
Best answer

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

Answer is (B).

answered by Loyal (6.1k points)
edited by
+3 votes

Option :- B

answered by Loyal (8.5k points)
+2 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}
\begin{array}{|c|c|c|}\hline 1_\boxed{2} \\ \hline \cancel{2}4_\boxed{3}\\\hline3_\boxed{1}\\ \hline \end{array}
\begin{array}{|c|c|c|}\hline 1_\boxed{2} \\ \hline \cancel{2}4_\boxed{3}\\\hline\cancel{3}2_\boxed{1}\\ \hline \end{array}
\begin{array}{|c|c|c|}\hline 1_\boxed{3} \\ \hline \cancel{2}4_\boxed{1}\\\hline\cancel{3}2_\boxed{2}\\ \hline \end{array}
\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. 

answered by Veteran (385k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
47,932 questions
52,335 answers
67,817 users