嵌入式系統設計中的存儲碎片收集策略

　　隨著(zhù)嵌入式系統數據對象處理量的急劇增加，對存儲碎片收集的實(shí)時(shí)性能的要求也顯得日益突出，本文介紹的真正高效、實(shí)時(shí)、確定性的兩種存儲碎片收集技術(shù)將對(中國)工程師提供策略上的指導。

　　在嵌入式系統設計過(guò)程中，Java程序員并不需要弄清楚哪些數據占用了哪些存儲器或者應該在什么位置釋放哪些存儲空間，設計工程師只需要簡(jiǎn)單地分配對象而后由系統來(lái)釋放這些資源。這樣就可以完全消除懸浮指針錯誤，因而極大地減小存儲空間浪費的可能性。由于并不需要一些顯式的規則來(lái)指定這些存儲空間的釋放，因此簡(jiǎn)化了接口并且增強了軟件復用。自動(dòng)診測并釋放這些不再使用的對象的系統進(jìn)程稱(chēng)為存儲碎片收集(garbage collection)。

　　假如存儲碎片收集真有這么好，人們也許會(huì )懷疑為什么在A(yíng)NSI C++中不具備這樣的功能。事實(shí)上，C++語(yǔ)言擴充版允許程序員將一些類(lèi)型指定為“受控對象類(lèi)型”，比如在Microsoft Visual C++的.NET平臺中就能找到這種應用。這些受控對象在一定的條件下，可以實(shí)現自動(dòng)存儲碎片收集。問(wèn)題的關(guān)鍵是存儲碎片收集器必須能夠找到所有的對象指針。由于C++允許將指針映射為其它類(lèi)型，所以通常情況下無(wú)法追蹤所有的指針。

　　關(guān)聯(lián)存儲碎片收集是對傳統存儲碎片收集算法的一個(gè)重大改進(jìn)?；镜乃悸肪褪顷P(guān)注最新的對象。這是由于大多數對象都是很快產(chǎn)生而又很快消失，這些很快消失的對象集通常構成了絕大部分存儲碎片。當然事情遠比這要復雜。

　　彈性清除存儲碎片

　　基于“標示和掃描”方式的傳統存儲碎片收集算法工作過(guò)程如下：當存儲空間太低(下降到一個(gè)失效的新值)時(shí)，系統就會(huì )停止所有用戶(hù)線(xiàn)程，定位無(wú)法訪(fǎng)問(wèn)的對象集合并且釋放這些對象。要做到這一點(diǎn)就必須檢查每一個(gè)對象索引，如從“根”開(kāi)始的局部變量和靜態(tài)類(lèi)型域。檢查每一個(gè)索引的對象確定其是否已經(jīng)被標記過(guò)。如果沒(méi)有，首先標記該對象并且對它所有的索引進(jìn)行處理，否則就繼續處理下一個(gè)索引。這一過(guò)程結束后，任何未被標示的對象都被認為是無(wú)法訪(fǎng)問(wèn)的對象，因而可以回收再利用其占用的存儲空間。由于這種技術(shù)能夠正確地檢測被其它消失對象索引的成組消失對象，因而要比索引計數機制高明。圖1和圖2分別顯示出這一對應過(guò)程前/后的圖像。

　　當然存儲空間在任何時(shí)候都有可能出現自由空間過(guò)低的情況，并且標示和掃描過(guò)程所需要的時(shí)間正比于對象以及索引的數量，因而就會(huì )出現應用程序可能周期性地出現不響應或者滯后短暫的時(shí)間間隔才開(kāi)始響應的問(wèn)題。這樣的滯后在實(shí)時(shí)系統甚至是在“軟”實(shí)時(shí)的系統中都是不能接受的。

　　有的設計師試圖使用一種稱(chēng)為增量式存儲碎片收集(incremental garbage collector)的技術(shù)來(lái)確保這種應用的滯后時(shí)間最小。簡(jiǎn)單地說(shuō)，就是存儲碎片收集器僅僅在一個(gè)固定的時(shí)間增量上運行，運行結束之后交給用戶(hù)線(xiàn)程一個(gè)重新執行的機會(huì )。應用程序有更多時(shí)間運行之后，增量式存儲碎片收集器將從原來(lái)停止的位置處繼續工作。注意：當應用程序線(xiàn)程先占了存儲碎片收集器線(xiàn)程后，有的存儲碎片收集器必須從頭開(kāi)始重新運行，這樣的存儲碎片收集器就稱(chēng)為可以被搶先的，但不是增量式的。

　　可以搶先式以及增量式存儲碎片收集器都聲稱(chēng)可以減少滯后時(shí)間，但是這些算法效率的差異卻很大。對搶先式存儲碎片收集器來(lái)說(shuō)，如果經(jīng)常被搶先，那么收集器線(xiàn)程永遠無(wú)法進(jìn)一步執行，因而也就沒(méi)有任何的用處。同樣，如果存儲碎片收集只有當某一個(gè)應用線(xiàn)程極度缺乏存儲空間時(shí)才啟動(dòng)執行的話(huà)，那么至少該線(xiàn)程(如果不是完整的應用程序)必須滯后運行，因為該線(xiàn)程要在存儲碎片收集線(xiàn)程釋放存儲空間之后才能繼續運行。

　　收集器時(shí)間增量的長(cháng)度也稱(chēng)為等待時(shí)間，它對于應用的響應同樣也是十分關(guān)鍵的。取決于應用的實(shí)現時(shí)間增量，其范圍大約從幾秒到幾十分之一毫秒。時(shí)間增量越小，應用的響應就越具有實(shí)時(shí)性。很顯然，在應用的響應速度與存儲空間收集器的工作能力之間存在一種工程折衷。

　　一個(gè)去碎片(defragmenting)的存儲碎片收集器可以在存儲器空間各處移動(dòng)有效對象，并且將閑置的存儲器空間合并成少數更大的存儲器區塊。如果不具備這種去碎片的能力，那么可用的存儲器空間將被分隔成許多小的存儲器小塊，因而最終大對象的存儲空間分配可能失敗(特別是在長(cháng)運行時(shí)間的程序中)。 

　　由于系統越來(lái)越難找到足夠大的自由存儲器空間以滿(mǎn)足應用程序的需要，因此存儲器去碎片也會(huì )導致每一次的存儲空間分配操作要花更長(cháng)的時(shí)間。相反，在一個(gè)已經(jīng)去碎片的存儲器空間中，存儲空間的分配要快得多。系統只需要增值一個(gè)自由指針，這并不比為一種功能調用而分配一個(gè)堆棧結構更困難。

　　去碎片存儲碎片收集器通常將存儲空間分為幾個(gè)區域。一個(gè)區域的存儲碎片收集完成之后，通常將該區域中的有效對象集中到其它區域中去。這一過(guò)程結束后，原來(lái)的區域會(huì )被清空，而且目標區域中也不存在任何間隙。當然這還需要附加存儲器，然后才能消除存儲器碎片。

　　關(guān)聯(lián)存儲碎片收集

　　關(guān)聯(lián)存儲碎片收集(generational garbage collection)的工作方式如下：許多存儲器區域被指定為存放新產(chǎn)生對象的特殊場(chǎng)所。當這些對象存在的時(shí)間變長(cháng)(存活的時(shí)間變長(cháng)，在存儲碎片收集期間依然存活)，就會(huì )將它們從這一特殊區域轉移出去并且放到主存儲區域。某些關(guān)聯(lián)存儲碎片收集算法甚至還區分幾個(gè)“較早的”代。.NET平臺以及C＃語(yǔ)言的存儲碎片收集器可以區分三代，所以可以將第一代與存放新產(chǎn)生對象的區域分別開(kāi)來(lái)。為了簡(jiǎn)單起見(jiàn)，介紹僅有兩代的情況，多代的算法與此相似，只是管理操作方面的運算更多。

　　關(guān)聯(lián)存儲碎片收集僅僅考慮新產(chǎn)生對象存儲區域，從本質(zhì)上來(lái)說(shuō)，它假定所有駐留在非新產(chǎn)生對象存儲區域的對象仍然在被引用(也就是說(shuō)它們仍然是有效的)。要做到這一點(diǎn)，就需要有一種方法來(lái)計算所有索引了新產(chǎn)生對象的集合。為了加速這一過(guò)程，需要維護一個(gè)獨立的“老對象到新產(chǎn)生對象的索引”表，這一索引表列出了所有非新產(chǎn)生對象對于新產(chǎn)生對象的索引。這一表格極大地加速了新產(chǎn)生對象存儲區域對象的檢查，與此同時(shí)非新產(chǎn)生對象則根本不需要檢查。

　　也許有人會(huì )關(guān)心：開(kāi)始的時(shí)候如何追蹤非新產(chǎn)生對象對新產(chǎn)生對象的索引？答案在于一種稱(chēng)為“寫(xiě)屏蔽”技術(shù)。寫(xiě)屏蔽監視所有的存儲操作，并且不斷查詢(xún)“正在存儲的對象索引了非新產(chǎn)生的對象嗎”？如果是這樣，接下來(lái)就會(huì )詢(xún)問(wèn)是否將正在被寫(xiě)的舊值以及/或正在被存儲的新值進(jìn)行了索引，并產(chǎn)生了新的對象。此外，還要對這一組老對象到新產(chǎn)生對象的索引進(jìn)行相關(guān)的刷新。請注意：通過(guò)比較索引的地址與新產(chǎn)生對象存儲區域的邊界地址，存儲碎片收集器可以迅速地判定一個(gè)索引是否指向了一個(gè)新產(chǎn)生的對象。

　　典型應用的實(shí)際測試表明：老對象到新產(chǎn)生對象的索引集合通常都比較小。測試也證實(shí)關(guān)聯(lián)存儲碎片收集可以線(xiàn)性地分配空間收集工作。也就是說(shuō)，關(guān)聯(lián)存儲碎片收集在大約八分之一全部存儲碎片收集的時(shí)間里可以收集到最新的第八個(gè)存儲器空間。這將釋放比八分之一存儲碎片要多得多的空間。

　　圖3顯示了存儲碎片收集之前的一種情況。新產(chǎn)生對象存儲空間包含三個(gè)對象：C、D和E。對象C包含到對象E的索引。主要存儲器區域包含兩個(gè)對象：A和B。對象A包含到對象C的索引。這一個(gè)索引被記錄在“老對象到新產(chǎn)生對象”的集合中。根索引集合包含到A和E的索引。這個(gè)實(shí)例顯示了對新產(chǎn)生對象存儲區域同時(shí)進(jìn)行存儲碎片收集和去碎片的情況。同時(shí)也顯示了對新產(chǎn)生對象存儲區域進(jìn)行存儲碎片收集并且直接收集到主存儲空間中的情況。這樣可以提升新產(chǎn)生對象存儲區域中的所有對象。也就是說(shuō)，這些對象下一輪的關(guān)聯(lián)存儲碎片收集過(guò)程中將不再被檢查。如果算法支持幾代關(guān)聯(lián)存儲碎片收集過(guò)程，那么就需要通過(guò)存儲器去碎片技術(shù)整合到一個(gè)區域并且進(jìn)行更高一代關(guān)聯(lián)存儲碎片收集。

　　在關(guān)聯(lián)存儲碎片收集過(guò)程中，根到A的索引將被忽略，但是根到E的索引將把E標示為有效，所以在目標區域中會(huì )創(chuàng )建E的一個(gè)副本，并且刷新C到E的索引。 

　　E不包括任何索引，因而對E不作任何處理。老對象到新產(chǎn)生對象的集合也需要檢查，在檢查中會(huì )發(fā)現A到C的索引。C會(huì )被標示為有效，所以在目標區域中就會(huì )創(chuàng )建C的一個(gè)副本，并且刷新從A到C的索引。對象C包含一個(gè)到E的索引。由于E已經(jīng)被復制，C中的索引被刷新，但是無(wú)需再復制E。而無(wú)法訪(fǎng)問(wèn)的對象D則不會(huì )被復制，因此該區域重新整理時(shí)D就會(huì )被刪除。這樣就會(huì )產(chǎn)生圖4中顯示出的結果。

　　增量式存儲碎片收集

　　增量式存儲碎片收集(incremental garbage collection)比關(guān)聯(lián)存儲碎片收集更加復雜。盡管現在有幾種不同的實(shí)現方式都聲稱(chēng)是增量式存儲碎片收集，但事實(shí)上這是多年來(lái)懸而未決的問(wèn)題。下面描述增量式存儲碎片收集的一種特定的實(shí)現方式。

　　考慮在“來(lái)源”和“目的”區域上運行的一個(gè)去碎片存儲碎片收集器(關(guān)聯(lián)型或者非關(guān)聯(lián)型)。隨著(zhù)存儲碎片收集的進(jìn)行，“來(lái)源”區域中的全部有效對象都會(huì )移到“目的”區域。復制過(guò)程由索引遍歷來(lái)驅動(dòng)。每一個(gè)索引都采取以下的處理方式：如果目標對象還沒(méi)有被復制，那么就復制該目標對象，并且將其索引添加到要處理的索引列表中。最初的索引都要重新改寫(xiě)以反映對象的新位置，并且指向目標對象新位置的一個(gè)前向地址會(huì )保留在那個(gè)對象最初的“來(lái)源位置”處。當所有索引的對象都已經(jīng)被復制，并且所有的索引都已經(jīng)重新改寫(xiě)，那么存儲碎片收集(那一個(gè)區域的)就結束，并且“來(lái)源”區域可以重新使用。 

　　增量式存儲碎片收集通常采取突發(fā)、短時(shí)運行方式。在這些突發(fā)的運行之間，允許用戶(hù)線(xiàn)程運行，這樣就可以減少等待時(shí)間。當然，在用戶(hù)線(xiàn)程執行之前，存儲碎片收集器并不能夠保證對一個(gè)對象的所有索引都進(jìn)行合適的重新改寫(xiě)。那么當索引僅僅修正了一半的時(shí)候，程序怎樣才能準確無(wú)誤地繼續運行？答案同樣也在于寫(xiě)屏蔽。

　　當程序試圖對存儲器進(jìn)行寫(xiě)操作時(shí)，系統會(huì )進(jìn)行檢查，以確保被寫(xiě)入的對象是否正在被存儲碎片收集器移走。如果是這樣，那么寫(xiě)操作就會(huì )在舊的位置和新的位置同時(shí)進(jìn)行。這樣的技術(shù)避免了“讀屏蔽”的必要性，同時(shí)也保證借助于沒(méi)有被修正的索引，所作的修改不會(huì )被丟失。

　　聰明的讀者會(huì )注意到：對象索引的集合在突發(fā)的存儲碎片收集之間可能會(huì )改變。去掉索引應該沒(méi)有什么壞處。存儲碎片收集器已經(jīng)標示出：一個(gè)對象是有效對象移去之后這個(gè)對象最后的索引，那么該對象肯定可以在下一次的存儲碎片收集過(guò)程中收集起來(lái)。

　　然而必須小心處理索引的增加。存儲碎片收集進(jìn)程“正在處理”的過(guò)程中，每一次存儲一個(gè)新的索引時(shí)，當存儲碎片收集繼續執行時(shí)，必須將該索引添加到需要處理的索引列表中。同樣寫(xiě)屏蔽也要確保這一過(guò)程將工作正常。

　　在增量式存儲碎片收集過(guò)程中，關(guān)于新對象的創(chuàng )建也有其它巧妙的細節。這些對象必須小心地分配在一個(gè)獨立的區域中，存儲碎片收集結束后，該區域將成為新產(chǎn)生對象的存儲區域。如果能讓這些新對象立即參與當前的存儲碎片收集過(guò)程，那么它們就可以迅速升級。而采用其它方法，它們則會(huì )錯過(guò)最開(kāi)始的機會(huì )，并且沒(méi)有機會(huì )存儲在新產(chǎn)生對象的存儲空間中，并通過(guò)關(guān)聯(lián)存儲碎片收集器來(lái)進(jìn)行快速收集。

　　新的問(wèn)題

　　通過(guò)上面所有的討論，存儲碎片收集聽(tīng)上去比實(shí)際情況更直觀(guān)。系統執行應用程序代碼需要花費的時(shí)間總量，以及執行存儲碎片收集的時(shí)間總量之間存在某種精細的平衡。如果系統需要花費太多的時(shí)間去實(shí)施存儲碎片收集，那么數據吞吐量就會(huì )受到影響。如果系統花費太多的時(shí)間去執行應用程序代碼，那么存儲碎片收集器就不能進(jìn)一步運行下去，最終導致應用程序必須等待完整的存儲碎片收集完成，所以最壞情況下，滯后問(wèn)題可能得不到解決，當然這種情況極為稀少。

　　由于存儲碎片收集器上的負載隨應用行為而變化，因此僅僅調節存儲碎片收集的靜態(tài)參數不太可能達到較好的平衡。要切實(shí)解決這一問(wèn)題，存儲碎片收集子系統需要動(dòng)態(tài)地監視其自身與應用的相對情況。應用分配了多少存儲器？存儲器從新產(chǎn)生對象存儲區域到主要存儲區域之間的升級有多快？存儲碎片收集正在順利進(jìn)行還是已經(jīng)滯后？如果已經(jīng)滯后，那么應該怎么辦？需要更加頻繁地實(shí)施關(guān)聯(lián)存儲碎片收集或者將對象在新產(chǎn)生對象存儲區域中保持更長(cháng)的時(shí)間嗎？在哪一個(gè)特定時(shí)刻必須實(shí)施一輪完整的存儲碎片收集，以確保所有存儲器在消耗光之前有時(shí)間來(lái)完成這一過(guò)程？

　　關(guān)鍵的一點(diǎn)是“協(xié)調步伐”以確保存儲碎片收集器總是在應用程序之前，避免最終可能產(chǎn)生的所有滯后，并且獲得真正的實(shí)時(shí)性和確定型的行為。當然，通常這都取決于應用行為良好這樣的假定，也就是說(shuō)，這些應用并不會(huì )非?？焖俚胤峙浜歪尫糯鎯臻g，從而導致存儲碎片收集器不能協(xié)調工作。在那種情況下，因為沒(méi)有足夠的存儲空間可以使用，會(huì )導致存儲碎片收集器需要花時(shí)間來(lái)釋放存儲器。需要多少緩沖器取決于存儲碎片收集器的效率以及最壞情況下應用的行為。提高關(guān)聯(lián)存儲碎片收集的效率，就減少了需要獲得實(shí)時(shí)性能所必須的緩沖器總數。

　　討論如何達到這樣的一種奇跡超出了本文的范疇。一個(gè)優(yōu)秀的存儲碎片收集器應該能夠體現許多關(guān)于內部的信息。

　　存儲碎片收集器的評價(jià)

　　在評價(jià)系統性能時(shí)，存儲器使用以及存儲碎片收集的開(kāi)銷(xiāo)是關(guān)鍵的一個(gè)統計量。許多存儲碎片收集器都提供一種測量API來(lái)查詢(xún)存儲空間的創(chuàng )建、收集、以及從新產(chǎn)生對象存儲空間到主要存儲器空間升級的比率。跟蹤應用隨時(shí)間的行為的能力，對于進(jìn)一步的性能調整很有價(jià)值。

　　對性能進(jìn)一步調整的工具通常關(guān)注測量對象創(chuàng )建和撤銷(xiāo)的比率。高明的程序員通常都知道如何通過(guò)重寫(xiě)代碼打亂對象次序來(lái)極大地提高速度。我們有一個(gè)Java程序需要將幾千個(gè)時(shí)間信息(長(cháng)總數)轉換為字符串。有一種標準的Java類(lèi)型方法可以一步實(shí)現這種轉換，但是在它內部創(chuàng )建(并且丟棄)了一個(gè)“日期格式化程序”對象。將根據步長(cháng)重新替換高級運算，就能夠得到一種準確的日期格式化程序對象。這樣就節省了用于創(chuàng )建(以及存儲碎片收集)幾千個(gè)日期格式化程序對象所需要的時(shí)間。

　　有時(shí)候應用程序知道什么時(shí)候會(huì )被閑置，這是通知存儲碎片收集器啟動(dòng)一個(gè)完整的存儲碎片收集的最好時(shí)機。要做到這一點(diǎn)就需要利用一個(gè)控制API來(lái)影響存儲碎片收集器的行為。然而，從前面的討論中可以了解到，存儲碎片收集器通常都比較清楚什么時(shí)候應該清理這些存儲碎片。

　　本文小結

　　一般來(lái)說(shuō)，存儲碎片收集以及特殊情況下的關(guān)聯(lián)存儲碎片收集已經(jīng)成為近年來(lái)人們不斷研究的課題。關(guān)聯(lián)存儲碎片收集最先出現在桌面應用環(huán)境中。比如Sun的HotSpot JVM就是采用關(guān)聯(lián)存儲碎片收集。增量式存儲碎片收集由于減少了等待時(shí)間，所以通常在嵌入式領(lǐng)域應用更多。HotSpot也可以進(jìn)行增量式存儲碎片收集，但是時(shí)間增量非常大，在桌面應用中存儲碎片收集的進(jìn)展被認為比等待時(shí)間更重要。

　　關(guān)聯(lián)存儲碎片收集在性能上提升了一個(gè)數量級。它極大地提高了增量式存儲碎片收集的效率。嵌入式應用開(kāi)發(fā)人員會(huì )發(fā)現，綜合運用增量式存儲碎片收集以及關(guān)聯(lián)存儲碎片收集會(huì )得到最好的存儲碎片收集效果，也可以調整等待時(shí)間以適合響應時(shí)間的要求。