GATE CS 2026 Set 2 Q45 — Memory Management and Virtual Memory

We are given the initial set of 8 memory holes of sizes:

$$\{20\text{ KB}, 4\text{ KB}, 25\text{ KB}, 18\text{ KB}, 7\text{ KB}, 9\text{ KB}, 15\text{ KB}, 12\text{ KB}\}$$

Using the best-fit allocation strategy, we allocate memory to processes $P_1$ and $P_2$ in order:

1. Allocation of $P_1$ ($16\text{ KB}$):
   The available holes of size $\ge 16\text{ KB}$ are $18\text{ KB}$, $20\text{ KB}$, and $25\text{ KB}$. The best-fit (smallest sufficient) hole is $18\text{ KB}$.
   After allocation, the remaining hole size is $18 - 16 = 2\text{ KB}$.
   The updated set of holes is: $\{20\text{ KB}, 4\text{ KB}, 25\text{ KB}, 2\text{ KB}, 7\text{ KB}, 9\text{ KB}, 15\text{ KB}, 12\text{ KB}\}$.
2. Allocation of $P_2$ ($9\text{ KB}$):
   The available holes of size $\ge 9\text{ KB}$ are $9\text{ KB}$, $12\text{ KB}$, $15\text{ KB}$, $20\text{ KB}$, and $25\text{ KB}$. The best-fit hole is exactly $9\text{ KB}$.
   After allocation, no remaining hole is left from this block ($9 - 9 = 0\text{ KB}$).
   The final set of holes is: $\{20\text{ KB}, 4\text{ KB}, 25\text{ KB}, 2\text{ KB}, 7\text{ KB}, 15\text{ KB}, 12\text{ KB}\}$.

Now, we count the number of holes of size less than $8\text{ KB}$:

• $4\text{ KB}$ (Yes)
• $2\text{ KB}$ (Yes)
• $7\text{ KB}$ (Yes)

Thus, there are exactly 3 holes of size less than $8\text{ KB}$.