One paper PARLE89 , written with
Barbara Beaudoing and Jean-Pierre Queille, presents a concurrent GC
that prevents mutator starvation. The work of the mutator is
interleaved with the work of the marker and the work of the sweeper
ensuring a smooth control of their speeds.
The main point of that paper was the remark that the sweeper is only interested in cells proven dead, while the marker only sorts the possibly live cells therefore, they have no connection. This was already recognized with the "lazy-sweep" scheme where the sweep phase is performed by the allocation routine. But the sweeper must wait for the end of the marker before being able to perform its work and this may force the mutator to enter a starvation state if it wants to allocate a cell at the beginning of the marking phase since it must at least wait for the end of the marker to let the sweeper scans dead cells and recycle the one the mutator asked for. Returning to the independence of the marker and the sweeper, it is possible to start a new marking phase as soon as one has finished so, at any time and concurrently to the mutator, there is one marker and one sweeper (this latter scanning the results of the previous marking phase). The allocation routine may therefore combine part of the old sweep phase, part of the new mark phase and thus completely avoids starvation of the mutator.
My
other work POPL92 with Bernard Lang and
José Piquer describes a pretty general distributed and
fault-tolerant family of GC algorithms.
The main points of that technique are the following. On every node is a local GC that is able to propagate marks from Entry items to Exit items. These Entry and Exit items supports remote references. Entry items support a reference counter and are reclaimed when this counter reaches zero. Distributed garbage cycles are identified by non-local tracing GCs called group-GC. A group GC is performed by a group of mutually collaborating machines. The Entry items that are referenced from outside the group are identified and considered as local roots. Local GCs locally propagate marks, messages are sent from marked Exit items to the associated Entry items (if still in the same group) until the marks are stable. An unmarked Entry item in the group is garbage. Multiple group-GCs may be performed simultaneously, a single proof of unreachability is sufficient to recycle an Entry item. A group-GC may fail to terminate without impact on the others. Moreover a group-GC may act as a local GC for a wider group-GC.
This GC influenced my later work on a distributed Scheme.