自適應垃圾收集方法及設備的製作方法
2023-05-01 11:22:41 1
專利名稱：自適應垃圾收集方法及設備的製作方法
技術領域：
本發明涉及垃圾收集(garbage collection)，更具體地說，涉及使用在其中空間邊界的位置在半空間(semi-空間)複製收集算法的結構中改變的自適應非對稱空間結構的自適應垃圾收集。
背景技術：
在程序設計術語中，垃圾是被確定為由不再被程序引用的對象佔用並隨後被作業系統收集的數據存儲空間。垃圾收集是釋放這樣的存儲空間從而該存儲空間可以為其它程序有效地重複利用的處理。換句話說，垃圾收集是用於動態地管理存儲器的方法。
傳統地，必要時作業系統可以強制地終止未能將由不再被程序引用的對象佔用的存儲空間返回的程序，但是通常，程式設計師需要顯式地聲明必要的存儲空間並當程序不再需要該存儲空間時使程序將該存儲空間返回給作業系統。
當不再被需要的存儲空間的返回被忽視時，程序可能會由於未知原因而不是邏輯上的錯誤而終止。程式設計師很難找出難懂的問題。因此，在系統中自動地查找不被使用的存儲空間並將該存儲空間釋放的技術已經被開發。
用於垃圾收集的算法包括半空間複製收集算法和世代垃圾收集算法。以下的描述涉及這兩種算法。
圖1示出傳統的半空間複製收集算法。
如圖1中所示，存儲區域被分成兩個相等空間的區域from-空間和to-空間。From-空間是分配給對象的存儲區域的一部分，to-空間是根據垃圾收集佔用from-空間的對象被複製到其的存儲區域的一部分。這裡，to-空間的大小需要與from-空間的大小相同，因為，當所有佔據from-空間的對象為「活躍」時，所有的對象需要在垃圾收集期間被複製到to-空間。此外，為執行傳統的半空間複製收集算法，單一對象的兩次複製臨時地需要指針反轉(pointerreversal)。這是由Cheney公開的[「A Nonrecursive List Compaction Algorithm，」(非遞歸列表壓縮算法)Communications of the ACM，13(11)，pp 677-678，1970]。
在面向對象的程序設計中，對象是通過其具有數據變量的子類和特定類的方法或過程通過其被實現的實例。
如圖1中所示，從第1階段到第3階段，對象被分配到from-空間。在第3階段，from-空間變滿並且不再被分配給對象。因此，在第4階段，在佔用from-空間的對象中，只有「活動」對象，而不是不再被使用的對象，即垃圾，被複製到to-空間。象這樣，先前的from-空間變為to-空間，並且先前的to-空間變成from-空間。因此，在第5階段，如在第1階段，對象被分配到from-空間。
通常，半空間複製收集算法被應用於其它動態存儲管理算法，例如世代垃圾收集算法，而不是單獨地被使用。
圖2示出傳統的世代垃圾收集算法。
傳統的世代垃圾收集算法自80年代起已被廣泛地使用。在傳統的世代垃圾收集算法中，根據對象的年代(age)，存儲堆(heap)被分為兩個或多個世代空間。在圖2中，存儲堆被分為年輕代區域200和年老代區域250。由於在年輕代區域200中使用如圖1中所示的半空間複製收集算法的垃圾收集被執行，所以年輕代區域200包含from-空間210和to-空間220。
對象的年代與該對象從一個半空間到另一個半空間產生的複製的次數相關。因此，當對象已經被複製多次時，該對象可以被認為變老了。
在下文中，將詳細地描述傳統的世代垃圾收集算法。
參考圖2，對於垃圾收集，在年輕代區域200中使用半空間複製收集算法，並且在年老代區域250中使用標記整理(mark-compact)算法。新對象被分配到年輕代區域中的from-空間210。附圖標記212、214、216和218表示被分配到from-空間210的對象。
在年輕代區域200中，通過僅將活動對象212和216從from-空間210複製到to-空間220來執行垃圾收集。當在年輕代區域200中執行多次垃圾收集操作時已經為「活躍」狀態的對象218被定義為年老的對象並且被轉移到年老代區域250。
當年老代區域250中沒有對象被轉移到其的空間時，在年老代區域250中執行垃圾收集，並且通常比在年輕代區域200中花更多時間。
如圖1所示，在半空間複製收集算法中，在兩個半空間中只有一個存儲空間被用於對象分配。換句話說，由於垃圾收集是在存儲空間充滿對象時被執行，所以半空間複製收集算法存在隨著存儲空間的大小減少垃圾收集的次數增加的問題。
由於半空間複製收集算法通常被用在年輕代區域200中，所以如圖2所示的世代垃圾收集算法也具有上述問題。此外，世代垃圾收集算法具有浮動(floating)垃圾數量增加的問題。浮動垃圾是指不再被使用但仍然存在於存儲空間，即在年老代區域250中的對象，因為對象通過在年輕代區域200中執行的垃圾收集被轉移到年老代區域250，而在年老代區域250中還沒有執行垃圾收集。執行垃圾收集越頻繁，轉移到年老代區域250的對象就越多。結果浮動垃圾的數量增加，降低了整體存儲效率。
發明內容
本發明提供一種通過改變用於半空間複製收集算法的必要空間的大小來收集垃圾的更有效的方法。
根據本發明的一方面，提供了一種關於動態存儲分配的垃圾收集方法。該垃圾收集方法包含響應來自預定處理的請求分配第一存儲空間的一部分給新對象，將所有佔用第一存儲空間的對象中被該預定處理使用的對象複製到第二存儲空間，並根據預定的信息調整第一存儲空間的大小和第二存儲空間的大小。
優選地，該預定的信息是在分配和複製步驟中生成的歷史信息。
該預定信息最好是所有在第一存儲空間中的對象佔用的部分的大小和由所有被從第一存儲空間複製到第二存儲空間的對象佔用的部分大小之間的比率。
根據本發明的另一方面，提供了一種提供關於動態存儲分配的垃圾收集功能的設備。該設備包含用於響應預定的處理而將新對象分配到其的第一存儲空間；在所有佔用第一存儲空間的對象中由預定處理使用的對象被複製到其的第二存儲空間；和垃圾收集模塊，其被該處理激活並分配用於將對象存儲在第一和第二存儲空間的空間，根據預定信息調整第一存儲空間的大小和第二存儲空間的大小，將控制權交還給預定的處理，並隨後處於非激活狀態。這裡，該預定處理可以由用戶應用程式或系統程序生成。
預定信息最好是當第一存儲空間的一部分被分配給新對象以響應來自預定處理的請求時，和在所有佔用第一存儲空間的對象中由該預定處理使用的對象被複製到第二存儲空間時生成的歷史信息。
此外，該預定信息最好是由所有在第一存儲空間中的對象佔用的部分的大小和由從第一存儲空間複製到第二存儲空間的對象佔用的部分的大小之間的比率。
通過參考附圖對其示例性實施例的詳細描述本發明的上述特點和其它特點和優點將變得更加清楚，其中圖1示出傳統的半空間複製收集算法；圖2示出傳統的世代垃圾收集算法；圖3示出用在用於根據本發明的實施例的自適應世代垃圾收集的方法的存儲結構；和圖4是根據本發明的實施例在年輕代區域中執行垃圾收集的方法的流程圖。
具體實施例方式
現在將參考附圖更全面地描述本發明，本發明的示例性實施例表示在附圖中。然而，本發明可以以不同的形式實現，並且不應被解釋為僅限於在此提出的實施例；這些實施例被提供以使公開更徹底和完整、並全面地向本領域的技術人員傳達本發明的概念。本發明的精神和範圍由所附權利要求限定。在圖中，相同的標號表示相同部件。
在下文中，將參考附圖詳細地描述本發明的優選實施例。
圖3示出在根據本發明的實施例的自適應世代垃圾收集的方法中使用的存儲結構。
如圖3所示，用於垃圾收集的存儲區域例如堆被分為年輕代區域300和年老代區域350。使用空間邊界320，年輕代區域300分割為from-空間310和to-空間330。空間邊界320不是固定的以限定兩個相等大小的空間，而是自由地被移動。
圖4是根據本發明的實施例在年輕代中執行垃圾收集的方法的流程圖。執行垃圾收集的垃圾收集器400是在系統中運行的處理機(processor)。垃圾收集器400通過與用戶處理470交互來執行垃圾收集功能。換句話說，垃圾收集器400是一個獨立的模塊，其在接收到來自用戶處理470的存儲空間分配請求時分配存儲空間並在存儲空間不足時通過從由垃圾收集器400管理的存儲堆中刪除垃圾來保證存儲器的剩餘。此外，由於垃圾收集器400自動地分配和釋放存儲空間，它能被連接到任何類型的處理器並用於存儲管理器。更具體地說，垃圾收集器400可以被應用於包括Java的虛擬機。
在步驟S410，垃圾收集器400在接收到來自用戶處理470用於新對象地存儲空間的分配請求時開始操作。接下來，在步驟S420，垃圾收集器400檢查from-空間是否足以給新對象分配新的存儲空間。當from-空間對新對象是充足的時，垃圾收集器400將相應於新對象的大小的from-空間的部分分配給用戶處理470，並將控制權交給用戶處理470。
然而，在步驟S420，當from-空間對新對象是不充足的時，則在步驟S430，在年輕代中執行垃圾收集。在步驟S440，當to-空間不足以複製存在於from-空間中的所有對象時，在步驟S450，通過在from-空間中執行眾所周知的標記整理算法收集在from-空間中剩餘的對象。
在正常地完成垃圾收集後，在步驟S460，垃圾收集器400重置from-空間和to-空間之間的空間邊界。這裡，垃圾收集器400使用預定的估計值重置空間邊界。
在下文中，將詳細地描述重置空間邊界的方法。
傳統上，from-空間的大小等於to-空間的大小。然而，在本發明中，from-空間和to-空間之間的空間邊界被自適應地計算。通常，大多數被分配到from-空間的對象被歸類為垃圾而被清除，並只有少數對象被從from-空間複製到to-空間。因此，，空間邊界被重置從而無論何時垃圾收集結束from-空間都比to-空間大得多。
下面的描述涉及計算空間邊界的方法。當在年輕代中執行垃圾收集時，在垃圾收集前分配給所有對象的存儲空間總和與在垃圾收集後分配給所有活動對象存儲空間總和之間的比率被表示為R，並且關於第i次垃圾收集測量的比率R被表示為R(i)。當假定比率R(i)具有穩定的概率分布時，關於最近的「k」次垃圾收集的比率的平均值可以被表示為avg＝(R(i)+R(i-1)+…+R(i-k+1))/k.
關於下一次垃圾收集的比率R可以使用關於最近的「k」次垃圾收集的比率的平均值的線性逼近(linear approximation)來估計。這裡，線性差(lineardivergence)由每個比率R(i)與R(i)的平均值之差所定義，並作為垃圾收集歷史的一項分別地被存儲。線性差被表示為div(i)＝|R(i)-avg|.
在本發明的實施例中，為了防止from-空間和to-空間之間的空間邊界的快速運動並使內存配置信息穩定，驗證關於最近的「k」次垃圾收集的div(i)的值是否都在最大限制值MAX_D之內。當驗證所有的div(i)的值都在限制值MAX_D之內時，用於重置空間邊界的差「div」被定義為具有至少一個最小值MIN_D從而根據概率分布可能出現的噪聲波動(noise fluctuation)可被吸收。因此，差「div」被表示為div＝max(div，MIN_D).
最後，僅當差值「div」小於最大限制值MAX_D時，空間邊界被定義為R*＝max(avg，R(i))+div.
在本發明中，from-空間和to-空間之間的空間邊界使用這個估計值而變化。
圖3示出在年輕代區域300中的垃圾收集。關於年老代區域350的處理，例如將經過多次在年輕代區域300中執行的垃圾收集而已經變老的對象轉移到年老代區域350的處理、在年老代區域350中執行垃圾收集的處理、和在年輕和年老代300和350之間更新內存引用的處理，可以採用傳統的世代垃圾收集算法執行。典型的世代垃圾收集算法由Jones和Lins公開在[「GarbageCollectionAlgorithms for Automatic Dynamic Memory Management」，pp.1-41，Wiley，1996]。
為了對比根據本發明實施例的自適應垃圾收集器的性能與傳統的垃圾收集器的性能，由昇陽電腦公司(Sun Microsystems)作為標準提供的J2小型版連接裝置配置參考實現(Micro Edition Connected Device ConfigurationReference Implemetation)(以下稱為J2ME CDC RI)作為測試平臺。
例如標記清除(mark-sweep)算法、複製半空間算法和世代算法的垃圾收集算法可以在J2ME CDC RI中被執行。在這三種算法中，世代算法，即世代垃圾收集算法(以下稱為RI GC)，在與根據本發明實施例的算法(以下稱為newGC)進行對比時具有最高的性能。
此外，兩種算法性能被在使用被廣泛應用於測定Java虛擬機性能的SPECjvm98基準的測試中測定的。在該測試中，參考個人計算機(PC)使用Linux RedHat 8.0作為作業系統並具有硬體系統規格Pentium II 233MHz和32MB RAM。採用這種PC規格是因為本發明在存儲資源管理非常重要的嵌入式系統中非常有用。表1顯示了關於SPECjvm98基準的傳統的垃圾收集的性能與根據本發明實施例的垃圾收集的性能的比較結果。
表1
在表1中，「存儲器」表示被用作基準的存儲空間大小。GC延時總和以毫秒讀取，並且是當垃圾收集被執行時用戶處理暫停期間的時間的累積。隨著GC延時總和的減少，已經提高。
如表1中顯示，當根據本發明實施例的自適應垃圾收集被使用時，用在Java虛擬機上執行垃圾收集的時間顯著地減少，並且最大GC延時也減少。
對本發明的某個實施例進行這樣的描述後，在不脫離本發明的精神和範圍的情況下，各種變換、修改和改進將對本領域的普通技術人員很清楚。因此，以上描述和附圖並不是想要作為限定。
與在其中只有年輕代的一半可被用於存儲空間分配的傳統垃圾收集不同，本發明允許超過年輕代區域一半，並且最好地，大部分年輕代區域被用於存儲空間分配，因此提高了存儲器使用效率。
此外，由於本發明提供了用於存儲空間分配的更多的區域，所以每單位時間垃圾收集的次數減少，並因此浮動垃圾的數量減少。結果存儲器使用效率提高。
由於存儲器使用效率的提高，與傳統的垃圾收集器相比，垃圾收集總時間，垃圾收集器的最重要的性能指標減少。
權利要求
1.一種在動態存儲器分配中的垃圾收集方法，包含(a)分配第一存儲空間的一部分給新對象以響應來自預定的處理的請求；(b)將所有佔用在第一存儲空間的對象中由該預定的處理使用的對象複製到第二存儲空間；和(c)根據預定的信息調整第一存儲空間的大小和第二存儲空間的大小。
2.如權利要求1所述的垃圾收集方法，其中，該預定的處理由用戶應用程式生成。
3.如權利要求1所述的垃圾收集方法，其中，該預定處理由系統應用程式生成。
4.如權利要求1所述的垃圾收集方法，其中，該預定信息是在步驟(a)和步驟(b)期間生成的歷史信息。
5.如權利要求1所述的垃圾收集方法，其中，該預定信息是由所有在第一存儲空間中的對象佔用的部分的大小和由被從第一存儲空間複製到第二存儲空間的對象所佔用的部分的大小之間的比率。
6.一種在動態存儲器分配中提供垃圾收集功能的設備，包含第一存儲空間，其被分配給新對象以響應預定的處理；第二存儲空間，用於分配給被複製的所有佔用第一存儲空間的對象中被預定處理使用的對象；和垃圾收集模塊，其被處理激活並在第一和第二存儲空間中分配用於存儲對象的空間，根據預定的信息調整第一存儲空間的大小和第二存儲空間的大小，將控制權交給預定的處理，並處於非激活狀態。
7.如權利要求6所述的設備，其中，該預定的處理是由用戶應用程式生成的處理。
8.如權利要求6所述設備，其中，該預定處理是由系統應用程式生成的處理。
9.如權利要求6所述設備，其中，該預定信息是當第一存儲空間的一部分被分配給新對象以響應來自預定的處理的請求時和當在所有佔用第一存儲空間的對象中由預定的處理使用的對象被複製到第二存儲空間時生成的歷史信息。
10.如權利要求6所述的設備，其中，該預定的信息是由所有的在第一存儲空間中的對象佔用的部分的大小和由從第一存儲空間複製到第二存儲空間的對象佔用的部分的大小之間的比率。
全文摘要
一種用於在動態存儲器分配中的自適應垃圾收集的方法和設備。該方法包含分配第一存儲空間的一部分給新對象以響應來自預定的處理的請求；將所有佔用第一存儲空間存儲的對象中由預定的處理使用的對象複製到第二存儲空間；並根據預定的信息調整第一存儲空間的大小和第二存儲空間的大小。
文檔編號G06F12/02GK1648879SQ200510004908
公開日2005年8月3日 申請日期2005年1月28日 優先權日2004年1月28日
發明者鄭承範, 羅曼諾夫斯基·亞裡克賽, 趙雄石, 許得萬, 馬爾科夫·亞歷山大, 米謝耶夫·維塔利 申請人:三星電子株式會社