Garbage collection and task deletion in distributed applicative processing systems

ABSTRACT

The problem of automatic storage reclamation for distributed implementations of applicative languages is explored. Highly parallel distributed systems have several unique characteristics that complicate the reclamation process; in this setting, the deficiencies of existing storage reclamation schemes are thus noted. A real-time, effectively distributed, garbage collector of the mark-sweep variety, called the marking-tree collector, is shown to accomplish reclamation in parallel with the main computation, with no centralized data or control other than a logical rendezvous between phases of the collector. In addition, it is capable of finding and subsequently deleting active processes which are determined to be no longer relevant to the computation.

REFERENCES

• 1: Guy Thomas Almes, Garbage collection in an object-oriented system, 1980
• 2: Henry G. Baker, Jr. , Carl Hewitt, The Incremental Garbage Collection of Processes, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 3: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 4: Bishop, P. Computer Systems With a Very Large Address Space and Garbage Collection. Ph.D. Th., Laboratory for Computer Science, Mass. Institute of Technology, May 1977.
• 5: Douglas W. Clark , C. Cordell Green, An empirical study of list structure in Lisp, Communications of the ACM, v.20 n.2, p.78-87, Feb. 1977 [doi>10.1145/359423.359427]
• 6: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
• 7: D.P. Friedman and D.S. Wise. Applicative multiprogramming. Tech. Rept. 72, Computer Science Dept., Indiana University, Dec., 1978.
• 8: Friedman, D.P. and Wise, D.S. "Aspects of applicative programming for parallel processing." IEEE Trans. Computers 27, 4 (April 1978), 289-296.
• 9: Dale H. Grit , Rex L. Page, Deleting Irrelevant Tasks in an Expression-Oriented Multiprocessor System, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.1, p.49-59, Jan. 1981 [doi>10.1145/357121.357125]
• 10: Halstead, R.H. Jr. Reference tree networks: virtual machine and implementation. Tech. Rept.MIT/LCS/TR-22, Massachusetts Institute of Technology Laboratory for Computer Science, 1979.
• 11: Hearn, A.C. Reduce 2 symbolic mode primer. Utah Symbolic Computation Group, Operating Note 5.1, University of Utah, October, 1974.
• 12: Hibino, Y. "A Practical Parallel Garbage Collection Algorithm and its Implementation." Sigarch Newsletter 8, 3 (May 1980),.
• 13: Paul Raymond Hudak, Object and task reclamation in distributed applicative processing systems, 1982
• 14: Keller, R.M., Lindstrom, G., and Patil, S. A loosely-coupled applicative multi-processing system. AFIPS, AFIPS, June, 1979, pp. 613-622.
• 15: Keller, R.M. Semantics and Applications of Function Graphs. Tech. Rept. UUCS-80-112, Department of Computer Science, University of Utah, Oct., 1980.
• 16: Kung, H.T. and Song, W. An Efficient Parallel Garbage Collection System and Its Correctness Proof. Department of Computer Science, Carnegie-Mellon Univ., Sept., 1977.
• 17: Lieberman, H. and Hewitt, C. A Real Time Garbage Collector That Can Recover Temporary Storage Quickly. AI Memo 569, Mass. Institute of Technology, Cambridge, Mass., April, 1980.
• 18: Nori, A.K. A Storage Reclamation Scheme For Applicative Multiprocessor System. Master Th., Department of Computer Science, University of Utah, Dec. 1979.
• 19: 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]
• 20: 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]
• 21: Philip L. Wadler, Analysis of an algorithm for real time garbage collection, Communications of the ACM, v.19 n.9, p.491-500, Sept. 1976 [doi>10.1145/360336.360338]
• 22: S. Ward, FUNCTIONAL DOMAINS OF APPLICATIVE LANGUAGES, Massachusetts Institute of Technology, Cambridge, MA, 1974

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Management