內(nèi)存碎片處理技術(shù)

內(nèi)存碎片是一個很棘手的問題。如何分配內(nèi)存決定著內(nèi)存碎片是否會、何時會、如何會成為一個問題。

即使在系統(tǒng)中事實上仍然有許多空閑內(nèi)存時，內(nèi)存碎片還會終導(dǎo)致出現(xiàn)內(nèi)存用完的情況。一個不斷產(chǎn)生內(nèi)存碎片的系統(tǒng)，不管產(chǎn)生的內(nèi)存碎片多么小，只要時間足夠長，就會將內(nèi)存用完。這種情況在許多嵌入式系統(tǒng)中，特別是在高可用性系統(tǒng)中是不可接受的。有些軟件環(huán)境，如 OSE 實時操作系統(tǒng)已經(jīng)備有避免內(nèi)存碎片的良好工具，但個別程序員做出的選擇仍然會對終結(jié)果形成影響。

“碎片的內(nèi)存”描述一個系統(tǒng)中所有不可用的空閑內(nèi)存。這些資源之所以仍然未被使用，是因為負(fù)責(zé)分配內(nèi)存的分配器使這些內(nèi)存無法使用。這一問題通常都會發(fā)生，原因在于空閑內(nèi)存以小而不連續(xù)方式出現(xiàn)在不同的位置。由于分配方法決定內(nèi)存碎片是否是一個問題，因此內(nèi)存分配器在保證空閑資源可用性方面扮演著重要的角色。

編譯時間與運(yùn)行時間

在許多情況下都會出現(xiàn)內(nèi)存分配問題。程序員可以通過編譯程序和鏈接程序，為結(jié)構(gòu)、并集、數(shù)組和標(biāo)量（用作局部變量、靜態(tài)變量或全局變量）方面的數(shù)據(jù)分配內(nèi)存，程序員還可以在運(yùn)行時間使用諸如 malloc()調(diào)用命令動態(tài)地分配內(nèi)存。當(dāng)用編譯程序和鏈接程序完成內(nèi)存分配功能時，就不會出現(xiàn)內(nèi)存碎片，因為編譯程序了解數(shù)據(jù)壽命。掌握可供使用的數(shù)據(jù)壽命，好處在于可以使數(shù)據(jù)以后進(jìn)先出的方式疊加起來。這樣就可以使內(nèi)存分配程序工作效率更高，而不會出現(xiàn)內(nèi)存碎片。一般來說，運(yùn)行時間內(nèi)的內(nèi)存分配是不可疊加的。內(nèi)存分配在時間上是獨(dú)立的，從而使得碎片問題難以解決。
內(nèi)存分配程序浪費(fèi)內(nèi)存的基本方式有三種：即額外開銷、內(nèi)部碎片以及外部碎片（圖 1）。內(nèi)存分配程序需要存儲一些描述其分配狀態(tài)的數(shù)據(jù)。這些存儲的信息包括任何一個空閑內(nèi)存塊的位置、大小和所有權(quán)，以及其它內(nèi)部狀態(tài)詳情。一般來說，一個運(yùn)行時間分配程序存放這些額外信息的地方是它管理的內(nèi)存。內(nèi)存分配程序需要遵循一些基本的內(nèi)存分配規(guī)則。例如，所有的內(nèi)存分配必須起始于可被 4、8 或 16 整除（視處理器體系結(jié)構(gòu)而定）的地址。內(nèi)存分配程序把僅僅預(yù)定大小的內(nèi)存塊分配給客戶，可能還有其它原因。當(dāng)某個客戶請求一個 43 字節(jié)的內(nèi)存塊時，它可能會獲得 44字節(jié)、48字節(jié) 甚至更多的字節(jié)。由所需大小四舍五入而產(chǎn)生的多余空間就叫內(nèi)部碎片。

外部碎片的產(chǎn)生是當(dāng)已分配內(nèi)存塊之間出現(xiàn)未被使用的差額時，就會產(chǎn)生外部碎片。例如，一個應(yīng)用程序分配三個連續(xù)的內(nèi)存塊，然后使中間的一個內(nèi)存塊空閑。內(nèi)存分配程序可以重新使用中間內(nèi)存塊供將來進(jìn)行分配，但不太可能分配的塊正好與全部空閑內(nèi)存一樣大。倘若在運(yùn)行期間，內(nèi)存分配程序不改變其實現(xiàn)法與四舍五入策略，則額外開銷和內(nèi)部碎片在整個系統(tǒng)壽命期間保持不變。雖然額外開銷和內(nèi)部碎片會浪費(fèi)內(nèi)存，因此是不可取的，但外部碎片才是嵌入系統(tǒng)開發(fā)人員真正的敵人，造成系統(tǒng)失效的正是分配問題。

定義內(nèi)存碎片的方法有幾種，其中常用的是：
這一方法適用于外部碎片，但可以修改這一公式使之包括內(nèi)部碎片，辦法是把內(nèi)部碎片加入到分母中。內(nèi)存碎片是一個介于 0 和 1 之間的分?jǐn)?shù)。一個碎片為 1(100%)的系統(tǒng)就是把內(nèi)存全用完了。如果所有空閑內(nèi)存都在一個內(nèi)存塊（內(nèi)存塊）中，碎片為 0%。當(dāng)所有空閑內(nèi)存的四分之一在內(nèi)存塊中時，碎片為 75%。例子如下：一個系統(tǒng)有 5M 字節(jié)的空閑內(nèi)存，當(dāng)它可用來分配的內(nèi)存塊為 50 k 字節(jié)時，其內(nèi)存碎片為99%。這個 99%內(nèi)存碎片實例來自開發(fā)嵌入式軟實時系統(tǒng)期間出現(xiàn)的一種真實情況。當(dāng)這種碎片程度發(fā)生一秒后，系統(tǒng)就崩潰了。該系統(tǒng)在碎片率達(dá)到 99% 之前，已經(jīng)進(jìn)行了約兩周的連續(xù)現(xiàn)場測試。這種情況是如何發(fā)生的？為什么會發(fā)現(xiàn)得如此晚？當(dāng)然，系統(tǒng)都經(jīng)過測試，但測試很少超過兩個小時。交付前的壓力測試持續(xù)了一個周末。在這樣短的測試周期內(nèi)未必會產(chǎn)生內(nèi)存碎片的后果，所以就發(fā)生了內(nèi)存碎片需要多長時間才會達(dá)到臨界值，這一問題很難回答。

對某些應(yīng)用來說，在某些情況下，系統(tǒng)會在用完內(nèi)存前達(dá)到一種穩(wěn)定狀態(tài)。而對于另一些應(yīng)用來說，系統(tǒng)則不會及時達(dá)到穩(wěn)定狀態(tài)（圖 2）。只要消除不確定性因素和風(fēng)險因素，不產(chǎn)生碎片的內(nèi)存分配程序（圖 3）就能快速達(dá)到一種穩(wěn)定狀態(tài)，從而有助于開發(fā)人員夜晚安穩(wěn)睡覺。在開發(fā)數(shù)月甚至數(shù)年不再重新啟動的長期運(yùn)行系統(tǒng)時，快速收斂到穩(wěn)定狀態(tài)是一個重要因素。在比系統(tǒng)連續(xù)運(yùn)行周期短的時間內(nèi)，對系統(tǒng)進(jìn)行適當(dāng)?shù)臏y試，這是必不可少的。
很難確定哪種內(nèi)存分配算法更勝一籌，因為每種算法在不同的應(yīng)用中各有所長（表 1）。適合內(nèi)存分配算法是常用的一種。它使用了四個指針：MSTART 指向被管理內(nèi)存的始端；MEND 指向被管理內(nèi)存的末尾；MBREAK 指向 MSTART 和 MEND 之間已用內(nèi)存的末端； PFREE 則指向個空閑內(nèi)存塊（如果有的話）。
在系統(tǒng)開始運(yùn)行時，PFREE 為 NULL，MBREAK 指向 MSTART。當(dāng)一個分配請求來到時，分配程序首先檢查 PFREE有無空閑內(nèi)存塊。由于 PFREE 為 NULL，一個具有所請求存儲量加上管理標(biāo)題的內(nèi)存塊就脫離 MBREAK ，然后MBREAK就更新。這一過程反復(fù)進(jìn)行，直至系統(tǒng)使一個內(nèi)存塊空閑，管理標(biāo)題包含有該存儲塊的存儲量為止。此時，PFREE 通過頭上的鏈接表插入項被更新為指向該內(nèi)存塊，而塊本身則用一個指向舊 PFREE 內(nèi)容的指針進(jìn)行更新，以建立一個鏈接表。下出現(xiàn)分配請求時，系統(tǒng)就會搜索空閑內(nèi)存塊鏈接表，尋找適合請求存儲量的個空閑內(nèi)存塊。一旦找到合適的內(nèi)存塊，它將此內(nèi)存塊分成兩部分，一部分返還給系統(tǒng)，另一部分則送回給自由表。

適合內(nèi)存分配算法實現(xiàn)起來簡單，而且開始時很好用。但是，經(jīng)過一段時間后，會出現(xiàn)如下的情況：當(dāng)系統(tǒng)將內(nèi)存交給自由表時，它會從自由表的開頭部分去掉大內(nèi)存塊，插入剩余的小內(nèi)存塊。適合算法實際上成了一個排序算法，即把所有小內(nèi)存碎片放在自由表的開頭部分。因此，自由表會變得很長，有幾百甚至幾千個元素。因此，內(nèi)存分配變得時間很長又無法預(yù)測，大內(nèi)存塊分配所花時間要比小內(nèi)存塊分配來得長。另外，內(nèi)存塊的無限制拆分使內(nèi)存碎片程度很高。有些實現(xiàn)方法在使內(nèi)存空閑時會將鄰近的空閑內(nèi)存塊連接起來。這種方法多少有些作用，而適合算法與時間共處算法(time co-location)和空間共處算法(spatial co-location)不同，它在使內(nèi)存塊空閑時，無法提高相鄰內(nèi)存塊同時空閑的概率。

適合與差適合分配程序

適合算法在功能上與適合算法類似，不同之處是，系統(tǒng)在分配一個內(nèi)存塊時，要搜索整個自由表，尋找接近請求存儲量的內(nèi)存塊。這種搜索所花的時間要比適合算法長得多，但不存在分配大小內(nèi)存塊所需時間的差異。適合算法產(chǎn)生的內(nèi)存碎片要比適合算法多，因為將小而不能使用的碎片放在自由表開頭部分的排序趨勢更為強(qiáng)烈。由于這一消極因素，適合算法幾乎從來沒有人采用過。

差適合算法也很少采用。差適合算法的功能與適合算法相同，不同之處是，當(dāng)分配一個內(nèi)存塊時，系統(tǒng)在整個自由表中搜索與請求存儲量不匹配的內(nèi)存快。這種方法比適合算法速度快，因為它產(chǎn)生微小而又不能使用的內(nèi)存碎片的傾向較弱。始終選擇空閑內(nèi)存塊，再將其分為小內(nèi)存塊，這樣就能提高剩余部分大得足以供系統(tǒng)使用的概率。

伙伴(buddy)分配程序與本文描述的其它分配程序不同，它不能根據(jù)需要從被管理內(nèi)存的開頭部分創(chuàng)建新內(nèi)存。它有明確的共性，就是各個內(nèi)存塊可分可合，但不是任意的分與合。每個塊都有個朋友，或叫“伙伴”，既可與之分開，又可與之結(jié)合?；锇榉峙涑绦虬褍?nèi)存塊存放在比鏈接表更先進(jìn)的數(shù)據(jù)結(jié)構(gòu)中。這些結(jié)構(gòu)常常是桶型、樹型和堆型的組合或變種。一般來說，伙伴分配程序的工作方式是難以描述的，因為這種技術(shù)隨所選數(shù)據(jù)結(jié)構(gòu)的不同而各異。由于有各種各樣的具有已知特性的數(shù)據(jù)結(jié)構(gòu)可供使用，所以伙伴分配程序得到廣泛應(yīng)用。有些伙伴分配程序甚至用在源碼中?；锇榉峙涑绦蚓帉懫饋沓３：軓?fù)雜，其性能可能各不相同?；锇榉峙涑绦蛲ǔＴ谀撤N程度上限制內(nèi)存碎片。

固定存儲量分配程序有點(diǎn)像空閑算法。通常有一個以上的自由表，而且更重要的是，同一自由表中的所有內(nèi)存塊的存儲量都相同。至少有四個指針：MSTART 指向被管理內(nèi)存的起點(diǎn)，MEND 指向被管理內(nèi)存的末端，MBREAK 指向 MSTART 與 MEND 之間已用內(nèi)存的末端，而 PFREE[n] 則是指向任何空閑內(nèi)存塊的一排指針。

在開始時，PFREE[*] 為 NULL，MBREAK 指針為 MSTART。當(dāng)一個分配請求到來時，系統(tǒng)將請求的存儲量增加到可用存儲量之一。然后，系統(tǒng)檢查 PFREE[ 增大后的存儲量 ] 空閑內(nèi)存塊。因為 PFREE[ 增大后的存儲量 ] 為 NULL，一個具有該存儲量加上一個管理標(biāo)題的內(nèi)存塊就脫離 MBREAK，MBREAK 被更新。

這些步驟反復(fù)進(jìn)行，直至系統(tǒng)使一個內(nèi)存塊空閑為止，此時管理標(biāo)題包含有該內(nèi)存塊的存儲量。當(dāng)有一內(nèi)存塊空閑時，PFREE[ 相應(yīng)存儲量 ] 通過標(biāo)題的鏈接表插入項更新為指向該內(nèi)存塊，而該內(nèi)存塊本身則用一個指向 PFREE[ 相應(yīng)存儲量 ] 以前內(nèi)容的指針來更新，以建立一個鏈接表。下分配請求到來時，系統(tǒng)將 PFREE[ 增大的請求存儲量 ] 鏈接表的個內(nèi)存塊送給系統(tǒng)。沒有理由搜索鏈接表，因為所有鏈接的內(nèi)存塊的存儲量都是相同的。

固定存儲量分配程序很容易實現(xiàn)，而且便于計算內(nèi)存碎片，至少在塊存儲量的數(shù)量較少時是這樣。但這種分配程序的局限性在于要有一個它可以分配的存儲量。固定存儲量分配程序速度快，并可在任何狀況下保持速度。這些分配程序可能會產(chǎn)生大量的內(nèi)部內(nèi)存碎片，但對某些系統(tǒng)而言，它們的優(yōu)點(diǎn)會超過缺點(diǎn)。

減少內(nèi)存碎片

內(nèi)存碎片是因為在分配一個內(nèi)存塊后，使之空閑，但不將空閑內(nèi)存歸還給內(nèi)存塊而產(chǎn)生的。這一步很關(guān)鍵。如果內(nèi)存分配程序是有效的，就不能阻止系統(tǒng)分配內(nèi)存塊并使之空閑。即使一個內(nèi)存分配程序不能保證返回的內(nèi)存能與內(nèi)存塊相連接（這種方法可以徹底避免內(nèi)存碎片問題），但你可以設(shè)法控制并限制內(nèi)存碎片。所有這些作法涉及到內(nèi)存塊的分割。每當(dāng)系統(tǒng)減少被分割內(nèi)存塊的數(shù)量，確保被分割內(nèi)存塊盡可能大時，你就會有所改進(jìn)。

這樣做的目的是盡可能多次反復(fù)使用內(nèi)存塊，而不要每次都對內(nèi)存塊進(jìn)行分割，以正好符合請求的存儲量。分割內(nèi)存塊會產(chǎn)生大量的小內(nèi)存碎片，猶如一堆散沙。以后很難把這些散沙與其余內(nèi)存結(jié)合起來。比較好的辦法是讓每個內(nèi)存塊中都留有一些未用的字節(jié)。留有多少字節(jié)應(yīng)看系統(tǒng)要在多大程度上避免內(nèi)存碎片。對小型系統(tǒng)來說，增加幾個字節(jié)的內(nèi)部碎片是朝正確方向邁出的一步。當(dāng)系統(tǒng)請求1字節(jié)內(nèi)存時，你分配的存儲量取決于系統(tǒng)的工作狀態(tài)。

如果系統(tǒng)分配的內(nèi)存存儲量的主要部分是 1 ～ 16 字節(jié)，則為小內(nèi)存也分配 16 字節(jié)是明智的。只要限制可以分配的內(nèi)存塊，你就能夠獲得較大的節(jié)約效果。但是，這種方法的缺點(diǎn)是，系統(tǒng)會不斷地嘗試分配大于極限的內(nèi)存塊，這使系統(tǒng)可能會停止工作。減少和內(nèi)存塊存儲量之間內(nèi)存存儲量的數(shù)量也是有用的。采用按對數(shù)增大的內(nèi)存塊存儲量可以避免大量的碎片。例如，每個存儲量可能都比前一個存儲量大 20%。在嵌入式系統(tǒng)中采用“一種存儲量符合所有需要”對于嵌入式系統(tǒng)中的內(nèi)存分配程序來說可能是不切實際的。這種方法從內(nèi)部碎片來看是代價極高的，但系統(tǒng)可以徹底避免外部碎片，達(dá)到支持的存儲量。

將相鄰空閑內(nèi)存塊連接起來是一種可以顯著減少內(nèi)存碎片的技術(shù)。如果沒有這一方法，某些分配算法（如適合算法）將根本無法工作。然而，效果是有限的，將鄰近內(nèi)存塊連接起來只能緩解由于分配算法引起的問題，而無法解決根本問題。而且，當(dāng)內(nèi)存塊存儲量有，相鄰內(nèi)存塊連接可能很難實現(xiàn)。

有些內(nèi)存分配器很先進(jìn)，可以在運(yùn)行時收集有關(guān)某個系統(tǒng)的分配習(xí)慣的統(tǒng)計數(shù)據(jù)，然后，按存儲量將所有的內(nèi)存分配進(jìn)行分類，例如分為小、中和大三類。系統(tǒng)將每次分配指向被管理內(nèi)存的一個區(qū)域，因為該區(qū)域包括這樣的內(nèi)存塊存儲量。較小存儲量是根據(jù)較大存儲量分配的。這種方案是適合算法和一組有限的固定存儲量算法的一種有趣的混合，但不是實時的。

有效地利用暫時的局限性通常是很困難的，但值得一提的是，在內(nèi)存中暫時擴(kuò)展共處一地的分配程序更容易產(chǎn)生內(nèi)存碎片。盡管其它技術(shù)可以減輕這一問題，但限制不同存儲量內(nèi)存塊的數(shù)目仍是減少內(nèi)存碎片的主要方法。

現(xiàn)代軟件環(huán)境業(yè)已實現(xiàn)各種避免內(nèi)存碎片的工具。例如，專為分布式高可用性容錯系統(tǒng)開發(fā)的 OSE 實時操作系統(tǒng)可提供三種運(yùn)行時內(nèi)存分配程序：內(nèi)核 alloc()，它根據(jù)系統(tǒng)或內(nèi)存塊池來分配；堆 malloc()，根據(jù)程序堆來分配； OSE 內(nèi)存管理程序 alloc_region，它根據(jù)內(nèi)存管理程序內(nèi)存來分配。

從 許多方面來看，Alloc就是內(nèi)存分配程序。它產(chǎn)生的內(nèi)存碎片很少，速度很快，并有判定功能。你可以調(diào)整甚至去掉內(nèi)存碎片。只是在分配一個存儲量后，使之空閑，但不再分配時，才會產(chǎn)生外部碎片。內(nèi)部碎片會不斷產(chǎn)生，但對某個給定的系統(tǒng)和八種存儲量來說是恒定不變的。

Alloc 是一種有八個自由表的固定存儲量內(nèi)存分配程序的實現(xiàn)方法。系統(tǒng)程序員可以對每一種存儲量進(jìn)行配置，并可決定采用更少的存儲量來進(jìn)一步減少碎片。除開始時以外，分配內(nèi)存塊和使內(nèi)存塊空閑都是恒定時間操作。首先，系統(tǒng)必須對請求的存儲量四舍五入到下一個可用存儲量。就八種存儲量而言，這一目標(biāo)可用三個 如果 語句來實現(xiàn)。其次，系統(tǒng)總是在八個自由表的表頭插入或刪除內(nèi)存塊。開始時，分配未使用的內(nèi)存要多花幾個周期的時間，但速度仍然極快，而且所花時間恒定不變。

堆 malloc() 的內(nèi)存開銷（8 ～ 16 字節(jié)/分配）比 alloc小，所以你可以停用內(nèi)存的專用權(quán)。malloc() 分配程序平均來講是相當(dāng)快的。它的內(nèi)部碎片比alloc()少，但外部碎片則比alloc()多。它有一個分配存儲量，但對大多數(shù)系統(tǒng)來說，這一極限值足夠大?？蛇x的共享所有權(quán)與低開銷使 malloc() 適用于有許多小型對象和共享對象的 C++ 應(yīng)用程序。堆是一種具有內(nèi)部堆數(shù)據(jù)結(jié)構(gòu)的伙伴系統(tǒng)的實現(xiàn)方法。在 OSE 中，有 28 個不同的存儲量可供使用，每種存儲量都是前兩種存儲量之和，于是形成一個斐波那契（Fibonacci）序列。實際內(nèi)存塊存儲量為序列數(shù)乘以 16 字節(jié)，其中包括分配程序開銷或者 8 字節(jié)/分配（在文件和行信息啟用的情況下為 16 字節(jié)）。

當(dāng)你很少需要大塊內(nèi)存時，則OSE內(nèi)存管理程序適用。典型的系統(tǒng)要把存儲空間分配給整個系統(tǒng)、堆或庫。在有 MMU 的系統(tǒng)中，有些實現(xiàn)方法使用 MMU 的轉(zhuǎn)換功能來顯著降低甚至消除內(nèi)存碎片。在其他情況下，OSE 內(nèi)存管理程序會產(chǎn)生非常多的碎片。它沒有分配存儲量，而且是一種適合內(nèi)存分配程序的實現(xiàn)方法。內(nèi)存分配被四舍五入到頁面的偶數(shù)——典型值是 4 k 字節(jié)。