本文使用隱式空閒鏈表實現簡單的動態內存分配。
動態內存分配器維護一個大塊區域,也就是堆,處理動態的內存分配請求。分配器將堆視為一組不同大小的塊的集合來維護,每個塊要麼是已分配的,要麼是空閒的。
實現動態內存分配要考慮以下問題:
(1)空閒塊組織:我們如何記錄空閒塊?
(2)放置:我們如何選擇一個合適的空閒塊來放置一個新分配的塊?
(3)分割:在我們將一個新分配的塊放置到某個空閒塊之後,我們如何處理這個空閒塊中的剩余部分?
(4)合並:我們如何處理一個剛剛被釋放的塊?
任何分配器都需要一些開銷,需要數據結構來記錄信息,區分塊邊界,區分已分配塊和空閒塊等。大多數實現方式都把信息放在塊本身內部。隱式空閒鏈表就是通過每個塊的頭部中存放的信息可以方便的定位到下一個塊的位置。頭部一般就是本塊的大小及使用情況(分配或空閒)。
本塊的起始地址加上本塊的大小就是下一個塊的起始地址。
本文使用的控制塊結構如下:
struct mem_block
{
int size; // 本塊的大小,包括控制結構
int is_free; // 使用情況,1為空閒,0為已分配
}
為了內存對齊,這裡is_free也是用4字節的int存儲。起始控制信息根本不需要這麼多,此處為了方便理解。
下面是一個塊的表示圖
返回給用戶的區域並不包含控制信息。
當接收到一個內存分配請求時,從頭開始遍歷堆,找到一個空閒的滿足大小要求的塊,若有剩余,將剩余部分變成一個新的空閒塊,更新相關塊的控制信息。調整起始位置,返回給用戶。
釋放內存時,僅需把使用情況標記為空閒即可。
隱式空閒鏈表的優點是簡單。顯著的缺點是任何操作的開銷,例如放置分配的塊,要求空閒鏈表的搜索與堆中已分配塊和空閒塊的總數呈線性關系。
搜索可以滿足請求的空閒塊時,常見的策略有以下幾種:
(1)首次適應法(First Fit):選擇第一個滿足要求的空閒塊
(2)最佳適應法(Best Fit):選擇滿足要求的,且大小最小的空閒塊
(3)最壞適應法(Worst Fit):選擇最大的空閒塊
(4)循環首次適應法(Next Fit):從上次分配位置開始找到第一個滿足要求的空閒塊
這裡不對各種策略的優劣進行比較了。