More Web Proxy on the site http://driver.im/

Article

TMOS: A Transactional Garbage Collector

Authors:

John N. Zigman,

Stephen Blackburn,

J. Eliot B. MossAuthors Info & Claims

POS-9: Revised Papers from the 9th International Workshop on Persistent Object Systems

Pages 138 - 156

Published: 06 September 2000 Publication History

Abstract

Defining persistence in terms of reachability is fundamental to achieving orthogonality of persistence. It is implicit to the principles of orthogonal persistence and is a part of the ODMG 3.0 data objects standard. Although space reclamation in the context of persistence by reachability can be achieved automatically using garbage collection, relatively few papers address the problem of implementing garbage collection in a transactional storage system.Atransactional GC algorithm must operate correctly in the face of failure, and in particular must deal with the problem of transaction abort, which by undoing changes such as the deletion of references, subverts the GC reachability axiom of 'once garbage always garbage'.In this paper we make two key contributions. First, we present a generic approach to the design of transactional collectors that promotes clarity, generality, and understandability, and then using this approach, we present a new transactional garbage collection algorithm, TMOS. Our design approach brings together three independent components--a mutator, a transactional store, and a GC algorithm. TMOS represents the application of the Mature Object Space family of GC algorithms to the transactional context through our approach to transactional GC design.

References

[1]

AMSALEG, L., FRANKLIN, M. J., AND GRUBER, O. 1995. Efficient incremental garbage collection for client-server object database systems. In U. Dayal, P. M. D. Gray, and S. NISHIO Eds., VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland (1995), pp. 42-53. Morgan Kaufmann.

[2]

ATKINSON, M. P. AND MORRISON, R. 1995. Orthogonally persistent systems. The VLDB Journal 4 , 3 (July), 319-402.

[3]

BLACKBURN, S. M. AND STANTON, R. B. 1999. The transactional object cache: A foundation for high performance persistent system construction. In R. MORRISON, M. JORDAN, and M. ATKINSON Eds., Advances in Persistent Object Systems: Proceedings of the Eighth InternationalWorkshop on Persistent Object Systems, Aug. 30-Sept. 1, 1998, Tiburon, CA, U.S.A. (San Francisco, 1999), pp. 37-50. Morgan Kaufmann.

[4]

BLACKBURN, S. M. AND ZIGMAN, J. N. 1999. Concurrency-- The fly in the ointment? In R. MORRISON, M. JORDAN, and M. ATKINSON Eds., Advances in Persistent Object Systems: Third International Workshop on Persistence and Java, Sept. 1-3, 1998, Tiburon, CA, U.S.A. (San Francisco, 1999), pp. 250-258. Morgan Kaufmann.

[5]

CATTELL, R. G. G., BARRY, D. K., BERLER, M., EASTMAN, J., JORDAN, D., RUSSELL, C., SCHADOW, O., STANIENDA, T., AND VELEZ, F. Eds. 2000. The Object Data Standard: ODMG 3.0 . Morgan Kaufmann Publishers.

[6]

COOK, J. E., WOLF, A. L., AND ZORN, B. G. 1994. Partition selection policies in object database garbage collection. In R. T. Snodgrass and M. Winslett Eds., Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, Minneapolis, Minnesota, May 24-27, 1994 (1994), pp. 371-382. ACM Press.

[7]

DIJKSTRA, E. W., LAMPORT, L., MARTIN, A. J., SCHOLTEN, C. S., AND STEFFENS, E. F. M. 1978. On-the-fly garbage collection: an exercise in cooperation. Communications of the ACM 21 , 11, 966-975.

[8]

HäRDER, T. AND REUTER, A. 1983. Principles of transactionoriented database recovery. ACM Computing Surveys 15 , 4 (Dec.), 287-317.

[9]

HE, Z., BLACKBURN, S. M., KIRBY, L., AND ZIGMAN, J. N. 2000. Platypus: Design and implementation of a flexible high performance object store. In Proceedings of the Ninth International Workshop on Persistent Object Systems, Lillehammer, Norway September 6-9, 2000 (2000).

[10]

HE, Z., MARQUEZ, A.,ANDBLACKBURN, S.M. 2000. Opportunistic prioritised clustering framework (OPCF). In ECOOP2000 Symposium on Objects and Databases - Object-Oriented Programming, Sophia Antipolis, France, June 13, 2000, Proceedings , Lecture Notes in Computer Science (LNCS) (2000). Springer. To appear.

[11]

HUDSON, R. AND MOSS, J. E. B. 1992. Incremental garbage collection of mature objects. In Y. BEKKERS AND J. COHEN Eds., InternationalWorkshop on Memory Management, St. MALO, France Sept. 17-19, 1992 , Volume 637 of Lecture Notes in Computer Science (LNCS) (1992, 1992), pp. 388-403. Springer.

[12]

KOLODNER, E. K. AND WEIHL, W. E. 1993. Atomic incremental garbage collection and recovery for large stable heap. In P. BUNEMAN and S. JAJODIA Eds., SIGMOD 1993, Proceedings ACM SIGMOD International Conference on the Management of Data, May 26-28,Washington, DC , Volume 22 of SIGMOD Record (June 1993), pp. 177-186. ACM Press.

[13]

LAKHAMRAJU, M. K., RASTOGI, R., SESHADRI, S., and SUDARSHAN, S. 2000. On-line reorganization in object databases. In SIGMOD 2000, Proceedings ACM SIGMOD International Conference on Management of Data, May 14-19, 2000, Dallas, Texas, USA , Volume 28 of SIGMOD Record (May 2000). ACM Press.

[14]

MAHESHWARI, U. AND LISKOV, B. 1997. Partitioned garbage collection of large object store. In J. PECKHAM Ed., SIGMOD1997, ProceedingsACMSIGMOD International Conference on Management of Data, May 13-15, 1997, Tucson, Arizona, USA , Volume 26 of SIGMOD Record (June 1997), pp. 313-323. ACM Press.

[15]

MAIER, D. 1999. Review - An approach to persistent programming. ACM SIGMOD Digital Review 1 .

[16]

MOSS, J. E. B., MUNRO, D. S., AND HUDSON, R. L. 1996. PMOS: A complete and coarse-grained incremental garbage collector. In R. Connor and S. Nettles Eds., Seventh (Cape May, NJ, U.S.A., May 29-31 1996), pp. 140-150. Morgan Kaufmann.

[17]

MUNRO, D. S., BROWN, A. L., MORRISON, R., AND MOSS, J. E. B. 1999. Incremental garbage collection of a persistent object store using PMOS. In R. MORRISON, M. J. Jordan, and M. P.ATKINSON Eds., Advances in Persistent Object Systems: Eigth International Workshop on Persistence Object SystemsSept. 1-3, 1998, Tiburon, CA, U.S.A. (San Francisco, 1999), pp. 78-91. Morgan Kaufmann.

[18]

SKUBISZEWSKI, M. AND VALDURIEZ, P. 1997. Concurrent garbage collection in o2. In M. JARKE, M. J. CAREY, K. R. DITTRICH, F. H. LOCHOVSKY, P. LOUCOPOULOS, and M. A. JEUSFELD Eds., VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece (1997), pp. 356- 365. Morgan Kaufmann.

[19]

SNODGRASS, R. T. 1999. Review - PM3: An orthogonal persistent systems programming language - design, implementation, performance. ACM SIGMOD Digital Review 1 .

[20]

Sun Microsystems. 1999. Java Data Objects Specification, JSR-

[21]

http://java.sun.com/aboutjava/communityprocess/jsr (July), Sun Microsystems Inc., 2550 Garcia Avenue, Mountain View, CA 94043.

[22]

YONG, V.-F., NAUGHTON, J., AND YU, J.-B. 1994. Storage reclamation and reorganization in client-server persistent stores. In Proceedings of the 10th International Conference on Data Engineering , IEEE Computing Society (Feb. 1994), pp. 120-131.

Cited By

Ritson CUgawa TJones R(2014)Exploring garbage collection with haswell hardware transactional memoryACM SIGPLAN Notices10.1145/2775049.260299249:11(105-115)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2775049.2602992
Ritson CUgawa TJones RGrove DGuyer S(2014)Exploring garbage collection with haswell hardware transactional memoryProceedings of the 2014 international symposium on Memory management10.1145/2602988.2602992(105-115)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2602988.2602992
Bond MMcKinley K(2008)Tolerating memory leaksACM SIGPLAN Notices10.1145/1449955.144977443:10(109-126)Online publication date: 19-Oct-2008
https://dl.acm.org/doi/10.1145/1449955.1449774
Show More Cited By

TMOS: A Transactional Garbage Collector
1. Information systems
  1. Information retrieval
    1. Specialized information retrieval

Recommendations

Mark-copy: fast copying GC with less space overhead
OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications

Copying garbage collectors have a number of advantages over non-copying collectors, including cheap allocation and avoiding fragmentation. However, in order to provide completeness (the guarantee to reclaim each garbage object eventually), standard ...
A generational on-the-fly garbage collector for Java
PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation

An on-the-fly garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly collectors are useful for multi-threaded applications ...
Mark-copy: fast copying GC with less space overhead
Special Issue: Proceedings of the OOPSLA '03 conference

Copying garbage collectors have a number of advantages over non-copying collectors, including cheap allocation and avoiding fragmentation. However, in order to provide completeness (the guarantee to reclaim each garbage object eventually), standard ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

POS-9: Revised Papers from the 9th International Workshop on Persistent Object Systems

September 2000

319 pages

ISBN:354042735X

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 06 September 2000

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ritson CUgawa TJones R(2014)Exploring garbage collection with haswell hardware transactional memoryACM SIGPLAN Notices10.1145/2775049.260299249:11(105-115)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2775049.2602992
Ritson CUgawa TJones RGrove DGuyer S(2014)Exploring garbage collection with haswell hardware transactional memoryProceedings of the 2014 international symposium on Memory management10.1145/2602988.2602992(105-115)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2602988.2602992
Bond MMcKinley K(2008)Tolerating memory leaksACM SIGPLAN Notices10.1145/1449955.144977443:10(109-126)Online publication date: 19-Oct-2008
https://dl.acm.org/doi/10.1145/1449955.1449774
Bond MMcKinley KHarris GKiczales GRiehle DBlack A(2008)Tolerating memory leaksProceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications10.1145/1449764.1449774(109-126)Online publication date: 19-Oct-2008
https://dl.acm.org/doi/10.1145/1449764.1449774
Printezis TGarthwaite A(2002)Visualising the train garbage collectorACM SIGPLAN Notices10.1145/773039.51243638:2 supplement(50-63)Online publication date: 20-Jun-2002
https://dl.acm.org/doi/10.1145/773039.512436
Printezis TGarthwaite ABoehm HDetlefs D(2002)Visualising the train garbage collectorProceedings of the 3rd international symposium on Memory management10.1145/512429.512436(50-63)Online publication date: 20-Jun-2002
https://dl.acm.org/doi/10.1145/512429.512436

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents