In summary, garbage collection must be used in all functional languages, and it promotes reliability and module design in imperative and object-oriented languages.
Pros
Cons
Reference counting is not used in general purpose programming languages
because of the above mentioned disadvantages. It is mostly used in
applications such as file, disk block management system and some simple
graphic toolkits.
Algorithm
Pros
Cons
Pros
Cons
Stop and Copy
Cheney's Algorithm
Advantages
Optimization
Non-Copying Implicit Collector
Advantages over copying
Disadvantages
Why Incremental?
The previous garbage collection algorithms are not feasible for real-time applications because they involve halting execution of the program while it runs.
Instead, the garbage collector and the mutator (executing program) should be interwoven. This allows the garbage collector to be run in small increments, making the pauses in the executing program shorter and more frequent.
Unfortunately, while the collector is tracing the graph of reachable data structures, the mutator may be changing the graph.
Tricolor Marking and Coherence
Tricolor marking is a method of marking which objects have been looked at in a collection cycle, and determining which ones to recycle at the end of the cycle.
Black
Grey
White
The collector examines all data objects that are in use by starting with the root stack and making successive waves of examining objects.
step 1
All objects pointed to by the root stack are colored gray.
step 2
Each gray object is viewed in turn and all of its child objects (objects
pointed to by it) are colored gray, and then it is colored black.
step 3
The mutator makes a change in the graph of objects by swapping the pointers
A->C and B->D. Now when the collector looks at object B, it is only
pointing to object C, which is already gray.
step 4
When the collector finishes its sweep (there are no more gray objects) any
remaining white objects should be garbage (unreachable) but D isn't in this
case.
Maintaining Coherence
There are two basic approaches to coordinating the collector with the mutator:
Read Barrier - A read barrier detects when the mutator attempts to reference a white object. The barrier then colors the white object gray and lets the mutator reference it. This way the mutator is never allowed to reference white objects and therefore cannot install a reference to a white object in a black one.
Write Barrier - On the write side, the mutator must do two things to fool the incremental garbage collector. First it must write a pointer from a black object to a white object, and second, it must destroy the original pointer to the white object before the collector gets to it. Since it must do both of these things, a write barrier would only have to prevent one of them from succeeding to maintain coherence.
incremental update
snapshot-at-beginning
Both read and write barriers are usually implemented in software by having the compiler add instructions in the appropriate place. The overhead for this is great, but less so for the write barriers because heap writes tend to be less common than heap reads. For the read barriers, tens of percent was a common estimate for the increase in overhead [Wilson, p23].
The Rebellion (c)1999 consists of Dorene Mboya, Dmitry Krivin, Raphen Becker, and Wyatt Gaswick.