Access Restriction

Author Steele, Guy L.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Garbage collection ♦ Storage reclamation ♦ List processing ♦ Reclaimer ♦ Data structures ♦ Storage allocation ♦ Synchronization ♦ Gc processor ♦ Pointers ♦ Compactification ♦ Multiprocessing ♦ Semaphores ♦ Parallel processing ♦ Free storage ♦ Relocation ♦ Lisp
Abstract 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.
Description Affiliation: Harvard Univ., Cambridge, MA (Steele, Guy L.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 18
Issue Number 9
Page Count 14
Starting Page 495
Ending Page 508

Open content in new tab

   Open content in new tab
Source: ACM Digital Library