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

1、RESEARCHONALGORITHMOFPARALLELCOPYINGGARBAGECoLLECTIoNBASEDONLISP2FORMUI』rICORESYSTEMADissertationSubmittedtotheGraduateSchoolofHenanNormalUniversityinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofEngineeringSc

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

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

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

5、點復(fù)制垃圾收集算法一Lisp2CopyingGCAlgorithm。基本思想是把Lisp2垃圾收集算法在整個內(nèi)存堆上收集改為在節(jié)點復(fù)制算法的一個半?yún)^(qū)(稱為FromSpace半?yún)^(qū))上進(jìn)行，把存活對象復(fù)制到另一個半?yún)^(qū)(稱為ToSpace半?yún)^(qū))。(3)提出了Lisp2Copying—GCAlgorithm算法的并行化算法一并行節(jié)點復(fù)制垃圾收集算法(Lisp2Parallel—Copying—GC)?；舅枷胧前褍?nèi)存堆的兩個半?yún)^(qū)(FromSpa