Multiprocessing compactifying garbage collection
Guy Lewis Steele · Communications of the ACM · 1975
Algorithms for a multiprocessing compactifying garbage collector are presented and discussed. The simple case of two processors, one performing LISP-like list operations and the other performing garbage collection continuously, is thoroughly examined. The necessary capabilities of each processor are defined, as well as interprocessor communication and interlocks. Complete procedures for garbage collection and for standard list processing primitives are presented and thoroughly explained. Particular attention is given to the problems of marking and relocating list cells while another processor may be operating on them. The primary aim throughout is to allow the list processor to run unimpeded while the other processor reclaims list storage The more complex case involving several list processors and one or more garbage collection processors are also briefly discussed.
Cited by 250 works. doi:10.1145/361002.361005 Open-access PDF
Authors
References
- The Art of Computer Programming
- The structure of the “THE”-multiprogramming system
- Recursive functions of symbolic expressions and their computation by machine, Part I
- LISP 1.5 PROGRAMMER'S MANUAL
- Symmetric list processor
- Information Processing Language-V Manual
- Recursive Functions of Symbolic Expressions and Their Computation by Machine (1960)
- The structure of “THE”-multiprogramming system
- Knotted list structures
- A LISP garbage-collector for virtual-memory computer systems