用於垃圾回收的並行標記處理方法及裝置與流程

2023-08-11 15:06:46

本申請涉及計算機技術領域，尤其涉及一種用於垃圾回收的並行標記處理方法及裝置。

背景技術：

垃圾回收(即garbagecollection簡稱gc)技術被廣泛使用在當今流行的許多高級語言虛擬機中。gc技術根據垃圾收集器(簡稱collector)和宿主(簡稱mutator)的關係可以分為兩種：collector工作時mutator暫停(簡稱stop-the-world-gc即stw-gc)，collector工作時mutator不暫停(簡稱並發gc即concurrent-gc)。目前完全並發gc還沒有哪一款虛擬機真正實現，流行的高級語言虛擬機比如jvm，v8等都是stw-gc或者部分concurrent-gc。非引用計數的stw-gc方案可以分為3種，即標記-拷貝(簡稱marking-copy)，標記-清理(簡稱marking-sweep)，和標記-壓縮(簡稱marking-compact)。

目前流行的高級語言虛擬機產品比如jvm，v8等的內存都是通過堆(heap)來進行統一管理，堆以指定大小的內存塊(簡稱為一個page，一般為作業系統的內存頁大小的整數倍)為基本單位進行組織。比如v8虛擬機的page大小為1mbyte。而且在每一個內存塊(即page)的起始部分劃分出一塊位圖區域(稱為bitmap)用來標記所在的page中每一個對象是否是活躍對象。比如某個page中的某個對象對應在該page頭部的bitmap位被置為1，則說明該對象是活躍對象，進行gc時候不應該進行回收。

當前用於垃圾回收的標記方法為單線程的標記方式，根據標記對象的不斷增加，所佔用的內存空間會不斷增大，由此可見，目前的單線程標記方式浪費了大量的內存空間，降低了處理性能和效率。

技術實現要素：

本申請旨在至少在一定程度上解決相關技術中的技術問題之一。

為此，本申請的第一個目的在於提出一種用於垃圾回收的並行標記處理方法，該方法利用有限的內存實現多線程的並行標記處理，提高整個垃圾回收的性能。

本申請的第二個目的在於提出一種用於垃圾回收的並行標記處理方法。

本申請的第三個目的在於提出一種用於垃圾回收的並行標記處理裝置。

本申請的第四個目的在於提出一種用於垃圾回收的並行標記處理裝置。

為達上述目的，本申請第一方面實施例提出了一種用於垃圾回收的並行標記處理方法，包括：根據虛擬機堆中的內存塊與n個標記線程的對應關係，遍歷所述虛擬機堆中的第一對象，其中，n為大於1的整數，n個標記線程佔用的內存容量是預先設置的，每個標記線程至少包括：1個私有棧；將當前處理的第一對象的第一指針壓入與該第一對象所在的內存塊對應的標記線程的私有棧，根據所述第一指針的壓入情況對所述第一對象進行第一標記處理；對所述第一對象遍歷完成後，向所述n個標記線程發送線程啟動指令，以使所述n個標記線程根據各自私有棧中所述第一指針的壓入情況，同步進行用於垃圾回收的標記處理。

本申請實施例的用於垃圾回收的並行標記處理方法，通過根據虛擬機堆中的內存塊與n個標記線程的對應關係，遍歷所述虛擬機堆中的第一對象，其中，n個標記線程佔用的內存容量是預先設置的，將當前處理的第一對象的第一指針壓入與該第一對象所在的內存塊對應的標記線程的私有棧，根據所述第一指針的壓入情況對所述第一對象進行第一標記處理，對所述第一對象遍歷完成後，向所述n個標記線程發送線程啟動指令，以使所述n個標記線程根據各自私有棧中所述第一指針的壓入情況，同步進行用於垃圾回收的標記處理。由此，利用有限的內存實現多線程的並行標記處理，提高整個垃圾回收的性能。

為達上述目的，本申請第二方面實施例提出了一種用於垃圾回收的並行標記處理方法，包括：預設的n個標記線程中的每個標記線程至少包括：1個私有棧，所述方法應用在每個標記線程中，其中，應用在第一標記線程中的所述方法包括以下步驟：第一標記線程根據線程啟動指令，從第一私有棧中取出預先壓入的第一對象的第一指針；所述第一標記線程遍歷所述第一指針指示的所述第一對象引用的第二對象，並根據預設的n個標記線程與虛擬機堆中內存塊的對應關係對所述第二對象進行第二標記處理。

本申請實施例的用於垃圾回收的並行標記處理方法，通過第一標記線程根據線程啟動指令，從第一私有棧中取出預先壓入的第一對象的第一指針，遍歷所述第一指針指示的所述第一對象引用的第二對象，並根據預設的n個標記線程與虛擬機堆中內存塊的對應關係對所述第二對象進行第二標記處理。由此，參照第一標記線程的標記處理過程，通過n個標記線程的並行標記處理，實現了利用有限的內存進行並行標記處理，提高整個垃圾回收的性能。

為達上述目的，本申請第三方面實施例提出了一種用於垃圾回收的並行標記處理裝置，包括：遍歷模塊，用於根據虛擬機堆中的內存塊與n個標記線程的對應關係，遍歷所述虛 擬機堆中的第一對象，其中，n為大於1的整數，n個標記線程佔用的內存容量是預先設置的，每個標記線程至少包括：1個私有棧；第一標記模塊，用於將當前處理的第一對象的第一指針壓入與該第一對象所在的內存塊對應的標記線程的私有棧，根據所述第一指針的壓入情況對所述第一對象進行第一標記處理；啟動模塊，用於對所述第一對象遍歷完成後，向所述n個標記線程發送線程啟動指令，以使所述n個標記線程根據各自私有棧中所述第一指針的壓入情況，同步進行用於垃圾回收的標記處理。

本申請實施例的用於垃圾回收的並行標記處理裝置，通過根據虛擬機堆中的內存塊與n個標記線程的對應關係，遍歷所述虛擬機堆中的第一對象，其中，n個標記線程佔用的內存容量是預先設置的，將當前處理的第一對象的第一指針壓入與該第一對象所在的內存塊對應的標記線程的私有棧，根據所述第一指針的壓入情況對所述第一對象進行第一標記處理，對所述第一對象遍歷完成後，向所述n個標記線程發送線程啟動指令，以使所述n個標記線程根據各自私有棧中所述第一指針的壓入情況，同步進行用於垃圾回收的標記處理。由此，利用有限的內存實現多線程的並行標記處理，提高整個垃圾回收的性能。

為達上述目的，本申請第四方面實施例提出了一種用於垃圾回收的並行標記處理裝置，包括：預設的n個標記線程中的每個標記線程至少包括：1個私有棧，所述裝置應用在每個標記線程中，其中，應用在第一標記線程中的所述裝置包括：獲取模塊，用於根據線程啟動指令，從第一私有棧中取出預先壓入的第一對象的第一指針；第二標記模塊，用於遍歷所述第一指針指示的所述第一對象引用的第二對象，並根據預設的n個標記線程與虛擬機堆中內存塊的對應關係對所述第二對象進行第二標記處理。

本申請實施例的用於垃圾回收的並行標記處理裝置，通過第一標記線程根據線程啟動指令，從第一私有棧中取出預先壓入的第一對象的第一指針，遍歷所述第一指針指示的所述第一對象引用的第二對象，並根據預設的n個標記線程與虛擬機堆中內存塊的對應關係對所述第二對象進行第二標記處理。由此，參照第一標記線程的標記處理過程，通過n個標記線程的並行標記處理，實現了利用有限的內存進行並行標記處理，提高整個垃圾回收的性能。

附圖說明

本發明上述的和/或附加的方面和優點從下面結合附圖對實施例的描述中將變得明顯和容易理解，其中：

圖1是本申請一個實施例的用於垃圾回收的並行標記處理方法的流程圖；

圖2是本申請另一個實施例的用於垃圾回收的並行標記處理方法的流程圖；

圖3為用於垃圾回收的第一標記處理流程示意圖；

圖4為預先申請的n個標記線程的示意圖；

圖5是應用圖4所示的標記線程並行標記處理的流程圖一；

圖6是應用圖4所示的標記線程並行標記處理的流程圖二；

圖7是應用圖4所示的標記線程並行標記處理的流程圖三；

圖8是應用圖4所示的標記線程並行標記處理的流程圖四；

圖9是應用圖4所示的標記線程並行標記處理的流程圖五；

圖10是應用圖4所示的標記線程並行標記處理的流程圖六；

圖11是本申請一個實施例的用於垃圾回收的並行標記處理裝置的結構示意圖；

圖12是本申請另一個實施例的用於垃圾回收的並行標記處理裝置的結構示意圖；

圖13是本申請另一個實施例的用於垃圾回收的並行標記處理裝置的結構示意圖；

圖14是本申請另一個實施例的用於垃圾回收的並行標記處理裝置的結構示意圖；

圖15是本申請另一個實施例的用於垃圾回收的並行標記處理裝置的結構示意圖；

圖16是本申請另一個實施例的用於垃圾回收的並行標記處理裝置的結構示意圖；

圖17是本申請另一個實施例的用於垃圾回收的並行標記處理裝置的結構示意圖。

具體實施方式

下面詳細描述本申請的實施例，所述實施例的示例在附圖中示出，其中自始至終相同或類似的標號表示相同或類似的元件或具有相同或類似功能的元件。下面通過參考附圖描述的實施例是示例性的，旨在用於解釋本申請，而不能理解為對本申請的限制。

下面參考附圖描述本申請實施例的用於垃圾回收的並行標記處理方法及裝置。

圖1是本申請一個實施例的用於垃圾回收的並行標記處理方法的流程圖。

如圖1所示，該用於垃圾回收的並行標記處理方法包括：

步驟101，根據虛擬機堆中的內存塊與n個標記線程的對應關係，遍歷所述虛擬機堆中的第一對象，其中，n為大於1的整數，n個標記線程佔用的內存容量是預先設置的，每個標記線程至少包括：1個私有棧。

具體地，為了提高用於垃圾回收的標記處理效率，本發明各實施例提供的處理方法利用了多核cpu的並行處理能力，預先申請n個標記線程，其中，每個標記線程至少包括：1個私有棧，私有棧用於存儲本線程負責標記的對象的指針。

需要說明的是，n為大於1的整數，根據實際應用的cpu的並行處理能力而定。例如：

如果cpu的並行處理能力為雙核，可以申請2個容量限定的標記線程；或，

如果cpu的並行處理能力為四核，可以申請4個容量限定的標記線程；或，

如果cpu的並行處理能力為八核，可以申請8個容量限定的標記線程。

需要注意的是，以上僅為舉例說明，可以根據實際應用需要進行設置和調整。

需要強調的是，隨著標記對象的增加，現有的標記處理技術需要不斷的增加標記線程的內存佔用量，降低了標記處理的性能和效率。因此，本發明提供的並行標記處理方法，預先對n個標記線程佔用的內存容量進行設置，也就是會所，n個標記線程佔用的內存容量不會隨著標記對象的溢出而增加，以便保證標記處理的性能和效率。

需要說明的是，可以根據應用需要採用多種方式對n個標記線程佔用的內存容量進行設置，例如：

示例一，對每個標記線程的容量進行設置；

示例二，對n個標記線程佔用的內存總容量進行設置，每個標記線程可以不限定，或者，比如限定最大的一個等。

為了提高標記效率，實現多線程並行標記的負載均衡，預先建立虛擬機堆中的內存塊與n標記線程的對應關係。也就是說，預先為每個標記線程配置好對應負責標記的虛擬機堆中的內存塊。

需要注意的是，可以根據實際應用需要建立虛擬機堆中內存塊與n個標記線程的對應關係，例如包括：

示例一：為每個內存塊指定對應的標記線程；或者，

示例二：為每個標記線程指定負責標記的內存塊。

進而，從虛擬機系統中獲取預先存儲的虛擬機堆中所有的第一對象，根據上述設置的虛擬機堆中的內存塊與n個標記線程的對應關係，遍歷虛擬機堆中的第一對象。

步驟102，將當前處理的第一對象的第一指針壓入與該第一對象所在的內存塊對應的標記線程的私有棧，根據所述第一指針的壓入情況對所述第一對象進行第一標記處理。

步驟103，對所述第一對象遍歷完成後，向所述n個標記線程發送線程啟動指令，以使所述n個標記線程根據各自私有棧中所述第一指針的壓入情況，同步進行用於垃圾回收的標記處理。

具體地，首先確定當前處理的第一對象所在的內存塊，然後根據上述的對應關係獲取與該第一對象所在的內存塊對應的標記線程。將該第一對象的第一指針壓入到與該第一對象所在的內存塊對應的標記線程的私有棧中。

進而，根據該第一對象的第一指針的壓入情況，對當前處理的第一對象進行第一標記處理。也就是說，如果將當前第一對象的第一指針成功壓入到對應標記線程的私有棧中， 則確定該私有棧沒有溢出，將當前處理的第一對象標記為壓入狀態；如果沒有將當前第一對象的第一指針成功壓入到對應標記線程的私有棧中，則確定該私有棧溢出，將當前處理的第一對象標記為溢出狀態。

需要說明的是，對第一對象是否溢出的標記方式有很多，可以根據需要進行選擇，例如：

示例一，可以通過列表的方式記錄與每個標記線程的私有棧對應的第一對象的壓入情況；或者，

示例二，可以通過第一對象所在內存塊位圖中的相應位置標記第一對象的壓入情況。

需要說明的是，以上僅為舉例說明，可以根據實際應用需要進行選擇標記方式。

對虛擬機堆中的第一對象遍歷完成後，各個標記線程的私有棧中都存放了本線程負責標記的內存塊中第一對象的第一指針。如果標記線程的私有棧中溢出，說明私有棧的空間已滿，無法繼續存放本線程負責標記的內存塊中第一對象的第一指針，則將這些第一對象標記為溢出狀態。當標記線程的私有棧中有新的處理空間時，繼續存放本線程負責標記的內存塊中第一對象的第一指針。

進而，向n個標記線程發送線程啟動指令，從而n個標記線程根據各自私有棧中第一指針的壓入情況，同步進行用於垃圾回收的標記處理。

本申請實施例的用於垃圾回收的並行標記處理方法，通過根據虛擬機堆中的內存塊與n個標記線程的對應關係，遍歷所述虛擬機堆中的第一對象，其中，n個標記線程佔用的內存容量是預先設置的，將當前處理的第一對象的第一指針壓入與該第一對象所在的內存塊對應的標記線程的私有棧，根據所述第一指針的壓入情況對所述第一對象進行第一標記處理，對所述第一對象遍歷完成後，向所述n個標記線程發送線程啟動指令，以使所述n個標記線程根據各自私有棧中所述第一指針的壓入情況，同步進行用於垃圾回收的標記處理。由此，利用有限的內存實現多線程的並行標記處理，提高整個垃圾回收的性能。

為了更加清楚的說明上述實施例中虛擬機堆中所有內存塊與n個標記線程的對應關係的建立過程，以及第一標記過程，通過圖2所示實施例進行說明。

圖2是本申請另一個實施例的用於垃圾回收的並行標記處理方法的流程圖。

如圖2所示，該用於垃圾回收的並行標記處理方法可以包括以下步驟：

步驟201，申請n個標記線程，其中，n為大於1的整數，n個標記線程佔用的內存容量是預先設置的，每個標記線程至少包括：1個私有棧。

具體地，根據實際應用需要和cpu的多核處理能力，設置標記線程的數量n，以及設置n個標記線程所佔的內存容量。其中，每個標記線程包括一個私有棧，私有棧用於存儲 本線程負責標記的對象的指針。

步驟202，遍歷虛擬機堆的所有內存塊，為每個內存塊分配編號；

步驟203，根據內存塊編號和標記線程總數n，確定與每個內存塊編號對應的標記線程編號。

具體地，為了向虛擬機堆的每個內存塊分配負責標記內存塊對象的標記線程，遍歷虛擬機堆的內存塊，為每個內存塊分配編號。

進而，根據內存塊編號和標記線程總數n，確定與每個內存塊編號對應的標記線程編號。

需要說明的是，根據內存塊編號和標記線程總數n，確定與每個內存塊編號對應的標記線程編號的方式有很多，例如：可以通過獲取標記線程總數n被內存塊編號整除後的餘數，確定與每個內存塊編號對應的標記線程編號，公式表達如下所示：

id＝id％n，其中，

n為標記線程總數；id為內存塊編號；id為標記線程編號；「％」表示n被id整除後的取餘處理。

例如：假設當前申請的標記線程總數n＝4，編號分別為0-3，內存塊為十個，編號分別為1-10，通過上述公式處理後獲知：

內存塊編號1對應的標記線程編號為0；

內存塊編號2對應的標記線程編號為1；

內存塊編號3對應的標記線程編號為2；

內存塊編號4對應的標記線程編號為3；

內存塊編號5對應的標記線程編號為0；

內存塊編號6對應的標記線程編號為1；

內存塊編號7對應的標記線程編號為2；

內存塊編號8對應的標記線程編號為3；

內存塊編號9對應的標記線程編號為1；

內存塊編號10對應的標記線程編號為2。

步驟204，根據虛擬機堆中的內存塊與n個標記線程的對應關係，遍歷所述虛擬機堆中的第一對象，將當前處理的第一對象的第一指針壓入與該第一對象所在的內存塊對應的標記線程的私有棧；

步驟205，判斷是否將當前第一對象的第一指針成功壓入對應標記線程的私有棧中；

步驟206，如果將所述第一指針成功壓入對應標記線程的私有棧，則將當前第一對象 所在內存塊的位圖中、與該第一對象對應的狀態標記為壓入狀態；

步驟207，如果未能將所述第一指針成功壓入對應標記線程的私有棧，則將當前第一對象所在內存塊的位圖中、與該第一對象對應的狀態標記為溢出狀態。

步驟208，對所述第一對象遍歷完成後，向所述n個標記線程發送線程啟動指令，以使所述n個標記線程根據各自私有棧中所述第一指針的壓入情況，同步進行用於垃圾回收的標記處理。

具體地，確定當前處理的第一對象所在的內存塊，然後根據上述的對應關係獲取與該第一對象所在的內存塊對應的標記線程。將該第一對象的第一指針壓入到與該第一對象所在的內存塊對應的標記線程的私有棧中。

進而，根據該第一對象的第一指針的壓入情況，對當前處理的第一對象進行第一標記處理。也就是說，如果將當前第一對象的第一指針成功壓入到對應標記線程的私有棧中，則確定該私有棧沒有溢出，將當前處理的第一對象標記為壓入狀態；如果沒有將當前第一對象的第一指針成功壓入到對應標記線程的私有棧中，則確定該私有棧溢出，將當前處理的第一對象標記為溢出狀態。

對所述第一對象遍歷完成後，各個標記線程的私有棧中都存放了本線程負責標記的內存塊中第一對象的第一指針。如果標記線程的私有棧中溢出，說明私有棧的空間已滿，無法繼續存放本線程負責標記的內存塊中第一對象的第一指針，則將這些第一對象標記為溢出狀態。當標記線程的私有棧中有新的處理空間時，繼續存放本線程負責標記的內存塊中第一對象的第一指針。

進而，向n個標記線程發送線程啟動指令，從而n個標記線程根據各自私有棧中第一指針的壓入情況，同步進行用於垃圾回收的標記處理。

為了更加清楚的說明上述實施例中涉及的對第一對象進行第一標記處理的處理過程，通過圖3所示實施例說明如下。

圖3為用於垃圾回收的第一標記處理流程示意圖。

參見圖3，本實施例中採用在內存塊位圖中進行著色標記的方式對第一對象的壓入情況進行第一標記處理，具體標記如下：

如果將當前處理的第一對象的第一指針成功壓入對應標記線程的私有棧中，則將與該第一對象所在內存塊位圖中的對應位置進行標黑處理；

如果沒有將當前處理的第一對象的第一指針成功壓入對應標記線程的私有棧中，則將與該第一對象所在內存塊位圖中的對應位置進行標灰處理。

需要說明的是，以上根據第一對象的第一指針向對應標記線程的私有棧的不同壓入情 況，在內存塊位圖中與第一對象的對應位置進行的著色處理僅僅是示例性說明，可以根據具體的應用需要進行調整。

基於上述標記方式，具體以處理虛擬堆中的根對象a(本示例中虛擬堆中的根對象相當於上述實施例中涉及的第一對象)為例說明如下：

步驟10：申請n個標記線程，其中，n為大於1的整數，n個標記線程佔用的內存容量是預先設置的，每個標記線程至少包括：1個私有棧。

步驟20：建立虛擬機堆中的內存塊與n個標記線程的對應關係。

步驟30：遍歷虛擬機堆中的根對象，如果遍歷完畢，則退出，否則執行步驟40。

步驟40：將當前處理的根對象a的第一指針壓入與a所在的內存塊10對應的標記線程1的私有棧1中。

步驟50：判斷是否將a的第一指針成功壓入標記線程1的私有棧1中；

步驟60：如果將a的第一指針成功壓入標記線程1的私有棧1中，則將內存塊10的位圖中、與a對應的位置標黑，即a為壓入狀態。

步驟70：如果沒有將a的第一指針成功壓入標記線程1的私有棧1中，則將內存塊10的位圖中、與a對應的位置標灰，即a為溢出狀態。

本申請實施例的用於垃圾回收的並行標記處理方法，通過申請n個標記線程，遍歷虛擬機堆的所有內存塊，為每個內存塊分配編號；根據內存塊編號和標記線程總數n，確定與每個內存塊編號對應的標記線程編號，進而將當前處理的第一對象的第一指針壓入與該第一對象所在的內存塊對應的標記線程的私有棧，根據所述第一指針的壓入情況對所述第一對象進行第一標記處理，對所述第一對象遍歷完成後，向所述n個標記線程發送線程啟動指令，以使所述n個標記線程根據各自私有棧中所述第一指針的壓入情況，同步進行用於垃圾回收的標記處理。由此，利用有限的內存實現高效的並行標記，同時實現標記線程負載均衡，提高整個垃圾回收的性能。

基於上述實施例，對所述第一對象遍歷完成後，各個標記線程的私有棧中都存放了本線程負責標記的內存塊中第一對象的第一指針。如果標記線程的私有棧中溢出，說明私有棧的空間已滿，無法繼續存放本線程負責標記的內存塊中第一對象的第一指針，則將這些第一對象標記為溢出狀態。當標記線程的私有棧中有新的處理空間時，繼續存放本線程負責標記的內存塊中第一對象的第一指針。

進而，向n個標記線程發送線程啟動指令，從而n個標記線程根據各自私有棧中第一指針的壓入情況，同步進行用於垃圾回收的標記處理。

需要說明的是，預先申請的n個標記線程的處理過程是同步並行的，為了更加清楚的 說明n個標記線程的標記處理過程，以第一標記線程的標記處理過程為例，通過下述實施例說明如下，其他(n-1)個標記線程的標記處理過程參見第一標記線程，不再一一贅述。

圖4為預先申請的n個標記線程的示意圖。

參見圖4，預先申請的n個標記線程，以及n個標記線程所佔用的內存容量。n個標記線程包括：thread-1、thread-2，…thread-n。其中，每個標記線程至少包括：1個私有棧(stack)，經過上述處理，各個私有棧中存儲有本線程負責標記的第一對象(rootobjects)的第一指針。

圖5是應用圖4所示的標記線程並行標記處理的流程圖一。

參見圖5，本實施例中以第一標記線程(thread-1)的標記處理過程為例，該用於垃圾回收的並行標記處理方法包括：

步驟301，第一標記線程根據線程啟動指令，從第一私有棧中取出預先壓入的第一對象的第一指針。

步驟302，所述第一標記線程遍歷所述第一指針指示的所述第一對象引用的第二對象，並根據預設的n個標記線程與虛擬機堆中內存塊的對應關係對所述第二對象進行第二標記處理。

具體地，第一標記線程接收到線程啟動指令之後，根據該線程啟動指令，從第一私有棧中取出預先壓入的第一對象的第一指針。

進而，第一標記線程查詢預存的對象關係表，獲取當前處理的第一指針指示的第二對象，需要解釋的是，第二對象為第一對象的引用對象。

第一標記線程遍歷當前處理的第一指針指示的第二對象，根據預設的n個標記線程與虛擬機堆中內存塊的對應關係，判斷負責處理當前第二對象所在的內存塊的標記線程是否為本線程，從而對第二對象進行第二標記處理。

本申請實施例，通過第一標記線程根據線程啟動指令，從第一私有棧中取出預先壓入的第一對象的第一指針，遍歷所述第一指針指示的所述第一對象引用的第二對象，並根據預設的n個標記線程與虛擬機堆中內存塊的對應關係對所述第二對象進行第二標記處理。由此，參照第一標記線程的標記處理過程，通過n個標記線程的並行標記處理，實現了利用有限的內存進行並行標記處理，提高整個垃圾回收的性能。

圖6是應用圖4所示的標記線程並行標記處理的流程圖二。

繼續參見圖4，基於圖5所示實施例，每個標記線程還包括：(n-1)個公用輸出隊列(queue-1、queue-2…queue-n-1)，以及1個緩存隊列(buf-queue)。其中，(n-1)個公用輸出隊列用於存儲其他(n-1)個標記線程負責標記的對象的指針；當與其他(n-1)個標 記線程對應的公用輸出隊列溢出時，1個緩存隊列用於緩存其他(n-1)個標記線程負責標記的對象的指針。

參見圖6，繼續以第一標記線程(thread-1)的標記處理過程為例，圖5所示實施例中的步驟302具體包括：

步驟401，第一標記線程根據所述對應關係，判斷是否負責對當前處理的第二對象所在的內存塊p1進行標記處理；

具體地，第一標記線程根據預設的n個標記線程與虛擬機堆中內存塊的對應關係，判斷本線程是否負責對當前處理的第二對象所在的內存塊p1進行標記處理。

如果第一標記線程獲知負責對該內存塊p1進行標記處理的標記線程為第一標記線程，即本線程負責對該內存塊p1進行標記處理，進而執行步驟402-步驟406；

如果第一標記線程獲知負責對該內存塊p1進行標記處理的標記線程為標記線程m，標記線程m不是第一標記線程，即本線程不負責對該內存塊p1進行標記處理，進而執行步驟407-步驟415。

步驟402，將當前處理的第二對象的第二指針壓入到所述第一私有棧中。

具體地，針對步驟401中第一標記線程負責對所述內存塊p1進行標記處理的判斷分支，第一標記線程將負責處理對象的指針壓入到本線程的私有棧中進行處理。即將當前處理的第二對象的第二指針壓入到所述第一私有棧中進行第二標記處理。

步驟403，所述第一標記線程判斷是否成功將所述第二指針壓入到所述第一私有棧中。

具體地，第一標記線程判斷是否成功將當前處理的第二對象的第二指針壓入到本線程的第一私有棧中。

如果第一標記線程未能成功將當前處理的第二對象的第二指針壓入到本線程的第一私有棧中，則執行步驟404和步驟405對第二對象進行溢出狀態的標記處理；

如果第一標記線程成功將當前處理的第二對象的第二指針壓入到本線程的第一私有棧中，則執行步驟406繼續對下一個第二對象進行第二標記處理。

步驟404，將所述內存塊p1的位圖中、與該第二對象對應的狀態標記為溢出狀態。

步驟405，設置與所述內存塊p1對應的溢出標誌。

具體地，針對步驟403中第一標記線程未能成功將當前處理的第二對象的第二指針壓入到本線程的第一私有棧中的判斷分支，將第二對象設置為溢出狀態。例如：將上述內存塊p1的位圖中、與該第二對象對應的狀態標記為溢出狀態。並且進一步地設置與該內存塊p1對應的溢出標誌。

步驟406，如果所述第一標記線程成功將所述第二指針壓入到所述第一私有棧中，則 繼續對所述第一指針對應的下一個第二對象進行處理。

具體地，針對步驟403中第一標記線程成功將所述第二指針壓入到所述第一私有棧中的判斷分支，繼續對從第一私有棧中取出的第一指針對應的下一個第二對象進行處理。

步驟407，確定標記線程m負責對所述內存塊p1進行標記處理；

步驟408，將所述第二指針壓入到所述第一標記線程中與所述標記線程m對應的公用輸出隊列m中；

具體地，針對步驟401中第一標記線程不負責對所述內存塊p1進行標記處理的判斷分支，根據n個標記線程與虛擬機堆中內存塊的對應關係，確定標記線程m負責對所述內存塊p1進行標記處理。

進而，第一標記線程將當前處理的第二對象的第二指針壓入到第一標記線程中與標記線程m對應的公用輸出隊列m中，以使標記線程m後續從第一標記線程中的公用輸出隊列m中獲取待處理的第二對象的第二指針。

步驟409，所述第一標記線程判斷是否成功將所述第二指針壓入到所述公用輸出隊列m中；

第一標記線程判斷是否成功將當前處理的第二對象的第二指針壓入到公用輸出隊列m中。

如果第一標記線程成功將當前處理的第二對象的第二指針壓入到第一標記線程中的公用輸出隊列m中，則執行步驟410，繼續對當前從第一私有棧中中獲取的第一指針對應的下一個第二對象進行處理。

如果第一標記線程未能成功將當前處理的第二對象的第二指針壓入到第一標記線程中的公用輸出隊列m中，則執行步驟411，通過第一標記線程的第一緩存隊列緩存該第二指針。

步驟410，繼續對所述第一指針對應的下一個第二對象進行處理。

具體地，針對步驟409中第一標記線程成功將當前第二指針壓入到第一標記線程中的公用輸出隊列m中的判斷分支，繼續對上述第一指針對應的下一個第二對象進行處理。

步驟411，將所述第二指針壓入到所述第一標記線程中的第一緩存隊列中；

具體地，針對步驟409中第一標記線程未能成功將當前第二指針壓入到第一標記線程中的公用輸出隊列m中的判斷分支，將該第二指針壓入到第一標記線程中的第一緩存隊列中。

步驟412，所述第一標記線程判斷是否成功將所述第二指針壓入到所述第一緩存隊列中；

具體地，第一標記線程判斷是否成功將該第二指針壓入到第一標記線程的第一緩存隊列中；

如果第一標記線程未能成功將所述第二指針壓入到所述第一緩存隊列中，則執行步驟413和步驟414,對當前處理的第二對象標記溢出狀態；

如果第一標記線程成功將所述第二指針壓入到所述第一緩存隊列中，則執行步驟415,對下一個第二對象繼續進行標記處理。

步驟413，將所述內存塊p1的位圖中、與當前處理的第二對象對應的狀態標記為溢出狀態。

步驟414，設置與所述內存塊p1對應的溢出標誌。

具體地，針對步驟412中第一標記線程未能成功將所述第二指針壓入到所述第一緩存隊列中的判斷分支，將商戶內存塊p1的位圖中、與當前處理的第二對象對應的狀態標記為溢出狀態，並進一步地設置與該內存塊p1對應的溢出標誌。

步驟415，繼續對所述第一指針對應的下一個第二對象進行處理。

具體地，針對步驟412中第一標記線程成功將所述第二指針壓入到所述第一緩存隊列中的判斷分支，繼續對當前第一指針對應的下一個第二對象進行處理。

基於圖6所示實施例，進一步地，在步驟401之前，還包括：

查詢當前處理的第二對象所在內存塊p1的位圖中與該第二對象對應的狀態標記。如果與該第二對象對應的狀態標記為未標記狀態，則將與該第二對象對應的狀態修改為壓入狀態。

需要說明的是，對第二對象是否溢出的標記方式有很多，可以根據需要進行選擇，例如：

示例一，可以通過列表的方式記錄與每個第二對象的壓入情況；或者，

示例二，可以通過第二對象所在內存塊位圖中的相應位置標記第二對象的壓入情況。

需要說明的是，以上僅為舉例說明，可以根據實際應用需要進行選擇標記方式。

本申請實施例，通過第一標記線程根據線程啟動指令，從第一私有棧中取出預先壓入的第一對象的第一指針，遍歷所述第一指針指示的所述第一對象引用的第二對象，並根據預設的n個標記線程與虛擬機堆中內存塊的對應關係對所述第二對象進行第二標記處理。由此，參照第一標記線程的標記處理過程，通過n個標記線程的並行標記處理，利用有限的內存實現高效的並行標記，同時實現標記線程負載均衡，從而減少cpu緩存一致性衝突，提高整個垃圾回收的性能。

圖7是應用圖4所示的標記線程並行標記處理的流程圖三。

繼續參見圖4，每個標記線程包括：1個私有棧(stack)、(n-1)個公用輸出隊列(queue-1、queue-2…queue-n-1)，以及1個緩存隊列(buf-queue)。其中，1個私有棧(stack)用於存儲本線程負責標記的對象的指針；(n-1)個公用輸出隊列用於存儲其他(n-1)個標記線程負責標記的對象的指針；當與其他(n-1)個標記線程對應的公用輸出隊列溢出時，1個緩存隊列用於緩存其他(n-1)個標記線程負責標記的對象的指針。

參見圖7，基於圖5所示實施例，所述方法還包括：

步驟501，第一標記線程接到線程啟動指令後，判斷本線程的第一私有棧是否為空；

具體地，第一標記線程判斷本線程的第一私有棧是否為空；

如果第一標記線程的第一私有棧不為空，則按照圖5中所示實施例中的步驟302從第一私有棧中取出預先壓入的第一對象的第一指針，並按照圖5或圖6所示的實施過程進行處理，此處不再贅述。

如果第一標記線程的第一私有棧為空，則執行步驟502繼續判斷第一標記線程中的第一緩存隊列是否為空。

步驟502，所述第一標記線程判斷本線程的第一緩存隊列是否為空；

具體地，第一標記線程判斷本線程的第一緩存隊列是否為空；

如果第一標記線程中的第一緩存隊列不為空，執行步驟503，從而對第一標記線程不負責處理的第三對象向本線程中與該第三對象對應的公用輸出隊列進行分配處理；

如果第一標記線程中的第一緩存隊列為空，則通過圖8所示實施例描述如何進一步地對其他(n-1)個標記線程中與第一標記線程對應的公用輸出隊列中的第四對象進行標記處理，後續實施例詳細說明。

步驟503，所述第一標記線程從所述第一緩存隊列中取出預先壓入的第三對象的第三指針，其中，所述第一標記線程不負責對當前處理的第三對象所在的內存塊p2進行標記處理；

步驟504，所述第一標記線程根據所述對應關係，確定標記線程w負責對當前處理的第三對象所在的內存塊p2進行標記處理；

步驟505，所述第一標記線程將所述第三指針壓入到所述第一標記線程中與所述標記線程w對應的公用輸出隊列w中；

具體地，第一標記線程從本線程的第一緩存隊列中取出預先壓入的第三對象的第三指針，由於第一緩存隊列中存放的對象是需要放入第一標記線程中的公用輸出隊列中，以供對應的其他標記線程進行處理的。當第一標記線程中的公用輸出隊列中出現溢出時，將溢出的第三對象放入第一標記線程中的第一緩存隊列中緩存。

由此可見，第一標記線程不負責對當前處理的第三對象所在的內存塊p2進行標記處理。第一標記線程根據虛擬機堆的內存塊與標記線程的對應關係，確定標記線程w負責對當前處理的第三對象所在的內存塊p2進行標記處理。

進而，第一標記線程將該第三指針壓入到第一標記線程中與標記線程w對應的公用輸出隊列w中，以供標記線程w從第一標記線程的公用輸出隊列w中獲取該第三指針進行標記處理。

步驟506，所述第一標記線程判斷是否成功將當前處理的第三指針壓入到所述公用輸出隊列w中；

步驟507，繼續對所述第一緩存隊列中的下一個第三對象向對應的公用輸出隊列進行壓入處理。

步驟508，將所述第三指針重新壓入所述第一緩存隊列中。

具體地，第一標記線程判斷是否成功將當前處理的第三指針壓入到本線程的公用輸出隊列w中。

如果第一標記線程成功將該第三指針壓入到本線程的公用輸出隊列w中，則執行步驟507，繼續對所第一緩存隊列中的下一個第三對象向對應的公用輸出隊列進行壓入處理。

如果第一標記線程未能成功將該第三指針壓入到本線程的公用輸出隊列w中，則將該第三指針重新壓入本線程的第一緩存隊列中。此時，不存在溢出的問題，因為該第三指針就是從本線程的第一緩存隊列中取出來的。

基於上述實施例，本申請在第一標記線程的第一私有棧為空時，且第一緩存隊列不為空，從第一緩存隊列中取出預先壓入的第三對象的第三指針，向本線程中與對應標記線程的公用輸出隊列中進行壓入處理，以供與第三對象對應的標記線程對其進行標記處理。由此，參照第一標記線程的標記處理過程，通過n個標記線程的進行協同並行的標記處理，利用有限的內存實現高效的並行標記，同時實現標記線程負載均衡，從而減少cpu緩存一致性衝突，提高整個垃圾回收的性能。

圖8是應用圖4所示的標記線程並行標記處理的流程圖四。

參見圖8，基於圖7所示實施例，本實施例是基於圖7中的步驟502，針對如果第一標記線程中的第一緩存隊列為空的判斷分支，通過圖8所示實施例描述如何進一步地對其他(n-1)個標記線程中與第一標記線程對應的公用輸出隊列中的第四對象進行標記處理，具體包括：

步驟601，第一標記線程判斷其他(n-1)個標記線程中與所述第一標記線程對應的公用輸出隊列是否為空；

具體地，第一標記線程判斷其他(n-1)個標記線程中與所述第一標記線程對應的公用輸出隊列是否為空；

如果其他(n-1)個標記線程中與第一標記線程對應的公用輸出隊列不為空，則執行步驟602，從而第一標記線程從其他標記線程中獲取本線程負責處理的第四對象，向本線程的第一私有棧進行壓入處理。

如果其他(n-1)個標記線程中與第一標記線程對應的公用輸出隊列為空，則通過圖9所示實施例描述如何進一步地對第一標記線程負責標記的、且具有溢出狀態的第五對象進行標記處理，後續實施例詳細說明。

步驟602，第一標記線程從當前處理的公用輸出隊列中取出預先壓入的第四對象的第四指針，其中，所述第四對象為所述標記線程t預先壓入的、由所述第一標記線程負責對所述第四對象所在的內存塊p3進行標記處理；

步驟603，所述第一標記線程將所述第四指針壓入到所述第一私有棧中；

具體地，針對步驟601中如果其他(n-1)個標記線程中與第一標記線程對應的公用輸出隊列不為空的判斷分支，說明其他的標記線程中還具有需要由第一標記線程標記處理的第四對象。

進而，第一標記線程從當前處理的公用輸出隊列中取出預先壓入的第四對象的第四指針，其中，該第四對象為標記線程t預先壓入的、並且由第一標記線程負責對該第四對象所在的內存塊p3進行標記處理。從而第一標記線程將該第四指針壓入到所述第一私有棧中。

步驟604，所述第一標記線程判斷是否成功將所述第四指針壓入到所述第一私有棧中；

步驟605，將所述內存塊p3的位圖中、與該第四對象對應的狀態標記為溢出狀態。

步驟606，設置與所述內存塊p3對應的溢出標誌。

步驟607，繼續對下一個第四對象向所述第一私有棧中進行壓入處理。

具體地，第一標記線程判斷是否成功將該第四指針壓入到本線程的第一私有棧中。

如果第一標記線程未能成功將該第四指針壓入到本線程的第一私有棧中，則執行步驟605和步驟606，將該第四對象所在的內存塊p3的位圖中、與該第四對象對應的狀態標記為溢出狀態，並且設置與所述內存塊p3對應的溢出標誌。

如果第一標記線程成功將該第四指針壓入到本線程的第一私有棧中，則則執行步驟607，繼續對下一個第四對象向本線程的第一私有棧中進行壓入處理。

基於上述實施例，本申請的第一標記線程在第一私有棧和第一緩存隊列為空，且其他標記線程中與第一標記線程對應的公用輸出隊列不為空時，取出預先壓入的第四對象的第 四指針，向本線程中的第一私有棧壓入處理。由此，參照第一標記線程的標記處理過程，通過n個標記線程的進行協同並行的標記處理，利用有限的內存實現高效的並行標記，同時實現標記線程負載均衡，從而減少cpu緩存一致性衝突，提高整個垃圾回收的性能。

圖9是應用圖4所示的標記線程並行標記處理的流程圖五。

參見圖9，基於圖8所示實施例，本實施例是基於圖9中的步驟601，針對如果其他(n-1)個標記線程中與第一標記線程對應的公用輸出隊列為空的判斷分支，則通過圖9所示實施例描述如何進一步地對第一標記線程負責標記的、且具有溢出狀態的第五對象進行標記處理，具體包括：

步驟701，第一標記線程判斷本線程負責標記的內存塊中是否有溢出狀態的第五對象；

步驟702，如果所述第一標記線程負責標記的內存塊中不具有溢出狀態的第五對象，則標記結束，退出線程。

步驟703，如果所述第一標記線程負責標記的內存塊中具有溢出狀態的第五對象，所述第一標記線程將當前處理的內存塊p4中標記溢出狀態的第五對象修改為壓入狀態，將當前第五對象的第五指針壓入到所述第一私有棧中；

具體地，第一標記線程判斷本線程負責標記的內存塊中是否有溢出狀態的第五對象。

如果第一標記線程負責標記的內存塊中不具有溢出狀態的第五對象，則說明本線程負責標記的對象遍歷完成，標記結束，執行步驟702退出線程。

如果第一標記線程負責標記的內存塊中具有溢出狀態的第五對象，則說明本線程負責標記的對象還沒有遍歷完成。進而，第一標記線程執行步驟703，將當前處理的內存塊p4中標記溢出狀態的第五對象修改為壓入狀態，將當前第五對象的第五指針壓入到所述第一私有棧中。

步驟704，所述第一標記線程判斷是否成功將所述第五指針壓入到所述第一私有棧中；

步驟705，如果所述第一標記線程未能成功將所述第五指針壓入到所述第一私有棧中，則將所述內存塊p4的位圖中、與該第五對象對應的狀態標記為溢出狀態。

步驟706，設置與所述內存塊p5對應的溢出標誌。

步驟707，如果所述第一標記線程成功將所述第五指針壓入到所述第一私有棧中，則繼續對下一個第五對象進行處理。

具體地，第一標記線程判斷是否成功將當前的第五指針壓入到本線程的第一私有棧中。

如果第一標記線程未能成功將該第五指針壓入到本線程的第一私有棧中，則說明第一私有棧空間不足有溢出，則執行步驟705和步驟706，將該第五對象所在的內存塊p4的位圖中、與該第五對象對應的狀態標記為溢出狀態，並且進一步地設置與所述內存塊p5對應 的溢出標誌。

如果第一標記線程成功將該第五指針壓入到本線程的第一私有棧中，則執行步驟707，繼續對下一個第五對象進行處理。

基於上述實施例，本申請的第一標記線程在第一私有棧、第一緩存隊列、以及其他標記線程中與第一標記線程對應的公用輸出隊列都為空時，根據本線程負責標記的具有溢出狀態的第五對象進行壓入處理。由此，參照第一標記線程的標記處理過程，通過n個標記線程的並行的標記處理，利用有限的內存實現高效的並行標記，提高整個垃圾回收的性能。

為了更加清楚的說明圖4-圖9所示實施例中涉及的對第二對象至第五對象進行處理的處理過程，通過圖10所示實施例說明如下。

圖10是應用圖4所示的標記線程並行標記處理的流程圖六。

參見圖10，本實施例中採用在內存塊位圖中進行著色標記的方式對第二對象至第五對象的壓入情況進行標記處理，具體標記如下：

如果將當前處理的對象的指針成功壓入對應的目標空間中，則將與當前對象所在內存塊位圖中的對應位置進行標黑處理；

如果沒有將當前處理的對象的指針成功壓入對應的目標空間中，則將與當前對象所在內存塊位圖中的對應位置進行標灰處理；

如果當前處理對象所在內存塊位圖中的對應位置為標白狀態，說明該對象為未處理狀態。

需要說明的是，以上根據處理對象的指針向對應目標空間的不同壓入情況，在內存塊位圖中與當前處理對象的對應位置進行的著色處理僅僅是示例性說明，可以根據具體的應用需要進行調整。

基於上述標記方式，具體以對象a等同於上述實施例中涉及的第一對象，對象a1等同於上述實施例中涉及的第二對象，對象b等同於上述實施例中涉及的第三對象，對象d等同於上述實施例中涉及的第四對象，對象c等同於上述實施例中涉及的第五對象，舉例說明如下：

如圖10所示，該並行標記處理方法包括：

步驟1：線程啟動。

步驟2：如果私有stack已經空了，則跳轉到步驟3。否則彈出一個對象比如a，跳轉到步驟4。

步驟3：如果buf-queue為空，跳轉到步驟7，否則遍歷buf-queue，彈出對象比如b，跳轉到步驟5。如果已經遍歷完成，則跳轉到步驟7。

步驟4：依次遍歷對象a所引用的所有對象，遍歷完成則跳轉到步驟2。否則，比如遍歷到對象a1，並跳轉到步驟9。

步驟5：嘗試把步驟3中彈出來的對象b壓入本線中t(b)號queue中，壓入成功則跳轉到步驟3，反之標記對象b所在的page(內存塊)溢出，然後跳轉到步驟6。

步驟6：對象b重新壓回到buf-queue中，這時候不會失敗，因為對象b是從buf-queue中彈出來的。

步驟7：遍歷另外n-1個線程中的本線程對應的queue，取出標記對象。只要有一個queue非空，則pop出(彈出)標記對象，比如對象d，然後跳轉到步驟16。如果所有n-1個線程中和本線程對應的queue都為空，則跳轉到步驟8。

步驟8：遍曆本線程負責的page時如發現有溢出，則遍歷有溢出的page的bitmap(位圖)，找到灰色的對象比如c，如果找到則跳轉到步驟14。遍歷完畢，清理page的溢出標誌，然後跳轉到步驟15。

步驟9：判斷步驟4中遍歷到的對象a1所在的page的對應的bitmap是否為白色，如果已經是黑色則跳轉到步驟4。如果是白色，則跳轉到步驟10。

步驟10：標記對象a1所在的page的對應的bitmap值為黑色。如果t(a1)為本線程，則跳轉到步驟17。否則跳轉到步驟11。

步驟11：嘗試把對象a1壓入本線程的t(a1)號queue中，如果壓入失敗，則設置a1所在的page的溢出。並跳轉到步驟12，如果成功，則跳轉到步驟4。

步驟12：嘗試把對象a1壓入buf-queue，如果成功則跳轉到步驟4。反之跳轉到步驟13。

步驟13：設置對象a1所在的page對應的bitmap的值為灰色，並設置page的溢出標誌。

步驟14：把步驟8遍歷到的灰色對象c標記對應的bitmap為黑色並壓入私有棧stack中，如果成功則跳轉到步驟8。如果失敗，則設置c所在的page的溢出標誌，並跳轉到步驟19。

步驟15：如果標記結束，則線程退出，否則跳轉到步驟2，繼續並行標記。

步驟16：標記對象d對應的bitmap為黑色，嘗試把對象d壓入本線程的stack中，如壓入成功，跳轉到步驟7。溢出跳轉到步驟19。

步驟17：嘗試把對象a1壓入本線程的私有stack中，如果壓入成功即沒有溢出，則跳轉到步驟4，否則跳轉到步驟18。

步驟18：標記對象a1對應的bitmap為灰色，並設置a1所在的page的溢出標誌。 然後跳轉到步驟4。

步驟19：標記對象(d或者c，即可能來自步驟14或者16)對應的bitmap為灰色，並設置標記對象所在的page的溢出標誌。然後跳轉到步驟2。

具體地，結合本示例中的19個步驟和附圖，具體通過下述的處理步驟示意圖6至圖9的處理過程，其詳細的描述過程參見圖6至圖9所示實施例，此處不再贅述。

針對圖6所示實施例的處理過程如下示意的步驟流程(1)，其具體實施過程參見上述實施例，此處不再贅述。

步驟流程(1)：

針對圖7所示實施例的處理過程如下示意的步驟流程(2)，其具體實施過程參見上述實施例，此處不再贅述。

步驟流程(2)：

針對圖8所示實施例的處理過程如下示意的步驟流程(3)，其具體實施過程參見上述實施例，此處不再贅述。

步驟流程(3)：

針對圖9所示實施例的處理過程如下示意的步驟流程(4)，其具體實施過程參見上述 實施例，此處不再贅述。

步驟流程(4)：

為了實現上述實施例，本申請還提出一種用於垃圾回收的並行標記處理裝置。

圖11是本申請一個實施例的用於垃圾回收的並行標記處理裝置的結構示意圖。

參見圖11，該用於垃圾回收的並行標記處理裝置包括：

遍歷模塊11，用於根據虛擬機堆中的內存塊與n個標記線程的對應關係，遍歷所述虛擬機堆中的第一對象，其中，n為大於1的整數，n個標記線程佔用的內存容量是預先設置的，每個標記線程至少包括：1個私有棧；

第一標記模塊12，用於將當前處理的第一對象的第一指針壓入與該第一對象所在的內存塊對應的標記線程的私有棧，根據所述第一指針的壓入情況對所述第一對象進行第一標記處理；

啟動模塊13，用於對所述第一對象遍歷完成後，向所述n個標記線程發送線程啟動指令，以使所述n個標記線程根據各自私有棧中所述第一指針的壓入情況，同步進行用於垃圾回收的標記處理。

需要說明的是，前述對用於垃圾回收的並行標記處理方法實施例的解釋說明也適用於該實施例的用於垃圾回收的並行標記處理裝置，此處不再贅述。

本實施例提供的用於垃圾回收的並行標記處理裝置，通過根據虛擬機堆中的內存塊與n個標記線程的對應關係，遍歷所述虛擬機堆中的第一對象，其中，n個標記線程佔用的內存容量是預先設置的，將當前處理的第一對象的第一指針壓入與該第一對象所在的內存塊對應的標記線程的私有棧，根據所述第一指針的壓入情況對所述第一對象進行第一標記處理，對所述第一對象遍歷完成後，向所述n個標記線程發送線程啟動指令，以使所述n個標記線程根據各自私有棧中所述第一指針的壓入情況，同步進行用於垃圾回收的標記處理。由此，利用有限的內存實現多線程的並行標記處理，提高整個垃圾回收的性能。

圖12是本申請另一個實施例的用於垃圾回收的並行標記處理裝置的結構示意圖。

參見圖12，基於圖11，該用於垃圾回收的並行標記處理裝置還包括：

申請模塊14，用於申請所述n個標記線程；

建立模塊15，用於遍歷所述虛擬機堆中的內存塊，建立內存塊與n個標記線程的對應關係。

具體地，所述建立模塊15用於：

為每個內存塊指定對應的標記線程；或者，

為每個標記線程指定負責標記的內存塊。

其中，在一個具體的示例中，所述建立模塊15包括：

分配單元151，用於遍歷虛擬機堆中的內存塊，為每個內存塊分配編號；

確定單元152，用於根據內存塊的編號和標記線程總數n，確定與每個內存塊編號對應的標記線程編號。

具體地，所述確定單元152用於：

獲取標記線程總數n被內存塊編號整除後的餘數，確定與每個內存塊編號對應的標記線程編號。

具體地，所述第一標記模塊12用於：

如果將所述第一指針成功壓入與當前第一對象所在的內存塊對應的標記線程的私有棧，則將當前第一對象所在內存塊的位圖中、與該第一對象對應的狀態標記為壓入狀態；

如果未能將所述第一指針成功壓入與當前第一對象所在的內存塊對應的標記線程的私有棧，則將當前第一對象所在內存塊的位圖中、與該第一對象對應的狀態標記為溢出狀態。

需要說明的是，前述對用於垃圾回收的並行標記處理方法實施例的解釋說明也適用於該實施例的用於垃圾回收的並行標記處理裝置，此處不再贅述。

本實施例提供的用於垃圾回收的並行標記處理裝置，通過申請n個標記線程，遍歷虛擬機堆的所有內存塊，為每個內存塊分配編號；根據內存塊編號和標記線程總數n，確定與每個內存塊編號對應的標記線程編號，進而將當前處理的第一對象的第一指針壓入與該第一對象所在的內存塊對應的標記線程的私有棧，根據所述第一指針的壓入情況對所述第一對象進行第一標記處理，對所述第一對象遍歷完成後，向所述n個標記線程發送線程啟動指令，以使所述n個標記線程根據各自私有棧中所述第一指針的壓入情況，同步進行用於垃圾回收的標記處理。由此，利用有限的內存實現高效的並行標記，同時實現標記線程負載均衡，提高整個垃圾回收的性能。

圖13是本申請另一個實施例的用於垃圾回收的並行標記處理裝置的結構示意圖。

參見圖13，本實施例中預先申請的n個標記線程，以及n個標記線程所佔用的內存容量。n個標記線程包括：thread-1、thread-2，…thread-n。其中，每個標記線程至少包 括：1個私有棧(stack)，經過上述處理，各個私有棧中存儲有本線程負責標記的第一對象(rootobjects)的第一指針。本實施例中用於垃圾回收的並行標記處理裝置包括：

獲取模塊21，用於根據線程啟動指令，從第一私有棧中取出預先壓入的第一對象的第一指針；

第二標記模塊22，用於遍歷所述第一指針指示的所述第一對象引用的第二對象，並根據預設的n個標記線程與虛擬機堆中內存塊的對應關係對所述第二對象進行第二標記處理。

需要說明的是，前述對用於垃圾回收的並行標記處理方法實施例的解釋說明也適用於該實施例的用於垃圾回收的並行標記處理裝置，此處不再贅述。

本實施例提供的用於垃圾回收的並行標記處理裝置，通過第一標記線程根據線程啟動指令，從第一私有棧中取出預先壓入的第一對象的第一指針，遍歷所述第一指針指示的所述第一對象引用的第二對象，並根據預設的n個標記線程與虛擬機堆中內存塊的對應關係對所述第二對象進行第二標記處理。由此，參照第一標記線程的標記處理過程，通過n個標記線程的並行標記處理，實現了利用有限的內存進行並行標記處理，提高整個垃圾回收的性能。

圖14是本申請另一個實施例的用於垃圾回收的並行標記處理裝置的結構示意圖。

參見圖14，基於圖13所示實施例，所述第二標記模塊22包括：

第一判斷單元221，用於根據所述對應關係，判斷是否負責對當前處理的第二對象所在的內存塊p1進行標記處理；

第一處理單元222，用於如果所述第一標記線程負責對所述內存塊p1進行標記處理，則將當前處理的第二對象的第二指針壓入到所述第一私有棧中；

第二判斷單元223，用於判斷是否成功將所述第二指針壓入到所述第一私有棧中；

第二處理單元224，用於如果所述第一標記線程未能成功將所述第二指針壓入到所述第一私有棧中，則將所述內存塊p1的位圖中、與該第二對象對應的狀態標記為溢出狀態。

進一步地，所述第二處理單元224還用於：

設置與所述內存塊p1對應的溢出標誌。

進一步地，在另一個實施例中，

所述第二處理單元224還用於：如果所述第一標記線程成功將所述第二指針壓入到所述第一私有棧中，則繼續對所述第一指針對應的下一個第二對象進行處理。

進一步地，在另一個實施例中，所述第二標記模塊22還包括：

所述第一處理單元222，還用於如果所述第一標記線程不負責對所述內存塊p1進行標 記處理，確定標記線程m負責對所述內存塊p1進行標記處理，將所述第二指針壓入到所述第一標記線程中與所述標記線程m對應的公用輸出隊列m中；

第三判斷單元225，用於判斷是否成功將所述第二指針壓入到所述公用輸出隊列m中；

第三處理單元226，用於如果所述第一標記線程成功將所述第二指針壓入到所述公用輸出隊列m中，則繼續對所述第一指針對應的下一個第二對象進行處理。

進一步地，在另一個實施例中，所述第二標記模塊22還包括：

所述第三處理單元226，還用於如果所述第一標記線程未能成功將所述第二指針壓入到所述公用輸出隊列m中，則把所述第二指針壓入到所述第一標記線程中的第一緩存隊列中；

第四判斷單元227，用於判斷是否成功將所述第二指針壓入到所述第一緩存隊列中；

第四處理單元228，用於如果所述第一標記線程未能成功將所述第二指針壓入到所述第一緩存隊列中，則將所述內存塊p1的位圖中、與當前處理的第二對象對應的狀態標記為溢出狀態。

進一步地，在另一個實施例中，

所述第四處理單元228還用於：

設置與所述內存塊p1對應的溢出標誌。

進一步地，在另一個實施例中，

所述第四處理單元228，還用於如果所述第一標記線程成功將所述第二指針壓入到所述第一緩存隊列中，則繼續對所述第一指針對應的下一個第二對象進行處理。

進一步地，在另一個實施例中，

所述第二處理單元224，還用於查詢所述內存塊p1的位圖中與該第二對象對應的狀態標記；如果與該第二對象對應的狀態標記為未標記狀態，則將與該第二對象對應的狀態修改為壓入狀態。

需要說明的是，前述對用於垃圾回收的並行標記處理方法實施例的解釋說明也適用於該實施例的用於垃圾回收的並行標記處理裝置，此處不再贅述。

本實施例提供的用於垃圾回收的並行標記處理裝置，通過第一標記線程根據線程啟動指令，從第一私有棧中取出預先壓入的第一對象的第一指針，遍歷所述第一指針指示的所述第一對象引用的第二對象，並根據預設的n個標記線程與虛擬機堆中內存塊的對應關係對所述第二對象進行第二標記處理。由此，參照第一標記線程的標記處理過程，通過n個標記線程的並行標記處理，利用有限的內存實現高效的並行標記，同時實現標記線程負載均衡，從而減少cpu緩存一致性衝突，提高整個垃圾回收的性能。

圖15是本申請另一個實施例的用於垃圾回收的並行標記處理裝置的結構示意圖。

參見圖15，基於圖13所示實施例，本實施例中預設的n個標記線程中每個標記線程還包括：1個緩存隊列，以及與其他(n-1)個標記線程對應的(n-1)個公用輸出隊列；所述第二標記模塊22還包括：

第五判斷單元229，用於判斷所述第一私有棧是否為空；

第六判斷單元210，用於如果所述第一私有棧為空，判斷第一標記線程的第一緩存隊列是否為空；

第五處理單元211，用於如果所述第一緩存隊列不為空，所述第一標記線程從所述第一緩存隊列中取出預先壓入的第三對象的第三指針，其中，所述第一標記線程不負責對當前處理的第三對象所在的內存塊p2進行標記處理；根據所述對應關係，確定標記線程w負責對當前處理的第三對象所在的內存塊p2進行標記處理；將所述第三指針壓入到所述第一標記線程中與所述標記線程w對應的公用輸出隊列w中；

第七判斷單元212，用於判斷是否成功將當前處理的第三指針壓入到所述公用輸出隊列w中；

第六處理單元213，用於如果所述第一標記線程成功將所述第三指針壓入到所述公用輸出隊列w中，則繼續對所述第一緩存隊列中的下一個第三對象向對應的公用輸出隊列進行壓入處理。

進一步地，在另一個實施例中，

所述第六處理單元213，還用於如果所述第一標記線程未能成功將所述第三指針壓入到所述公用輸出隊列w中，則將所述第三指針重新壓入所述第一緩存隊列中。

需要說明的是，前述對用於垃圾回收的並行標記處理方法實施例的解釋說明也適用於該實施例的用於垃圾回收的並行標記處理裝置，此處不再贅述。

本實施例提供的用於垃圾回收的並行標記處理裝置，在第一標記線程的第一私有棧為空時，且第一緩存隊列不為空，從第一緩存隊列中取出預先壓入的第三對象的第三指針，向本線程中與對應標記線程的公用輸出隊列中進行壓入處理，以供與第三對象對應的標記線程對其進行標記處理。由此，參照第一標記線程的標記處理過程，通過n個標記線程的進行協同並行的標記處理，利用有限的內存實現高效的並行標記，同時實現標記線程負載均衡，從而減少cpu緩存一致性衝突，提高整個垃圾回收的性能。

圖16是本申請另一個實施例的用於垃圾回收的並行標記處理裝置的結構示意圖。

參見圖16，基於圖15所示實施例，所述第二標記模塊22還包括：

第八判斷單元214，用於如果所述第一緩存隊列為空，判斷其他(n-1)個標記線程中 與所述第一標記線程對應的公用輸出隊列是否為空；

第七處理單元215，用於如果當前處理的標記線程t中與所述第一標記線程對應的公用輸出隊列不為空，所述第一標記線程從當前處理的公用輸出隊列中取出預先壓入的第四對象的第四指針，其中，所述第四對象為所述標記線程t預先壓入的、由所述第一標記線程負責對所述第四對象所在的內存塊p3進行標記處理；將所述第四指針壓入到所述第一私有棧中；

第九判斷單元216，用於判斷是否成功將所述第四指針壓入到所述第一私有棧中；

第八處理單元217，用於如果所述第一標記線程未能成功將所述第四指針壓入到所述第一私有棧中，則將所述內存塊p3的位圖中、與該第四對象對應的狀態標記為溢出狀態。

進一步地，在另一個實施例中，

所述第八處理單元217，還用於設置與所述內存塊p3對應的溢出標誌。

進一步地，在另一個實施例中，

所述第八處理單元217，還用於如果所述第一標記線程成功將所述第四指針壓入到所述第一私有棧中，則繼續對下一個第四對象向所述第一私有棧中進行壓入處理。

需要說明的是，前述對用於垃圾回收的並行標記處理方法實施例的解釋說明也適用於該實施例的用於垃圾回收的並行標記處理裝置，此處不再贅述。

本實施例提供的用於垃圾回收的並行標記處理裝置，第一標記線程在第一私有棧和第一緩存隊列為空，且其他標記線程中與第一標記線程對應的公用輸出隊列不為空時，取出預先壓入的第四對象的第四指針，向本線程中的第一私有棧壓入處理。由此，參照第一標記線程的標記處理過程，通過n個標記線程的進行協同並行的標記處理，利用有限的內存實現高效的並行標記，同時實現標記線程負載均衡，從而減少cpu緩存一致性衝突，提高整個垃圾回收的性能。

圖17是本申請另一個實施例的用於垃圾回收的並行標記處理裝置的結構示意圖。

參見圖17，基於圖16所示實施例，所述第二標記模塊22還包括：

第十判斷單元218，用於如果其他(n-1)個標記線程中與所述第一標記線程對應的公用輸出隊列都為空，所述第一標記線程判斷本線程負責標記的內存塊中是否有溢出狀態的第五對象；

第九處理單元219，用於如果所述第一標記線程負責標記的內存塊中具有溢出狀態的第五對象，所述第一標記線程將當前處理的內存塊p4中標記溢出狀態的第五對象修改為壓入狀態，將當前第五對象的第五指針壓入到所述第一私有棧中；

第十一判斷單元220，用於所述第一標記線程判斷是否成功將所述第五指針壓入到所 述第一私有棧中；

第十處理單元221，用於如果所述第一標記線程未能成功將所述第五指針壓入到所述第一私有棧中，則將所述內存塊p4的位圖中、與該第五對象對應的狀態標記為溢出狀態。

進一步地，在另一個實施例中，

所述第十處理單元221，還用於設置與所述內存塊p5對應的溢出標誌。

進一步地，在另一個實施例中，

所述第十處理單元221，還用於如果所述第一標記線程成功將所述第五指針壓入到所述第一私有棧中，則繼續對下一個第五對象進行處理。

進一步地，在另一個實施例中，

所述第九處理單元219，還用於如果所述第一標記線程負責標記的內存塊中不具有溢出狀態的第五對象，則標記結束，退出線程。

需要說明的是，前述對用於垃圾回收的並行標記處理方法實施例的解釋說明也適用於該實施例的用於垃圾回收的並行標記處理裝置，此處不再贅述。

本實施例提供的用於垃圾回收的並行標記處理裝置，第一標記線程在第一私有棧、第一緩存隊列、以及其他標記線程中與第一標記線程對應的公用輸出隊列都為空時，根據本線程負責標記的具有溢出狀態的第五對象進行壓入處理。由此，參照第一標記線程的標記處理過程，通過n個標記線程的並行的標記處理，利用有限的內存實現高效的並行標記，提高整個垃圾回收的性能。

在本說明書的描述中，參考術語「一個實施例」、「一些實施例」、「示例」、「具體示例」、或「一些示例」等的描述意指結合該實施例或示例描述的具體特徵、結構、材料或者特點包含於本申請的至少一個實施例或示例中。在本說明書中，對上述術語的示意性表述不必須針對的是相同的實施例或示例。而且，描述的具體特徵、結構、材料或者特點可以在任一個或多個實施例或示例中以合適的方式結合。此外，在不相互矛盾的情況下，本領域的技術人員可以將本說明書中描述的不同實施例或示例以及不同實施例或示例的特徵進行結合和組合。

此外，術語「第一」、「第二」僅用於描述目的，而不能理解為指示或暗示相對重要性或者隱含指明所指示的技術特徵的數量。由此，限定有「第一」、「第二」的特徵可以明示或者隱含地包括至少一個該特徵。在本申請的描述中，「多個」的含義是至少兩個，例如兩個，三個等，除非另有明確具體的限定。

流程圖中或在此以其他方式描述的任何過程或方法描述可以被理解為，表示包括一個或更多個用於實現特定邏輯功能或過程的步驟的可執行指令的代碼的模塊、片段或部分， 並且本申請的優選實施方式的範圍包括另外的實現，其中可以不按所示出或討論的順序，包括根據所涉及的功能按基本同時的方式或按相反的順序，來執行功能，這應被本申請的實施例所屬技術領域的技術人員所理解。