Richard L. Hudson
J. Eliot B. Moss
Skip Abstract Section
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.
- Bakker+87 W. Jacobus Bakk'er~ L. Nijman, and Philip C. Treleaven, editors. Parallel Architectures and Languages Europe, numbers 258, 259 in Lecture Notes in Computer Science, Springer- Verlag, June 1987. Google Scholar
Digital Library
- BC92 Bekkers and Cohen, editors. In Proceedings of the International Workshop on Memory Management, St. Male, France, 1992. Published as number 637, Lecture Notes in Computer Science, Springer-Verlag, 1992. Google ScholarDigital Library
- 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.Google Scholar
- Bevan87 David I. Bevan. Distributed garbage collection using reference counting. In {Bakker+87}. Google ScholarDigital Library
- 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.Google Scholar
- CM86 K.M. Chandy and J. Misra. An example of stepwise refinement of distributed programs: quiescence detection. ACM Trans. on Prog, Lang. and Systems 8,326 (1986). Google ScholarDigital Library
- CWZ94 Johnathan E. Cook, Alexander L. Wolf, and Benjamin G. Zorn. Partition selection policies in object database garbage collection. In Proceedings of the 1994 A CM SIGMOD International Conference on Management of Data (SIGMOD '94) (Minneapolis, MN, May 1994), pp, 371-382. Google ScholarDigital Library
- 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).Google ScholarCross Ref
- 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.Google Scholar
- Fidge96 C.J. Fidge. Fundamentals of distributed system observation. IEEE Software, 13(6):77- 83, November 1996. Google ScholarDigital Library
- FS96 Paulo Ferreira and Mare Shapiro. Larehant: Persistence by reachability in distributed shared memory through garbage collection, In Proceedings of the 16th International Conference on Distributed Computing Systems, IEEE Press, 1996. Google ScholarDigital Library
- Fuchs95 Matthew Fuehs. Garbage collection on an open network. In {IWMM95}, pp. 251-266. Google ScholarDigital Library
- HM92 Richard L. Hudson and J. Eliot B. Moss. Incremental garbage collection for mature objects. In {BC92}. Google ScholarDigital Library
- 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).Google Scholar
- Hughes85 R. John M. Hughes. A distributed garbage collection algorithm. In Proceedings of the 1985 Conference on Functional Programming and Computer Architecture, number 201, Lecture Notes in Computer Science, pp, 256- 272, Springer-Verlag, 1985. Google ScholarDigital Library
- 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.Google Scholar
- LJ91 Rafael D. Lins and Richard E. Jones. Cyclic weighted reference counting. Technical Report 95, University of Kent, Canterbury, United Kingdom, December 1991.Google Scholar
- LL86 Barbara Liskov and Rivka Ladin. Highlyavailable distributed services and faulttolerant distributed garbage collection. In Fifth ACM Symposium on the Principles of Distributed Computing, pp. 29-39, 1986. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- LQP92 Bernard Lang, Christian Queinniec, and Jose Piquer. Garbage collecting the world, in Proceedings of the A CM Symposium on Principles of Programming Languages, pp. 39-50, ACM Press, 1992. Google ScholarDigital Library
- MKI+95 M. Maeda, H. Konake, Y. Ishikawa, T. Tomokiyo, A. Hori, and J. Nolte. On the fly global garbage collection based on partly mark-sweep. In {1WMM95}, pp. 283-296. Google ScholarDigital Library
- Mattern87 F. Mattem. Algorithms for distributed termination detection. Distributed Computing, 2,161 (1987).Google ScholarDigital Library
- ML97 Umesh Maheshwari and Barbara Liskov. Partitioned garbage collection of a large object store. In Proceedings of A CM SIGMOD '97, Phoenix, Arizona, 1997. Google ScholarDigital Library
- 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.Google Scholar
- PS95 David Plainfoss6 and Mare Shapiro. A survey of distributed garbage collection techniques. In Proceedings of International Workshop on Memory Management, Kinross, Scotland, pp. 211-249, September 1995. Google ScholarDigital Library
- RJ96 Helena Rodrigues and Richard Jones. A eyelie distributed garbage collector for Network Objects. in Proceedings of l Oth International Workshop on Distributed Algorithms (WDAG '96) Bologna (Italy) 9-11 October 1996. Google ScholarDigital Library
- Rudalics90 Martin Rudalies. Correctness of distributed garbage collection algorithms. Technical Report 90-40.0, Johannes Kepler Universitat,' Linz Austria, 1990.Google Scholar
- SG95 Jacob Seligmann and Steffen Grarup. Incremental mature garbage collection using the train algorithm. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP "95) (Aarhus, Denmark, August 1995), no. 952 in Lecture Notes in Computer Science, Springer-Verlag, pp. 235- 252. Google ScholarDigital Library
- Vestal87 S.C. Vestal. Garbage collection: An exercise in distributed, fault-tolerant programming. PhD thesis, University of Washington, Seattle, Washington, January 1987. Google ScholarDigital Library
- WW87 E Watson and L Watson. An efficient garbage collection scheme for parallel computer architecture. In {Bakker+87}, pp. 432-443. Google ScholarDigital Library
- Wilson92 Paul R. Wilson. Uniproeessor garbage collection techniques, in {BC92}.Google Scholar
Index Terms
- Garbage collecting the world: one car at a time
Recommendations
Garbage collecting the world
POPL '92: Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languagesDistributed symbolic computations involve the existence of remote references allowing an object, local to a processor, to designate another object located on another processor. To reclaim inaccessible objects is the non trivial task of a distributed ...
Garbage collecting the world: one car at a time
OOPSLA '97: Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applicationsA 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 (...
Garbage collecting the grid: a complete DGC for activities
Middleware '07: Proceedings of the ACM/IFIP/USENIX 2007 International Conference on MiddlewareGrids are becoming more and more dynamic, running parallel applications on large scale and heterogeneous resources. Explicitly stopping a whole distributed application is becoming increasingly difficult. In that context, there is a strong need to free ...
Comments