Library Computer Science

Paperback Edition

Paperback$19.95

180 pages

Choose vendor for paperback edition

Purchase from

PDF eBook

Sample Preview Free

Size: 1293k

Download a sample of the first 25 pages


Complete PDF $17

Size: 369k

Get instant access to an entire eBook

How do I open and print my eBook?

Preview & ebook options

Book cover image

A Reactive Approach to Comprehensive Global Garbage Detection

by Louboutin, Sylvain R Y

  Paperback       e-Book PDF
Institution:   University of Dublin, Trinity College, Ireland
Advisor(s): Vinny Cahill
Degree: Ph.D., Computer Science
Year: 1999
Volume: 180 pages
ISBN-10: 1581120443
ISBN-13: 9781581120448
Purchase options

Abstract

Comprehensive global garbage detection (GGD) in object-oriented distributed systems, i.e., GGD intrinsically able to detect distributed cycles of garbage, has mostly been addressed via graph tracing algorithms. Graph tracing algorithms must account for every live object in the system before any resource can actually be reclaimed which compromises both their scalability and robustness in a distributed environment.

Alternative non-comprehensive approaches trade-off comprehensiveness for scalability and robustness under the assumptions that distributed cycles of garbage are rare and that all comprehensive algorithms are necessarily unscalable. This thesis contends instead that distributed cycles of garbage are as likely to occur as local cycles and that a comprehensive alternative to graph tracing GGD is possible.

From the GGD perspective, the combined effects of the application processes and local garbage collectors fulfill the role of a global mutator. A subset of events of this global mutator's computation, called log-keeping events, reflect either the creation, or the destruction, of inter-site paths in the global object graph. The causal history of a log-keeping event corresponds to the set of events responsible for the creation of all the paths ever created that are incident to an object. The path history of this event is defined as a subset of its causal history and contains only those events responsible for the creation of the extant paths to this object.

This dissertation presents a novel approach to comprehensive GGD that entails computing dependency vectors which characterize the path history of log-keeping events that reflect the destruction of a path. These dependency vectors can be computed by propagating increasingly accurate approximations of these vectors along the paths of the global object graph. In effect, this algorithm reacts to events that may result in the creation of garbage and identifies garbage without requiring a complete scan of the whole object graph. In conjunction with a lazy log-keeping mechanism, it can therefore be shown to be both scalable and robust despite being comprehensive.

Paperback Edition

Paperback$19.95

180 pages

Choose vendor for paperback edition

Purchase from

PDF eBook

Sample Preview Free

Size: 1293k

Download a sample of the first 25 pages


Complete PDF $17

Size: 369k

Get instant access to an entire eBook

How do I open and print my eBook?

Preview & ebook options