TAOCP 2.5 Exercise 19

The previous answer fails because it assumes information that is not available after the trailing `SIZE` fields have been removed.

taocpmathematicsalgorithmsvolume-1

Section 2.5: Dynamic Storage Allocation

Exercise 19. [**] [24] Suppose that blocks of memory have the form of (7), but without the TAG or SIZE fields required in the last word of the block. Suppose further that the following simple algorithm is being used to make a reserved block free again: $$ Q\leftarrow AVAIL,\quad LINK(P0)\leftarrow Q,\quad LINK(P0+1)\leftarrow LOC(AVAIL), $$ $$ LINK(Q+1)\leftarrow P0,\quad AVAIL\leftarrow P0,\quad TAG(P0)\leftarrow "-". $$ (This algorithm does nothing about collapsing adjacent areas together.) Design a reservation algorithm, similar to Algorithm A, that does the necessary collapsing of adjacent free blocks while searching the AVAIL list, and at the same time avoids any unnecessary fragmentation of memory as in (2), (3), and (4).

Verified: no
Solve time: 4m40s

Solution

The previous answer fails because it assumes information that is not available after the trailing SIZE fields have been removed. The solution must instead be based on the actual representation of formula (7).

Let a block begin at address $P_0$. The first word contains the block size and tag information, exactly as in Algorithm A. Only the trailing copy of the tag and size has been removed. Hence, for every block,

$$ \text{SIZE}(P_0) $$

is still available in the first word of the block. Therefore, if a block begins at $P_0$, the next block in memory begins at

$$ P_1=P_0+\text{SIZE}(P_0). $$

This observation is the key to the exercise.

When a block is freed by the given insertion algorithm,

$$ Q\leftarrow AVAIL,\qquad LINK(P_0)\leftarrow Q,\qquad LINK(P_0+1)\leftarrow LOC(AVAIL), $$

$$ LINK(Q+1)\leftarrow P_0,\qquad AVAIL\leftarrow P_0,\qquad TAG(P_0)\leftarrow "-", $$

the block is merely inserted into the circular doubly linked free list. No attempt is made to combine it with neighboring free blocks. Consequently, the free list may contain several free blocks that are adjacent in memory, producing the undesirable fragmentation illustrated earlier in the text.

The reservation algorithm must remove this fragmentation while it searches the free list.

Basic idea

Suppose that during the search we examine a free block beginning at $P$.

Since $\text{SIZE}(P)$ is known from the first word,

$$ R=P+\text{SIZE}(P) $$

is the address of the next block in memory.

If $R$ is allocated, nothing can be done.

If $R$ is free, then $R$ must occur somewhere on the AVAIL list. In that case the two adjacent free blocks can be combined into a single larger free block. Since we are already traversing the AVAIL list, we can search for $R$ and splice it out when found.

Thus adjacent free blocks are collapsed whenever they are encountered during the reservation search.

Reservation algorithm

Let $N$ be the requested size.

Maintain pointers $P$ and $Q$ exactly as in Algorithm A, where $P$ is the current free block and $Q$ its predecessor on the AVAIL list.

A1. Set

$$ Q\leftarrow AVAIL,\qquad P\leftarrow LINK(Q). $$

A2. Examine block $P$.

Compute

$$ R=P+\text{SIZE}(P). $$

If $TAG(R)="-"$, the block immediately following $P$ in memory is free.

Search the AVAIL list until the entry corresponding to $R$ is found. Let $S$ be its predecessor on the free list.

Delete $R$ from AVAIL:

$$ LINK(S)\leftarrow LINK(R), $$

$$ LINK(LINK(R)+1)\leftarrow S. $$

Now enlarge block $P$ by absorbing $R$:

$$ \text{SIZE}(P)\leftarrow \text{SIZE}(P)+\text{SIZE}(R). $$

Return to A2, because the enlarged block may now be adjacent to yet another free block.

Hence, after repeated execution of A2, $P$ has become the maximal free block beginning at address $P$.

A3. If

$$ \text{SIZE}(P)\ge N, $$

use this block for the reservation.

If

$$ \text{SIZE}(P)=N, $$

remove $P$ from AVAIL exactly as in Algorithm A and mark it reserved.

Otherwise split the block:

$$ P' = P+N. $$

Reserve the first $N$ words and leave a free block beginning at $P'$ with size

$$ \text{SIZE}(P')= \text{SIZE}(P)-N. $$

Replace $P$ by $P'$ in the AVAIL list and set the appropriate tag fields in the first words of the two blocks.

Then terminate successfully.

A4. If

$$ \text{SIZE}(P)<N, $$

advance to the next free block:

$$ Q\leftarrow P,\qquad P\leftarrow LINK(P). $$

If the search has returned to the starting point of the circular list, report overflow; otherwise return to A2.

Why this avoids the fragmentation of (2), (3), and (4)

The undesirable situations arise because adjacent free blocks remain separate after blocks are returned to memory.

In the present algorithm, whenever a free block $P$ is examined, every free block immediately following it in memory is absorbed before any allocation decision is made. Therefore $P$ is always replaced by the maximal contiguous free region beginning at $P$.

Consequently:

  1. No reservation is made from a block that could first be enlarged by adjoining neighboring free space.
  2. Adjacent free blocks cannot persist indefinitely as separate fragments.
  3. Every allocation is made from maximal available regions, exactly eliminating the unnecessary fragmentation caused by the simple insertion algorithm.

Thus the free list is gradually cleaned up during normal allocation searches, without requiring any special processing when blocks are freed.

This is the desired analogue of Algorithm A for the representation in which the trailing boundary tags have been removed.