This thesis describes a new approach to achieving high quality distributed garbage collection using the Train Algorithm. This algorithm has been investigated for its ability to provide high quality collection in a variety of contexts, including persistent object systems and distributed object systems. Prior literature on the distributed Train Algorithm suggests that safe, complete, asynchronous, and scalable collection can be attained, however an approach that achieves this combination of behaviour has yet to emerge. The mechanisms and policies described in this thesis are unique in their ability to exploit the distributed Train Algorithm in a manner that displays all four desirable qualities. Further the mechanisms allow any number of mutator and collector threads to operate concurrently within a site; this is also a unique property amongst train-based mechanisms (distributed or otherwise). Confidence in the quality of the approach promoted in this thesis is obtained via a top-down approach. Firstly a concise behavioural model is introduced to capture fundamental requirements for safe and complete behaviour from train-based collection mechanisms. The model abstracts over the techniques previously introduced under the banner of the Train Algorithm. It serves as a self- contained template for correct train-based collection that is independent of a target object system for deployment of the algorithm. Secondly a means to instantiate the model in a distributed object system is described. The instantiation includes well-established techniques from prior literature, and via the model these are correctly refined and reorganised with new techniques to achieve asynchrony, scalability, and support for concurrency. The result is a flexible approach that allows a distributed system to exhibit a variety of local collection mechanisms and policies, while ensuring their interaction is safe, complete, asynchronous, and scalable regardless of the local choices made by each site. Additional confidence in the properties of the new approach is obtained from implementation within a distributed object system simulation. The implementation provides some insight into the practical issues that arise through the combination of distribution, concurrent execution within sites, and train-based collection. Executions of the simulation system are used to verify that safe collection is observed at all times, and obtain evidence that asynchrony, scalability, and concurrency can be observed in practice. / Thesis (Ph.D.)--School of Computer Science, 2004.
| Identifer | oai:union.ndltd.org:ADTP/263601 |
| Date | January 2004 |
| Creators | Lowry, Matthew C. |
| Source Sets | Australiasian Digital Theses Program |
| Language | en_US |
| Detected Language | English |
Page generated in 0.0015 seconds