page 1  (18 pages)
2to next section

A Cyclic Distributed Garbage Collector for

Network Objects

Helena Rodrigues? and Richard Jones

Computing Laboratory, University of Kent, Canterbury, Kent CT2 7NF, UK Tel: +44 1227 764000 x7754, Fax +44 1227 762811
email: fhccdr,R.E.Jonesg@ukc.ac.uk

Abstract. This paper presents an algorithm for distributed garbage collection and outlines its implementation within the Network Objects system. The algorithm is based on a reference listing scheme, which is augmented by partial tracing in order to collect distributed garbage cycles. Processes may be dynamically organised into groups, according to appropriate heuristics, to reclaim distributed garbage cycles. The algorithm places no overhead on local collectors and suspends local mutators only briefly. Partial tracing of the distributed graph involves only objects thought to be part of a garbage cycle: no collaboration with other processes is required. The algorithm offers considerable flexibility, allowing expediency and fault-tolerance to be traded against completeness.

Keywords: distributed systems, garbage collection, algorithms, termination detection, fault tolerance

1 Introduction

With the continued growth of interest in distributed systems, designers of languages for distributed systems are turning their attention to garbage collection [24, 21, 16, 14, 15, 3, 18, 19, 17, 9, 22], motivated by the complexity of memory management and the desire for transparent object management. The goals of an ideal distributed garbage collector are

safety: only garbage should be reclaimed;
completeness: all objects that are garbage at the start of a garbage collection cycle should be reclaimed by its end. In particular, it should be possible to reclaim distributed cycles of garbage;
concurrency: distributed garbage collection should not require the suspension of mutator or local collector processes; distinct distributed garbage collection processes should be able to run concurrently;
efficiency: garbage should be reclaimed promptly;
expediency: wherever possible, garbage should be reclaimed despite the unavailability of parts of the system;

? Work supported by JNICT grant (CIENCIA/BD/2773/93-IA) through the PRAXIS XXI Program (Portugal).