article

Free access

On-the-fly garbage collection: an exercise in cooperation

Authors:

E. F. M. SteffensAuthors Info & Claims

Communications of the ACM, Volume 21, Issue 11

Pages 966 - 975

https://doi.org/10.1145/359642.359655

Published: 01 November 1978 Publication History

PDF eReader

Abstract

As an example of cooperation between sequential processes with very little mutual interference despite frequent manipulations of a large shared data space, a technique is developed which allows nearly all of the activity needed for garbage detection and collection to be performed by an additional processor operating concurrently with the processor devoted to the computation proper. Exclusion and synchronization constraints have been kept as weak as could be achieved; the severe complexities engendered by doing so are illustrated.

References

[1]

Dijkstra, E.W. Guarded commands, nondeterminacy and formal derivation of programs. Comm. A CM 18, 8 (Aug. 1975), 453~;57.

Digital Library

Google Scholar

[2]

Gries, D. An exercise in proving parallel programs correct. Comm. ACM. 20, 12 (Dec. 1977), 921-930.

Digital Library

Google Scholar

[3]

Lamport, L. Proving the correctness of multiprocess programs. IEEE Trans. Software Eng. SE-3, 2 (March 1977), 125-143.

Digital Library

Google Scholar

[4]

Steele, Jr., G.L. Multiprocessing compactifying garbage collection. Comm. ACM 18, 9 (Sep. 1975), 495-508.

Digital Library

Google Scholar

[5]

Woodger, M. Private communications.

Google Scholar

Cited By

View all

Zhang YDhawal ONandivada VChiba SUgawa TLaemmel RPereira JMosses P(2024)Reducing Write Barrier Overheads for Orthogonal PersistenceProceedings of the 17th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3687997.3695646(210-223)Online publication date: 17-Oct-2024
https://dl.acm.org/doi/10.1145/3687997.3695646
Havelund KShankar N(2024)What Is a Garbage Collector? An Exercise in Compositional RefinementThe Practice of Formal Methods10.1007/978-3-031-66676-6_10(195-215)Online publication date: 4-Sep-2024
https://doi.org/10.1007/978-3-031-66676-6_10
Nanjekye JBremner DMicic AShirani POnut INg TKent KBaşar AOnut I(2022)The Garbage Collection Cost For Meta-Tracing JIT-based Dynamic LanguagesProceedings of the 32nd Annual International Conference on Computer Science and Software Engineering10.5555/3566055.3566071(140-149)Online publication date: 15-Nov-2022
https://dl.acm.org/doi/10.5555/3566055.3566071
Show More Cited By

Index Terms

On-the-fly garbage collection: an exercise in cooperation
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection
        Process management
        Multiprocessing / multiprogramming / multitasking

Recommendations

Garbage-first garbage collection
ISMM '04: Proceedings of the 4th international symposium on Memory management

<i>Garbage-First</i> is a server-style garbage collector, targeted for multi-processors with large memories, that meets a soft real-time goal with high probability, while achieving high throughput. Whole-heap operations, such as global marking, are ...
Multiprocessing compactifying garbage collection

Algorithms for a multiprocessing compactifying garbage collector are presented and discussed. The simple case of two processors, one performing LISP-like list operations and the other performing garbage collection continuously, is thoroughly examined. ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 21, Issue 11

Nov. 1978

95 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/359642

Editor:
Robert L. Ashenhurst
The Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

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 November 1978

Published in CACM Volume 21, Issue 11

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

506
Total Citations
View Citations
3,166
Total Downloads

Downloads (Last 12 months)344
Downloads (Last 6 weeks)42

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhang YDhawal ONandivada VChiba SUgawa TLaemmel RPereira JMosses P(2024)Reducing Write Barrier Overheads for Orthogonal PersistenceProceedings of the 17th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3687997.3695646(210-223)Online publication date: 17-Oct-2024
https://dl.acm.org/doi/10.1145/3687997.3695646
Havelund KShankar N(2024)What Is a Garbage Collector? An Exercise in Compositional RefinementThe Practice of Formal Methods10.1007/978-3-031-66676-6_10(195-215)Online publication date: 4-Sep-2024
https://doi.org/10.1007/978-3-031-66676-6_10
Nanjekye JBremner DMicic AShirani POnut INg TKent KBaşar AOnut I(2022)The Garbage Collection Cost For Meta-Tracing JIT-based Dynamic LanguagesProceedings of the 32nd Annual International Conference on Computer Science and Software Engineering10.5555/3566055.3566071(140-149)Online publication date: 15-Nov-2022
https://dl.acm.org/doi/10.5555/3566055.3566071
Veresov A(2022)On a possible embedding of Lisp into the C languageKeldysh Institute Preprints10.20948/prepr-2022-30(1-35)Online publication date: 2022
https://doi.org/10.20948/prepr-2022-30
Schneider F(2022)Evoking Whitehead’s DictumEdsger Wybe Dijkstra10.1145/3544585.3544614(445-454)Online publication date: 12-Jul-2022
https://dl.acm.org/doi/10.1145/3544585.3544614
Randell B(2022)Edsger Dijkstra—Some ReminiscencesEdsger Wybe Dijkstra10.1145/3544585.3544613(423-444)Online publication date: 12-Jul-2022
https://dl.acm.org/doi/10.1145/3544585.3544613
Lengauer C(2022)A Personal View of Edsger W. Dijkstra and His Stance on Software ConstructionEdsger Wybe Dijkstra10.1145/3544585.3544596(205-214)Online publication date: 12-Jul-2022
https://dl.acm.org/doi/10.1145/3544585.3544596
Lamport L(2022)Concurrent AlgorithmsEdsger Wybe Dijkstra10.1145/3544585.3544591(47-80)Online publication date: 12-Jul-2022
https://dl.acm.org/doi/10.1145/3544585.3544591
Lampson B(2022)Programming Concurrent SystemsEdsger Wybe Dijkstra10.1145/3544585.3544590(27-46)Online publication date: 12-Jul-2022
https://dl.acm.org/doi/10.1145/3544585.3544590
Yang AWrigstad T(2022)Deep Dive into ZGC: A Modern Garbage Collector in OpenJDKACM Transactions on Programming Languages and Systems10.1145/353853244:4(1-34)Online publication date: 21-Sep-2022
https://dl.acm.org/doi/10.1145/3538532
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Abstract

References

Cited By

Index Terms

Recommendations

Garbage-first garbage collection

Multiprocessing compactifying garbage collection

A generational on-the-fly garbage collector for Java

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations