Complementary Garbage Collector

. This paper describes the design and the evaluation of Complementary Garbage Collector that is a fundamental algorithm for the parallel and incremental garbage collector. Our algorithm is a combination of two types of fundamental algorithms, incremental update and snapshot-at-beginning, which are complementary to each other. The algorithm has the advantages of both types: great efficiency of the garbage collection and ease of consistent implementation. This algorithm can be substituted for the snapshot-at-beginning algorithm widely used in several types of parallel and incremental garbage collectors. Measurements of this algorithm in a parallel and an incremental mark-sweep GC indicate that it improves the efficiency of the collection making it equivalent to the stop garbage collector. Consequently, the execution time of the list processing is shortened and the range of non-stop processing is extended. Keywords: real-time garbage collection, parallel garbage collection, incremental ..