Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Exercises

  1.   Let M be the size of the heap and let f be the fraction of the heap occupied by live data. Estimate the running time of the Mark method of the mark-and-sweep garbage collection scheme as a function of f and M.
  2.   Repeat Exercise gif for the Copy method Estimate the running time of the Copy method of the stop-and-copy garbage collection scheme.
  3.   Repeat Exercise gif for the Copy method Estimate the running time of the Compact method of the stop-and-compact garbage collection scheme.
  4. Using your answers to Exercises gif, gif and gif, show that running time of garbage collection is inversely proportional to the amount of storage recovered.
  5. The efficiency of a garbage collection scheme is the rate at which memory is reclaimed. Using your answers to Exercises gif and gif compare the efficiency of mark-and-sweep with that of stop-and-copy.
  6.   Devise a non-recursive algorithm for the Mark method of the mark-and-sweep garbage collection scheme.
  7. Repeat Exercise gif for the Copy method of the stop-and-copy garbage collection scheme.
  8. Repeat Exercise gif for the Mark method of the mark-and-compact garbage collection scheme.
  9. Consider the use of handles for representing object references. Is it correct to assume that the order which objects appear in the heap is the same as the order in which the corresponding handles appear in the array of handles? How does this affect compaction of the heap?
  10. Consider the Compact method of the mark-and-compact garbage collection scheme. The algorithm visits the objects in the heap in the order in which they appear in the heap, rather than in the order in which the corresponding handles appear in the array of handles. Why is this necessary?
  11. The Compact method of the mark-and-compact garbage collection scheme slides the objects in the heap all to one end, but leaves the handles where they are. As a result, the handle array becomes fragmented. What modifications are necessary in order to compact the handle array as well as the heap?

next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.