Concurrent and Real Time GC: HoPL 3/11/2004
Presented by Peter Douglass
Transcribed by Jeffrey Palm
Real time GC, as defined occurs in a bounded, small amount of time. The
aim is todo away with the embarrassing pause. Concurrency, as
defined, involves atomic GC operations with a fine granularity. Four papers
Dijkstra, Lamport '75
The goal is to formally specify concurrent GC and provide an algorithm for this
specification. In doing so, the mutator has to cooperate with the collecter. As
an example of the problem, consider the following graph were nodes are cons
cells and edges are links:
If the collecter is looking at
B, then stops and the
mutator adds the B
and deletes the A
-C link we get
So, if the collecter has moved to
A it will conclude
C is garbage, which is not true. So the Dijkstra and Lamport
propose the following algorithm based on a coloring system (black, gray, and
white) with the following two invariants:
The algorithm follows:
During marking darkness increases monotonically. That is, white -> gray
During marking no pointers from black to white are allowed.
The cooperation between the mutator and collecter is the following:
Color all nodes white.
Make the root node gray
Make the children of any gray node at least gray gray.
When a node's children are all gray, color that node black.
Terminate when no nodes are gray and begin a collection.
any link is made, the target was be made at least gray. "At least gray" here
means that if the collector is making a node black, and the mutator tries to
make it gray, we make it black; otherwise we make it gray. This
algorithm is actually wrong because the link operations are not atomic with the
"make at least gray" operation.
Steele wants to make a correct concurrent GC. Everytime a mutator or
GC accesses an object the accessor must lock that object. This is clearly
correct because it solves the atomicity problem of Dijkstra and Lamport. In
addition he compactifies memory. To implement this he added forwarding pointers
when a live object tried to point to a non-live object. This required modifying
car, ... as well as
eq so that
pointers could be properly compared. This was accomplished using forwarding
pointers and pointer chasing.
Baker used two spaces, called to- and from-space. The mutator
only sees objects in to-space, so we need a read barrier because the
live objects could still have pointers to objects in from-space. Hence the read
barrier prevented pointers to from-space from reaching registers. So, when a
reference was made to a live object's, o1, pointer, that
pointer was analyzed. If it was to an object in to-space this is fine. If it is
to an object in from-space, o2, we check to see if it is a
forwarding pointer. If it is not a forwarding pointer, we copy o2
to to-space and add a forwarding pointer to its old location. Thus the memory
is related to Dijkstra and Lamport's colors by the following figure:
This method weas relatively efficient and didn't involve locks.
| new black |
| free |
| gray unscanned |
| black scanned |
Appel, Ellis, Li '88
A read barrier was implemented through page faults in hardware and was real
time, but not concurrent. The gray, unscanned region of memory was protected by
the kernel and generated a page fault when accessed by the mutator. The
advantage of this is that the mutator only sees black objects and is better
than Dijkstra and Lamport. A disadvantage is that is relies on support
from the operating system. The authors claim to have had good
results, but experiments by Zorn support the argument that read barriers can be
implemented more efficiently in software. The reliability of
benchmark results were questioned by members of the audience.