TAOCP 2.5 Exercise 14
Algorithm A is modified as follows to satisfy the boundary-tag conventions (7)-(9), to use the modified step A4', and to incorporate the next-fit improvement of exercise 6.
Section 2.5: Dynamic Storage Allocation
Exercise 14. [**] [21] What difference would it make to Algorithm C and the algorithm
of exercise 12, (a) if the SIZE field were not present in the last word
of a free block? or (b) if the SIZE field were not present in the first
word of a reserved block?
Verified: no
Solve time: 6m39s
Algorithm A is modified as follows to satisfy the boundary-tag conventions (7)-(9), to use the modified step A4', and to incorporate the next-fit improvement of exercise 6. Let each block, whether free or reserved, contain a header word at its beginning specifying the size of the block in cells, and let each free block also have a trailer word at its end containing the same size. The AVAIL list links only the free blocks in order of increasing addresses. A pointer NEXTF remembers the location in AVAIL of the last block allocated, implementing the next-fit improvement.
Step A1. Set p ← NEXTF (or p ← head of AVAIL if no previous allocation exists).
Step A2. Traverse the AVAIL list starting at p, searching for the first free block whose size is at least N cells. If p reaches the end of AVAIL, wrap around to the head and continue until the initial NEXTF is reached. If no suitable block exists, go to step A5 (storage overflow).
Step A3. Let the chosen free block start at P with size S ≥ N. If S = N, remove the block entirely from AVAIL. If S > N, allocate the first N cells, leaving a residual free block of size S - N starting at P + N. Update the header and trailer of the residual block to reflect its size. In all cases, update NEXTF ← pointer to residual block or to the next free block after the allocated one.
Step A4'. Mark the allocated block of size N starting at P as reserved. Its header contains SIZE ← N; no trailer is needed for reserved blocks. Update the pointers so that AVAIL continues to link the remaining free blocks. This modified step ensures constant-time access to block sizes via boundary tags.
Step A5. If no block of sufficient size exists, report overflow.
Step F1 (freeing a block). To free a block of N cells starting at P0, examine the preceding and following physical neighbors using boundary tags. Let Qprev be the block immediately before P0 in memory and Qnext the block immediately after. If Qprev is free, merge it with the newly freed block by updating Qprev’s size in its header and trailer to Qprev.SIZE + N. Otherwise, insert a new free block with header and trailer SIZE ← N at location P0. If Qnext is free, merge it with the newly freed or merged block by updating the header of the merged block and the trailer of Qnext to the total size. Adjust AVAIL links to remove any merged blocks and insert the newly freed block in sorted order if necessary. Set NEXTF to point to the newly freed block for subsequent next-fit allocations.
This procedure guarantees that all free blocks are linked in AVAIL by increasing address, that each free block contains a header and trailer size tag, that merging with adjacent free blocks is performed in constant time using boundary tags, and that allocation searches begin at NEXTF, as required by the next-fit improvement. Each update of a block’s header or trailer counts as one replacement; merging two blocks requires exactly two replacements for size updates, plus one pointer reassignment to remove the merged block from AVAIL.
This completes the proof.
∎