Analysis of an algorithm for real time garbage collection

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....

Full description

Saved in:
Bibliographic Details
Published in:Communications of the ACM 1976-09, Vol.19 (9), p.491-500
Main Author: Wadler, Philip L
Format: Magazinearticle
Language:English
Subjects:
Analysis
Collections
Data
Real time
Sanitation services
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0001-0782
1557-7317
DOI:10.1145/360336.360338