TAOCP 2.5 Exercise 12

Let the memory contain permanent boundary sentinels at both extremes.

taocpmathematicsalgorithmsvolume-1

Section 2.5: Dynamic Storage Allocation

Exercise 12. [**] [20] Modify Algorithm A so that it follows the boundary-tag conventions of (7)-(9), uses the modified step A4' described in the text, and also incorporates the improvement of exercise 6.

Verified: no
Solve time: 4m32s

Let the memory contain permanent boundary sentinels at both extremes. Specifically, assume that location $0$ and the final location $M+1$ contain the reserved tag $0$. Hence every actual block lies strictly between two accessible tag words, and tests of neighboring tags are always defined.

Every block has a boundary tag at each end. If a block occupies locations

$$ p,\ldots,p+s-1, $$

then the words at $p$ and $p+s-1$ both contain the same signed size:

$$ +s \quad \text{if the block is free}, $$

$$ -s \quad \text{if the block is reserved}. $$

A free block therefore has the form

$$ \begin{array}{|c|c|c|c|c|} \hline +s & \mathrm{LLINK} & \mathrm{RLINK} & \cdots & +s\ \hline \end{array} $$

and must satisfy $s\ge4$, since two link fields are required in addition to the two tags.

The free blocks form a circular doubly linked list. The variable $R$ is the roving pointer of exercise 6. The convention

$$ R=\Lambda $$

means that the free list is empty.

For a free block beginning at $p$,

$$ \mathrm{LLINK}(p+1),\qquad \mathrm{RLINK}(p+1) $$

are its predecessor and successor in the circular list.

The user receives the address

$$ p+1 $$

when the reserved block begins at $p$. Thus the leading boundary tag is always immediately before the user address.

The modified algorithm is as follows.

A1. [Initialize.]

Initially one free block occupies locations

$$ 1,\ldots,M. $$

Set

$$ \mathrm{TAG}(1)=M, \qquad \mathrm{TAG}(M)=M. $$

Set

$$ \mathrm{LLINK}(2)=1, \qquad \mathrm{RLINK}(2)=1. $$

Set

$$ R=1. $$

Also set the permanent sentinels

$$ \mathrm{TAG}(0)=0, \qquad \mathrm{TAG}(M+1)=0. $$

Given a request for $N$ usable words, compute

$$ n=\max(N+2,4). $$

The quantity $n$ is the total block size including the two tags.

If

$$ R=\Lambda, $$

the allocation fails immediately.

Otherwise begin at the block pointed to by $R$, and traverse the circular list until a free block of size at least $n$ is found.

Suppose the selected free block begins at $p$ and has size $s$.

A3. [Test the remainder.]

Set

$$ r=s-n. $$

If

$$ r<4, $$

execute step A4'. Otherwise execute step A5.

A4'. [Allocate the whole block.]

The entire free block is allocated.

Let

$$ u=\mathrm{LLINK}(p+1), \qquad v=\mathrm{RLINK}(p+1). $$

There are two cases.

Case 1. The block is the only free block.

This occurs when

$$ u=p, \qquad v=p. $$

Set

$$ R=\Lambda. $$

The free list is now empty.

Case 2. The list contains other free blocks.

Splice the block out of the circular list:

$$ \mathrm{RLINK}(u+1)\leftarrow v, $$

$$ \mathrm{LLINK}(v+1)\leftarrow u. $$

If

$$ R=p, $$

set

$$ R=v. $$

Now mark the block reserved:

$$ \mathrm{TAG}(p)\leftarrow -s, $$

$$ \mathrm{TAG}(p+s-1)\leftarrow -s. $$

Return the user address

$$ p+1. $$

A5. [Split the block.]

Assume

$$ r\ge4. $$

Retain the lower portion as a free block of size $r$, and allocate the upper portion of size $n$.

Thus the free block occupies

$$ p,\ldots,p+r-1, $$

and the reserved block occupies

$$ q,\ldots,q+n-1, \qquad q=p+r. $$

The free block remains in the free list, so its link fields are unchanged.

Write the new free tags:

$$ \mathrm{TAG}(p)\leftarrow r, $$

$$ \mathrm{TAG}(p+r-1)\leftarrow r. $$

Write the reserved tags:

$$ \mathrm{TAG}(q)\leftarrow -n, $$

$$ \mathrm{TAG}(q+n-1)\leftarrow -n. $$

Set

$$ R=p, $$

since the search terminated there.

Return the user address

$$ q+1. $$

A6. [Release a block.]

Suppose the user returns the address

$$ q. $$

Then the block itself begins at

$$ p=q-1. $$

Its size is determined from the leading tag:

$$ n=-\mathrm{TAG}(p). $$

Hence the released block occupies

$$ p,\ldots,p+n-1. $$

Define

$$ L=p-1, \qquad U=p+n. $$

If

$$ \mathrm{TAG}(L)>0, $$

the left neighbor is free. Its size is

$$ a=\mathrm{TAG}(L), $$

and its starting address is

$$ u=p-a. $$

If

$$ \mathrm{TAG}(U)>0, $$

the right neighbor is free. Its size is

$$ b=\mathrm{TAG}(U), $$

and its starting address is

$$ v=p+n. $$

There are four cases.

Case 1. Neither neighbor is free.

Thus

$$ \mathrm{TAG}(L)\le0, \qquad \mathrm{TAG}(U)\le0. $$

Mark the block free:

$$ \mathrm{TAG}(p)\leftarrow n, $$

$$ \mathrm{TAG}(p+n-1)\leftarrow n. $$

If

$$ R=\Lambda, $$

create a one-element circular list:

$$ \mathrm{LLINK}(p+1)\leftarrow p, $$

$$ \mathrm{RLINK}(p+1)\leftarrow p, $$

$$ R\leftarrow p. $$

Otherwise insert the block immediately after $R$.

Let

$$ t=\mathrm{RLINK}(R+1). $$

Set

$$ \mathrm{RLINK}(p+1)\leftarrow t, $$

$$ \mathrm{LLINK}(p+1)\leftarrow R, $$

$$ \mathrm{LLINK}(t+1)\leftarrow p, $$

$$ \mathrm{RLINK}(R+1)\leftarrow p. $$

Finally set

$$ R\leftarrow p. $$

Case 2. Left neighbor free, right neighbor reserved.

The left free block begins at

$$ u=p-a. $$

Enlarge it to size

$$ a+n. $$

Write the new boundary tags:

$$ \mathrm{TAG}(u)\leftarrow a+n, $$

$$ \mathrm{TAG}(p+n-1)\leftarrow a+n. $$

No link changes are required. The free block already belongs to the free list, and its header remains at $u$, so all list pointers continue to reference the correct location.

Set

$$ R=u. $$

Case 3. Left neighbor reserved, right neighbor free.

The right free block begins at

$$ v=p+n, $$

and has size $b$.

Its predecessor and successor in the free list are

$$ x=\mathrm{LLINK}(v+1), \qquad y=\mathrm{RLINK}(v+1). $$

The merged free block will begin at $p$ and have size

$$ n+b. $$

Write its tags:

$$ \mathrm{TAG}(p)\leftarrow n+b, $$

$$ \mathrm{TAG}(p+n+b-1)\leftarrow n+b. $$

Now replace the old free-list node at $v$ by the new node at $p$.

If

$$ x=v, \qquad y=v, $$

then the right block was the only free block. Set

$$ \mathrm{LLINK}(p+1)\leftarrow p, $$

$$ \mathrm{RLINK}(p+1)\leftarrow p, $$

$$ R\leftarrow p. $$

Otherwise set

$$ \mathrm{RLINK}(x+1)\leftarrow p, $$

$$ \mathrm{LLINK}(y+1)\leftarrow p, $$

$$ \mathrm{LLINK}(p+1)\leftarrow x, $$

$$ \mathrm{RLINK}(p+1)\leftarrow y. $$

If

$$ R=v, $$

set

$$ R=p. $$

Thus the list remains correctly linked even though the block header has moved from $v$ to $p$.

Case 4. Both neighbors free.

The left free block begins at

$$ u=p-a, $$

and the right free block begins at

$$ v=p+n. $$

The right block has size $b$.

Remove the right block from the free list.

Let

$$ x=\mathrm{LLINK}(v+1), \qquad y=\mathrm{RLINK}(v+1). $$

If

$$ x=v, \qquad y=v, $$

then the right block was the only free-list node besides the left block itself. No special action is needed, because the left block already remains in the list.

Otherwise splice out the right block:

$$ \mathrm{RLINK}(x+1)\leftarrow y, $$

$$ \mathrm{LLINK}(y+1)\leftarrow x. $$

Now combine all three blocks into one free block of size

$$ a+n+b. $$

Write the new tags:

$$ \mathrm{TAG}(u)\leftarrow a+n+b, $$

$$ \mathrm{TAG}(p+n+b-1)\leftarrow a+n+b. $$

No further link updates are needed. The surviving free-list node is still located at $u$, so every pointer that formerly referenced the left block remains valid.

Set

$$ R=u. $$

This algorithm satisfies all requirements of the exercise.

  1. Boundary tags at both ends permit immediate detection and coalescing of adjacent free blocks.
  2. Modified step $A4'$ allocates the entire block whenever the remainder would be too small to form a legal free block.
  3. The roving pointer $R$ implements the improvement of exercise 6, because searches continue from the location of the previous successful allocation rather than restarting at the beginning of the free list.