A Non-Blocking Reference Listing Algorithm for Mobile Active Object Garbage Collection Wei-Jen Wang Carlos A. Varela Distributed garbage collection Reference listing Actors Automatic garbage collection (GC) gives abstraction to distributed application development, promoting code quality and improving resource management. Unreachability of active objects or actors from the root set is not a sufficient condition to collect actor garbage, making passive object GC algorithms unsafe when directly used on actor systems. In practical actor languages, all actors have references to the root set since they can interact with users, e.g., through standard input or output streams. This feature makes every unblocked actor live, and thus we call it the live unblocked actor principle. Following this idea, we introduce pseudo-roots: a dynamic set of actors that can be viewed as the root set. Pseudo-roots use protected (undeletable) references to ensure that no actors are erroneously collected even with messages in transit. The pseudo-root approach simplifies distributed actor garbage collection by representing in-transit messages in the actor reference graph even if both application and system messages are unordered (non-FIFO) and communication is asynchronous. Our algorithm also supports systems not following the live unblocked actor principle and therefore, is applicable to more traditional actor garbage collection. We formalize the computing model of the pseudo-root approach and provide proofs of correctness. Furthermore, we summarize empirical results on the performance and scalability of distributed GC using a particle physics maximum likelihood evaluation fitter on a 72-processor cluster environment.Categories and Subject Descriptors: D.3.4 [Programming Languages]: Processors—Memorymanagement; D.4.2 [Operating Systems]: Storage Management—Garbage collection; D.4.7[Operating Systems]: Organization and Design—Distributed systemsGeneral Terms: Algorithms, LanguagesAdditional Key Words and Phrases: Distributed garbage collection, Reference listing, Actors,Active objects, Mobile objects Department of Computer Science, Rensselaer Polytechnic Institute cs-07-05
A Non-Blocking Reference Listing Algorithm for Mobile Active Object Garbage Collection
Wei-Jen Wang
Carlos A. Varela
Distributed garbage collection
Reference listing
Actors
Automatic garbage collection (GC) gives abstraction to distributed application development, promoting code quality and improving resource management. Unreachability of active objects or actors from the root set is not a sufficient condition to collect actor garbage, making passive object GC algorithms unsafe when directly used on actor systems. In practical actor languages, all actors have references to the root set since they can interact with users, e.g., through standard input or output streams. This feature makes every unblocked actor live, and thus we call it the live unblocked actor principle. Following this idea, we introduce pseudo-roots: a dynamic set of actors that can be viewed as the root set. Pseudo-roots use protected (undeletable) references to ensure that no actors are erroneously collected even with messages in transit. The pseudo-root approach simplifies distributed actor garbage collection by representing in-transit messages in the actor reference graph even if both application and system messages are unordered (non-FIFO) and communication is asynchronous. Our algorithm also supports systems not following the live unblocked actor principle and therefore, is applicable to more traditional actor garbage collection. We formalize the computing model of the pseudo-root approach and provide proofs of correctness. Furthermore, we summarize empirical results on the performance and scalability of distributed GC using a particle physics maximum likelihood evaluation fitter on a 72-processor cluster environment.Categories and Subject Descriptors: D.3.4 [Programming Languages]: Processors—Memorymanagement; D.4.2 [Operating Systems]: Storage Management—Garbage collection; D.4.7[Operating Systems]: Organization and Design—Distributed systemsGeneral Terms: Algorithms, LanguagesAdditional Key Words and Phrases: Distributed garbage collection, Reference listing, Actors,Active objects, Mobile objects
Department of Computer Science, Rensselaer Polytechnic Institute
cs-07-05