Buddy算法在μC/OSII動(dòng)態(tài)內(nèi)存管理改進(jìn)方案中的應(yīng)用

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

④ 內(nèi)存塊釋放函數(shù)OSMemPut（）負(fù)責(zé)回收內(nèi)存塊。當(dāng)應(yīng)用程序不再使用某一個(gè)內(nèi)存塊時(shí)，必須及時(shí)把它釋放，并放回到相應(yīng)的內(nèi)存分區(qū)中。

2.2 μC/OSII內(nèi)存管理方案的不足之處

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

① 原μC/OSII內(nèi)存管理方案可靠性不高。因?yàn)樵桨钢懈鲀?nèi)存分區(qū)之間是孤立的，沒(méi)有聯(lián)系。一個(gè)內(nèi)存分區(qū)上的內(nèi)存塊用完時(shí)，不能利用其他分區(qū)上的內(nèi)存塊，而只是簡(jiǎn)單地報(bào)錯(cuò)，從而使系統(tǒng)可靠性大大降低。在內(nèi)存塊大小及需求量不確定的場(chǎng)合，如果經(jīng)常發(fā)生內(nèi)存申請(qǐng)得不到滿足的情況，是嵌入式系統(tǒng)所不能容忍的。

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

3 Buddy算法簡(jiǎn)介

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

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

圖2 Buddy算法簡(jiǎn)介

假設(shè)要請(qǐng)求一個(gè)128個(gè)頁(yè)框的塊，算法先檢查128個(gè)頁(yè)框的鏈表是否有空閑塊，如果沒(méi)有則查256個(gè)頁(yè)框的鏈表，有則將256個(gè)頁(yè)框的塊分裂為兩份，一份使用，一份插入128個(gè)頁(yè)框的鏈表。如果還沒(méi)有，就查512個(gè)頁(yè)框的鏈表，有的話就分裂為128、128、256，一個(gè)128使用，剩余兩個(gè)插入對(duì)應(yīng)鏈表。如果在512還沒(méi)查到，則返回出錯(cuò)信號(hào)。用這種方法來(lái)分配頁(yè)框，由Linux內(nèi)核的穩(wěn)定性可知其可靠性。

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

4 μC/OSII內(nèi)存管理改進(jìn)方案

4.1 改進(jìn)方案思路

① 修改內(nèi)存控制塊的結(jié)構(gòu)OS_MEM，去掉OS_MemAddr、OS_MemNFree成員，添加一個(gè)內(nèi)存塊鏈表尾指針OSMemBlkTail，所以O(shè)S_MEM結(jié)構(gòu)還含有4個(gè)成員：OSMemFreeLiST、OSMemBlkSize、OSMemNBlks、OSMemBlkTail。改進(jìn)后的內(nèi)存控制塊結(jié)構(gòu)如圖3所示。