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

1、RESEARCHONALGORITHMOFPARALLELCOPYINGGARBAGECoLLECTIoNBASEDONLISP2FORMUI』rICORESYSTEMADissertationSubmittedtotheGraduateSchoolofHenanNormalUniversityinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofEngineeringSc

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

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

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

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