Concurrent Compacting Garbage Collection of
a Persistent Heap
Authors: James O'Toole, Scott Nettles, and David
Gifford
Appears in Proceedings of SOSP '93.
The full text of this paper is here (in
PostScript).
Abstract
We describe a replicating garbage collector for a persistent heap. The
garbage collector cooperates with a transaction manager to provide safe
and efficient transactional storage management. Clients read and
write the heap in primary memory and can commit or abort their write
operations. When write operations are committed they are preserved in
stable storage and survive system failures. Clients can freely access
the heap during garbage collection because the collector concurrently
builds a compact replica of the heap. A log captures client write
operations and is used to support both the transaction manager and the
replicating garbage collector.
Our implementation is the first to provide concurrent and compacting
garbage collection of a persistent heap. Measurements show that
concurrent replicating collection produces significantly shorter pause
times than stop-and-copy collection. For small transactions, throughput
is limited by the logging bandwidth of the underlying log manager. The
results suggest that replicating garbage collection offers a flexible
and efficient way to provide automatic storage management in transaction
systems, object-oriented databases and persistent programming
environments.