Garbage collecting the world: one car at a time

ABSTRACT

A new garbage collection algorithm for distributed object systems, called DMOS (Distributed. Mature Object Space), is presented. It is derived from two previous algorithms, MOS (Mature Object Space), sometimes called the train algorithm, and PMOS (Persistent Mature Object Space). The contribution of DMOS is that it provides the following unique combination of properties for a distributed collector: safety, completeness, non-disruptiveness, incrementality, and scalability. Furthermore, the DMOS collector is non-blocking and does not use global tracing.

REFERENCES

• Bakker+87: Volume I: Parallel architectures on PARLE: Parallel Architectures and Languages Europe, March 1987
• BC92: Proceedings of the International Workshop on Memory Management, September 1992
• BEN+93: Andrew Birrell, David Evers, Greg Nelson, Susan Owieki, and Edward Wobber. Distributed garbage collection for network objects. Digital Equipment Corporation, Systems Research Center Tech. Rep. 116, 15 December 1993.
• Bevan87: D I Bevan, Distributed garbage collection using reference counting, Volume II: Parallel Languages on PARLE: Parallel Architectures and Languages Europe, p.176-187, March 1987, Eindhoven, The Netherlands
• Bishop77: Peter B. Bishop. Computer systems with a very large address space and garbage collection. Ph.D. thesis, published as Technical Report MIT/LCS/TR- 178, Massachusetts Institute of Technology, 1977.
• CM86: Mani Chandy , Jayadev Misra, An example of stepwise refinement of distributed programs: quiescence detection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.326-343, July 1986 [doi>10.1145/5956.5958]
• CWZ94: Jonathan E. Cook , Alexander L. Wolf , Benjamin G. Zorn, Partition selection policies in object database garbage collection, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.371-382, May 24-27, 1994, Minneapolis, Minnesota, United States
• DFG83: E.W. Dijkstra, H. H. J. Feijen, and A. J. M. van Gasteren. Derivation of a termination detection algorithm for distributed computation. Information Processing Letters 16,217 (1983).
• Dickman91: Peter Diekman. Distributed object management in a non-small graph of autonomous networks with few failures. PhD thesis, University of Cambridge, United Kingdom, September 1991.
• Fidge96: Colin Fidge, Fundamentals of Distributed System Observation, IEEE Software, v.13 n.6, p.77-83, November 1996 [doi>10.1109/52.542297]
• FS96: Larchant: persistence by reachability in distributed shared memory through garbage collection, Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96), p.394, May 27-30, 1996
• Fuchs95: Matthew Fuchs, Garbage Collection on an Open Network, Proceedings of the International Workshop on Memory Management, p.251-265, September 27-29, 1995
• HM92: Richard L. Hudson , J. Eliot B. Moss, Incremental Collection of Mature Objects, Proceedings of the International Workshop on Memory Management, p.388-403, September 17-19, 1992
• HMMM97: Richard L. Hudson, Ron Morrison, j. Eliot B, Moss, David S. Munro. Training distributed garbage: The DMOS collector. Submitted for publication. Also available as a University of St Andrews, Dept. of Computer Science Technical Report (http://www-fide.dcs.st. and.ae.uk/Publieations/1997.html#dmos).
• Hughes85: John Hughes, A distributed garbage collection algorithm, Proc. of a conference on Functional programming languages and computer architecture, p.256-272, January 1985, Nancy, France
• IWMM95: Proceedings of the 1995 international Workshop on Memory Management (Ktnross, Scotland, United Kingdom). Published as number 986, Lecture Notes in Computer Science, Springer-Verlag.
• LJ91: Rafael D. Lins and Richard E. Jones. Cyclic weighted reference counting. Technical Report 95, University of Kent, Canterbury, United Kingdom, December 1991.
• LL86: Barbara Liskov , Rivka Ladin, Highly available distributed services and fault-tolerant distributed garbage collection, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.29-39, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10593]
• LL92: Rivka Ladin and Barbara Liskov. Garbage collection of a distributed heap. In Proceedings of the International Conference on Distributed Computing Systems, IEEE Press, 1992.
• LQP92: Bernard Lang , Christian Queinnec , José Piquer, Garbage collecting the world, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.39-50, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143176]
• MKI+95: Munenori Maeda , Hiroki Konaka , Yutaka Ishikawa , Takashi Tomokiyo , Atsushi Hori , Jörg Nolte, On-the-fly Global Garbage Collection Based on Partly Mark-Sweep, Proceedings of the International Workshop on Memory Management, p.283-296, September 27-29, 1995
• Mattern87: F. Mattem. Algorithms for distributed termination detection. Distributed Computing, 2,161 (1987).
• ML97: Umesh Maheshwari , Barbara Liskov, Partitioned garbage collection of a large object store, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.313-323, May 11-15, 1997, Tucson, Arizona, United States
• MMH96: L Eliot B. Moss, David 8. Munro, and Richard L. Hudson. PMOS: A complete and coarsegrained incremental garbage collector for persistent object stores, in Proceedings of the 7th International Workshop on Persistent Object Systems, pp. 140-150, Morgan Kaufmann, 1996.
• PS95: David Plainfossé , Marc Shapiro, A Survey of Distributed Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.211-249, September 27-29, 1995
• RJ96: Helena Rodrigues , Richard Jones, A Cyclic Distributed Garbage Collector for Network Objects, Proceedings of the 10th International Workshop on Distributed Algorithms, p.123-140, October 09-11, 1996
• Rudalics90: Martin Rudalies. Correctness of distributed garbage collection algorithms. Technical Report 90-40.0, Johannes Kepler Universitat,' Linz Austria, 1990.
• SG95: Jacob Seligmann , Steffen Grarup, Incremental Mature Garbage Collection Using the Train Algorithm, Proceedings of the 9th European Conference on Object-Oriented Programming, p.235-252, August 07-11, 1995
• Vestal87: S. C. Vestal, Garbage collection: an exercise in distributed, fault-tolerant programming, University of Washington, Seattle, WA, 1987
• WW87: P Watson , I Watson, An efficient garbage collection scheme for parallel computer architectures, Volume II: Parallel Languages on PARLE: Parallel Architectures and Languages Europe, p.432-443, March 1987, Eindhoven, The Netherlands
• Wilson92: Paul R. Wilson. Uniproeessor garbage collection techniques, in {BC92}.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Measurement, Performance, Theory