OSDev.org

Wikipedia wrote:Because of these pitfalls, most modern tracing garbage collectors implement some variant of the tri-colour marking abstraction, but simple collectors (such as the mark-and-sweep collector) often do not make this abstraction explicit. Tri-colour marking works as follows:
Create initial white, grey, and black sets; these sets will be used to maintain progress during the cycle.
Initially the white set or condemned set is the set of objects that are candidates for having their memory recycled.
The black set is the set of objects that cheaply can be proven to have no references to objects in the white set; in many implementations the black set starts off empty.
The grey set is all the objects that are reachable from root references but the objects referenced by grey objects haven't been scanned yet. Grey objects are known to be reachable from the root, so cannot be garbage collected: grey objects will eventually end up in the black set. The grey state means we still need to check any objects that the object references.
The grey set is initialised to objects which are referenced directly at root level; typically all other objects are initially placed in the white set.
Objects can move from white to grey to black, never in the other direction.
Pick an object from the grey set. Blacken this object (move it to the black set), by greying all the white objects it references directly. This confirms that this object cannot be garbage collected, and also that any objects it references cannot be garbage collected.
Repeat the previous step until the grey set is empty.
When there are no more objects in the grey set, then all the objects remaining in the white set have been demonstrated not to be reachable, and the storage occupied by them can be reclaimed.

The 3 sets partition memory; every object in the system, including the root set, is in precisely one set.

The tri-colour marking algorithm preserves an important invariant:
No black object points directly to a white object.

This ensures that the white objects can be safely destroyed once the grey set is empty. (Some variations on the algorithm do not preserve the tricolour invariant but they use a modified form for which all the important properties hold.)

The tri-colour method has an important advantage: it can be performed 'on-the-fly', without halting the system for significant time periods. This is accomplished by marking objects as they are allocated and during mutation, maintaining the various sets. By monitoring the size of the sets, the system can perform garbage collection periodically, rather than as-needed. Also, the need to touch the entire working set each cycle is avoided.

A = B;
C = D;
//garbage collector thread starts
//at the start B and D have been allocated and are referenced by A and C respectively (no other references to these objects exist)
//A and C are accessible from the root, and are placed in the grey set
//B and D are placed in the white set, as it is not yet known if they are referenced
//A's references are checked. A is moved to the black set, and B is moved into the grey set
//garbage collector thread yields
A, C = C, A; //swap A's reference with C's
//garbage collector thread resumes
//C's references are checked and B is found. C is moved to the black set, and B stays in the grey set
//D remains in the white set
//no other references to D are found, so it is deallocated

Xzyx987X wrote:How would one get around this issue? I can think of a few ways, but they would all require user level code to cooperate with the garbage collector. For instance you could notify the garbage collector whenever a reference to an object is assigned.

Wikipedia wrote: The tri-colour method has an important advantage: it can be performed 'on-the-fly', without halting the system for significant time periods. This is accomplished by marking objects as they are allocated and during mutation, maintaining the various sets.

Xzyx987X wrote:But this would add significant overhead, and may potentially pose a security risk, so it's far from a viable solution.

Colonel Kernel wrote:It must be viable, because it is used by many collectors, including the one Apple uses for Objective-C in OS X. There is definitely overhead though. It's a tradeoff between GC pause time and overhead while the program is running.

Note that the program code itself is not required to do anything to co-operate with the collector. Instead, write barriers are inserted to track assignments. This is done by the compiler for the OS X collector AFAIK.

NickJohnson wrote:If I were you, I would probably take a look at ocaml's garbage collection system: apparently even with garbage collection, it can rival C in execution speed, although based on this article that may be partly from the combination of immutable (functional) objects and garbage collection. The standard implementation is open source IIRC, so it may prove useful as a reference implementation.

berkus wrote:I hope your OS is not intended to do any real-time work.

Xzyx987X wrote:

berkus wrote:I hope your OS is not intended to do any real-time work.

Why not? If the garbage collector is running 1% of the time (and in practice I'll probably also try to work memory defragmentation into that 1% as well), it still leaves 99% of the time for everything else.

Solar wrote:"Real-time" does not mean "really fast". It means that an event can be deterministically guaranteed to be handled within a contracted time frame. That time frame might actually be rather slow, but the event must be served within it.

Imagine the computer driving the control rods in a nuclear reactor. From the moment something triggers a SCRAM event to the moment the control rods are inserted, no more than x milliseconds may pass. No matter if your OS is currently running the garbage collector or not, or if the system has triggered every possible other event at the same time. You promised x milliseconds, you have to serve within x milliseconds. That is what "real-time" is about.