Buddy算法的μC/OSII高可靠內(nèi)存管理方案

3 Buddy算法簡介

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

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

圖2 Buddy算法簡介

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

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

圖3 改進(jìn)方案中的內(nèi)存管理組織結(jié)構(gòu)

② 首先初始化一個(gè)內(nèi)存控制塊結(jié)構(gòu)數(shù)組struct OS_MEM []，其下標(biāo)是內(nèi)存塊規(guī)模的對(duì)數(shù)，引入結(jié)構(gòu)數(shù)組的目的是在申請(qǐng)內(nèi)存塊時(shí)能夠快速定位，起到索引的作用。而內(nèi)存塊的實(shí)際大小為內(nèi)存塊規(guī)模與內(nèi)存塊粒度的乘積。然后將內(nèi)存塊按內(nèi)存塊規(guī)模從小到大掛到不同結(jié)構(gòu)數(shù)組指向的鏈表上，并且保證初始化后同一鏈表上的內(nèi)存塊地址不連續(xù)。在申請(qǐng)內(nèi)存塊通過內(nèi)存控制結(jié)構(gòu)數(shù)組的下標(biāo)快速定位到內(nèi)存塊鏈表，查看內(nèi)存塊控制結(jié)構(gòu)字段中OSMemFreeList成員指針是否為空。若不為空，則從表頭取一個(gè)內(nèi)存塊，并返回該內(nèi)存塊的地址；否則向后搜索數(shù)組，看是否有空閑內(nèi)存塊。若有則將該內(nèi)存塊一分為二，低地址的那塊分配給申請(qǐng)者，高地址的那塊則掛到前一個(gè)結(jié)構(gòu)數(shù)組的表頭，以備其他申請(qǐng)者申請(qǐng)。同樣，釋放內(nèi)存塊時(shí)也是通過結(jié)構(gòu)數(shù)組快速定位到具體結(jié)構(gòu)數(shù)組，然后檢查該結(jié)構(gòu)數(shù)組內(nèi)存塊鏈表中是否有和要釋放的內(nèi)存塊地址連續(xù)的內(nèi)存塊。若有，則合并兩內(nèi)存塊并掛到后一個(gè)結(jié)構(gòu)數(shù)組，并檢查地址是否連續(xù)，直至沒有為止；若無，則將該內(nèi)存塊掛到該內(nèi)存塊鏈表的表尾。改進(jìn)后的內(nèi)存管理組織結(jié)構(gòu)如圖3所示。

4.2 具體改進(jìn)措施

① 改進(jìn)函數(shù)OS_MemInit（void）。此函數(shù)原來是初始化空閑內(nèi)存控制塊鏈表，改進(jìn)后此函數(shù)用于初始化OS_MEM結(jié)構(gòu)數(shù)組即可，根據(jù)OS_CFG.H文件中宏OS_MAX_MEM_PART來決定數(shù)組元素個(gè)數(shù)。

② 改進(jìn)函數(shù)OSMemCreate（void *addr, INT32U nblks, INT32U granularity , INT8U *err）。根據(jù)Buddy的規(guī)則橫向創(chuàng)建內(nèi)存塊，每創(chuàng)建一個(gè)內(nèi)存塊就鏈到相應(yīng)的結(jié)構(gòu)體數(shù)組上，如圖3的Create Direction所示，這樣能保證每個(gè)結(jié)構(gòu)數(shù)組上的相同大小的內(nèi)存塊地址不連續(xù)，從而避免了所有內(nèi)存塊合并的現(xiàn)象。創(chuàng)建出來的內(nèi)存塊組織結(jié)構(gòu)如圖3所示。

③ 改進(jìn)函數(shù)OSMemGet（INT32U size, INT32U granularity, INT8U *err）。因?yàn)榻Y(jié)構(gòu)體數(shù)組名是在OS_CFG.H文件中宏定義的，所以本函數(shù)的參數(shù)只包括需求的內(nèi)存塊大小及內(nèi)存塊粒度即可。用內(nèi)存塊大小除以內(nèi)存塊粒度，首先判斷所得值是否為2的冪次，若是直接取對(duì)數(shù)即得結(jié)構(gòu)數(shù)組的下標(biāo)；若不是則取對(duì)數(shù)后向上取整。得到指定數(shù)組元素后若有內(nèi)存塊，取下一內(nèi)存塊然后指針下移，若無內(nèi)存塊則繼續(xù)搜索下一個(gè)結(jié)構(gòu)數(shù)組。若該數(shù)組有空閑內(nèi)存塊則取將其平分為兩塊，一塊分配出去，一塊掛到前面結(jié)構(gòu)數(shù)組鏈表。這樣一直搜索到最后一個(gè)結(jié)構(gòu)數(shù)組，若一直無內(nèi)存塊，則報(bào)錯(cuò)返回。

④ 改進(jìn)函數(shù)OSMemPut（INT32U size, INT32U granularity）。如何取得結(jié)構(gòu)數(shù)組下標(biāo)值同OSMemGet（）函數(shù)。在找到所要回收的結(jié)構(gòu)數(shù)組后，判斷該數(shù)組內(nèi)存塊鏈表上是否有與要回收的內(nèi)存塊連續(xù)的地址。若有合并且掛到下一內(nèi)存塊結(jié)構(gòu)數(shù)組內(nèi)存塊鏈表，這樣一直到最后一個(gè)結(jié)構(gòu)數(shù)組，目的是為了保證有更大的內(nèi)存塊可滿足應(yīng)用程序的申請(qǐng)，提高了內(nèi)存管理的可靠性。

在改進(jìn)以上函數(shù)的基礎(chǔ)上，還可以在申請(qǐng)內(nèi)存塊之前有選擇地使用OSMemQuery（）查詢內(nèi)存中是否有滿足需要的內(nèi)存塊。如果沒有則作好相應(yīng)的規(guī)避措施，進(jìn)一步提高內(nèi)存管理的可靠性，使系統(tǒng)更穩(wěn)定。

5 實(shí)驗(yàn)結(jié)果及性能分析

針對(duì)改進(jìn)前后μC/OSII內(nèi)存管理策略的特點(diǎn)，設(shè)計(jì)一組具有代表性的測試用例來分析μC/OSII系統(tǒng)在改進(jìn)前后內(nèi)存管理的可靠性和靈活性。實(shí)驗(yàn)環(huán)境為ARM Develop Suit V1. 2及三星公司S3C2440微控制器，由于S3C2440片內(nèi)包含MMU模塊，所以需要將協(xié)處理器CP15的C1寄存器0位置0,以禁用MMU功能。

假設(shè)兩種方案內(nèi)存初始化都創(chuàng)建了5個(gè)分區(qū)，每個(gè)分區(qū)中所含內(nèi)存塊為10個(gè)，且這5個(gè)內(nèi)存分區(qū)中的內(nèi)存塊大小依次為16 B、32 B、64 B、128 B、256 B。原方案創(chuàng)建分區(qū)時(shí)要調(diào)用5次OSMemCreate（）函數(shù)，而改進(jìn)方案只需調(diào)用一次。表1是申請(qǐng)內(nèi)存塊大小與兩種方案可以滿足的次數(shù)之間的關(guān)系。

表1 申請(qǐng)內(nèi)存塊大小與兩種方案可以滿足的次數(shù)比較

由表1的數(shù)據(jù)及圖4的對(duì)比曲線可看出，改進(jìn)方案與原方案在可用內(nèi)存完全相同的情況下，使內(nèi)存的利用率大大提高。因?yàn)榭煽啃耘c可滿足次數(shù)正相關(guān)，而可滿足次數(shù)與曲線與坐標(biāo)軸圍成的面積成正比，所以該面積與可靠性正相關(guān)。新方案曲線所圍圖形面積為12960， 而原方案曲線所圍成的圖形面積為2400。所以新方案的可靠性將比原來方案提高大約4倍，而且申請(qǐng)內(nèi)存塊越小，可滿足次數(shù)越多，提高了內(nèi)存分配的靈活性。