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

1內(nèi)存管理概述

內(nèi)存管理是操作系統(tǒng)的中心任務(wù)之一，其主要任務(wù)是組織內(nèi)存以容納內(nèi)核和待執(zhí)行程序，跟蹤當(dāng)前內(nèi)存的使用情況，在需要時(shí)為進(jìn)程分配內(nèi)存，使用完畢后釋放并回收內(nèi)存。目前嵌入式系統(tǒng)中常用的內(nèi)存管理策略主要有兩種--靜態(tài)內(nèi)存分配和動(dòng)態(tài)內(nèi)存分配。

靜態(tài)內(nèi)存分配： 編譯或鏈接時(shí)將所需內(nèi)存分配好，程序運(yùn)行起來(lái)后所分配的內(nèi)存不釋放。對(duì)于實(shí)時(shí)性和可靠性要求極高的系統(tǒng)，不允許延遲或者分配失效，必須采用靜態(tài)內(nèi)存分配的方式。

動(dòng)態(tài)內(nèi)存分配： 根據(jù)程序執(zhí)行過(guò)程中所需內(nèi)存的大小而動(dòng)態(tài)分配內(nèi)存的策略。此方案按需分配內(nèi)存，避免了靜態(tài)分配中的內(nèi)存浪費(fèi)，靈活性比較強(qiáng)，給程序的實(shí)現(xiàn)帶來(lái)了很大方便。缺點(diǎn)是容易造成內(nèi)存碎片，且容易造成程序響應(yīng)不及時(shí)等問(wèn)題。

綜上所述，靜態(tài)內(nèi)存分配和動(dòng)態(tài)內(nèi)存分配各有優(yōu)點(diǎn)，出于嵌入式系統(tǒng)可靠性、實(shí)時(shí)性及成本、功耗的考慮，如何在兩種方案中作出平衡的選擇是令嵌入式操作系統(tǒng)設(shè)計(jì)者頭疼的事。一般的嵌入式操作系統(tǒng)都是兩種方案的高效結(jié)合，μC/OSII也不例外。除此之外，嵌入式操作系統(tǒng)對(duì)內(nèi)存的分配還有以下幾點(diǎn)要求：

① 可靠性。內(nèi)存分配的請(qǐng)求必須得到滿足，如果分配失敗可能會(huì)帶來(lái)災(zāi)難性的后果。比如，航天飛機(jī)的嵌入式操作系統(tǒng)若發(fā)生內(nèi)存分配失效，損失是不可估量的。

② 快速性。嵌入式系統(tǒng)對(duì)實(shí)時(shí)性的保證，要求簡(jiǎn)單、快速地分配內(nèi)存。

③ 高效性。嵌入式系統(tǒng)中內(nèi)存是一種有限、昂貴的資源，內(nèi)存分配要盡可能地減少浪費(fèi)。

μC/OSII作為一種典型的嵌入式操作系統(tǒng)，其內(nèi)存管理同樣要滿足以上3點(diǎn)要求，下面簡(jiǎn)單介紹μC/OSII的內(nèi)存管理策略，并分析其不足之處。

2μC/OSII動(dòng)態(tài)內(nèi)存管理方案及不足

2.1μC/OSII內(nèi)存管理方案簡(jiǎn)介

μC/OS?II內(nèi)存管理模塊主要由一個(gè)數(shù)據(jù)結(jié)構(gòu)體和5個(gè)函數(shù)組成：

◆ 內(nèi)存控制塊數(shù)據(jù)結(jié)構(gòu)OS_MEM；
◆ 內(nèi)存分區(qū)創(chuàng)建函數(shù)OSMemCreate（void *addr, INT32U nblks, INT32U blksize, INT8U *err）；
◆ 內(nèi)存塊分配函數(shù)OSMemGet（OS_MEM *pmem , INT8U *err）；
◆ 內(nèi)存塊釋放函數(shù)OSMemPut（OS_MEM *pmem , void *pblk）；
◆ 內(nèi)存分區(qū)狀態(tài)查詢函數(shù)OSMemQuery（OS_MEM *pmem, OS_MEM_DATA *p_mem_data）；
◆ 內(nèi)存控制塊鏈表初始化函數(shù)OSMemInit（void）。

μC/OSII用一個(gè)內(nèi)存控制塊（OS_MEM）來(lái)管理內(nèi)存分區(qū)，主要通過(guò)以下4步來(lái)管理：

① 內(nèi)存控制塊鏈表初始化函數(shù)OSMemInit（）負(fù)責(zé)創(chuàng)建空內(nèi)存控制塊結(jié)構(gòu)的鏈表，鏈表長(zhǎng)度由內(nèi)核OS_CFG.H文件中定義的OS_MAX_MEM_PART宏確定。

② 內(nèi)存塊創(chuàng)建函數(shù)OSMemCreate（）先從空內(nèi)存控制塊結(jié)構(gòu)鏈表上獲取一個(gè)空的內(nèi)存控制根塊結(jié)構(gòu)，根據(jù)用戶需要內(nèi)存塊的大小來(lái)創(chuàng)建分區(qū)。一個(gè)分區(qū)中含有相同大小的內(nèi)存塊，各內(nèi)存塊也是通過(guò)鏈表鏈接起來(lái)，而不同分區(qū)中的內(nèi)存塊大小一般不同，如圖1所示的PartitiON # 1和Partition # 2中內(nèi)存塊的大小是不同的。

圖1μC/OSII通過(guò)內(nèi)存控制塊管理內(nèi)存

③ 內(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ù)，效率較低。

3Buddy算法簡(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ù)。

圖2Buddy算法簡(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所示。

圖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)存塊通過(guò)內(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í)也是通過(guò)結(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ù)，直至沒(méi)有為止；若無(wú)，則將該內(nèi)存塊掛到該內(nèi)存塊鏈表的表尾。改進(jìn)后的內(nèi)存管理組織結(jié)構(gòu)如圖3所示。

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

① 改進(jìn)函數(shù)OS_MemInit（void）。此函數(shù)原來(lái)是初始化空閑內(nèi)存控制塊鏈表，改進(jìn)后此函數(shù)用于初始化OS_MEM結(jié)構(gòu)數(shù)組即可，根據(jù)OS_CFG.H文件中宏OS_MAX_MEM_PART來(lái)決定數(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)建出來(lái)的內(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)存塊然后指針下移，若無(wú)內(nèi)存塊則繼續(xù)搜索下一個(gè)結(jié)構(gòu)數(shù)組。若該數(shù)組有空閑內(nèi)存塊則取將其平分為兩塊，一塊分配出去，一塊掛到前面結(jié)構(gòu)數(shù)組鏈表。這樣一直搜索到最后一個(gè)結(jié)構(gòu)數(shù)組，若一直無(wú)內(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)存塊。如果沒(mé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è)試用例來(lái)分析μ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。所以新方案的可靠性將比原來(lái)方案提高大約4倍，而且申請(qǐng)內(nèi)存塊越小，可滿足次數(shù)越多，提高了內(nèi)存分配的靈活性。

圖4兩種方案可滿足次數(shù)對(duì)比曲線

6 結(jié)語(yǔ)

本文的創(chuàng)新之處在于針對(duì)μC/OSII在內(nèi)存管理可靠性不高、內(nèi)存塊分配不夠靈活的特點(diǎn)，借鑒Buddy算法思想，對(duì)其進(jìn)行改進(jìn)，形成了一種基于Buddy算法思想、高可靠性的內(nèi)存管理策略。實(shí)驗(yàn)表明，新方案一次創(chuàng)建內(nèi)存區(qū)，即可滿足內(nèi)存塊大小需求不均勻的場(chǎng)合，既提高內(nèi)存分配的靈活性，避免了大量?jī)?nèi)碎片的產(chǎn)生，又增強(qiáng)了內(nèi)存分配的可靠性。因此，新方案在可靠性要求高的嵌入式系統(tǒng)中可以得到更好的應(yīng)用。