【作者】 吴长茂；

【导师】 张聪品；

【作者基本信息】 河南师范大学 ， 计算机软件与理论， 2011， 硕士

【摘要】 随着面向对象语言和程序设计方法的广泛使用,垃圾收集日益受到重视。垃圾收集,即自动内存管理,是指运行时系统负责自动回收无用对象的一种―废料‖回收机制。当代流行语言如Java、C#语言等都具有垃圾收集功能。垃圾收集机制的出现,使程序员只需专注于对象的分配,而无需考虑对象何时被销毁,垃圾对象的回收由垃圾收集器在后台动态地完成而毋须程序员干预。垃圾收集避免了内存泄漏和不正确的内存操作(如悬挂引用)引起的软件错误,提高了软件健壮性。然而,垃圾收集器回收垃圾对象时造成用户程序反应迟缓,一定程度上影响了用户程序效率和用户体验。因此,如何缩短垃圾回收时间,提高垃圾收集器效率,对于提高用户程序执行效率和改善用户体验具有重要的应用价值。近年来,多核CPU和多核GPU日益普及,以及它们并行计算性能的提高,为垃圾收集并行化提供了坚实的硬件基础。在多核系统下,本文基于Lisp 2算法提出了一种新颖的节点复制算法以及该算法的并行化算法,并分别给出了该并行化算法在多核CPU和多核GPU下的一个实现。围绕多核系统下并行节点复制垃圾收集算法研究,本文重点完成了以下工作:(1)深入研究了常用垃圾收集算法。通过查阅大量的垃圾收集文献,对常用垃圾收集算法如引用计数算法、标记-清扫算法、标记-压缩算法、节点复制算法、分代式算法特别是并行垃圾收集算法进行了深入研究,比较了这些算法的优缺点及适用环境。(2)基于Lisp 2算法,提出了一种新颖的节点复制垃圾收集算法-- Lisp 2-Copying-GC-Algorithm。基本思想是把Lisp 2垃圾收集算法在整个内存堆上收集改为在节点复制算法的一个半区(称为FromSpace半区)上进行,把存活对象复制到另一个半区(称为ToSpace半区)。(3)提出了Lisp 2-Copying-GC-Algorithm算法的并行化算法--并行节点复制垃圾收集算法(Lisp 2-Parallel-Copying-GC)。基本思想是把内存堆的两个半区(FromSpace半区和ToSpace半区)划分为大小相同的块(block),为块定义了6个不同状态,这些状态标识了在垃圾收集过程中块(block)的不同地位和作用。这样,块为并行垃圾收集线程提供了一个收集尺度,而块的状态为并行垃圾收集线程间的同步提供了保障。(4)给出了并行节点复制垃圾收集算法(Lisp 2-Parallel-Copying-GC)在多核CPU环境下基于OpenMP3.0规范的一个实现。OpenMP是一种面向共享内存以及分布式共享内存的多处理器(多核)多线程并行编程语言,是一种多线程、共享内存的并行应用程序编程接口。实验数据显示,在4个逻辑核心下该算法加速比达到了2.53,提高了垃圾收集效率。(5)给出了并行节点复制垃圾收集算法(Lisp 2-Parallel-Copying-GC)在多核GPU环境下基于NVIDIA CUDA(Compute Unified Device Architecture)架构的一个实现。CUDA是NVIDIA并行计算架构,通过利用GPU使计算能力大幅提高。本文首次在垃圾收集领域利用CUDA加速进行了有益尝试。实验结果表明,得益于多核GPU数量众多的处理核心和轻量级线程设计,多核GPU相对多核CPU的加速比达到了278.13。多核环境下多线程并行垃圾收集提高了垃圾收集效率,改善了用户体验。更多还原

【Abstract】 As object-oriented languages and programming approach are widely used at present, garbage collection is drawing people’s more attention. Garbage collection which is also called Dynamic Memory Management is a mechanism of deallocating unreachable objects by Runtime System. The prevailing object-oriented languages such as C# and Java all support garbage collection. With garbage collection, programmers only pay attention to allocate memory for objects without taking destroying objects into consideration. The unreachable objects are deallocated automatically by garbage collector without the intervention of programmers, which considerably decreases the burden of programmers. Garbage collection avoids memory leak and errors caused by incorrect memory operations, e.g. dangling reference, improves the robustness of software as well. The performance and efficiency of garbage collector, however, directly affect the program’s executive efficiency and user’s experience. Therefore, improving the efficiency of garbage collector is of great importance in application fields.At the present time, multicore CPU and multicore GPU increasingly prevail, consequently their parallel computing ability sharply rise, all these offer the parallelization of garbage collection a solid basisWith the study on garbage collection, we have mainly accomplished the following works in this paper:1. We have deeply researched on the algorithms of garbage collectionBy means of looking up a large number of papers and treatises about garbage collection, we do many researches on the garbage collection algorithms e.g. Reference-Count algorithm, Mark-Sweep Algorithm, Copying Algorithm as well Generational Algorithm, especially parallel garbage collection algorithm, and compare these methods in the aspects of disadvantages, advantages and applicable surroundings.2. We have presented a novel copying garbage collection algorithm (Lisp 2-Copying-GC-Algorithm) based on Lisp 2 through deallocating unreachable objects on FromSpace and copying live objects to ToSpace.3. By means of dividing heap into equal blocks and defining 6 statuses for blocks, we have presented the parallel algorithm of Lisp 2-Copying-GC-Algorithm, called Lisp 2-Parallel-Copying-GC.4. The implementation of Lisp 2-Parallel-Copying-GC in multicore CPU systemIn multicore CPU system, we have implemented the algorithm of Lisp 2-Parallel-Copying-GC using the OpenMP 3.0 specification. OpenMP is a parallel language for shared memory system and distributed shared memory system, and also is a programming interface for multithread programming. The experimental results show that in multicore CPU system the proposed algorithm is able to improve the garbage collection efficiency in a large scale.5. The implementation of Lisp 2-Parallel-Copying-GC in multicore GPU systemCUDA is NVIDIA’s parallel computing architecture. It enables dramatic increases in computing performance by harnessing the power of the GPU. For the first time we conduct an effective exploration in garbage collection field using GPU system. In multicore GPU system, we have implemented Lisp 2-Parallel-Copying-GC. From the results we can see that the garbage collection efficiency is much improved in multicore GPU system than that in multicore CPU system.From the works above, we realize that with the multicore framework (multicore CPU system and multicore GPU system) prevailing, if garbage collection could employ the strong computing ability in multicore system, the efficiency of garbage collector will be largely improved so that the user’s experience will be better.更多还原