GATE 2018 CS Q.10: solution and answer

GATE 2018 · CSQ.10 · 1 mark · MCQ

Consider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is M units if the corresponding memory page is available in memory, and D units if the memory access causes a page fault. It has been experimentally measured that the average time taken for a memory access in the process is X units.

Which one of the following is the correct expression for the page fault rate experienced by the process?

(A)
(D - M) / (X - M)
(B)
(X - M) / (D - M)
(C)
(D - X) / (D - M)
(D)
(X - M) / (D - X)

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The page fault rate is $p = \frac{X - M}{D - M}$ , which is option (B).

Official answer: BSource: Official answer key, GATE 2018 CS (IIT Guwahati)

Let $p$ be the page fault rate. A fraction $1 - p$ of accesses find the page in memory and cost $M$ units; a fraction $p$ cause a page fault and cost $D$ units.
The average access time is the weighted average: $X = (1 - p) M + p D$
Expand: $X = M + p (D - M)$ .
Rearrange: $X - M = p (D - M)$ .
Solve for $p$ : $p = \frac{X - M}{D - M}$
This is option (B). Check: if $X = M$ then $p = 0$ ; if $X = D$ then $p = 1$ .
The other options fail the same check. (A) is the reciprocal of (B), so it gives $p = 1$ when $X = D$ but is undefined when $X = M$ . (C) gives $1$ at $X = M$ and $0$ at $X = D$ , the reverse of what is needed. (D) is undefined at $X = D$ .

KEY IDEA

The measured average access time is a weighted average of the hit time $M$ and the fault time $D$ , with weights $1 - p$ and $p$ . Solve that linear equation for $p$ .

WATCH OUT FOR

Writing the weights the wrong way round, as $X = pM + (1 - p) D$ . That gives $p = \frac{D - X}{D - M}$ , which is option (C), and it is the fraction of accesses that did not fault.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 6 Virtual memory questions, with notes

GATE 2018 CS Q.10: solution and answer

Answer and solution

More Virtual memory questions