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

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

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

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

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

　　彈性清除存儲碎片

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

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

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

　　可以搶先式以及增量式存儲碎片收集器都聲稱可以減少滯后時間，但是這些算法效率的差異卻很大。對搶先式存儲碎片收集器來說，如果經常被搶先，那么收集器線程永遠無法進一步執(zhí)行，因而也就沒有任何的用處。同樣，如果存儲碎片收集只有當某一個應用線程極度缺乏存儲空間時才啟動執(zhí)行的話，那么至少該線程(如果不是完整的應用程序)必須滯后運行，因為該線程要在存儲碎片收集線程釋放存儲空間之后才能繼續(xù)運行。

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

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

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

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

　　關聯存儲碎片收集

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

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

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

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

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

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

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

　　增量式存儲碎片收集

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

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

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

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

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

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

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

　　新的問題

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

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

　　關鍵的一點是“協調步伐”以確保存儲碎片收集器總是在應用程序之前，避免最終可能產生的所有滯后，并且獲得真正的實時性和確定型的行為。當然，通常這都取決于應用行為良好這樣的假定，也就是說，這些應用并不會非常快速地分配和釋放存儲空間，從而導致存儲碎片收集器不能協調工作。在那種情況下，因為沒有足夠的存儲空間可以使用，會導致存儲碎片收集器需要花時間來釋放存儲器。需要多少緩沖器取決于存儲碎片收集器的效率以及最壞情況下應用的行為。提高關聯存儲碎片收集的效率，就減少了需要獲得實時性能所必須的緩沖器總數。

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

　　存儲碎片收集器的評價

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

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

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

　　本文小結

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

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