GATE CS 1998 Q2.16 — Memory Management and Virtual Memory

In an overlay structure, only the modules lying on a single active path from the root to a leaf need to reside in the physical memory simultaneously. Therefore, the minimum size of the physical memory partition required is the maximum sum of module sizes along any root-to-leaf path.

The overlay tree consists of the following paths and their respective memory requirements:

• Path 1: $\text{Root (2 KB)} \rightarrow \text{A (4 KB)} \rightarrow \text{C (6 KB)} \implies 2 + 4 + 6 = 12\text{ KB}$
• Path 2: $\text{Root (2 KB)} \rightarrow \text{A (4 KB)} \rightarrow \text{D (8 KB)} \implies 2 + 4 + 8 = 14\text{ KB}$
• Path 3: $\text{Root (2 KB)} \rightarrow \text{B (6 KB)} \rightarrow \text{E (2 KB)} \implies 2 + 6 + 2 = 10\text{ KB}$
• Path 4: $\text{Root (2 KB)} \rightarrow \text{B (6 KB)} \rightarrow \text{F (4 KB)} \implies 2 + 6 + 4 = 12\text{ KB}$

The maximum memory required by any path is $\max(12, 14, 10, 12) = 14\text{ KB}$. Thus, a partition of size 14 KB is required to run this program.