記憶體碎片處理技術

magicalloveshe

記憶體碎片處理技術

記憶體碎片是一個很棘手的問題。如何配置記憶體決定了記憶體碎片是否會、何時會、如何會成為一個問題。
作者︰ Jan Lindblad，Enea Embedded Technology

即使在系統中事實上仍然有許多閒置記憶體時，記憶體碎片（memory fragmentation）最終還是會讓記憶體用完的情況出現。
一個不斷產生記憶體碎片的系統，不管產生的記憶體碎片是多麼地小，只要時間夠長，就會將記憶體用完。
這種情況在許多嵌入式系統中，特別是在高可用性系統中是不可接受的。
有些軟體環境，如OSE即時作業系統已經備有避免記憶體碎片發生的有用工具，但個別程式設計師做出的選擇仍然會對最終結果造成影響。

“碎片的記憶體”描述一個系統中所有不可用的閒置記憶體。
這些資源之所以仍然未被使用，是因為負責配置記憶體的配置器（allocator）使這些記憶體無法使用。
這種問題通常都會發生，原因在於閒置記憶體以小而不連續的方式出現在不同的位置。
由於配置方法決定記憶體碎片是否會成為一個問題，因此記憶體配置器在保証閒置資源可用性方面，扮演著重要的角色。

編譯時間與運行時間
在許多情況下都會出現記憶體配置問題。
程式設計師可以通過編譯程式和鏈接程式，為結構、聯集（union）、陣列和純量（用來當作區域變數、靜態變數或全域變數）方面的數據配置記憶體，程式設計師還可以在運行時間使用諸如 malloc()的呼叫（call）來動態地配置記憶體。
當用編譯程式和鏈接程式完成記憶體配置功能時，就不會出現記憶體碎片，因為編譯程式了解數據壽命。
掌握可供使用的數據壽命，好處在於可以使數據以後進先出的方式堆疊起來。
這樣就可以使記憶體配置程式工作效率更高，而不會出現記憶體碎片。
一般來說，運行時間內的記憶體配置是不可堆疊的。記憶體配置在時間上是獨立的，從而使得碎片問題難以解決。

記憶體配置程式浪費記憶體的基本方式有三種︰即額外開銷、內部碎片以及外部碎片（圖 1）。
記憶體配置程式需要儲存一些描述其配置狀態的數據。
這些儲存的訊息包括任何一個閒置記憶體區塊的位置、大小和所有權，以及其它內部狀態的詳情。
一般來說，一個運行時間配置程式（runtime allocator）存放這些額外訊息最好的地方是它管理的記憶體。
記憶體配置程式需要遵循一些基本的記憶體配置規則。
例如，所有的記憶體配置必須起始於可被4、8或16整除（視處理器架構而定）的地址。
記憶體配置程式把僅僅預定大小的記憶體區塊配置給客戶，可能還有其它原因。
當某個客戶端程式請求一個43位元組的記憶體區塊時，它可能會獲得44位元組、48位元組甚至更多的位元組。由所需大小四捨五入而產生的多餘空間就叫內部碎片。


圖 1: 記憶體碎片的幾種形式。

外部碎片的產生是當已配置記憶體區塊之間出現未被使用的差額時，就會產生外部碎片。

例如，一個應用程式配置三個連續的記憶體區塊，然後使中間的一個記憶體區塊閒置。記憶體配置程式可以重新使用中間記憶體區塊供將來進行配置，但不太可能配置的區塊正好與全部閒置記憶體一樣大。
倘若在運行期間，記憶體配置程式不改變其實現法與四捨五入策略，則額外開銷和內部碎片在整個應用的生命週期期間就會保持不變。
額外開銷和內部碎片會浪費記憶體，因此是不可取的，但外部碎片才是嵌入式系統開發人員真正的敵人，造成系統失效的正是配置問題。

定義記憶體碎片的方法有幾種，其中最常用的是︰


此一方法適用於外部碎片，但也可以修改此一公式使它也可應用到內部碎片，辦法是把內部碎片加到分母中。
記憶體碎片是一個介於0和1之間的分數。一個碎片為1(100%)的系統就是把記憶體全用完了。
如果所有閒置記憶體都在一個記憶體區塊（最大記憶體區塊）中，碎片為 0%。
當所有閒置記憶體的四分之一在最大記憶體區塊中時，碎片為 75%。
舉例如下︰一個系統有5M位元組的閒置記憶體，當它可用來配置的最大記憶體區塊為50k位元組時，其記憶體碎片為99%。


圖 2: 此一案例研究把最先適合記憶體配置程式用於一個嵌入系統計畫。系統在現場測試中連續運行了兩周，然後碎片率達到99%。

這個99%記憶體碎片實例來自開發嵌入式、軟即時（soft-real-time）應用期間出現的一種真實情況。
當這種碎片程度發生一秒後，系統就崩潰了。
該系統在碎片率達到99%之前，已經進行了約兩周的連續現場測試。
這種情況是如何發生的？為什麼會發現得如此晚？當然，系統都經過測試，但測試很少超過兩個小時。
運交前的最後壓力測試持續了一個周末。
在這樣短的測試周期內未必會產生記憶體碎片的後果，所以就發生了記憶體碎片需要多長時間才會達到臨界值的問題，此一問題很難回答。
對某些應用來說，在某些情況下，系統會在用完記憶體前達到一種穩定狀態。
而對於另一些應用來說，系統則不會及時達到穩定狀態（圖 2）。
只要消除不確定性因素和風險因素，不產生碎片的記憶體配置程式（圖 3）就能快速達到一種穩定狀態，從而有助於開發人員夜晚安穩睡覺。magicalloveshe呵呵
在開發那種數月甚至數年不再重新啟動的長期運行應用時，快速收斂到穩定狀態是一個重要因素。
在比應用連續運行周期短的時間內，對應用進行適當的測試是不可少的。


圖 3: 一個不產生碎片的記憶體配置程式一旦運作過應用程式的全部，它就能達到穩定狀態。

很難確定哪種記憶體配置演算法更勝一籌，因為每種算法在不同的應用中各有所長（表 1）。
最先適合(first-fit)記憶體配置演算法是最常用的一種。它使用了四個指標（pointer）︰MSTART指向被管理記憶體的起始端；MEND指向被管理記憶體的末端；MBREAK指向 MSTART和 MEND之間已用記憶體的末端； PFREE則指向第一個閒置記憶體區塊（如果有的話）。

在系統開始運行時，PFREE為NULL，MBREAK指向 MSTART。
當一個配置請求來到時，配置程式首先檢查 PFREE有無閒置記憶體區塊。
由於PFREE為NULL，一個具有所請求儲存量加上管理標頭（header）的記憶體區塊就脫離MBREAK，然後MBREAK就更新。
此一過程將反覆進行，直至系統使一個記憶體區塊閒置，管理標頭包含有該儲存區塊的儲存量為止。
此時，PFREE透過頭上的鏈接表插入項被更新為指向該記憶體區塊，而區塊本身則用一個指向舊 PFREE內容的指標進行更新，以建立一個鏈接表。
下一次出現配置請求時，系統就會搜索閒置記憶體區塊鏈接表，尋找適合請求儲存量的第一個閒置記憶體區塊。
一旦找到合適的記憶體區塊，它將此記憶體區塊分成兩部分，一部分還給應用程式，另一部分則送回給自由表（free list）。

最先適合記憶體配置演算法實現起來簡單，而且開始時很好用。
但是，經過一段時間後，會出現如下的情況︰當系統將記憶體交給自由表時，它會從自由表的開頭部分去掉大記憶體區塊，插入剩餘的小記憶體區塊。最先適合演算法實際上成了一個排序演算法，即把所有小記憶體碎片放在自由表的開頭部分。
因此，自由表會變得很長，有幾百甚至幾千個元素。
因此，記憶體配置變得時間很長又無法預測，大記憶體區塊配置所花時間要比小記憶體區塊配置來得長。
另外，記憶體區塊的無限制拆解會使記憶體碎片的程度變高。
有些實現方法在使記憶體閒置時會將鄰近的閒置記憶體區塊連接起來。
這種方法多少有些作用，而最先適合演算法與時間共處演算法(time co-location)和空間共處演算法(spatial co-location)不同，它在使記憶體區塊閒置時，無法提高相鄰記憶體區塊同時閒置的機率。

最佳適合與最差適合配置程式
最佳適合演算法在功能上與最先適合演算法類似，不同之處是，系統在配置一個記憶體區塊時，要搜索整個自由表，尋找最接近請求儲存量的記憶體區塊。
這種搜索所花的時間要比最先適合演算法長得多，但沒有配置大小記憶體區塊所需時間的差異。最佳適合演算法產生的記憶體碎片要比最先適合演算法多，因為將小而不能使用的碎片放在自由表開頭部分的排序趨勢更為強烈。由於此一消極因素，最佳適合演算法幾乎從來沒有人採用過。

最差適合演算法也很少採用。最差適合演算法的功能與最佳適合演算法相同，不同之處是，當配置一個記憶體區塊時，系統在整個自由表中搜索與請求儲存量不匹配的記憶體區塊。這種方法比最佳適合演算法速度快，因為它產生微小而又不能使用的記憶體碎片的傾向較弱。
始終選擇最大閒置記憶體區塊，再將其分為小記憶體區塊，這樣就能提高剩餘部分大得足以供系統使用的機率。

伙伴(buddy)配置程式與本文描述的其它配置程式不同，它不能根據需要從被管理記憶體的開頭部分建立新的區塊。
它有明確的共通性，就是各個記憶體區塊可分可合，但不是任意的分與合。
每個塊都有個朋友，或叫“伙伴”，既可與之分開，又可與之結合。
伙伴配置程式把記憶體區塊存放在比鏈接表更先進的數據結構中。
這些結構常常是桶型、樹型和堆型的組合或變種。
一般來說，伙伴配置程式的工作方式是難以描述的，因為這種技術隨所選數據結構的不同而各異。
由於有各式各樣的具有已知特性之數據結構可供使用，所以伙伴配置程式得到廣泛應用。有些伙伴配置程式甚至用在原始碼中。
伙伴配置程式編寫起來常常很複雜，其性能可能各不相同。伙伴配置程式通常在某種程度上限制了記憶體碎片的發生。

固定儲存量配置程式有點像最先閒置演算法。
通常有一個以上的自由表，而且更重要的是，同一自由表中的所有記憶體區塊的儲存量都相同。
至少有四個指標︰MSTART指向被管理記憶體的起點，MEND指向被管理記憶體的末端，MBREAK指向MSTART與MEND之間已用記憶體的末端，而PFREE[n]則是指向任何閒置記憶體區塊的一排指標。
在開始時，PFREE

為 NULL，MBREAK指標為 MSTART。
當一個配置請求到來時，系統將請求的儲存量增加到可用儲存量之一。
然後，系統檢查 PFREE[增大後的儲存量]閒置記憶體區塊。
因為 PFREE[增大後的儲存量 ]為 NULL，一個具有該儲存量加上一個管理標頭的記憶體區塊就脫離MBREAK，MBREAK被更新。

這些步驟反覆進行，直到系統使一個記憶體區塊閒置為止，此時管理標頭包含有該記憶體區塊的儲存量。
當有一記憶體區塊閒置時，PFREE[相應儲存量 ]通過標頭的鏈接表插入項，更新為指向該記憶體區塊，而該記憶體區塊本身則用一個指向PFREE[相應儲存量 ]以前內容的指標來更新，以建立一個鏈接表。下一次配置請求到來時，系統將PFREE[增大的請求儲存量]鏈接表的第一個記憶體區塊送給系統。沒有理由搜索鏈接表，因為所有鏈接的記憶體區塊的儲存量都是相同的。

儲存量固定的配置程式很容易實現，而且便於計算記憶體碎片，至少在區塊儲存量的數量較少時是這樣。但這種配置程式的局限性在於要有一個它可以配置的最大儲存量。固定儲存量配置程式速度快，並可在任何狀況下保持速度。
這些配置程式可能會產生大量的內部記憶體碎片，但對某些應用而言，它們的優點會超過缺點。

減少記憶體碎片
記憶體碎片是因為在配置一個記憶體區塊後，使之閒置，但不將閒置記憶體還給最大記憶體區塊而產生的。
最後這一步很關鍵。如果記憶體配置程式是有效的，就不能阻止系統配置記憶體區塊並使之閒置。
即使一個記憶體配置程式不能保証歸還的記憶體能與最大記憶體區塊相連接（這種方法可以徹底避免記憶體碎片問題），但你可以設法控制並限制記憶體碎片。
所有這些作法涉及到記憶體區塊的分割。
每當系統減少被分割記憶體區塊的數量，確保被分割記憶體區塊盡可能大時，你就會有所改進。


表1 一般配置演算法

這樣做的目的是盡可能多次反覆使用記憶體區塊，而不要每次都對記憶體區塊進行分割，以正好符合請求的儲存量。
分割記憶體區塊會產生大量的小記憶體碎片，猶如一堆散沙。以後很難把這些散沙與其餘記憶體結合起來。
比較好的辦法是讓每個記憶體區塊中都留有一些未用的位元組。
留有多少位元組應看應用要在多大程度上避免記憶體碎片。
為小型配置增加幾個位元組的內部碎片，是朝正確方向邁出的一步。
當應用請求1位元組記憶體時，你配置的儲存量取決於該應用的行為。
如果應用的配置記憶體儲存量之主要部分是1～16位元組，則為小型配置的需求配置16位元組是明智的。
只要限制可以配置的最大記憶體區塊，你就能夠獲得較大的節約效果。
但是，這種方法的缺點是，系統會不斷地嘗試配置大於極限的記憶體區塊，這使應用可能會停止工作。
減少最大和最小記憶體區塊儲存量之間記憶體儲存量的數量也是有用的。採用按對數增大的記憶體區塊儲存量可以避免大量的碎片。
例如，每個儲存量可能都比前一個儲存量大20%。“單一儲存量符合所有需要”的作法，對於嵌入式系統中的記憶體配置程式來說可能是不切實際的。
這種方法從內部碎片來看是代價極高的，但系統可以徹底避免外部碎片，達到支持的最大儲存量。

將相鄰閒置記憶體區塊連接起來是一種可以顯著減少記憶體碎片的技術。
如果沒有此一方法，某些配置演算法（如最先適合演算法）將根本無法工作。
然而，效果是有限的，將鄰近記憶體區塊連接起來只能舒緩由於配置演算法引起的問題，而無法解決根本問題。而且，當記憶體區塊儲存量有限時，相鄰記憶體區塊連接可能很難實現。

有些記憶體配置器很先進，可以在運行時收集有關某個系統的配置習慣之統計數據，然後，按儲存量將所有的記憶體配置進行分類，例如分為小、中和大三類。
系統將每次配置指向被管理記憶體的一個區域，因為該區域包括這樣的記憶體區塊儲存量。較小儲存量是根據較大儲存量配置的。
這種方案是最先適合演算法和一組有限的固定儲存量演算法的一種有趣混合，但不是即時的。

有效地利用暫時的局限性，通常是很困難的，但值得一提的是，在記憶體中暫時擴展共處一地的配置程式更容易產生記憶體碎片。
盡管其它技術可以減輕這一問題，但限制不同儲存量記憶體區塊的數目仍是減少記憶體碎片的主要方法。

現代軟體環境業已實現各種可以避免記憶體碎片的工具。例如，專為分布式高可用性容錯系統開發的 OSE即時作業系統可提供三種運行時記憶體配置程式︰內核 alloc()，它根據系統或記憶體區塊庫（block pools）來配置；堆積（heap）malloc()，根據程式堆積來配置； OSE記憶體管理程式 alloc_region，它根據記憶體管理程式記憶體來配置。

從許多方面來看，Alloc就是終極記憶體配置程式。它產生的記憶體碎片很少，速度很快，並有判定功能。你可以調整甚至去掉記憶體碎片。只是在配置一個儲存量後，使之閒置，但不再配置時，才會產生外部碎片。內部碎片會不斷產生，但對某個給定的系統和八種儲存量來說是恆定不變的。

Alloc是一種有8個自由表的固定儲存量記憶體配置程式之實現方法。系統程式設計師可以對每一種儲存量進行配置，並可決定採用更少的儲存量來進一步減少碎片。
除開始時以外，配置記憶體區塊和使記憶體區塊閒置都是恆定時間操作。
首先，系統必須對請求的儲存量四捨五入到下一個可用儲存量。
就8種儲存量而言，此一目標可用三個if語句來實現。
其次，系統總是在8個自由表的表頭插入或刪除記憶體區塊。開始時，配置未使用的記憶體要多花幾個周期的時間，但速度仍然極快，而且所花時間恆定不變。

堆積 malloc()的記憶體開銷（8～ 16位元組/配置）比 alloc小，所以你可以停用記憶體的專用權。
malloc()配置程式平均來講是相當快的。
它的內部碎片比alloc()少，但外部碎片則比alloc()多。
它有一個最大配置儲存量，但對大多數系統來說，此一極限值夠大。
可選的共享所有權與低開銷使malloc()適用於有許多小型對象和共享對象的C++應用程式。
堆積是一種具有內部堆積數據（heap-data）結構的伙伴系統之實現方法。
在OSE中，有 28個不同的存儲量可供使用，每種儲存量都是前兩種儲存量之和，於是形成一個斐波那契（Fibonacci）序列。
實際記憶體區塊儲存量為序列數乘以16位元組，其中包括配置程式開銷或者8位元組/配置（在文件和行訊息啟用的情況下為16位元組）。

當你很少需要大的記憶體區塊時，則OSE記憶體管理程式最適用。
典型的應用要把儲存空間配置給整個系統、堆積或庫。
在有 MMU的系統中，有些實現方法使用 MMU的轉換功能來顯著降低、甚至消除記憶體碎片。
在其他情況下，OSE記憶體管理程式會產生非常多的碎片。
它沒有最大配置儲存量，而且是一種最先適合記憶體配置程式的實現方法。
記憶體配置被四捨五入到頁面的偶數──典型值是4k位元組。


作者簡介
Jan Lindblad是Enea Embedded Technology的系統設計師，他擁有瑞典斯德哥爾摩皇家技術學院（Royal Institute of Technology）的電腦科學碩士學位。

/******/
以上全部轉自
http://www.edntaiwan.com/article.asp?id=129

我發現轉過來之後字比較大，比較好閱讀= =

這篇對記憶體的控制寫的蠻深入的，也就是很難= =

不曉得linux控制記憶體的方式是不是比windows技高一籌

真有趣啊！