Research On Key Technologies Of Garbage Collection For Multicore System

During the last decades, on the one hand multi-core technology has become an important development trend of the hardware architecture at present, and the technology can provide an effective means for improving the performance of the modern computer. On the other hand, as the size and complexity of software design become much larger than ever before, better performance and scalability are required to the programming language runtime environment. The runtime environment plays an important role to exploit hardware parallelism and coordinate tasks of the operating system, it provides efficient resource management and scheduling for applications. In other words runtime environment has an important position in modern hardware and software architecture. Garbage collector is the main performance bottleneck in runtime environment which plays an important role in memory management, thus the design of garbage collector for multi-core and multi-threaded faces many challenges. Garbage collector is the most difficult component to be parallel and concurrent in runtime environment, and any small modifications may affect the correctness of the collector. In this paper, a study of parallel and concurrent garbage collection for multi-core and multi-threaded environment is presented. The study focuses on two aspects, that is, research on efficient parallel and concurrent collector, and data access locality optimization in garbage collector. A series of design strategies and optimizations for garbage collection are proposed based on the prior related work, which includes the design of high precision tracing for concurrent garbage collection, lock-free synchronization mechanism, cache prefetch in parallel tracing GC and heap fragments elimination and compaction. The main work and contributions of this paper include:A high precision concurrent tracing garbage collector based on tracing reference count is proposed. By using the tracing records and reference count in tracing process, most of the modifications by the application thread are monitored. In order to avoid live object lost problem, barrier mechanism are designed to perform store protection or deletion protection. In this paper, the approach can effectively track the modifications of the object references, and reduce the number of objects in the process of rescanning process, while effectively decrease the number of floating garbage during the concurrent collection.A lock-free synchronization mechanism for concurrent garbage collection is proposed in this thesis. In order to overcome the traditional lock-based synchronization system defect, we design a hardware-based CAS primitive for lock-free synchronization strategy. The proposed strategy supports multi-core and multi-threaded environment with arbitrary number of memory words synchronization in lock-free manner, and effective avoids lock contention due to serialization as well as improves the concurrent execution performance. On this basis, we present a new object structure model which supports multi-word CAS synchronization. Concurrent object copying mechanism in concurrent garbage collector will be better supported by this extended object structure. Experimental results show that the design has good concurrent access performance and scalability.In order to improve the data locality and collection performance, cache prefetching method is proposed to optimize the parallel tracing collectors. We perform a comprehensive measurement and analyze the performance bottleneck of the tracing GC. We implement software cache prefetching in the existing hardware and software platform to support parallel object trace and data load. By controlling the prefetch queue and combining the schedule mechanism of parallel tracing GC, most of the useless prefetch requests are avoided. The proposed strategy reduces the influence of memory band races and cache pollutions.We propose a heap compaction mechanism based on semi-space copying collection to eliminate heap fragments. By analyzing the reasons for fragmentation and performance impact on the runtime environment, we propose a partial heap compaction strategy on multi-core and multi-thread environment. The strategy optimizes the computation of reserved space in the compaction process, and the effect of the live object ratios is fully considered. And on this basis, a two-phased compaction method is proposed to solve the problem of reserved space exhaustion in the compaction process, the compaction can be completed with less heap consumption in comparison with the previous methods. The evaluation results show that our solution can reduce the reserved space consumption and improve the heap utilization. The triggered collection times are also decreased by heap fragments elimination.