Garbage Collection Algorithm for Ubiquitous Real-Time System

Abstract

Most parallel garbage collection algorithms are based on the mark-and-collect technique. A mark-and-collect technique an effective asynchronous marking algorithm. There are two basic marking techniques: coloring and stacking. The coloring technique is asynchronous but its time complexity is O(MN) where M and N are the total number of nodes in the list memory and the total number of active nodes, respectively. The stacking technique offers effective marking process having only O(N) time complexity but requires extra stack space which can be as large as the size of entire active nodes(N). A new parallel garbage collection algorithm in ubiquitous environment has been devised which takes advantage of the asynchronous processing of coloring algorithms and the time efficiency of stacking algorithms. The algorithm requires no synchronization between the collectors and the mutators. and its tome complexity is close to O(N) with a small fixed-size stack in ubiquitous real-time system.