Repeat Exercise 7.7.1 on the assumption that a) Events (ii) and (v) are interchanged in order. b) Events (ii) and (v) occur before (i), (Hi), and (iv). Exercise 7.7.1 Suppose that the network of...

Repeat Exercise 7.7.1 on the assumption that


a) Events (ii) and (v) are interchanged in order.


b) Events (ii) and (v) occur before (i), (Hi), and (iv).

Exercise 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:

i. A is scanned.

ii. The pointer A -» D is rewritten to be A ->• iJ.


m. i? is scanned.


iv. D is scanned.

v. The pointer 5 -> C is rewritten to be 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?

Fig. 7.20