Multiprocessing compactifying garbage collection

ABSTRACT

Algorithms for a multiprocessing compactifying garbage collector are presented and discussed. The simple case of two processors, one performing LISP-like list operations and the other performing garbage collection continuously, is thoroughly examined. The necessary capabilities of each processor are defined, as well as interprocessor communication and interlocks. Complete procedures for garbage collection and for standard list processing primitives are presented and thoroughly explained. Particular attention is given to the problems of marking and relocating list cells while another processor may be operating on them. The primary aim throughout is to allow the list processor to run unimpeded while the other processor reclaims list storage The more complex case involving several list processors and one or more garbage collection processors are also briefly discussed.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Berkeley, E.C., and Bobrow, Daniel G. (Eds.) Tile Programming Language LISP: Its Operation and Applications. Information International, Inc., Cambridge, Mass., 1964.
	2	Bogen, R.A. MACSYMA Reference Manual. Project MAC, Mathlab Group, MIT, Cambridge, Mass., 1974.
	3	Conrad, W.R. A compaetifying garbage collector for ECL's non-homogeneous heap. Tech. Rep. 2-74, Center for Research in Computing Technology, Harvard U., Cambridge, Mass., Feb. 1974.
	4	Digital Equipment Corp. DecSystem 10 Assembly Language Handbook (third ed.). Maynard, Mass., 1973.
	5	Edsger W. Dijkstra, The structure of the “THE”-multiprogramming system, Communications of the ACM, v.11 n.5, p.341-346, May 1968 [doi>10.1145/363095.363143]
	6	Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
	7	Greenblatt, R. The LISP machine. MIT Artificial Intelligence Working Paper 79, MIT, Cambridge, Mass., Nov. 1974.
	8	Hart, T.P., and Evans, T.G. Notes on implementing LISP for the M-460 computer. Ref. {1}, 191-203.
	9	Knight, T. The CONS microprocessor. MIT Artificial Intelligence Working Paper 80, MIT, Cambridge, Mass., Nov. 1974.
	10	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	11	J. Harold McBeth, Letters to the editor: on the reference counter method, Communications of the ACM, v.6 n.9, p.575, Sept. 1963 [doi>10.1145/367593.367649]
	12	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]
	13	John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
	14	Marvin Minsky, A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Massachusetts Institute of Technology, Cambridge, MA, 1963
	15	Moon, D.A. MaeLISP Reference Manual. Project MAC, MIT, Cambridge, Mass., April 1974.
	16	Newell, A. Information Processing Language V Manual. Prentice-Hall, Englewood Cliffs, N.J., 1961.
	17	Saunders, R.A. The LISP system for the Q-32 computer. Ref. {1}, 220-231.
	18	H. Schorr , W. M. Waite, An efficient machine-independent procedure for garbage collection in various list structures, Communications of the ACM, v.10 n.8, p.501-506, Aug. 1967 [doi>10.1145/363534.363554]
	19	Teitelman, W. lnterLlSP Reference Manual. Xerox Corp., Palo Alto, Calif., 1974, 3.11-3.15.
	20	Wegbreit, B. A generalised compactifying garbage collector. Computer J. 15, 3 (Aug. 1972), 204-208.
	21	Wegbreit, B., et al. ECL Programmer's Manual. Tech. Rep. 21-72, Center for Research in Computing Technology, Harvard U., Cambridge, Mass., Sept. 1972.
	22	Ben Wegbreit, The treatment of data types in EL1, Communications of the ACM, v.17 n.5, p.251-264, May 1974 [doi>10.1145/360980.360992]
	23	J. Weizenbaum, Knotted list structures, Communications of the ACM, v.5 n.3, p.161-165, March 1962 [doi>10.1145/366862.366897]
	24	J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]