Buddy算法在μC/OSII動態(tài)內存管理改進方案中的應用

③ 內存塊分配函數(shù)OSMemGet（）通過從內存控制塊鏈表中找到能夠滿足自己內存塊需要的內存控制塊，然后從這個內存控制塊指向的分區(qū)鏈表首部得到自己需要的內存塊。

④ 內存塊釋放函數(shù)OSMemPut（）負責回收內存塊。當應用程序不再使用某一個內存塊時，必須及時把它釋放，并放回到相應的內存分區(qū)中。

2.2 μC/OSII內存管理方案的不足之處

如前所述，μC/OSII的內存管理方案簡短精煉，僅百余行代碼，5個函數(shù)就能勝任。然而考慮到第1節(jié)提到的嵌入式系統(tǒng)對內存管理策略的3個要求，μC/OSII的內存管理策略存在以下不足之處：

① 原μC/OSII內存管理方案可靠性不高。因為原方案中各內存分區(qū)之間是孤立的，沒有聯(lián)系。一個內存分區(qū)上的內存塊用完時，不能利用其他分區(qū)上的內存塊，而只是簡單地報錯，從而使系統(tǒng)可靠性大大降低。在內存塊大小及需求量不確定的場合，如果經常發(fā)生內存申請得不到滿足的情況，是嵌入式系統(tǒng)所不能容忍的。

② 原μC/OSII內存管理方案中內存分配不夠靈活。舉個例子來說，一個應用程序需要大小為1 KB、512 B、256 B三種內存塊，原方案有兩種解決方案，一是創(chuàng)建一個內存塊大小為1 KB的內存分區(qū)，內存塊數(shù)目至少為3個；二是創(chuàng)建3個內存分區(qū)，內存塊大小分別為1 KB、512 B、256 B。方案一創(chuàng)建了較少分區(qū)，性能有保證，但造成內存資源的浪費；方案二雖然沒有浪費內存，但卻調用3次OS_MemCreate（）函數(shù)，效率較低。

3 Buddy算法簡介

Buddy算法是內存管理的經典算法，目的是為了解決內存的外碎片問題，以及提高內存管理的可靠性。Buddy算法在Linux內核內存管理模塊得到成功的應用。

如圖2 所示，Buddy算法將所有空閑頁框分組為10個塊鏈表，每個塊鏈表的每個塊元素分別包含1、2、4、8、16、32、64、128、256、512個連續(xù)的頁框，每個塊的第一個頁框的物理地址是該塊大小的整數(shù)倍。例如，大小為4個頁框的塊，其起始地址是4×212（一個頁框的大小為4K,4個頁框的大小為4×4K,1K=1024=210，4K=212）的倍數(shù)。

圖2 Buddy算法簡介

假設要請求一個128個頁框的塊，算法先檢查128個頁框的鏈表是否有空閑塊，如果沒有則查256個頁框的鏈表，有則將256個頁框的塊分裂為兩份，一份使用，一份插入128個頁框的鏈表。如果還沒有，就查512個頁框的鏈表，有的話就分裂為128、128、256，一個128使用，剩余兩個插入對應鏈表。如果在512還沒查到，則返回出錯信號。用這種方法來分配頁框，由Linux內核的穩(wěn)定性可知其可靠性。

回收過程相反，內核試圖把大小為b的空閑伙伴合并為一個大小為2b的單獨塊，滿足以下條件的兩個塊稱為伙伴：兩個塊具有相同的大小，記做b；它們的物理地址是連續(xù)的；第一個塊的第一個頁框的物理地址是2b×212的倍數(shù)。該算法迭代，如果成功合并所釋放的塊，會試圖合并2b的塊來形成更大的塊。在本方案中，只要滿足前兩個條件就足夠了。

4 μC/OSII內存管理改進方案

4.1 改進方案思路

① 修改內存控制塊的結構OS_MEM，去掉OS_MemAddr、OS_MemNFree成員，添加一個內存塊鏈表尾指針OSMemBlkTail，所以OS_MEM結構還含有4個成員：OSMemFreeLiST、OSMemBlkSize、OSMemNBlks、OSMemBlkTail。改進后的內存控制塊結構如圖3所示。