Exercises for Section 7.6

7.6.1

Show the steps of a mark-and-sweep garbage collector on

1. Fig. 7.19 with the pointer A to B deleted.
2. Fig. 7.19 with the pointer A to C deleted.
3. Fig. 7.20 with the pointer A to D deleted.
4. Fig. 7.20 with the object B deleted.

Answer

1. Fig. 7.19 with the pointer A to B deleted.

    before:     A.reached =  … = I.reached = 0  
                Unscanned = []
   

    line1:      A.reached = 1
                Unscanned.push(A)

    line2~7:

        loop1:  Unscanned.shift()
                C.reached = 1
                Unscanned.push( C )

        loop2:  Unscanned.shift()
                F.reached = 1
                Uncanned.push(F)

        loop3:  Unscanned.shift()
                H.reached = 1
                Uncanned.push(H)

        loop4:  Unscanned.shift()
                I.reached = 1
                Uncanned.push(I)

        loop5:  Unscanned.shift()
                G.reached = 1
                Uncanned.push(G)

        loop6:  Unscanned.shift()
                E.reached = 1
                Uncanned.push(E)

        loop7:  Unscanned.shift()
                // no more object add to list Unscanned
                // now it is empty, loop end

    line8:      Free = []

    line9~11:   Free = [B, D]
                A.reached = C.reached = E.reached = … = I.reached = 0

7.6.2

The Baker mark-and-sweep algorithm moves objects among four lists: Free, Unreached, Unscanned, and Scanned. For each of the object networks of Exercise 7.6.1, indicate for each object the sequence of lists on which it finds itself from just before garbage collection begins until just after it finishes.

Answer

1. Fig. 7.19 with the pointer A to B deleted.

    line1:      Free = [] // assume it is empty
                Unreached = [A, B, C, D, E, F, G, H, I]
                Unscanned = []
                Scanned = []
   
    line2:      Unscanned = [A]
                Unreached = [B, C, D, E, F, G, H, I]
   
    line3~7:
   
        loop1:  Scanned = [A]
                Unscanned = [C]
                Unreached = [B, D, E, F, G, H, I]
   
        loop2:  Scanned = [A, C]
                Unscanned = [F]
                Unreached = [B, D, E, G, H, I]
   
        loop3:  Scanned = [A, C, F]
                Unscanned = [H]
                Unreached = [B, D, E, G, I]
   
        loop4:  Scanned = [A, C, F, H]
                Unscanned = [I]
                Unreached = [B, D, E, G]
   
        loop5:  Scanned = [A, C, F, H, I]
                Unscanned = [G]
                Unreached = [B, D, E]
   
        loop6:  Scanned = [A, C, F, H, I, G]
                Unscanned = [E]
                Unreached = [B, D]
   
        loop7:  Scanned = [A, C, F, H, I, G, E]
                Unscanned = []
                Unreached = [B, D]
   
    line8:      Free = [B, D]
   
    line9:      Unreached = [A, C, F, H, I, G, E]
   

7.6.3

Suppose we perform a mark-and-compact garbage collection on each of the networks of Exercise 7.6.1. Also, suppose that

1. Each object has size 100 bytes, and
2. Initially, the nine objects in the heap are arranged in alphabetical order, starting at byte 0 of the heap.

What is the address of each object after garbage collection?

Answer

1. Fig. 7.19 with the pointer A to B deleted.

    A(0), C(100), E(200), F(300), G(400), H(500), I(600)
   

7.6.4

Suppose we execute Cheney's copying garbage collection al­gorithm on each of the networks of Exercise 7.6.1. Also, suppose that

1. Each object has size 100 bytes,
2. The unscanned list is managed as a queue, and when an object has more than one pointer, the reached objects are added to the queue in alpha­ betical order, and
3. The From semispace starts at location 0, and the To semispace starts at location 10,000.

What is the value of NewLocation(o) for each object o that remains after garbage collection?

Answer

1. Fig. 7.19 with the pointer A to B deleted.

    A(10000), C(10100), F(10200), H(10300), I(10400), G(10500), E(10600)