GATE CS 2016 Set 1 Q49 — Memory Management and Virtual Memory

We are given $10$ physical page frames and an access sequence of length $40$:

$$(a_{1}, a_{2}, \dots, a_{20}, a_{1}, a_{2}, \dots, a_{20})$$

1. Last-In-First-Out (LIFO) Policy:

• First 10 accesses ($a_1$ to $a_{10}$): $10$ page faults. Frames contain $\{a_1, a_2, \dots, a_{10}\}$.
• Next 10 accesses ($a_{11}$ to $a_{20}$): $10$ page faults. Each new page replaces the most recently loaded page in the $10^{\text{th}}$ frame. After $a_{20}$, the frames contain $\{a_1, a_2, \dots, a_9, a_{20}\}$.
• Second half ($a_1$ to $a_{20}$):
  • $a_1$ to $a_9$ are hits ($0$ faults).
  • $a_{10}$ causes a page fault and replaces $a_{20}$.
  • $a_{11}$ to $a_{20}$ each cause a page fault, sequentially replacing the page in the $10^{\text{th}}$ frame ($11$ faults total for $a_{10} \dots a_{20}$).

Total LIFO page faults = $10 + 10 + 11 = 31$.

2. Optimal Page Replacement Policy:

• First 10 accesses ($a_1$ to $a_{10}$): $10$ page faults. Frames contain $\{a_1, a_2, \dots, a_{10}\}$.
• Next 10 accesses ($a_{11}$ to $a_{20}$): $10$ page faults. To minimize future faults, we replace the page whose next reference is furthest in the future:
  • $a_{11}$ replaces $a_{10}$ (since $a_{10}$ is needed at step $30$, while $a_1 \dots a_9$ are needed earlier).
  • $a_{12}$ replaces $a_{11}$, and so on, up to $a_{20}$ replacing $a_{19}$.
  • Frames after the first half: $\{a_1, a_2, \dots, a_9, a_{20}\}$.
• Second half ($a_1$ to $a_{20}$):
  • $a_1$ to $a_9$ are hits ($0$ faults).
  • $a_{10}$ to $a_{19}$ cause $10$ page faults. We can replace any of the pages $a_1 \dots a_9$ as they are not needed anymore, keeping $a_{20}$ in memory.
  • $a_{20}$ is a hit ($0$ faults).

Total Optimal page faults = $10 + 10 + 10 = 30$.

The difference in the number of page faults is $31 - 30 = 1$.