article

Free access

Concurrent compacting garbage collection of a persistent heap

Authors:

David GiffordAuthors Info & Claims

ACM SIGOPS Operating Systems Review, Volume 27, Issue 5

Pages 161 - 174

https://doi.org/10.1145/173668.168632

Published: 01 December 1993 Publication History

Abstract

We describe a replicating garbage collector for a persistent heap. The garbage collector cooperates with a transaction manager to provide safe and efficient transactional storage management. Clients read and write the heap in primary memory and can commit or abort their write operations. When write operations are committed they are preserved in stable storage and survive system failures. Clients can freely access the heap during garbage collection because the collector concurrently builds a compact replica of the heap. A log captures client write operations and is used to support both the transaction manager and the replicating garbage collector.Our implementation is the first to provide concurrent and compacting garbage collection of a persistent heap. Measurements show that concurrent replicating collection produces significantly shorter pause times than stop-and-copy collection. For small transactions, throughput is limited by the logging bandwidth of the underlying log manager. The results suggest that replicating garbage collection offers a flexible and efficient way to provide automatic storage management in transaction systems, object-oriented databases and persistent programming environments.

References

[1]

Guy T. Almes. Garbage Collection in a Object-Oriented System. Technical Report CMU-CS-80-128, Carnegie Mellon University, June 1980.

[2]

A. Appel. Simple Generational Garbage Collection and Fast Allocation. Software-Practice and Experience, 19(2): 171-183, February 1989.

Digital Library

[3]

Andrew W. Appel, John R. Ellis, and Kai Li. Real-time Concurrent Garbage Collection on Stock Multiprocessots. In SIGPLAN Symposium on Programming Language Design and implementation, pages 11-20, 1988.

Digital Library

[4]

M. P. Atkinson, K. j. Chisolm, and W. E Cockshott. PS-Algol: an Algol with a persistent heap. SIGPLAN Notices, 17(7):24-31, July 1982.

Digital Library

[5]

H. G. Baker. List Processing in Real Time on a Serial Computer. Communications of the ACM, 21 (4):280- 294, 1978.

Digital Library

[6]

R.G.G. CattelI. An Engineering Database Benchmark. In Jim Gray, editor, The Benchmark Handbook for Database and Transaction Processing Systems, pages 247-281. Morgan-Kaufmann, 1991.

[7]

Eric Cooper, Scott Nettles, and Indira Subramanian. Improving the Performance of SML Garbage Collection using Application-Specific Virtual Memory Management. In Proceedings of the A CM Conference on Lisp and Functional Programming, pages 43-52, June 1992.

Digital Library

[8]

Transactions Processing Council. TPC-B. In Jim Gray, editor. The Benchmark Handbook for Database and Transaction Processing Systems, pages 79-114. Morgan-Kaufmann, 1991.

[9]

D. L. Detlefs, M. P. Herlihy, and J. M. Wing. Inheritance of Synchronization and Recovery Properties in Avalon/C++. IEEE Computer, pages 57-69, December 1988.

Digital Library

[10]

David L. Detlefs. Concurrent, atomic garbage collection. Technical Report CMU-CS-90-177, Carnegie Mellon University, October 1990.

[11]

E. Dijkstra, L. Lamport, A. Martin, C. Scholten, and E. Steffens. On-the-fly Garbage Collection:An Exercise in Cooperation. Communications of the A CM, 21(11):966-975, November 1978.

Digital Library

[12]

Olivier Gruber. Eos: An Environment for Persistent and Distributed Applications in a Shared Object Space. host ftp.inria.fr directory INRIA/Projects/RODIN file Olivier. Gruber.phd,ps.Z, December 1992.

[13]

Lorenz Huelsbergen and James R. Larus. A Concurrent Copying Garbage Collector for Languages that Distinguish (Ira)mutable Data. In Proceedings of the 1993 A CM Symposiym on Principles and Practice of Parallel Programming, 1993.

Digital Library

[14]

Eliot K. Kolodner. Atomic Incremental Garbage Collection and Recovery for a Large Stable Heap. Technical Report MIT/LCS/TR-534, Massachusetts Institute of Technology, February 1992.

[15]

B. Liskov and R. Scheifler. Guardians and Actions: Linguistic Support for Robust, Distributed Programs. A CM Transactions on Programming Languages and Systems, 5(3):382-404, july 1983.

Digital Library

[16]

Scott M. Nettles and James W. O'Toole. Real-Time Replication Garbage Collection. In SIGPLAN Symposium on Programming Language Design and Implementation, pages 217-226. ACM, June 1993.

Digital Library

[17]

Scott M. Nettles, James W. O'Toole, David Pierce, and Nicholas Haines. Replication-Based Incremental Copying Collection. In Proceedings of the SIGPLAN International Workshop on Memory Management, pages 357-364. ACM, Springer-Verlag, September 1992.

Digital Library

[18]

S.M. Nettles and J.M. Wing. Persistance + Undoability = Transactions. In Proceedings of the 25th Hawaii International Conference on System Sciences, volume 2, pages 832-843. IEEE, January 1992.

[19]

James W. O'Toole and Scott M. Nettles. Concurrent Replication Garbage Collection. Technical Report MIT- LC$-TR-570 and CMU-CS-93-138, Massachusetts Institute of Technology and Carnegie Mellon University, 1993.

Digital Library

[20]

M. Satyanarayanan, Henry H. Mashburn, Puneet Kumar, David C. Steere, and James J. Kistler. Lightweight Recoverable Virtual Memory. In Proceedings of the 14th A CM Symposium on Operating Systems Principles, December 1993.

Digital Library

[21]

Paul R. Wilson. Uniprocessor Garbage Collection Techniques, in Proceedings of the 1992 SiGPLAN international Workshop on Memory Management, pages 1-42. ACM, Springer-Verlag, September 1992.

Digital Library

[22]

J.M. Wing, M. Faehndrrich, N. Haines, K. Kietzke, D. Kindred, J.G. Morrisett, and S.M. Nettles. Venari/ML Interfaces and Examples. Technical Report CMU-CS-93-123, Carnegie Mellon University, March 1993.

Digital Library

[23]

Benjamin Zorn. The Measured Cost of Conservative Garbage Collection. SoftwaretPractice and Experience, 23(7):733-756, July 1993.

Digital Library

Cited By

Wu MZhao ZLi HLi HChen HZang BGuan H(2018)EspressoACM SIGPLAN Notices10.1145/3296957.317320153:2(70-83)Online publication date: 19-Mar-2018
https://dl.acm.org/doi/10.1145/3296957.3173201
Wu MZhao ZLi HLi HChen HZang BGuan HShen XTuck JBianchini RSarkar V(2018)EspressoProceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3173162.3173201(70-83)Online publication date: 19-Mar-2018
https://dl.acm.org/doi/10.1145/3173162.3173201
Amsaleg LFranklin MGruber O(1999)Garbage collection for a client-server persistent object storeACM Transactions on Computer Systems10.1145/320656.32274117:3(153-201)Online publication date: 1-Aug-1999
https://dl.acm.org/doi/10.1145/320656.322741
Show More Cited By

Index Terms

Concurrent compacting garbage collection of a persistent heap
1. General and reference
  1. Cross-computing tools and techniques
    1. Measurement
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Communications management
        Memory management
        Allocation / deallocation strategies
        Process management
        Concurrency control

Recommendations

Concurrent compacting garbage collection of a persistent heap
SOSP '93: Proceedings of the fourteenth ACM symposium on Operating systems principles

We describe a replicating garbage collector for a persistent heap. The garbage collector cooperates with a transaction manager to provide safe and efficient transactional storage management. Clients read and write the heap in primary memory and can ...
Concurrent Garbage Collection of Persistent Heaps
Concurrent Garbage Collection of Persistent Heaps

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGOPS Operating Systems Review

ACM SIGOPS Operating Systems Review Volume 27, Issue 5

Dec. 1993

283 pages

ISSN:0163-5980

DOI:10.1145/173668

Editor:
William M. Waite
Univ. of Colorado, Boulder

Issue’s Table of Contents

SOSP '93: Proceedings of the fourteenth ACM symposium on Operating systems principles
January 1994
284 pages
ISBN:0897916328
DOI:10.1145/168619
Chairmen:
Andrew P. Black
Digital Equipment Corp.
,
Barbara Liskov
Massachusetts Institute of Technology (MIT), Cambridge

Copyright © 1993 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1993

Published in SIGOPS Volume 27, Issue 5

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
633
Total Downloads

Downloads (Last 12 months)88
Downloads (Last 6 weeks)14

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu MZhao ZLi HLi HChen HZang BGuan H(2018)EspressoACM SIGPLAN Notices10.1145/3296957.317320153:2(70-83)Online publication date: 19-Mar-2018
https://dl.acm.org/doi/10.1145/3296957.3173201
Wu MZhao ZLi HLi HChen HZang BGuan HShen XTuck JBianchini RSarkar V(2018)EspressoProceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3173162.3173201(70-83)Online publication date: 19-Mar-2018
https://dl.acm.org/doi/10.1145/3173162.3173201
Amsaleg LFranklin MGruber O(1999)Garbage collection for a client-server persistent object storeACM Transactions on Computer Systems10.1145/320656.32274117:3(153-201)Online publication date: 1-Aug-1999
https://dl.acm.org/doi/10.1145/320656.322741
Ruffin M(1995)Log compaction and garbage collection-What could they bring to each other?Proceedings of International Workshop on Object Orientation in Operating Systems10.1109/IWOOS.1995.470577(64-67)Online publication date: 1995
https://doi.org/10.1109/IWOOS.1995.470577
Chen LZhao JWang CCao TZigman JVolos HMutlu OLv FFeng XXu GCui H(2022)Unified Holistic Memory Management Supporting Multiple Big Data Processing Frameworks over Hybrid MemoriesACM Transactions on Computer Systems10.1145/351121139:1-4(1-38)Online publication date: 5-Jul-2022
https://dl.acm.org/doi/10.1145/3511211
Lebeck NKrishnamurthy ALevy HZhang IGavrilovska AZadok E(2020)End the senseless killingProceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference10.5555/3489146.3489206(873-887)Online publication date: 15-Jul-2020
https://dl.acm.org/doi/10.5555/3489146.3489206
Wang CCui HCao TZigman JVolos HMutlu OLv FFeng XXu GMcKinley KFisher K(2019)Panthera: holistic memory management for big data processing over hybrid memoriesProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314650(347-362)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314650
Park SKelly TShen KHanzálek ZHärtig HCastro MKaashoek M(2013)Failure-atomic msync()Proceedings of the 8th ACM European Conference on Computer Systems10.1145/2465351.2465374(225-238)Online publication date: 15-Apr-2013
https://dl.acm.org/doi/10.1145/2465351.2465374
Narayanan DHodson O(2012)Whole-system persistenceACM SIGPLAN Notices10.1145/2248487.215101847:4(401-410)Online publication date: 3-Mar-2012
https://dl.acm.org/doi/10.1145/2248487.2151018
Narayanan DHodson O(2012)Whole-system persistenceACM SIGARCH Computer Architecture News10.1145/2189750.215101840:1(401-410)Online publication date: 3-Mar-2012
https://dl.acm.org/doi/10.1145/2189750.2151018
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Issue’s Table of Contents