Distributed garbage collection

ABSTRACT

There are two basic approachs to the problem of storage reclamation, process- and processor-based, named for the view point used to recognize when a particular piece of storage can be reclaimed. Examples of the processor approach include mark/sweep and copying algorithms and their variants, while reference counting schemes use a process view of the collection. It is argued that the process approach is better suited for distributed computation where links between dynamically allocated objects may cross processor boundaries. In addition, the process approach allows the heap to be more conveniently shared with other processes in those cases when different processes might not have their own virtual address spaces. A new algorithm using the process approach is given. Its space requirement per object is better than that for reference counting. In addition, a restricted form of pointer replacement is supported which allows circular structures so constructed to be properly collected.

REFERENCES

• 1: 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]
• 2: 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]
• 3: Jeffrey L. Dawson, Improved effectiveness from a real time LISP garbage collector, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.159-167, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802146]
• 4: Mordechai Ben-Ari, Algorithms for on-the-fly garbage collection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.3, p.333-344, July 1984 [doi>10.1145/579.587]
• 5: Ashwin Ram , Janak H. Patel, Parallel garbage collection without synchronization overhead, Proceedings of the 12th annual international symposium on Computer architecture, p.84-90, June 17-19, 1985, Boston, Massachusetts, United States
• 6: 6. Peter B. Bishop (May 1977), Computer Systems With a Very Large Address Space and Garbage Collection, Massachusetts Institute of Technology, PhD Dissertation, TR-178.
• 7: Paul Hudak , Robert M. Keller, Garbage collection and task deletion in distributed applicative processing systems, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.168-178, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802147]
• 8: David Spector, Minimal overhead garbage collection of complex list structure, ACM SIGPLAN Notices, v.17 n.3, p.80-82, March 1982 [doi>10.1145/947912.947919]
• 9: 9. J. Dana Eckart (Aug. 1987), Garbage Collection in Distributed Systems, Ph.D. Dissertation, Georgia Institute of Technology.

INDEX TERMS

Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
  D.4 OPERATING SYSTEMS

General Terms:
Algorithms, Design, Languages