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