Access Restriction

Author Wadler, Philip 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 ♦ Multiprocessing ♦ Parallel processing ♦ Data structures ♦ Analysis of algorithms ♦ Real time ♦ Lisp ♦ Time-sharing
Abstract A real time garbage collection system avoids suspending the operations of a list processor for the long times that garbage collection normally requires by performing garbage collection on a second processor in parallel with list processing operations, or on a single processor time-shared with them. Algorithms for recovering discarded list structures in this manner are presented and analyzed to determine sufficient conditions under which the list processor never needs to wait on the collector. These techniques are shown to require at most twice as much processing power as regular garbage collectors, if they are used efficiently. The average behavior of the program is shown to be very nearly equal to the worst-case performance, so that the sufficient conditions are also suitable for measuring the typical behavior of the algorithm.
Description Affiliation: Stanford Univ., Stanford CA, and Palo Alto, CA (Wadler, Philip 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 19
Issue Number 9
Page Count 10
Starting Page 491
Ending Page 500

Open content in new tab

   Open content in new tab
Source: ACM Digital Library