Basic Garbage Collection Algorithms
-
Mark-Sweep Collection:
- Two phases: marking live objects, sweeping unreachable ones
- Follows pointers from “root set” to find reachable objects
- Disadvantages: slow, unpredictable timing, poor locality of reference
-
Mark-Compact Collection:
- Three phases: marking, reclaiming, compacting
- Solves fragmentation problem
- Makes allocation fast
- Disadvantages: needs to move objects and update pointers
-
Copying Collection:
- Good for systems with low amounts of live objects
- Divides heap into two semi-spaces
- Copies live objects from one space to another (Cheney Algorithm)
- Reclaims entire unused semi-space at once
- Advantages: fast allocation, good locality
- Disadvantages: uses twice as much memory
Advanced Garbage Collection Techniques
-
Generational Collection:
- Divides objects by age: young and old generations
- Collects young generation more frequently
- Based on observation that most objects die young
- Reduces collection overhead for long-lived objects
-
Incremental Collection:
- Spreads collection work over time
- Uses “tri-color marking” to track object state
- White - not yet checked
- Grey - live, but some direct children not checked
- Black - live
- Coordinates with program using read or write barriers
- Reduces pauses but adds overhead
-
Real-Time Collection:
- Schedules collection as a periodic task
- Ensures collection can keep up with allocation rate
- Suitable for systems with strict timing requirements
Practical Considerations
- Trade-offs between memory usage, CPU time, and predictability
- Poor interaction with virtual memory (thrashing)
- Difficulties with weakly typed languages
- Memory overhead compared to manual management (see Resource Ownership and Memory Management)