The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+15 votes

A system uses $3$ page frames for storing process pages in main memory. It uses the Least Recently Used (**LRU**) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below?

$\text{4, 7, 6, 1, 7, 6, 1, 2, 7, 2}$

+15 votes

Best answer

Total page faults $=6.$

$\small\begin{array}{|c|c|c|c|} \hline \quad\bf{4}\quad& \quad\bf{7} \quad& \quad \bf{6}\quad & \quad\bf{1}\quad&\quad\bf{7}\quad&\quad \bf{6}\quad &\quad \bf{1}\quad &\quad \bf{2}\quad &\quad \bf{7}\quad &\quad \bf{2}\quad \\ \hline & & \underset{\boxed{F}}6&6&6&6&6&6&\underset{\boxed{F}}7&7\\ \hline \hline &\underset{\boxed{F}}7 &7 &7&7&7&7&\underset{\boxed{F}}2&2&2\\ \hline

\hline \underset{\boxed{F}}{4}&4 & 4&\underset{\boxed{F}}1&1&1&1&1&1&1\\ \hline

\end{array} \implies 6\text{ faults}$

Another way of answering the same.

$\require{cancel} \begin{array}{|c|}\hline

\quad6\quad \\\hline 7\\\hline\quad\cancel {4} \quad 1\\ \hline

\end{array}$ $\require{cancel} \begin{array}{|c|}\hline

\quad6\quad \\\hline \cancel{7}{2}\\\hline 1\\ \hline

\end{array}$ $\require{cancel} \begin{array}{|c|}\hline

\quad\cancel {6}{7}\quad \\\hline{2}\\\hline1\\ \hline

\end{array}$$\require{cancel} \begin{array}{|c|}\hline

\quad7\quad \\\hline {2}\\\hline 1\\ \hline

\end{array}$ $\implies 3 \text{ faults}+3 \text{ initial access faults} = 6 \text{ page faults}$

**OR**

$\require{cancel} \begin{array}{|c|}\hline

\quad\cancel6 7\quad \\\hline\cancel {7}2\\\hline\cancel 4 1\\ \hline

\end{array} \implies 3 \text{ faults}+3 \text{ initial access faults} = 6 \text{ page faults}$

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 585
- Exam Queries 572
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,126 questions

53,251 answers

184,757 comments

70,502 users