TAOCP 2.5 Exercise 15
Let the available-space list of Algorithm C be the doubly linked circular list maintained by the fields LINK(X),\qquad BACKLINK(X), with list header $AVAIL$.
Section 2.5: Dynamic Storage Allocation
Exercise 15. [**] [24] Show how to speed up Algorithm C at the expense of a slightly
longer program, by not changing any more links than absolutely necessary
in each of four cases depending on whether TAG(P0 - 1),
TAG(P0 + SIZE(P0)) are plus or minus.
Verified: yes
Solve time: 4m57s
Let the available-space list of Algorithm C be the doubly linked circular list maintained by the fields
$$ LINK(X),\qquad BACKLINK(X), $$
with list header $AVAIL$. Let $P_0$ be the block being returned to free storage.
The point of the exercise is that Algorithm C always removes neighboring free blocks from the list and then inserts the merged block again. This changes more links than necessary. We can do better by preserving an existing list element whenever the merged free block has the same initial address as one of the old free blocks.
Let
$$ L=P_0-SIZE(P_0-1) $$
when $TAG(P_0-1)=-$, and let
$$ R=P_0+SIZE(P_0) $$
when $TAG(P_0+SIZE(P_0))=-$.
We consider the four possible tag combinations.
Case 1: $TAG(P_0-1)=+$, $TAG(P_0+SIZE(P_0))=+$
Neither neighbor is free. A new free block begins at $P_0$, so a new list element must be inserted.
Insert $P_0$ immediately after the list header $AVAIL$. Let
$$ S=LINK(AVAIL). $$
Then perform
$$ LINK(P_0)\leftarrow S, $$
$$ BACKLINK(P_0)\leftarrow AVAIL, $$
$$ BACKLINK(S)\leftarrow P_0, $$
$$ LINK(AVAIL)\leftarrow P_0. $$
The free-list structure is now correct.
No existing list element can represent the new free block, because $P_0$ was not previously free. Hence a genuine insertion is unavoidable. In a doubly linked list, insertion requires exactly these four link-field changes.
Case 2: $TAG(P_0-1)=-$, $TAG(P_0+SIZE(P_0))=+$
The block merges only with the free block $L$.
After coalescing, the resulting free block still begins at $L$. Therefore the existing list element for $L$ already represents the correct maximal free block.
We simply enlarge the block:
$$ SIZE(L)\leftarrow SIZE(L)+SIZE(P_0), $$
and update the terminal boundary tag.
No list links are changed:
$$ \text{no changes to } LINK \text{ or } BACKLINK. $$
This is optimal, because every list element already remains valid.
Case 3: $TAG(P_0-1)=+$, $TAG(P_0+SIZE(P_0))=-$
The block merges only with the free block $R$.
After coalescing, the resulting free block begins at $P_0$, not at $R$. Therefore the list element corresponding to $R$ cannot be retained unchanged.
Let
$$ Q=BACKLINK(R),\qquad S=LINK(R). $$
Instead of deleting $R$ and inserting $P_0$, replace $R$ by $P_0$ in the same position of the doubly linked list:
$$ LINK(P_0)\leftarrow S, $$
$$ BACKLINK(P_0)\leftarrow Q, $$
$$ LINK(Q)\leftarrow P_0, $$
$$ BACKLINK(S)\leftarrow P_0. $$
Then set
$$ SIZE(P_0)\leftarrow SIZE(P_0)+SIZE(R), $$
and update the final boundary tag.
The list now contains exactly the same cyclic order as before, except that $P_0$ occupies the position formerly occupied by $R$.
This requires four link-field modifications. Two neighboring list elements must cease pointing to $R$ and point to $P_0$ instead; furthermore $P_0$ must acquire the forward and backward links formerly stored in $R$. Thus four changes are both sufficient and necessary.
Case 4: $TAG(P_0-1)=-$, $TAG(P_0+SIZE(P_0))=-$
The block lies between two free blocks $L$ and $R$.
After coalescing, the resulting maximal free block begins at $L$. Therefore the list element for $L$ should be preserved, while the list element for $R$ must disappear.
Let
$$ Q=BACKLINK(R),\qquad S=LINK(R). $$
Delete $R$ from the doubly linked list:
$$ LINK(Q)\leftarrow S, $$
$$ BACKLINK(S)\leftarrow Q. $$
Then enlarge $L$:
$$ SIZE(L)\leftarrow SIZE(L)+SIZE(P_0)+SIZE(R), $$
and update the final boundary tag.
Only two link fields change. Since the merged block still begins at $L$, the list element for $L$ remains correct. The only obsolete list element is $R$, and deletion from a doubly linked list requires exactly the two assignments above.
Optimized version of Algorithm C
The free-list manipulations become
$$ \begin{array}{c|c} \text{Case} & \text{Required link-field changes} \ \hline (+,+) & 4 \ (-,+) & 0 \ (+,-) & 4 \ (-,-) & 2 \end{array} $$
with the actual assignments
$$ \begin{array}{c|l} (+,+) & \begin{aligned} LINK(P_0)&\leftarrow S,\ BACKLINK(P_0)&\leftarrow AVAIL,\ BACKLINK(S)&\leftarrow P_0,\ LINK(AVAIL)&\leftarrow P_0 \end{aligned} \[18pt] (-,+) & \text{none} \[8pt] (+,-) & \begin{aligned} LINK(P_0)&\leftarrow S,\ BACKLINK(P_0)&\leftarrow Q,\ LINK(Q)&\leftarrow P_0,\ BACKLINK(S)&\leftarrow P_0 \end{aligned} \[18pt] (-,-) & \begin{aligned} LINK(Q)&\leftarrow S,\ BACKLINK(S)&\leftarrow Q \end{aligned} \end{array} $$
where $Q=BACKLINK(R)$ and $S=LINK(R)$.
Thus Algorithm C can be sped up by preserving existing free-list entries whenever possible. The resulting numbers of link-field modifications are
$$ 4,;0,;4,;2, $$
instead of removing and reinserting blocks unconditionally. These are the minimum changes compatible with Algorithm C's doubly linked circular free-space list.