In the Proceedings of the ACM SIGPLAN Symposium on Programming Language Design and Implementation (PLDI), May 1999.

82k compressed postscript / 243k PDF

**Abstract:**

This paper presents the first multiprocessor garbage collection
algorithm with provable bounds on time and space. The algorithm is a
real-time shared-memory copying collector. We prove that the
algorithm requires at most *2 (R(1 + 2/k) + N + 5PD)* memory
locations, where *P* is the number of processors, *R* is the maximum
reachable space during a computation (number of locations accessible
from the root set), *N* is the maximum number of reachable objects,
D is the maximum depth of any data object, and *k* is a parameter
specifying how many locations are copied each time a location is
allocated. Furthermore we show that client threads are never
stopped for more than time proportional to *k* non-blocking machine
instructions. The bounds are guaranteed even with arbitrary length
arrays. The collector only requires write-barriers (reads are
unaffected by the collector), makes few assumptions about the threads
that are generating the garbage, and allows them to run mostly
asynchronously.

@inproceedings{BlCh99, author = "Guy Blelloch and Perry Cheng", title = "On Bounding Time and Space for Multiprocessor Garbage Collection", booktitle = "Proc. ACM SIGPLAN Conference on Programming Language Design and Implementation {(PLDI)}", month = may, pages = "104--117", year = 1999}Scandal Homepage.

Guy Blelloch