Article

Using passive object garbage collection algorithms for garbage collection of active objects

Authors:

Gul AghaAuthors Info & Claims

ISMM '02: Proceedings of the 3rd international symposium on Memory management

Pages 106 - 113

https://doi.org/10.1145/512429.512443

Published: 20 June 2002 Publication History

Abstract

With the increasing use of active object systems, agents and concurrent object oriented languages like Java, the problem of garbage collection (GC) of unused resources has become more complex. Since active objects are autonomous computational agents, unlike passive object systems the criterion for identifying garbage in active objects cannot be based solely on reachability from a root set. This has led to development of specialized algorithms for GC of active objects. We reduce the problem of GC of active objects to that of passive objects by providing a transformation of the active object reference graph to a passive object reference graph so that if a garbage collector for a passive object system is applied to the transformed graph, precisely those objects are collected which correspond to garbage objects in the original active object reference graph. The transformation technique enables us to reuse the algorithms already developed for passive objects systems. We provide a proof of correctness of the transformation and discuss its cost. An advantage of the transformation is that it can prove valuable for mixed systems of active and passive objects by providing a common approach to GC.

References

[1]

The Actor Foundry. http://www-osl.cs.uiuc.edu/foundry

[2]

G. Agha. Actors: A Model of Concurrent Computation in Distributed Systems. MIT Press, Cambridge, Mass., 1986

Digital Library

[3]

G. Agha, N. Jamali, and C. Varela. Agent naming and coordination: Actor based models and infrastructures. In A. Omicini, F. Zambonelli, M. Klusch, and R. Tolksdorf, editors, Coordination of Internet Agents: Models, Technologies, and Applications, chapter~9, pages 225--246. Springer-Verlag, Mar. 2001

Digital Library

[4]

J. Armstrong, M. Williams, and R. Virding. Concurrent Programming in Erlang. Prentice-Hall, Englewood Cliffs, NJ, 1993

Digital Library

[5]

L. Augusteijn. Garbage collection in a distributed environment. In de Bakker et al. {11}, pages 75--93

Digital Library

[6]

Y. Bekkers and J. Cohen, editors. Proceedings of International Workshop on Memory Management, volume 637 of Lecture Notes in Computer Science, St Malo, France, 16--18 Sept. 1992. Springer-Verlag

Digital Library

[7]

D. I. Bevan. Distributed garbage collection using reference counting. In PARLE Parallel Architectures and Languages Europe, volume 259 of Lecture Notes in Computer Science, pages 176--187. Springer-Verlag, June 1987

[8]

A. Birrell, D. Evers, G. Nelson, S. Owicki, and E. Wobber. Distributed garbage collection for network objects. Technical Report 116, DEC Systems Research Center, 130 Lytton Avenue, Palo Alto, CA 94301, Dec. 1993

[9]

J.-P. Briot. Actalk: A testbed for classifying and designing actor languages in the Smalltalk-80 environment. In S. Cook, editor, Proceedings ECOOP'89, pages 109--129, Nottingham, 10-14 1989. Cambridge University Press

[10]

K. M. Chandy and L. Lamport. Distributed snapshots: Determining global states of distributed systems. ACM Transactions on Computer Systems, 3(1):63--75, 1985

Digital Library

[11]

J. W. de Bakker, L. Nijman, and P. C. Treleaven, editors. PARLE'87 Parallel Architectures and Languages Europe, volume 258/259 of Lecture Notes in Computer Science, Eindhoven, The Netherlands, June 1987. Springer-Verlag

Digital Library

[12]

P. Dickman. Incremental, distributed orphan detection and actor garbage collection using graph partitioning and euler cycles. In O. Babaoglu and K. Marzullo, editors, Tenth International Workshop on Distributed Algorithms WDAG'96, volume 1151 of Lecture Notes in Computer Science, Bologna, Oct. 1996. Springer-Verlag

Digital Library

[13]

C. Fournet and G. Gonthier. The reflexive chemical abstract machine and the join-calculus. In Proceedings of the 23rd ACM Symposium on Principles of Programming Languages, pages 372--385, St. Petersburg Beach, Florida, Jan. 21-24 1996. ACM

Digital Library

[14]

R. J. M. Hughes. A distributed garbage collection algorithm. In J.-P. Jouannaud, editor, Record of the 1985 Conference on Functional Programming and Computer Architecture, volume 201 of Lecture Notes in Computer Science, pages 256--272, Nancy, France, Sept. 1985. Springer-Verlag

Digital Library

[15]

N.-C. Juul and E. Jul. Comprehensive and robust garbage collection in a distributed system. In Bekkers and Cohen {6}

Digital Library

[16]

D. Kafura, M. Mukherji, and G. Lavender. A class library for concurrent programming in C++ using actors, 1993

[17]

D. Kafura, M. Mukherji, and D. Washabaugh. Concurrent and distributed garbage collection of active objects. IEEE Transactions on Parallel and Distributed Systems, 6(4), Apr. 1995

Digital Library

[18]

D. Kafura, D. Washabaugh, and J. Nelson. Garbage collection of actors. In N. Meyrowitz, editor, OOPSLA'90 ACM Conference on Object-Oriented Systems, Languages and Applications, volume 25(10) of ACM SIGPLAN Notices, pages 126--134, Ottawa, Ontario, Oct. 1990. ACM Press

Digital Library

[19]

T. Kamada, S. Matsuoka, and A. Yonezawa. Efficient parallel global garbage collection on massively parallel computers. In E. Moss, P. R. Wilson, and B. Zorn, editors, OOPSLA/ECOOP '93 Workshop on Garbage Collection in Object-Oriented Systems, Oct. 1993

[20]

R. Ladin and B. Liskov. Garbage collection of a distributed heap. In International Conference on Distributed Computing Systems, Yokohama, June 1992

[21]

B. Lang, C. Quenniac, and J. Piquer. Garbage collecting the world. In Conference Record of the Nineteenth Annual ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices, pages 39--50. ACM Press, Jan. 1992

Digital Library

[22]

F. Le Fessant, I. Piumarta, and M. Shapiro. An implementation for complete asynchronous distributed garbage collection. In Proceedings of SIGPLAN'98 Conference on Programming Languages Design and Implementation, ACM SIGPLAN Notices, Montreal, June 1998. ACM Press

Digital Library

[23]

S. Louboutin and V. Cahill. A lazy log-keeping mechanism for comprehensive global garbage detection on Amadeus. In OOIS (Object-Oriented Information Systems) '95, pages 118--132, London, Dec. 1995. Springer-Verlag. Technical report TCD--CS--95--11

Digital Library

[24]

S. R. Louboutin. A Reactive Approach to Comprehensive Global Garbage Detection. PhD thesis, Trinity College, Dublin, 1998. In preparation

[25]

S. R. Louboutin and V. Cahill. Comprehensive distributed garbage collection by tracking causal dependencies of relevant mutator events. In Proceedings of ICDCS'97 International Conference on Distributed Computing Systems. IEEE Press, 1997

Digital Library

[26]

U. Maheshwari and B. Liskov. Collecting cyclic distributed garbage by back tracing. In Proceedings of PODC'97 Principles of Distributed Computing, 1997

Digital Library

[27]

J. M. Piquer. Indirect reference counting: A distributed garbage collection algorithm. In Aarts et al., editors, PARLE'91 Parallel Architectures and Languages Europe, volume 505 of Lecture Notes in Computer Science. Springer-Verlag, June 1991

Digital Library

[28]

I. Puaut. Distributed garbage collection of active objects with no global synchronisation. In Bekkers and Cohen {6}

Digital Library

[29]

I. Puaut. A distributed garbage collector for active objects. In PARLE'94 Parallel Architectures and Languages Europe, Lecture Notes in Computer Science. Springer-Verlag, 1994. Also INRIA UCIS-DIFUSION RR 2134

Digital Library

[30]

H. C. C. D. Rodrigues and R. E. Jones. Cyclic distributed garbage collection with group merger. In E. Jul, editor, Proceedings of 12th European Conference on Object-Oriented Programming, ECOOP98, Lecture Notes in Computer Science, pages 249--273, Brussels, July 1998. Springer-Verlag. Also UKC Technical report 17--97, December 1997

Digital Library

[31]

G. Rodriguez-Riviera and V. Russo. Cyclic distributed garbage collection without global synchronization in CORBA. In P. Dickman and P. R. Wilson, editors, OOPSLA '97 Workshop on Garbage Collection and Memory Management, Oct. 1997

[32]

M. Schelvis. Incremental distribution of timestamp packets --- a new approach to distributed garbage collection. ACM SIGPLAN Notices, 24(10):37--48, 1989

Digital Library

[33]

P. Sewell and P. Wojciechowski. Nomadic Pict: Language and infrastructure design for mobile agents, 2000

[34]

M. Shapiro, P. Dickman, and D. Plainfosse. SSP chains: Robust, distributed references supporting acyclic garbage collection. Rapports de Recherche 1799, Institut National de la Recherche en Informatique et Automatique, Nov. 1992. Also available as Broadcast Technical Report 1

Digital Library

[35]

A. Vardhan. Distributed garbage collection of active objects: A transformation and its applications to Java programming. Master's thesis, University of Illinois at Urbana Champaign, October 1998

[36]

N. Venkatasubramanian, G. Agha, and C. Talcott. Scalable distributed garbage collection for systems of active objects. In Bekkers and Cohen {6}, pages 134--147

[37]

N. Venkatasubramanian and C. L. Talcott. Reasoning about meta level activities in open distributed systems. In Symposium on Principles of Distributed Computing, pages 144--152, 1995

Digital Library

[38]

P. Watson and I. Watson. An efficient garbage collection scheme for parallel computer architectures. In de Bakker et al. {11}, pages 432--443

Digital Library

[39]

A. Yonezawa, J. R. Briot, and E. Shibayama. Object-oriented concurrent programming in ABCL/1. In Proceedings of the 1986 Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA'86), pages 258--268. ACM Press, 1986

Digital Library

Cited By

Plyukhin DAgha GDe Koster JBergenti FFranco J(2018)Concurrent garbage collection in the actor modelProceedings of the 8th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control10.1145/3281366.3281368(44-53)Online publication date: 5-Nov-2018
https://dl.acm.org/doi/10.1145/3281366.3281368
Koumarelas IKroschk AMosley CNaumann F(2018)ExperienceJournal of Data and Information Quality10.1145/323285210:2(1-16)Online publication date: 7-Sep-2018
https://dl.acm.org/doi/10.1145/3232852
Karanja EMasupe SGasennelwe-Jeffrey M(2018)Challenge PaperJournal of Data and Information Quality10.1145/323066910:2(1-5)Online publication date: 7-Sep-2018
https://dl.acm.org/doi/10.1145/3230669
Show More Cited By

Index Terms

Using passive object garbage collection algorithms for garbage collection of active objects
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Mostly concurrent garbage collection revisited
OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications

The mostly concurrent garbage collection was presented in the seminal paper of Boehm et al. With the deployment of Java as a portable, secure and concurrent programming language, the mostly concurrent garbage collector turned out to be an excellent ...
Age-based garbage collection
OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Using passive object garbage collection algorithms for garbage collection of active objects
MSP 2002 and ISMM 2002

With the increasing use of active object systems, agents and concurrent object oriented languages like Java, the problem of garbage collection (GC) of unused resources has become more complex. Since active objects are autonomous computational agents, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISMM '02: Proceedings of the 3rd international symposium on Memory management

June 2002

192 pages

ISBN:1581135394

DOI:10.1145/512429

General Chair:
Hans-J. Boehm
Hewlett-Packard Labs, USA
,
Program Chair:
David Detlefs
Sun Microsystems Labs, USA

ACM SIGPLAN Notices Volume 38, Issue 2 supplement
MSP 2002 and ISMM 2002
February 2003
291 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/773039
Issue’s Table of Contents

Copyright © 2002 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]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISMM02

Sponsor:

SIGPLAN

ISMM02: 2002 International Symposium on Memory Management ( co-located with PLDI 2002 )

June 20 - 21, 2002

Berlin, Germany

Acceptance Rates

ISMM '02 Paper Acceptance Rate 17 of 41 submissions, 41%;

Overall Acceptance Rate 72 of 156 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
600
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Plyukhin DAgha GDe Koster JBergenti FFranco J(2018)Concurrent garbage collection in the actor modelProceedings of the 8th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control10.1145/3281366.3281368(44-53)Online publication date: 5-Nov-2018
https://dl.acm.org/doi/10.1145/3281366.3281368
Koumarelas IKroschk AMosley CNaumann F(2018)ExperienceJournal of Data and Information Quality10.1145/323285210:2(1-16)Online publication date: 7-Sep-2018
https://dl.acm.org/doi/10.1145/3232852
Karanja EMasupe SGasennelwe-Jeffrey M(2018)Challenge PaperJournal of Data and Information Quality10.1145/323066910:2(1-5)Online publication date: 7-Sep-2018
https://dl.acm.org/doi/10.1145/3230669
Puentes JLaso PBrosset D(2018)The Challenge of Quality Evaluation in Fraud DetectionJournal of Data and Information Quality10.1145/322834110:2(1-4)Online publication date: 7-Sep-2018
https://dl.acm.org/doi/10.1145/3228341
Bjorner NCanini MSultana N(2017)Report on Networking and Programming Languages 2017ACM SIGCOMM Computer Communication Review10.1145/3155055.315506147:5(39-41)Online publication date: 25-Oct-2017
https://dl.acm.org/doi/10.1145/3155055.3155061
Bajpai VEravuchira SSchönwälder J(2017)Dissecting Last-mile Latency CharacteristicsACM SIGCOMM Computer Communication Review10.1145/3155055.315505947:5(25-34)Online publication date: 25-Oct-2017
https://dl.acm.org/doi/10.1145/3155055.3155059
CACM Staff (2017)Beyond brute forceCommunications of the ACM10.1145/313524160:10(8-9)Online publication date: 25-Sep-2017
https://dl.acm.org/doi/10.1145/3135241
Ancona DDagnino FZucca E(2017)Reasoning on divergent computations with coaxiomsProceedings of the ACM on Programming Languages10.1145/31339051:OOPSLA(1-26)Online publication date: 12-Oct-2017
https://dl.acm.org/doi/10.1145/3133905
Albarghouthi AD'Antoni LDrews SNori A(2017)FairSquare: probabilistic verification of program fairnessProceedings of the ACM on Programming Languages10.1145/31339041:OOPSLA(1-30)Online publication date: 12-Oct-2017
https://dl.acm.org/doi/10.1145/3133904
Sakka LSundararajah KKulkarni M(2017)TreeFuser: a framework for analyzing and fusing general recursive tree traversalsProceedings of the ACM on Programming Languages10.1145/31339001:OOPSLA(1-30)Online publication date: 12-Oct-2017
https://dl.acm.org/doi/10.1145/3133900
Show More Cited By

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents