多核系統(tǒng)下并行節(jié)點復制垃圾收集算法研究.pdf

1、RESEARCHONALGORITHMOFPARALLELCOPYINGGARBAGECoLLECTIoNBASEDONLISP2FORMUI』rICORESYSTEMADissertationSubmittedtotheGraduateSchoolofHenanNormalUniversityinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofEngineeringSc

2、ienceByWuChangmaoSupervisor：ProfZhangCongpinMay2011摘要隨著面向對象語言和程序設計方法的廣泛使用，垃圾收集日益受到重視。垃圾收集，即自動內存管理，是指運行時系統(tǒng)負責自動回收無用對象的一種“廢料”回收機制。當代流行語言如Java、C撐語言等都具有垃圾收集功能。垃圾收集機制的出現，使程序員只需專注于對象的分配，而無需考慮對象何時被銷毀，垃圾對象的回收由垃圾收集器在后臺動態(tài)地完成而毋須程序員干

3、預。垃圾收集避免了內存泄漏和不正確的內存操作(如懸掛引用)引起的軟件錯誤，提高了軟件健壯性。然而，垃圾收集器回收垃圾對象時造成用戶程序反應遲緩，一定程度上影響了用戶程序效率和用戶體驗。因此，如何縮短垃圾回收時間，提高垃圾收集器效率，對于提高用戶程序執(zhí)行效率和改善用戶體驗具有重要的應用價值。近年來，多核CPU和多核GPU日益普及，以及它們并行計算性能的提高，為垃圾收集并行化提供了堅實的硬件基礎。在多核系統(tǒng)下，本文基于Lisp2算法提出了一

4、種新穎的節(jié)點復制算法以及該算法的并行化算法，并分別給出了該并行化算法在多核CPU和多核GPU下的一個實現。圍繞多核系統(tǒng)下并行節(jié)點復制垃圾收集算法研究，本文重點完成了以下工作：(1)深入研究了常用垃圾收集算法。通過查閱大量的垃圾收集文獻，對常用垃圾收集算法如引用計數算法、標記清掃算法、標記一壓縮算法、節(jié)點復制算法、分代式算法特別是并行垃圾收集算法進行了深入研究，比較了這些算法的優(yōu)缺點及適用環(huán)境。(2)基于Lisp2算法，提出了一種新穎的節(jié)

5、點復制垃圾收集算法一Lisp2CopyingGCAlgorithm。基本思想是把Lisp2垃圾收集算法在整個內存堆上收集改為在節(jié)點復制算法的一個半區(qū)(稱為FromSpace半區(qū))上進行，把存活對象復制到另一個半區(qū)(稱為ToSpace半區(qū))。(3)提出了Lisp2Copying—GCAlgorithm算法的并行化算法一并行節(jié)點復制垃圾收集算法(Lisp2Parallel—Copying—GC)。基本思想是把內存堆的兩個半區(qū)(FromSpa