GATE CS 2010 Q24 — Memory Management and Virtual Memory

We can analyze the page faults by dividing the process into two phases:

Phase 1: First 100 accesses
Let the 100 distinct pages be accessed in the order $P_1, P_2, \dots, P_{100}$. Since all 100 pages are distinct and the 4 frames are initially empty, every access results in a page fault.
$$\text{Page faults in Phase 1} = 100$$ At the end of Phase 1, the 4 frames will contain the last 4 accessed pages: $\{P_{97}, P_{98}, P_{99}, P_{100}\}$.

Phase 2: Reverse 100 accesses
The pages are now accessed in the reverse order: $P_{100}, P_{99}, P_{98}, P_{97}, P_{96}, \dots, P_1$.

• The first 4 accesses ($P_{100}, P_{99}, P_{98}, P_{97}$) are already present in the frames. Thus, these 4 accesses result in hits (0 page faults).
• The remaining 96 accesses ($P_{96}$ down to $P_1$) are not present in the frames. Since we are moving strictly downwards in index, each of these 96 accesses will result in a page fault.

$$\text{Page faults in Phase 2} = 96$$

Total Page Faults:
$$\text{Total faults} = 100 \text{ (Phase 1)} + 96 \text{ (Phase 2)} = 196$$