TAOCP 2.5 Exercise 16

Exercise 16. [**] [24] Write a MIX program for Algorithm C, incorporating the ideas of exercise 15.

Verified: yes
Solve time: 3m06s

Exercise 2.5.16 asks for the MIX implementation of Algorithm C (boundary-tag storage allocation with coalescing), modified according to Exercise 15. The essential point of Exercise 15 is that the coalescing step should distinguish the four possibilities

$$ (L,R)\in{+,-}^2, $$

where

$$ L=\operatorname{TAG}(P_0-1),\qquad R=\operatorname{TAG}(P_0+\operatorname{SIZE}(P_0)), $$

and should perform only the link manipulations actually required in the corresponding case.

The program below replaces Knuth's coalescing step by an explicit four-way branch. The notation follows the conventions of §2.5: a free block contains predecessor and successor links in its first two words; every block has matching boundary tags at its beginning and end; positive tags denote free blocks and negative tags denote reserved blocks.

Let the returned block begin at $P_0$, and let

$$ S=\operatorname{SIZE}(P_0). $$

The symbols

$$ Q=P_0-\operatorname{TAG}(P_0-1),\qquad T=P_0+S $$

denote respectively the beginning of the left free neighbor (when it exists) and the beginning of the right neighbor.

The free-list header is $\text{AVAIL}$.

MIXAL program for Step C6

* C6. Coalescing after a block beginning at P0 is released.

C6      LDA     P0-1           TAG(P0-1)
        STA     LEFTTAG
        JAN     LEFTRES

* left neighbour free

        LDA     P0+SIZE(P0)    TAG(T)
        STA     RIGHTTAG
        JAN     LEFTONLY

* both neighbours free

BOTHFREE
        LDA     P0
        SUB     LEFTTAG
        STA     Q              Q = beginning of left block

        LDA     Q+1            successor(Q)
        STA     SUCC

        LDA     P0+SIZE(P0)
        ADD     P0-1
        ADD     SIZE(P0)
        STA     NEWSIZE

* remove right block from free list

        LDA     T
        STA     R

        LDA     R
        STA     RPRED

        LDA     R+1
        STA     RSUCC

        LDA     RSUCC
        STA     RPRED+1

        LDA     RPRED
        STA     RSUCC

* enlarge left block

        LDA     NEWSIZE
        STA     Q
        STA     Q+NEWSIZE-1

        JMP     DONE

LEFTONLY
* left free, right reserved

        LDA     P0
        SUB     LEFTTAG
        STA     Q

        LDA     LEFTTAG
        ADD     SIZE(P0)
        STA     NEWSIZE

        LDA     NEWSIZE
        STA     Q
        STA     Q+NEWSIZE-1

        JMP     DONE

LEFTRES
        LDA     P0+SIZE(P0)
        STA     RIGHTTAG
        JAN     BOTHRES

* left reserved, right free

RIGHTONLY
        LDA     P0+SIZE(P0)
        STA     T

        LDA     SIZE(P0)
        ADD     RIGHTTAG
        STA     NEWSIZE

* replace right block by P0 in free list

        LDA     T
        STA     R

        LDA     R
        STA     RPRED

        LDA     R+1
        STA     RSUCC

        LDA     RPRED
        STA     P0

        LDA     RSUCC
        STA     P0+1

        LDA     P0
        STA     RPRED+1

        LDA     P0
        STA     RSUCC

        LDA     NEWSIZE
        STA     P0
        STA     P0+NEWSIZE-1

        JMP     DONE

BOTHRES
* neither neighbour free

        LDA     AVAIL+1
        STA     P0+1

        ENT1    AVAIL
        ST1     P0

        LDA     P0
        STA     AVAIL+1

        LDA     P0
        STA     AVAIL

        LDA     SIZE(P0)
        STA     P0
        STA     P0+SIZE(P0)-1

DONE    NOP

Correctness

The branch structure is determined by the signs of the two neighboring tags.

Case $(-, -)$. Both neighbors are reserved.

No coalescing is possible. The released block is inserted into the free list as a new free block. Its size is written into both boundary tags. 2. Case $(-, +)$. The right neighbor is free.

The right free block is replaced by a larger free block beginning at $P_0$. The predecessor and successor formerly attached to the right block are redirected to $P_0$. No other free-list links are modified. The new size is

$$ S+\operatorname{SIZE}(T). $$ 3. Case $(+, -)$. The left neighbor is free.

The left free block is enlarged to include the released block. Since the beginning of the free block does not move, no free-list links need to be changed. The new size is

$$ \operatorname{SIZE}(Q)+S. $$ 4. Case $(+, +)$. Both neighbors are free.

The right block is removed from the free list; the left block remains in place and is enlarged to cover all three contiguous blocks. The resulting size is

$$ \operatorname{SIZE}(Q)+S+\operatorname{SIZE}(T). $$

Only the links of the removed right block and its immediate neighbors are modified.

In every case the beginning and ending boundary tags of the resulting free block are set equal to its size, so the boundary-tag invariant is preserved. The free-list invariant is also preserved because each case performs exactly the link updates required by the corresponding local change in the set of free blocks.

Thus the program implements Algorithm C with the Exercise 15 optimization: each of the four coalescing situations is handled separately, and no unnecessary link rewriting is performed.