The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+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

- $\text{OPTIMAL} < \text{LRU} < \text{FIFO}$
- $\text{OPTIMAL} < \text{FIFO} < \text{LRU}$
- $\text{OPTIMAL} = \text{LRU}$
- $\text{OPTIMAL} = \text{FIFO}$

+14 votes

+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}

\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.

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 555
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,932 questions

52,335 answers

182,384 comments

67,817 users