[科普中國]-內存碎片

產生

內存分配有靜態(tài)分配和動態(tài)分配兩種。
靜態(tài)分配在程序編譯鏈接時分配的大小和使用壽命就已經確定，而應用上要求操作系統(tǒng)可以提供給進程運行時申請和釋放任意大小內存的功能，這就是內存的動態(tài)分配。
因此動態(tài)分配將不可避免會產生內存碎片的問題，那么什么是內存碎片？內存碎片即“碎片的內存”描述一個系統(tǒng)中所有不可用的空閑內存，這些碎片之所以不能被使用，是因為負責動態(tài)分配內存的分配算法使得這些空閑的內存無法使用，這一問題的發(fā)生，原因在于這些空閑內存以小且不連續(xù)方式出現(xiàn)在不同的位置。因此這個問題的或大或小取決于內存管理算法的實現(xiàn)上。

為什么會產生這些小且不連續(xù)的空閑內存碎片呢？

實際上這些空閑內存碎片存在的方式有兩種：a.內部碎片 b.外部碎片 。
內部碎片的產生：因為所有的內存分配必須起始于可被 4、8 或 16 整除（視處理器體系結構而定）的地址或者因為MMU的分頁機制的限制，決定內存分配算法僅能把預定大小的內存塊分配給客戶。假設當某個客戶請求一個 43 字節(jié)的內存塊時，因為沒有適合大小的內存，所以它可能會獲得 44字節(jié)、48字節(jié)等稍大一點的字節(jié)，因此由所需大小四舍五入而產生的多余空間就叫內部碎片。
外部碎片的產生： 頻繁的分配與回收物理頁面會導致大量的、連續(xù)且小的頁面塊夾雜在已分配的頁面中間，就會產生外部碎片。假設有一塊一共有100個單位的連續(xù)空閑內存空間，范圍是0~99。如果你從中申請一塊內存，如10個單位，那么申請出來的內存塊就為0~9區(qū)間。這時候你繼續(xù)申請一塊內存，比如說5個單位大，第二塊得到的內存塊就應該為10~14區(qū)間。如果你把第一塊內存塊釋放，然后再申請一塊大于10個單位的內存塊，比如說20個單位。因為剛被釋放的內存塊不能滿足新的請求，所以只能從15開始分配出20個單位的內存塊。現(xiàn)在整個內存空間的狀態(tài)是0~9空閑，10~14被占用，15~24被占用，25~99空閑。其中0~9就是一個內存碎片了。如果10~14一直被占用，而以后申請的空間都大于10個單位，那么0~9就永遠用不上了，變成外部碎片。1

分類內存碎片分為：內部碎片和外部碎片。

內部碎片內部碎片就是已經被分配出去（能明確指出屬于哪個進程）卻不能被利用的內存空間；

內部碎片是處于區(qū)域內部或頁面內部的存儲塊。占有這些區(qū)域或頁面的進程并不使用這個存儲塊。而在進程占有這塊存儲塊時，系統(tǒng)無法利用它。直到進程釋放它，或進程結束時，系統(tǒng)才有可能利用這個存儲塊。

單道連續(xù)分配只有內部碎片。多道固定連續(xù)分配既有內部碎片，又有外部碎片。

外部碎片外部碎片指的是還沒有被分配出去（不屬于任何進程），但由于太小了無法分配給申請內存空間的新進程的內存空閑區(qū)域。

外部碎片是出于任何已分配區(qū)域或頁面外部的空閑存儲塊。這些存儲塊的總和可以滿足當前申請的長度要求，但是由于它們的地址不連續(xù)或其他原因，使得系統(tǒng)無法滿足當前申請。

多道可變連續(xù)分配只有外部碎片2。

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

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

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

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

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

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

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

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

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

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

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