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

CACM September, 1976

Wadler, P. L.

garbage collection, storage reclamation, list
processing, Lisp, time-sharing, multiprocessing, 
parallel processing, real time, data structures, analysis of algorithms

3.69 3.89 4.19 4.29 4.32 4.34 4.9 5.25

CA760901 JB January 4, 1978  9:57 AM

1024	4	2838
1051	4	2838
1102	4	2838
1132	4	2838
1390	4	2838
1486	4	2838
1549	4	2838
1706	4	2838
1826	4	2838
1878	4	2838
378	4	2838
2060	4	2838
2155	4	2838
2168	4	2838
2719	4	2838
2723	4	2838
2838	4	2838
2838	4	2838
2842	4	2838
2855	4	2838
2879	4	2838
2896	4	2838
3039	4	2838
3074	4	2838
3077	4	2838
3080	4	2838
3106	4	2838
3112	4	2838
627	4	2838
106	4	2838
210	5	2838
2723	5	2838
2838	5	2838
2838	5	2838
2838	5	2838
3112	5	2838
106	6	2838
1380	6	2838
1826	6	2838
1972	6	2838
2438	6	2838
2723	6	2838
2736	6	2838
2833	6	2838
2838	6	2838
731	6	2838