從需求反推設計方案，假如讓你設計嵌入式系統的內存管理，你怎么設計？

最簡單的，用一個雙鏈表控制，所有已分配和未分配的內存用兩個雙鏈表標志：

單鏈表查詢時間復雜度不穩定，當空閑塊個數為n時，搜索復雜度在O（n）級別。而對內存塊大小進行分類，采用分級空閑塊鏈表可以優化空閑塊檢索的復雜度查詢復雜度大概降到O（log（n））級別。

以2的等次冪劃分大小可以使用位運算方便計算區間。另外可以根據系統的具體使用場景，如小內存分配比較多，可以在小內存大小上進行細粒度劃分，而大內存粗粒度。

分塊方式有了，那么如何按照內存大小進行分級呢，這就得用到位圖bitmap了。

ucos系統的TLSF分配算法采用兩級位圖來管理空閑空間，第一級位圖表示粗粒度范圍，假定內存最低從2^4（16字節）大小分配，那么第一個位可以管理16~32字節區間。如果不使用超過64k大小空間，一般到2^15就夠了。

第二級位圖是個二維鏈表數組，將一級位圖的每個區間等分成四個區間（也可細化為8、16個區間）。

第三部分才是真正的可分配內存。注意，每塊可分配內存首部都有個固定的頭部，用于記錄該塊的具體信息，實際返回給用戶的指針是加上了頭部偏移的。

分配流程

在位圖中搜索合適的空閑塊大小范圍，找到freelist頭指針；基于頭指針檢索list分配空閑塊并交給用戶。

具體點，比如我需要分配113字節大小內存，怎么知道對應的一二級索引值呢？

根據二進制最高位找到一級位圖位置，根據后面兩位找到二級位圖位置。

這是最基礎的思路，因為仍然需要查找二級位圖上掛載的鏈表，時間復雜度仍然為Ologn。一種優化方法是通過允許少量碎片換取O1的時間復雜度。仍以113大小為例，不是搜索【64，128】這個區間，而是向上大一個區間，從【128，256】這個區間內搜索，好處是該區間每一塊內存塊都滿足需求，直接找到最小的即可。

釋放流程

將需要釋放的內存塊標記為空閑內存，然后查找與前后相鄰的空閑塊合并，將合并后的空閑內存掛在位圖數組里。這里可以看到釋放時需要確認前后內存塊是否空閑，這個信息保存在首部，具體內存塊設計方法如下圖：

結合前面任務調度的分析，可以看到位圖和鏈表數組就能夠實現基本的嵌入式操作系統功能了。

嵌入式系統中使用位圖的優勢比較顯著：

節省存儲空間：用1bit來表示某個區間范圍大小的空閑塊是否存在；

位操作速度快：部分體系結構有加速特殊位操作的匯編指令如CLZ指令，編譯器對位操作優化比較深。

Java技術棧的同學對鏈表數組的優勢比較了解，hashmap就是鏈表數組+紅黑樹的構造。

另外需要注意，所有起始地址都需要四字節對齊。

這里所說的內存分配都是用戶態的，那么內存初始化時起始地址和內存大小如何確定呢？起始地址就是HEAP_ADDR_START，內存大小就是heap大小。這個就涉及到程序對于嵌入式系統空間與地址分配了。詳情參考前文：代碼是如何編譯成程序的？？可以先學習簡單的連接腳本，感興趣的參考《程序員的自我修養—鏈接、裝載與庫》第4.6節鏈接過程控制。不考慮可執行文件從flash到RAM的搬運，大致空間分配如下圖：

因此在連接腳本中BSS段末尾和stack底部地址就決定了用戶態內存的位置和大小。
?責任編輯人：CC