我們在前面的章節中已經詳細介紹了堆在進程中的地址空間是如何分佈的,對於程式來說,堆空間只是程式向操作系統申請划出來的一大塊地址空間。而程式在通過 malloc申請 記憶體空間時的大小卻是不一定的,從數個字到數個GB都是有可能的。於是我們必須將堆空間管理起來,將它分塊地按照用戶需求出售給最終的程式,並且 ...
我們在前面的章節中已經詳細介紹了堆在進程中的地址空間是如何分佈的,對於程式來說,堆空間只是程式向操作系統申請划出來的一大塊地址空間。而程式在通過 malloc申請
記憶體空間時的大小卻是不一定的,從數個字到數個GB都是有可能的。於是我們必須將堆空間管理起來,將它分塊地按照用戶需求出售給最終的程式,並且還可以按照一定的方式收回記憶體。其實這個問題可以歸結為:如何管理一大塊連續的記憶體空間,能夠按照需求分配、釋放其中的空間,這就是堆分配的演算法。堆的分配演算法有很多種,有很簡單的(比如這裡要介紹的幾種方法),也有些很複雜、適用於某些高性能或者有其他特殊要求的場合.
1. 空閑鏈表
空閑鏈表( Free List)的方法實際上就是把堆中各個空閑的塊按照鏈表的方式連接起來,當用戶請求一塊空間時,可以遍歷整個列表,直到找到合適大小的塊並且將它拆分;當用戶釋放空間時將它合併到空閑鏈表中。
我們首先需要一個數據結構來登記堆空間里所有的空閑空間,這樣才能知道程式請求空間的時候該分配給它哪一塊記憶體。這樣的結構有很多種,這裡介紹最簡單的一種空閑鏈表空閑鏈表是這樣一種結構,在堆里的每一個空閑空間的開頭(或結尾)有一個頭( header),頭結構里記錄了上一個(prev)和下一個(next)空閑塊的地址,也就是說,所有的空閑塊形成了一個鏈表。如圖10-15所示
在這樣結構下如何分配空間呢？
首先在空閑鏈表中查找足夠容納大小的一個空閑塊，然後將這個塊分為兩個部分，一部分為程式請求的空間，另一部分為剩餘的空閑空間。下麵將鏈表裡對應的原來的空閑塊的結構更新為新的剩下來的空閑塊，如果剩下的空閑塊大小為0，則直接將這個結構從鏈表裡刪除。圖10-16演示了用戶請求了一塊和空閑塊2恰好相等的記憶體空間的堆的狀態
這樣的空閑鏈表實現儘管簡單,但在釋放空間的時候,給定一個已分配塊的指針,堆無法確定這個塊的大小。一個簡單的解決方法是當用戶請求k個位元組空間的時候,我們實際分配k+4個位元組,這4個位元組用於存儲該分配的大小,即k+4。這樣釋放該記憶體的時候只要看看這4個位元組的值,就能知道該記憶體塊的大小,然後將其插入到空閑鏈表裡就可以了。
當然這僅僅是最簡單的一種分配策略,這樣的思路存在很多問題。例如,一旦鏈表被破壞,或者記錄長度的那4位元組被破壞,整個堆就無法正常工作,而這些數據恰恰很容易被越界讀寫所接觸到
2. 點陣圖
針對空閑鏈表的弊端,另一種分配方式顯得更加穩健。這種方式稱為點陣圖( Bitmap),其核心思想是將整個堆劃分為大量的塊( block),每個塊的大小相同。當用戶請求記憶體的時候,總是分配整數個塊的空間給用戶,第一個塊我們稱為已分配區域的頭(Head),其餘的稱為己分配區域的主體(Body)。而我們可以使用一個整數數組來記錄塊的使用情況,由於每個塊只有頭/主體空閑三種狀態,因此僅僅需要兩位即可表示一個塊,因此稱為點陣圖。
Q&A
假設堆的大小為1MB,那麼我們讓一個塊大小為128位元組,那麼總共就有1M/128=8k個塊,可以用8k/(32/2)=512個int來存儲。這有512個int的數組就是一個點陣圖,其中每兩位代表一個塊。當用戶請求300位元組的記憶體時,堆分配給用戶3個塊,並將點陣圖的相應位置
標記為頭或軀體。
圖10-17為一個這樣的堆的實例
這個堆分配了3片記憶體，分別有2/4/1個塊，用虛線框標出。其對應的點陣圖將是：
(HIGH) 11 00 00 10 10 10 11 00 00 00 00 00 00 00 10 11 (LOW)
其中11表示H（HEAD），10表示主體（Body），00表示空閑（Free）
這樣的實現方式有幾個優點：
- 速度快：由於整個堆的空閑信息存儲在一個數組內，因此訪問該數組時cache容易命中；
- 穩定性好：為了避免用戶越界讀寫破壞數據，我們只須簡單備份一下點陣圖即可，而且即使部分數據被破壞，也不會導致整個堆無法工作
- 塊也不需要額外信息，易於管理
當然缺點也是顯而易見的
- 分配記憶體的時候容易產生碎片。例如分配300位元組的時候，實際分配了3塊即384個位元組，浪費了84個位元組
- 如果堆很大，或者設定的一個塊很小（這樣可以減少碎片），那麼點陣圖將會很大，可能會失去cache命中率很高的優勢，而且也會浪費一定的空間。針對這種情況，我們可以使用多級的點陣圖。
3. 對象池
以上介紹的堆管理方法是最為基本的兩種,實際上在一些場合,被分配對象的大小是較為固定的幾個值,這時候我們可以針對這樣的特征設計一個更為高效的堆演算法,稱為對象池。
對象池的思路很簡單,如果每一次分配的空間大小都一樣,那麼就可以按照這個每次請求分配的大小作為一個單位,把整個堆空間劃分為大量的小塊,每次請求的時候只需要找到個小塊就可以了
對象池的管理方法可以採用空閑鏈表,也可以採用點陣圖,與它們的區別僅僅在於它假定了每次請求的都是一個固定的大小,因此實現起來很容易。由於每次總是只請求一個單位的記憶體,因此請求得到滿足的速度非常快,無須查找一個足夠大的空間。
實際上很多現實應用中,堆的分配演算法往往是採取多種演算法複合而成的。比如對於 glibc來說,它對於小於64位元組的空間申請是採用類似於對象池的方法;而對於大於512位元組的空間申請採用的是最佳適配演算法:對於大於64位元組而小於512位元組的,它會根據情況採取上述方法中的最佳折中策略:對於大於128KB的申請,它會使用mmap機制直接向操作系統申請空間。
