TAOCP 2.5 Exercise 3

Let the usable payload in a node be $k-b$ words.

taocpmathematicsalgorithmsvolume-1

Section 2.5: Dynamic Storage Allocation

Exercise 3. [**] [40] By computer simulation, compare the best-fit, first-fit, and worst-fit methods of storage allocation; in the latter method, the largest available block is always chosen. Is there any significant difference in the memory usage?

Verified: no
Solve time: 41s

Let the usable payload in a node be $k-b$ words. An item of length $l$ then occupies

$$ \left\lceil \frac{l}{k-b}\right\rceil $$

nodes, so the expected storage consumed is

$$ k,\left\langle \left\lceil \frac{l}{k-b}\right\rceil \right\rangle . $$

Using the assumption that the average value of $\bigl(l/(k-b)\bigr)\bmod 1$ is $1/2$, the average excess introduced by the ceiling function is $1/2$. Hence

$$ \left\langle \left\lceil \frac{l}{k-b}\right\rceil \right\rangle = \frac{L}{k-b}+\frac12, $$

and the average storage required is

$$ S(k)=k\left(\frac{L}{k-b}+\frac12\right). $$

Writing $x=k-b>0$, so that $k=x+b$, gives

$$ S(x)=\frac{L(x+b)}{x}+\frac{x+b}{2} = L+\frac{Lb}{x}+\frac{x}{2}+\frac{b}{2}. $$

The variable part is

$$ \frac{Lb}{x}+\frac{x}{2}. $$

By the arithmetic-geometric mean inequality,

$$ \frac{Lb}{x}+\frac{x}{2} \ge 2\sqrt{\frac{Lb}{2}} = \sqrt{2Lb}, $$

with equality if and only if

$$ \frac{Lb}{x}=\frac{x}{2}, $$

that is,

$$ x^2=2Lb. $$

Therefore the minimum occurs at

$$ x=\sqrt{2Lb}, $$

so the optimal node size is

$$ \boxed{k=b+\sqrt{2Lb}}. $$

Since equality in the arithmetic-geometric mean inequality is attained at this value, no other choice of $k$ can yield a smaller average storage requirement. ∎