Exercises for Section 7.7

7.7.1

Suppose that the network of objects from Fig.7.20 is managed by an incremental algorithm that uses the four lists Unreached, Unscanned, Scanned, and Free, as in Baker's algorithm. To be specific, the Unscanned list is managed as a queue, and when more than one object is to be placed on this list due to the scanning of one object, we do so in alphabetical order. Suppose also that we use write barriers to assure that no reachable object is made garbage. Starting with A and B on the Unscanned list, suppose the following events occur:

1. A is scanned.
2. The pointer A -> D is rewritten to be A -> H.
3. B is scanned.
4. D is scanned.
5. The pointer B -> C is rewritten to be B -> I.

Simulate the entire incremental garbage collection, assuming no more pointers are rewritten. Which objects are garbage? Which objects are placed on the Free list?

Answer

0. init

   

    Free = []
    Unreached = [C, D, E, F, G, H, I]
    Uscanned = [A, B]
    Scanned = []

1. A is scanned.

    Unreached = [C, F, G, H, I]
    Uscanned = [B, D, E]
    Scanned = [A]

2. The pointer A -> D is rewritten to be A -> H.

   

    Unreached = [C, F, G, I]
    Uscanned = [B, D, E, H]
    Scanned = [A]

3. B is scanned.

    Unreached = [F, G, I]
    Uscanned = [D, E, H, C]
    Scanned = [A, B]

4. D is scanned.

    Unreached = [F, G, I]
    Uscanned = [E, H, C]
    Scanned = [A, B, D]

5. The pointer B -> C is rewritten to be B -> I.

   

    Unreached = [F, G]
    Uscanned = [E, H, C, I]
    Scanned = [A, B, D]

6. E is scanned.

    Unreached = [F, G]
    Uscanned = [H, C, I]
    Scanned = [A, B, D, E]

7. H is scanned.

    Unreached = [F, G]
    Uscanned = [C, I]
    Scanned = [A, B, D, E, H]

8. C is scanned.

    Unreached = [F, G]
    Uscanned = [I]
    Scanned = [A, B, D, E, H, C]

9. I is scanned.

    Unreached = [F, G]
    Uscanned = []
    Scanned = [A, B, D, E, H, C, I]

10. end

     Free = [F, G]
     Unreached = [A, B, D, E, H, C, I]
     Unscanned = []
     Scanned = []

so, [C, D, F, G] is garbage, Free list is [F, G].

7.7.2

Repeat Exercise 7.7.1 on the assumption that

1. Events (2) and (5) are interchanged in order.
2. Events (2) and (5) occur before (1), (3), and (4).

Answer

1. Events (2) and (5) are interchanged in order.

   omit

2. Events (2) and (5) occur before (1), (3), and (4).

   0. init

      

       Free = []
       Unreached = [C, D, E, F, G, H, I]
       Uscanned = [A, B]
       Scanned = []

   1. The pointer A -> D is rewritten to be A -> H.

      

       Unreached = [C, D, E, F, G, I]
       Uscanned = [A, B, H]

   2. The pointer B -> C is rewritten to be B -> I.

      

       Unreached = [C, D, E, F, G]
       Uscanned = [A, B, H, I]

   3. A is scanned.

       Unreached = [C, D, F, G]
       Unscanned = [B, H, I, E]
       Scanned = [A]

   4. B is scanned.

       Unreached = [C, D, F, G]
       Unscanned = [H, I, E]
       Scanned = [A, B]

   5. H is scanned.

       Unreached = [C, D, F, G]
       Unscanned = [I, E]
       Scanned = [A, B, H]

   6. I is scanned.

       Unreached = [C, D, F, G]
       Unscanned = [E]
       Scanned = [A, B, H, I]

   7. E is scanned.

       Unreached = [C, D, F, G]
       Unscanned = []
       Scanned = [A, B, H, I, E]

   8. end

       Free = [C, D, F, G]
       Unreached = [A, B, H, I, E]
       Unscanned = []
       Scanned = []

   so, [C, D, F, G] is garbage, Free list also is [C, D, F, G].

7.7.3

Suppose the heap consists of exactly the nine cars on three trains shown in Fig. 7.30 (i.e., ignore the ellipses). Object o in car 11 has references from cars 12, 23, and 32. When we garbage collect car 11, where might o wind up?

Answer

if any room in trains 2 and 3
    o can go in some existing car of either trains 2 and 3.
else
    o can go in a new, last car of either trains 2 and 3. 

7.7.4

Repeat Exercise 7.7.3 for the cases that o has

1. Only references from cars 22 and 31.
2. No references other than from car 11.

Answer

1. Only references from cars 22 and 31.

   The same with Exercise 7.7.3.

2. No references other than from car 11.

    if there is room in car 12
        o can go in car 12
    else if there is room in other cars of train 1
        o can go in any car has room
    else
        o can go in a new, last car of train 1

7.7.5

Suppose the heap consists of exactly the nine cars on three trains shown in Fig. 7.30 (i.e., ignore the ellipses). We are currently in panic mode. Object o1 in car 11 has only one reference, from object o2 in car 12. That reference is rewritten. When we garbage collect car 11, what could happen to o1?

Answer

It is not important which train we move it to, as long as it is not the first train？