CPSC 425 Spring 2004
HW 5: Heap Management
- We discussed three heap-allocation systems: first fit, best fit, and
worst fit. For each system, give a memory size and sequence of
allocations and deallocations that will succeed for that scheme and
fail for the others.
- We discussed three garbage collection systems: reference
counting, mark-and-sweep and copying. Carefully evaluate each of these with
- correctness (will it ever collect non-garbage?)
- completeness (will it collect all garbage?), and
- time and space efficiency. Be as specific as possible on this last one:
exactly how much space is required, and for what? Is it possible to use
less space? If so, what is the penalty for doing so?
How much time is required, and for what? Big-O estimates are fine for time,
but clearly specify what the input size (N) represents.