Analysis of an algorithm for real time garbage collection

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.

REFERENCES

• 1: Dijkstra, E.W. Cooperating sequential processes. In Progrwnming Languages, F. Genuys, Ed., Academic Press, London, 1968.
• 2: Dijkstra, E.W. Notes on a real time garbage collection system. From a conversation with D.E. Knuth (private collection of D.E. Knuth), 1975.
• 3: Greenblatt, R. The LISP machine. Artificial Intelligence Working Paper 79, M.I.T., Cambridge, Mass., Nov. 1974.
• 4: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 5: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 6: Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975 [doi>10.1145/361002.361005]
• 7: Teitelman, W. Interlisp Reference Manual. Xerox Palo Alto Res. Center, Palo Alto, Calif., 1974.
• 8: Weissman, C. Lisp 1.5 Primer. Dickenson Pub. Co., Belmont, Calif., 1967.
• 9: Weyhrauch, R.W., and Thomas, A.J. FOL: A proof checker for first order logic. Memo 235, Artificial Intelligence Lab., Stanford U., Stanford, Calif., Sept. 1974.

INDEX TERMS

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