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 ScholarDigital 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
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 (...
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