GATE CS 2020 Q11 — Memory Management and Virtual Memory

Let the memory requirement of the new process be $P$. Suppose the available holes in the memory that are large enough to accommodate the process are represented by the set $S = \{H_1, H_2, \dots, H_k\}$, where each $H_i \ge P$.

When a process of size $P$ is allocated to a hole of size $H$, the size of the newly created remaining hole is given by $(H - P)$.

Analyzing the Options:

• Best Fit Strategy: By definition, the Best Fit algorithm searches the entire list of holes and allocates the process to the smallest hole that is large enough.
  Let $H_{\text{best}}$ be the hole selected by Best Fit. Then: $$H_{\text{best}} = \min(\{H_i \in S\})$$
• First Fit Strategy: First Fit allocates the process to the first hole $H_{\text{first}} \in S$ that it encounters. Since $H_{\text{best}}$ is the absolute minimum among all valid holes in $S$, we must have: $$H_{\text{best}} \le H_{\text{first}}$$ Subtracting $P$ from both sides: $$H_{\text{best}} - P \le H_{\text{first}} - P$$ This means the remaining hole created by Best Fit is always less than or equal to (i.e., never larger than) the remaining hole created by First Fit.
  Hence, Option C is TRUE.

Why other options are incorrect:

• Option A & B: If there is only one hole available in the system that can accommodate the process, all strategies (First Fit, Next Fit, Best Fit, Worst Fit) will choose this same hole. The resulting new hole size will be identical for all of them. Thus, the hole created by First Fit or Worst Fit is not always larger than others.
• Option D: Since Best Fit always produces the smallest possible leftover hole, any other strategy (including Next Fit) will produce a leftover hole that is greater than or equal to that of Best Fit. Thus, Next Fit is never smaller (i.e., it is often larger) than Best Fit.