TAOCP 2.5 Exercise 38
Let M=\left\lfloor\frac{3n-1}{2}\right\rfloor .
Section 2.5: Dynamic Storage Allocation
Exercise 38. [**] [M21] (J. M. Robson.) The lunch-counter problem in exercises 36 and 37 can be generalized to establish the worst-case performance of any dynamic storage allocation algorithm that never relocates reserved blocks. Let $N(n,m)$ be the smallest amount of memory such that any series of requests for allocation and liberation can be handled without overflow, provided that all block sizes are $\leq m$ and the total amount of space requested never exceeds $n$. Exercises 36 and 37 prove that $N(16,2)=23$; determine the exact value of $N(n,2)$ for all $n$.
Verified: no
Solve time: 5m15s
Let
$$ M=\left\lfloor\frac{3n-1}{2}\right\rfloor . $$
We shall prove that
$$ N(n,2)=M. $$
The proof has two parts.
Upper bound
We show that memory of size $M$ always suffices.
Number the memory locations $1,2,\ldots,M$. Reserve the locations
$$ 2,5,8,\ldots $$
for possible use by blocks of size $2$; blocks of size $1$ will never be placed there.
The reserved locations are exactly those congruent to $2 \pmod 3$. Their number is
$$ \left\lfloor\frac{M+1}{3}\right\rfloor . $$
If $n=2k$, then $M=3k-1$, hence
$$ \left\lfloor\frac{M+1}{3}\right\rfloor = \left\lfloor\frac{3k}{3}\right\rfloor = k = \left\lfloor\frac{n}{2}\right\rfloor . $$
If $n=2k+1$, then $M=3k+1$, hence
$$ \left\lfloor\frac{M+1}{3}\right\rfloor = \left\lfloor\frac{3k+2}{3}\right\rfloor = k = \left\lfloor\frac{n}{2}\right\rfloor . $$
Thus the number of nonreserved locations is
$$ M-\left\lfloor\frac n2\right\rfloor=n. $$
Therefore there are always at least $n$ locations available for blocks of size $1$. Since the total occupied space never exceeds $n$, every request for a block of size $1$ can be satisfied.
It remains to consider requests for blocks of size $2$.
Suppose that no pair of adjacent free locations exists. Partition the memory into triples
$$ (1,2,3),\ (4,5,6),\ldots . $$
In each complete triple, the pairs $(1,2)$ and $(2,3)$ cannot both be free. Hence every complete triple contains at least two occupied locations.
$n=2k+1$
Then $M=3k+1$. There are $k$ complete triples, so at least $2k=n-1$ locations are occupied.
$n=2k$
Then $M=3k-1$. There are $k-1$ complete triples and two remaining locations.
The complete triples contain at least
$$ 2(k-1)=n-2 $$
occupied locations. If both remaining locations were free, they would form a free adjacent pair. Hence at least one of them is occupied. Therefore at least
$$ n-1 $$
locations are occupied.
Thus in every case, if no size-$2$ block can be allocated, the currently occupied space is at least $n-1$.
A further request for a block of size $2$ would increase the occupied space to at least
$$ (n-1)+2=n+1, $$
contrary to the hypothesis that the total requested space never exceeds $n$.
Therefore every legal request can be satisfied, and
$$ N(n,2)\le M. $$
Lower bound
We now show that memory of size $M-1$ does not suffice.
Let
$$ L=M-1 = \left\lfloor\frac{3n-1}{2}\right\rfloor-1. $$
Consider an arbitrary allocation algorithm.
A packing parameter
For any memory configuration, let the free gaps have lengths
$$ g_1,g_2,\ldots,g_r . $$
Define
$$ P=\sum_{i=1}^{r}\Bigl\lfloor \frac{g_i}{2}\Bigr\rfloor . $$
$P$ is the maximum number of size-$2$ blocks that can be placed into the currently free space, because a gap of length $g$ can accommodate exactly $\lfloor g/2\rfloor$ disjoint blocks of length $2$.
If the total free space is
$$ F=\sum g_i, $$
and $x$ of the gaps have odd length, then
$$ \Bigl\lfloor\frac{g_i}{2}\Bigr\rfloor = \frac{g_i}{2} \quad(g_i\text{ even}), $$
$$ \Bigl\lfloor\frac{g_i}{2}\Bigr\rfloor = \frac{g_i-1}{2} \quad(g_i\text{ odd}), $$
hence
$$ P = \frac{F-x}{2}. \tag{1} $$
Initial configuration
The adversary first requests $n$ blocks of size $1$.
Let the occupied locations be listed from left to right. Select alternating occupied locations, beginning with the first. Let $S$ be the set of selected blocks.
Then
$$ |S| = \left\lceil\frac n2\right\rceil . \tag{2} $$
Let $x$ be the number of odd free gaps in the current configuration.
Since total free space equals
$$ F=L-n, $$
every odd gap has length at least $1$, so
$$ x\le F=L-n. \tag{3} $$
Delete from $S$ every selected block that is adjacent to an odd free gap.
Because the selected blocks are alternating, no two selected blocks are adjacent. An odd gap can touch at most one selected block. Therefore at most $x$ selected blocks are discarded.
Hence at least
$$ R=\left\lceil\frac n2\right\rceil-x \tag{4} $$
selected blocks remain.
The adversary now liberates exactly these $R$ blocks.
Effect on the packing parameter
We claim that liberating one of these chosen blocks does not increase $P$.
Let a liberated block be adjacent to gaps of lengths $a$ and $b$, where a missing side is regarded as a gap of length $0$.
Because the block was retained, it is adjacent to no odd gap. Therefore every nonzero gap among $a,b$ is even.
Before the liberation, the contribution to $P$ from the neighboring gaps is
$$ \frac a2+\frac b2. $$
After liberation, those gaps merge with the released location into one gap of length
$$ a+b+1, $$
which is odd. Its contribution becomes
$$ \Bigl\lfloor\frac{a+b+1}{2}\Bigr\rfloor = \frac{a+b}{2}. $$
Thus the contribution to $P$ is unchanged.
Since the chosen liberated blocks are separated by at least one occupied location, these local changes are independent. Consequently $P$ is unchanged after all $R$ liberations.
Therefore the final value of $P$ equals its initial value.
Computing the available capacity
Initially,
$$ F=L-n. $$
By (1),
$$ P=\frac{F-x}{2} = \frac{L-n-x}{2}. $$
Since
$$ L= \left\lfloor\frac{3n-1}{2}\right\rfloor-1, $$
one checks separately for even and odd $n$ that
$$ \frac{L-n}{2} = \left\lceil\frac n2\right\rceil-1. $$
Hence
$$ P = \left\lceil\frac n2\right\rceil-1-\frac x2. $$
Since $P$ is an integer,
$$ P \le \left\lceil\frac n2\right\rceil-1-x. \tag{5} $$
From (4),
$$ R=\left\lceil\frac n2\right\rceil-x. $$
Combining with (5),
$$ P<R. $$
Thus after the liberations there is room for at most $P$ blocks of size $2$, but the adversary can immediately request $R$ blocks of size $2$.
The total requested space is
$$ n-R+2R=n+R. $$
These requests are issued one at a time. Each liberated size-$1$ block frees one unit before the corresponding size-$2$ request is made, so the total amount simultaneously allocated never exceeds $n$.
Yet fewer than $R$ size-$2$ blocks can be packed. Therefore some request must fail.
Hence memory size $L=M-1$ is insufficient for every allocation strategy. Therefore
$$ N(n,2)\ge M. $$
Combining the upper and lower bounds,
$$ \boxed{ N(n,2)=\left\lfloor\frac{3n-1}{2}\right\rfloor }. $$
For $n=16$,
$$ N(16,2) = \left\lfloor\frac{47}{2}\right\rfloor = 23, $$
in agreement with Exercises 36 and 37.