A multithreaded concurrent generational garbage collector for Java

The recent popularity of the Java programming language has brought automatic dynamic memory management (a.k.a., garbage collection) into the mainstream. However, it has been a performance bottleneck of Java systems. In this thesis, we survey and analyze the existing garbage collection algorithms in terms of algorithms themselves and system related performance. After a thorough investigation, a new approach on analyzing generalized buddy systems, a new page replacement policy, mLRU, and a new multithreaded concurrent generational garbage collection algorithm are proposed. By applying a boundary analysis on generalized buddy systems, their properties such as blind spots can be formally defined. Some solutions to them are studied and simulation results are reported. Because of its special characteristics, the garbage collection heap may be applied a different page replacement policy. For the paging system, we find that the new mLRU policy outperforms LRU by 68%. Lastly, a new multithreaded concurrent generational garbage collector (MCGC) based on mark-sweep with the assistance of reference counting is presented. The proposed scheme can take advantage of multiple CPUs in an symmetric multiprocessor system and the merits of light-weight processes. Furthermore, the long garbage collection pause can be reduced and the garbage collection efficiency can be enhanced. We have implemented our scheme as part of the Kaffe JVM. Measurement results indicate that the MCGC yields a less garbage collection pause time and the speedup can be up to 96% over the traditional stop-the-world mark-sweep garbage collector. Moreover, the MCGC incurs minimal time and space penalties as shown in the report of the total execution time, the memory footprint and the sticky reference count rate.