Previous    Next

## EXERCISES

• *13.1 Analyze the cost of mark-sweep versus copying collection. Assume that every record is exactly two words long, and every field is a pointer. Some pointers may point outside the collectible heap, and these are to be left unchanged.

1. Analyze Algorithm 13.6 to estimate c1, the cost (in instructions per reachable word) of depth-first marking.

2. Analyze Algorithm 13.3 to estimate c2, the cost (in instructions per word in the heap) of sweeping.
3. Analyze Algorithm 13.9 to estimate c3, the cost per reachable word of copying collection.
4. There is some ratio γ so that with H = γR the cost of copying collection equals the cost of mark-sweep collection. Find γ.
5. For H > γR, which is cheaper, mark-sweep or copying collection?
• 13.2 Run Algorithm 13.6 (pointer reversal) on the heap of Image 13.1. Show the state of the heap; the done flags; and variables t, x, and y at the time the node containing 59 is first marked.
• *13.3 Assume main calls f with callee-save registers all containing 0. Then f saves the callee-save registers it is going to use; puts pointers into some callee-save registers, integers into others, and leaves the rest untouched; and then it calls g. Now g saves some of the callee-save registers, puts some pointers and integers into them, and calls alloc, which starts a garbage collection.
1. Write functions f and g matching this description.

2. Illustrate the pointer maps of functions f and g.
3. Show the steps that the collector takes to recover the exact locations of all the pointers.
• **13.4 Every object in the Java language supports a hashCode() method that returns a "hash code" for that object. Hash codes need not be unique ± different objects can return the same hash code − but each object must return the same hash code every time it is called, and two objects selected at random should have only a small chance of having the same hash code. The Java language specification says that "This is typically implemented by converting the address of the object to an integer, but this implementation technique is not required by the Java language."

Explain the problem in implementing hashCode() this way in a Java system with copying garbage collection, and propose a solution.

 JaVa Previous    Next