Concurrent and Real Time GC: HoPL 3/11/2004

Presented by Peter Douglass
Transcribed by Jeffrey Palm

Overview

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 were presented.

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: 
  A
 / \
O   C
 \
  B
If the collecter is looking at B, then stops and the mutator  adds the B -C link and deletes the A -C link we get the graph: 
  A
 / 
O   C
 \ /
  B
So, if the collecter has moved to A it will conclude that 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:
  1. During marking darkness increases monotonically. That is, white -> gray -> black.
  2. During marking no pointers from black to white are allowed.
The algorithm follows:
  1. Color all nodes white.
  2. Make the root node gray
  3. Make the children of any gray node at least gray gray.
  4. When a node's children are all gray, color that node black.
  5. Terminate when no nodes are gray and begin a collection.
The cooperation between the mutator and collecter is the following:
Before 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 '75

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 cdr,car, ... as well as eq so that pointers could be properly compared. This was accomplished using forwarding pointers and pointer chasing.

Baker '78

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: 
*----------------*
| new black      |
*----------------*
| free           |
*----------------*
| gray unscanned |
*----------------*
| black scanned  |
*----------------*
This method weas relatively efficient and didn't involve locks.

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.