TAOCP 2.5 Exercise 42
**Exercise 2.
Section 2.5: Dynamic Storage Allocation
Exercise 42. [**] [M40] (J. M. Robson, 1975.) Let $N_{\rm BF}(n,m)$ be the amount of memory needed to guarantee non-overflow when the best-fit method is used for allocation as in exercise 38. Find an attacking strategy to show that $$ N_{\rm BF}(n,m)\geq mn-O(n+m^2). $$
Verified: yes
Solve time: 3m55s
Exercise 2.5.42 [**]
Let $N_{\rm BF}(n,m)$ denote the amount of memory required to guarantee non-overflow when the best-fit allocation rule is used. We construct an attacking strategy showing that
$$ N_{\rm BF}(n,m)\ge mn-O(n+m^2). $$
The idea is to force best-fit into a state containing $n$ free blocks of size $m-1$. These blocks represent almost $mn$ units of free memory, yet none can satisfy a request of size $m$.
Construction of the fragmented state
Let
$$ S=1+2+\cdots +(m-1)=\frac{m(m-1)}2. $$
We first create one free block of each size $1,2,\ldots,m-1$.
Starting with empty memory, allocate consecutively blocks of sizes
$$ 1,2,\ldots,m-1 . $$
The occupied region has total length $S$.
Now repeat the following operation $n$ times.
Allocate a block of size $m-1$ immediately after the previously created blocks. Then allocate blocks of sizes
$$ 1,2,\ldots,m-2 $$
immediately after it. The total length of this group is again
$$ (m-1)+(1+\cdots +(m-2)) =S . $$
After creating $n$ such groups, free the leading block of size $m-1$ in every group and leave all other blocks allocated.
The memory now consists of $n$ free blocks, each of size $m-1$, separated by allocated blocks of total size
$$ 1+\cdots +(m-2). $$
Hence no two free $(m-1)$-blocks are adjacent, so coalescing cannot enlarge them.
The total memory occupied by this configuration is
$$ nS+S =(n+1)\frac{m(m-1)}2 . $$
The free memory equals
$$ n(m-1), $$
and the remaining allocated memory equals
$$ (n+1)S-n(m-1) = \frac{n(m-1)(m-2)}2+S . $$
Since $m$ is fixed in the asymptotic estimate, this allocated part is $O(n+m^2)$.
Why best-fit cannot use the free memory
Every free block has size exactly $m-1$.
Now issue $n$ allocation requests of size $m$.
For each request, best-fit searches for the smallest free block whose size is at least $m$. No existing free block qualifies, because every free block has size $m-1$.
Therefore none of the $n(m-1)$ free cells can be used to satisfy any of these requests. Each request of size $m$ must be placed in previously unused memory.
Consequently the allocator must supply $nm$ new cells in addition to the memory already tied up in the configuration above.
Lower bound
At the moment the $n$ requests of size $m$ have been satisfied, memory contains
- the $nm$ cells occupied by those requests;
- the original allocated separator blocks, whose total size is $O(n+m^2)$.
Thus the total memory required is at least
$$ nm+\bigl(O(n+m^2)\bigr). $$
Equivalently, since the free blocks contribute
$$ n(m-1)=nm-O(n) $$
cells that are present but unusable, we obtain
$$ N_{\rm BF}(n,m) \ge nm-O(n+m^2). $$
Therefore
$$ \boxed{,N_{\rm BF}(n,m)\ge mn-O(n+m^2),}. $$
This attacking strategy exhibits a state in which almost $mn$ cells of memory are fragmented into unusable blocks of size $m-1$, forcing best-fit to obtain essentially $mn$ additional cells before it can satisfy $n$ requests of size $m$. ∎