Abstract
Most modern middleware systems like Java Beans and .NET provide automatic garbage collection (GC). In spite of the many distributed solutions proposed in literature collection is typically limited to a single node and simple leasing techniques are used for remote references. In this paper we present a new incremental multistage GC. It has been implemented in the Plurix operating system but might easily be applied to other platforms. The scheme works incrementally and avoids blocking remote nodes. The reverse reference tracking scheme efficiently detects acyclic garbage and is also used for finding cyclic garbage without precomputing a global root set. To minimize network communication cycle detection splits into a local and a global detection part. Keeping the object markers in a separate stack avoids invalidation of replicated objects. Performance measurements show that the proposed distributed GC scheme scales very nicely.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Goeckelmann, R., Frenz, S., Schoettner, M., Schulthess, P.: Compiler Support for Reference Tracking in a type-safe DSM. In: Proc. of the Joint Modular Languages Conf., Klagen-furt, Austria (2003)
Wirt, N., Gutknecht, J.: Project Oberon. Addison-Wesley, Reading (1992)
The Plurix project: http://www.plurix.de
Amza, C., Cox, A.L., Drwarkadas, S., Keleher, P.: TreadMarks: Shared Memory Computing on Networks of Workstations. In: Proc. of the Winter 94 Usenix Conference (1994)
Le Sergent, T., Berthomieu, B.: Incremental multi-threaded garbage collection on virtually shared memory architectures. In: Bekkers, Y., Cohen, J. (eds.) IWMM-GIAE 1992. LNCS, vol. 637, pp. 179–199. Springer, Heidelberg (1992)
Jones, R.: Garbage Collection: Algorithms for Automatic Dynamic Memory Management, July 1996. John Wiley and Sons, Chichester (1996), with a chapter on Distributed Garbage Collection by Rafael Lins (reprinted 1997) (twice) (1999, 2000)
Birrell, A., et al.: Distributed garbage collection for network objects, in Technical Report 116, DEC Systems Research Center (1993)
Li, K.: IVY: A Shared Virtual Memory System for Parallel Computing. In: Proceedings of the International Conference on Parallel Processing (1988)
Shapiro, M., Plainfossé, D., Ferreira, P., Amsaleg, L.: Some Key Issues in the Design of Distributed Garbage Collection and References. In: Seminar on Unifying Theory and Practice in Distributed Systems. Dagstuhl Int. Conf. and Res. Center for Comp. Sc. (1994)
Yu, W.M., Cox, A.L.: Conservative garbage collection on distributed shared memory systems. In: Proc. of the Int’l Conf. on Distributed Computing Systems (ICDCS-16) (1996)
Bacon, D.F., Rajan, V.T.: Concurrent Cycle Collection in Reference Counting Sys-tems. In: Knudsen, J.L. (ed.) ECOOP 2001. LNCS, vol. 2072, Springer, Heidelberg (2001)
Fuchs, M.: Garbage Collection on an Open Network. In: Baker, H.G. (ed.) IWMM-GIAE 1995. LNCS, vol. 986, Springer, Heidelberg (1995)
Piquer, J.M.: Indirect Reference Counting, a distributed garbage collection algorithm. In: Aarts, E.H.L., Rem, M., van Leeuwen, J. (eds.) PARLE 1991. LNCS, vol. 505, pp. 150–165. Springer, Heidelberg (1991)
Piquer, J.M.: Indirect Mark and Sweep. In: Baker, H.G. (ed.) IWMM-GIAE 1995. LNCS, vol. 986, pp. 268–282. Springer, Heidelberg (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schoettner, M., Goeckelmann, R., Frenz, S., Fakler, M., Schulthess, P. (2006). Incremental Distributed Garbage Collection Using Reverse Reference Tracking. In: Nagel, W.E., Walter, W.V., Lehner, W. (eds) Euro-Par 2006 Parallel Processing. Euro-Par 2006. Lecture Notes in Computer Science, vol 4128. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11823285_59
Download citation
DOI: https://doi.org/10.1007/11823285_59
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37783-2
Online ISBN: 978-3-540-37784-9
eBook Packages: Computer ScienceComputer Science (R0)