[發(fā)明專利]用于垃圾回收的并行標(biāo)記處理方法及裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201610187840.2
• 申請(qǐng)日: 2016-03-29
• 公開(kāi)（公告）號(hào): CN107239406B
• 公開(kāi)（公告）日: 2021-03-09
• 發(fā)明（設(shè)計(jì)）人: 吳哲鋒;楊江華
• 申請(qǐng)（專利權(quán)）人: 斑馬智行網(wǎng)絡(luò)(香港)有限公司
• 主分類號(hào): G06F12/02
• 分類號(hào): G06F12/02
• 代理公司: 上海知錦知識(shí)產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 31327
• 代理人: 段潔汝

本申請(qǐng)?zhí)岢鲆环N用于垃圾回收的標(biāo)記方法及裝置，通過(guò)根據(jù)虛擬機(jī)堆中的內(nèi)存塊與N個(gè)標(biāo)記線程的對(duì)應(yīng)關(guān)系，遍歷所述虛擬機(jī)堆中的第一對(duì)象，其中，N為大于1的整數(shù)，N個(gè)標(biāo)記線程占用的內(nèi)存容量是預(yù)先設(shè)置的，每個(gè)標(biāo)記線程至少包括：1個(gè)私有棧；將當(dāng)前處理的第一對(duì)象的第一指針壓入與該第一對(duì)象所在的內(nèi)存塊對(duì)應(yīng)的標(biāo)記線程的私有棧，根據(jù)所述第一指針的壓入情況對(duì)所述第一對(duì)象進(jìn)行第一標(biāo)記處理；對(duì)所述第一對(duì)象遍歷完成后，向所述N個(gè)標(biāo)記線程發(fā)送線程啟動(dòng)指令，以使所述N個(gè)標(biāo)記線程根據(jù)各自私有棧中所述第一指針的壓入情況，同步進(jìn)行用于垃圾回收的標(biāo)記處理。由此，利用有限的內(nèi)存實(shí)現(xiàn)多線程的并行標(biāo)記處理，提高整個(gè)垃圾回收的性能。

技術(shù)領(lǐng)域

本申請(qǐng)涉及計(jì)算機(jī)技術(shù)領(lǐng)域，尤其涉及一種用于垃圾回收的并行標(biāo)記處理方法及裝置。

背景技術(shù)

垃圾回收(即Garbage Collection簡(jiǎn)稱GC)技術(shù)被廣泛使用在當(dāng)今流行的許多高級(jí)語(yǔ)言虛擬機(jī)中。GC技術(shù)根據(jù)垃圾收集器(簡(jiǎn)稱Collector)和宿主(簡(jiǎn)稱Mutator)的關(guān)系可以分為兩種：Collector工作時(shí)Mutator暫停(簡(jiǎn)稱Stop-The-World-GC即STW-GC)，Collector工作時(shí)Mutator不暫停(簡(jiǎn)稱并發(fā)GC即Concurrent-GC)。目前完全并發(fā)GC還沒(méi)有哪一款虛擬機(jī)真正實(shí)現(xiàn)，流行的高級(jí)語(yǔ)言虛擬機(jī)比如JVM，V8等都是STW-GC或者部分Concurrent-GC。非引用計(jì)數(shù)的STW-GC方案可以分為3種，即標(biāo)記-拷貝(簡(jiǎn)稱marking-copy)，標(biāo)記-清理(簡(jiǎn)稱marking-sweep)，和標(biāo)記-壓縮(簡(jiǎn)稱marking-compact)。

目前流行的高級(jí)語(yǔ)言虛擬機(jī)產(chǎn)品比如JVM，V8等的內(nèi)存都是通過(guò)堆(heap)來(lái)進(jìn)行統(tǒng)一管理，堆以指定大小的內(nèi)存塊(簡(jiǎn)稱為一個(gè)page，一般為操作系統(tǒng)的內(nèi)存頁(yè)大小的整數(shù)倍)為基本單位進(jìn)行組織。比如V8虛擬機(jī)的page大小為1MByte。而且在每一個(gè)內(nèi)存塊(即page)的起始部分劃分出一塊位圖區(qū)域(稱為bitmap)用來(lái)標(biāo)記所在的page中每一個(gè)對(duì)象是否是活躍對(duì)象。比如某個(gè)page中的某個(gè)對(duì)象對(duì)應(yīng)在該page頭部的bitmap位被置為1，則說(shuō)明該對(duì)象是活躍對(duì)象，進(jìn)行GC時(shí)候不應(yīng)該進(jìn)行回收。

當(dāng)前用于垃圾回收的標(biāo)記方法為單線程的標(biāo)記方式，根據(jù)標(biāo)記對(duì)象的不斷增加，所占用的內(nèi)存空間會(huì)不斷增大，由此可見(jiàn)，目前的單線程標(biāo)記方式浪費(fèi)了大量的內(nèi)存空間，降低了處理性能和效率。

發(fā)明內(nèi)容

本申請(qǐng)旨在至少在一定程度上解決相關(guān)技術(shù)中的技術(shù)問(wèn)題之一。

為此，本申請(qǐng)的第一個(gè)目的在于提出一種用于垃圾回收的并行標(biāo)記處理方法，該方法利用有限的內(nèi)存實(shí)現(xiàn)多線程的并行標(biāo)記處理，提高整個(gè)垃圾回收的性能。

本申請(qǐng)的第二個(gè)目的在于提出一種用于垃圾回收的并行標(biāo)記處理方法。

本申請(qǐng)的第三個(gè)目的在于提出一種用于垃圾回收的并行標(biāo)記處理裝置。

本申請(qǐng)的第四個(gè)目的在于提出一種用于垃圾回收的并行標(biāo)記處理裝置。

為達(dá)上述目的，本申請(qǐng)第一方面實(shí)施例提出了一種用于垃圾回收的并行標(biāo)記處理方法，包括：根據(jù)虛擬機(jī)堆中的內(nèi)存塊與N個(gè)標(biāo)記線程的對(duì)應(yīng)關(guān)系，遍歷所述虛擬機(jī)堆中的第一對(duì)象，其中，N為大于1的整數(shù)，N個(gè)標(biāo)記線程占用的內(nèi)存容量是預(yù)先設(shè)置的，每個(gè)標(biāo)記線程至少包括：1個(gè)私有棧；將當(dāng)前處理的第一對(duì)象的第一指針壓入與該第一對(duì)象所在的內(nèi)存塊對(duì)應(yīng)的標(biāo)記線程的私有棧，根據(jù)所述第一指針的壓入情況對(duì)所述第一對(duì)象進(jìn)行第一標(biāo)記處理；對(duì)所述第一對(duì)象遍歷完成后，向所述N個(gè)標(biāo)記線程發(fā)送線程啟動(dòng)指令，以使所述N個(gè)標(biāo)記線程根據(jù)各自私有棧中所述第一指針的壓入情況，同步進(jìn)行用于垃圾回收的標(biāo)記處理。