|
||||||||||||||||
|
Ph.D. ThesesDistributed Garbage Collection for Large-Scale Mobile Actor Systems
By Wei-Jen Wang
Distributed actor garbage collection is a notoriously hard problem due to the nature of distributed actor systems --- no common clock, no coherent global information, asynchronous and unordered message passing, autonomous behavior of actors, and counter-intuitive actor marking to identify live actors. Most existing distributed actor garbage collection algorithms rely on First-In-First-Out (FIFO) or simulated FIFO communication, which violates the precondition of the actor model and is impractical with actor mobility; others depend on stop-the-world synchronization, which is intrusive, impractical, and not scalable for users' computations. All existing actor garbage collection algorithms ignore actor mobility and resource access restrictions. All existing distributed passive object garbage collection algorithms cannot be directly reused because of the different nature of passive objects and actors. To overcome the problems that existing algorithms cannot solve, this thesis presents a practical actor garbage collection mechanism for actor-oriented programming languages and distributed mobile actor systems. Our approach starts from providing the definition of garbage actors from the perspective of the reference graph, and then we show two different but similar transformation methods that prove the equivalence of actor garbage collection and passive object garbage collection. Two actor marking algorithms are derived from the transformation methods --- the back pointer algorithm and the N-color algorithm. The back pointer algorithm has linear time complexity of O(E+V) and extra space complexity of O(E+V), and the N-color algorithm has time complexity of O(E lg*M) and extra space complexity of O(M), given that E is the number of references, V , the number of actors, and M, the number of unblocked and root actors. The N-color algorithm only requires scanning the reference graph once while the back pointer algorithm requires scanning it twice. The thesis follows by describing our distributed mobile actor garbage collection mechanism. It consists of 1) an asynchronous, non-FIFO reference listing based algorithm which identifies acyclic passive garbage and supports hierarchical garbage collection (local and global garbage collection), 2) a new fault-tolerant, distributed snapshot algorithm which collects cyclic and acyclic garbage in a partial set of computing hosts, and 3) formal models and correctness proofs. Experimental results have confirmed that our approach is practical and scales to over a hundred processors.
|
||||||||||||||||
Research
