Deriving distributed garbage collectors from distributed termination algorithms

Garbage collection (Computer science);Electronic data processing--Distributed processing

Norcross, Stuart John ; Morrison, Ron ; Morrison, Ron

University:University of St Andrews

Department:Computer Science (School of)

关键词: Garbage collection (Computer science);    Electronic data processing--Distributed processing;   

Others  :  https://research-repository.st-andrews.ac.uk/bitstream/handle/10023/14986/StuartJNorcrossPhDThesis.pdf?sequence=2&isAllowed=y

来源: DR-NTU

【 摘 要 】

This thesis concentrates on the derivation of a modularised version of the DMOS distributed garbage collection algorithm and the implementation of this algorithm in a distributed computational environment. DMOS appears to exhibit a unique combination of attractive characteristics for a distributed garbage collector but the original algorithm is known to contain a bug and, previous to this work, lacks a satisfactory, understandable implementation. The relationship between distributed termination detection algorithms and distributed garbage collectors is central to this thesis. A modularised DMOS algorithm is developed using a previously published distributed garbage collector derivation methodology that centres on mapping centralised collection schemes to distributed termination detection algorithms. In examining the utility and suitability of the derivation methodology, a family of six distributed collectors is developed and an extension to the methodology is presented. The research work described in this thesis incorporates the definition and implementation of a distributed computational environment based on the ProcessBase language and a generic definition of a previously unimplemented distributed termination detection algorithm called Task Balancing. The role of distributed termination detection in the DMOS collection mechanisms is defined through a process of step-wise refinement. The implementation of the collector is achieved in two stages; the first stage defines the implementation of two distributed termination mappings with the Task Balancing algorithm; the second stage defines the DMOS collection mechanisms.