Question 21

Let $P$ be the memory requirement of the new process. When allocating memory from an existing hole of size $H > P$, the size of the remaining smaller hole created is $H - P$.

Definitions of the placement strategies:

• Best Fit selects the smallest hole that is large enough: $H_{\text{best}} = \min \{H_i \mid H_i > P\}$.
• First Fit selects the first hole encountered in memory that satisfies $H_{\text{first}} > P$.

Comparison:

• By definition of the minimum, $H_{\text{best}} \le H$ for every candidate hole $H$ that fits the process. Specifically, $H_{\text{best}} \le H_{\text{first}}$.
• Subtracting $P$ from both sides: $H_{\text{best}} - P \le H_{\text{first}} - P$.
• Therefore, the hole left behind by best fit is never larger than the hole left behind by first fit.