雖然大部分系統(tǒng)都有提供內(nèi)存動(dòng)態(tài)分配和釋放函數(shù)（即C語(yǔ)言中的malloc和free函數(shù)），但是在嵌入式開(kāi)發(fā)中由于系統(tǒng)的限制往往需要自己來(lái)實(shí)現(xiàn)內(nèi)存管理，如在有些平臺(tái)上可動(dòng)態(tài)申請(qǐng)的最大空間不能滿(mǎn)足程序設(shè)計(jì)的需要，有些系統(tǒng)提供的內(nèi)存分配和釋放函數(shù)會(huì)造成大量的內(nèi)存碎片導(dǎo)致內(nèi)存不夠用，在這些時(shí)候往往就需要自己先申請(qǐng)一塊較大的內(nèi)存，然后在這個(gè)較大的內(nèi)存中進(jìn)行重新分配，即做一套獨(dú)立的內(nèi)存管理程序。其實(shí)自己設(shè)計(jì)一個(gè)內(nèi)存管理程序有如下幾個(gè)好處： 1、便于對(duì)程序在運(yùn)行中對(duì)內(nèi)存的使用情況進(jìn)行監(jiān)測(cè)，如是否有內(nèi)存泄漏，內(nèi)存使用的峰值等； 2、防止因程序設(shè)計(jì)不當(dāng)（如指針越界、野指針）造成對(duì)系統(tǒng)的破壞，便于界定問(wèn)題出現(xiàn)的范圍； 3、通過(guò)優(yōu)化內(nèi)存管理算法可以自行減少內(nèi)存碎片； 4、便于程序移植，在程序移植到不同平臺(tái)時(shí)可以不用考慮系統(tǒng)的內(nèi)存管理情況，只須考慮能否得到大塊內(nèi)存即可。 關(guān)于內(nèi)存的分配和釋放方法也許有很多方法可以采用，這里提出一個(gè)利用二叉樹(shù)的思想來(lái)管理內(nèi)存。二叉樹(shù)是一種常用的數(shù)據(jù)結(jié)構(gòu)，被運(yùn)用到很多種算法中，二叉樹(shù)的定義在這里就不再做贅述了，其從形態(tài)上可以看出二叉樹(shù)主要特點(diǎn)是：二叉樹(shù)中每一個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)且最多有一個(gè)父結(jié)點(diǎn)。內(nèi)存的分配即是對(duì)一個(gè)較大的內(nèi)存塊分割成幾個(gè)較小的內(nèi)存塊，一般采用的方法是以2的冪次作為塊的大小（即內(nèi)存粒度），當(dāng)要分配的內(nèi)存大小不等于所設(shè)定的內(nèi)存粒度時(shí)則找一個(gè)最靠近這個(gè)大小且比它大的粒度來(lái)分配，這種分配方法完全可以用一個(gè)二叉樹(shù)的形式來(lái)表示，如下圖： 上圖是從一個(gè)1KB的內(nèi)存空間中分配出64字節(jié)的情況，葉子結(jié)點(diǎn)表示被分割出來(lái)的內(nèi)存塊，當(dāng)要查找一塊空閑的內(nèi)存塊時(shí)，應(yīng)當(dāng)是在這些葉子結(jié)點(diǎn)中查找，如果找不到，則找一個(gè)較大一點(diǎn)的空閑結(jié)點(diǎn)進(jìn)行再分配。 運(yùn)用二叉樹(shù)的思想主要目的是用于理解空閑空間的回收方法，內(nèi)存的不斷分配和釋放勢(shì)必會(huì)造成大量的內(nèi)存碎片，如果不對(duì)內(nèi)存碎片進(jìn)行整理最終會(huì)導(dǎo)致無(wú)內(nèi)存可用，所以在釋放（free）內(nèi)存時(shí)要把連續(xù)的內(nèi)存空間合并起來(lái)，以免有內(nèi)存碎片，但并不是所有的連續(xù)空間都適宜合并，如下圖： 內(nèi)存塊h、i、j、k為連續(xù)空間，其中h和k空間為已被使用的空間，i和j空間是剛被釋放出來(lái)的空閑空間，顯然，空閑空間i和j可以組成一個(gè)更大的如128B大小的空閑空間，但是這樣做的結(jié)果是不僅破壞了二叉樹(shù)原有的思想也造成以后若要合并空間h和k會(huì)比較復(fù)雜，會(huì)增加很多算法，如要判斷空間i和j是否已合并,而且每釋放一個(gè)內(nèi)存空間都要對(duì)每層的二叉樹(shù)進(jìn)行這種類(lèi)似的判斷，雖然這樣可以更加減少內(nèi)存碎片，但是釋放內(nèi)存函數(shù)是個(gè)常用的函數(shù)，這種計(jì)算量特別是在嵌入式開(kāi)發(fā)中是無(wú)法承受的，而且出現(xiàn)上面的這種情況在程序中一般較少出現(xiàn)，所以我們對(duì)于這樣的連續(xù)空間不進(jìn)行合并，只有對(duì)是同一個(gè)父結(jié)點(diǎn)的兩個(gè)葉子結(jié)點(diǎn)才進(jìn)行合并。 總的思想是：對(duì)內(nèi)存進(jìn)行切割時(shí)，總是把一塊大的內(nèi)存空間切割成兩塊小的內(nèi)存空間，對(duì)內(nèi)存進(jìn)行合并時(shí)，只把原來(lái)都是由同一個(gè)內(nèi)存塊分割出來(lái)的兩塊內(nèi)存塊進(jìn)行合并。 下面就根據(jù)這樣的思想來(lái)實(shí)現(xiàn)內(nèi)存申請(qǐng)和釋放方法： 1．?數(shù)據(jù)結(jié)構(gòu)定義 用一個(gè)數(shù)組定義內(nèi)存粒度(以2的倍數(shù)來(lái)定義)： #define GRANULARITY_NUMBER 12??? const int MemGranularity [GRANULARITY_NUMBER] = {4,8,16,32,64,128,256,512,1024,2048,4096,0xffff}; 建立一個(gè)以粒度來(lái)分類(lèi)的內(nèi)存塊指針數(shù)組（內(nèi)存桶）： typedef struct mem_block_info_struct { void* memptr;??????????????????? //內(nèi)存塊指針 mem_block_info_struct* nextblock;//指向后一個(gè)內(nèi)存塊的指針 }MemBlockInfo; typedef struct mem_array_head_struct { MemBlockInfo*　freedmemarray;//指向空閑內(nèi)存塊鏈表的指針 MemBlockInfo*?usedmemarray;//指向已用內(nèi)存塊鏈表的指針 }MemArrayHead; MemArrayHead MemBucket[GRANULARITY_NUMBER] ={ }; 如MemBucket [0]是指向內(nèi)存塊大小為4字節(jié)的內(nèi)存塊鏈表，MemBucket [1]則是指向內(nèi)存塊大小為8字節(jié)的內(nèi)存塊鏈表，依此類(lèi)推。 可以在大塊內(nèi)存前面劃出一部分內(nèi)存來(lái)存儲(chǔ)每個(gè)內(nèi)存塊的信息，如下圖：

　這里就必須要預(yù)先估計(jì)要?jiǎng)澐殖龆啻蟮膬?nèi)存來(lái)存儲(chǔ)每個(gè)內(nèi)存塊的信息，對(duì)于較小的運(yùn)行程序比較容易估計(jì)，但是如果程序較復(fù)雜則要通過(guò)實(shí)驗(yàn)來(lái)確定劃分大小，可以事先設(shè)定一個(gè)宏定義值，以后只要改這個(gè)宏定義值就可以了，如：

#define MEMORY_BLOCK_MAX_NUMBER?2048 MemBlockInfo*?MemBlockArray = NULL; MemBucket指向的內(nèi)存塊鏈表都按內(nèi)存塊指針（memptr）值進(jìn)行由低到高的排序，其實(shí)只要在插入一個(gè)新內(nèi)存塊時(shí)按指針值大小有序插入就可以了，這樣做以便于查找鏈表中的結(jié)點(diǎn)，以提高查找效率。 2．?算法實(shí)現(xiàn) 1）、初始化方法 a.?初始化全局變量； b. 在內(nèi)存塊前部分出一部分用來(lái)存儲(chǔ)內(nèi)存塊信息； c. 從剩余的內(nèi)存空間開(kāi)始按設(shè)定的內(nèi)存粒度對(duì)內(nèi)存進(jìn)行切割，切割原則是使得切割出來(lái)的內(nèi)存塊總數(shù)為最小值，方法是按粒度由大到小進(jìn)行切割，假設(shè)有剩余空間大小為7680B，則可切割出內(nèi)存塊有：4096B、2048B、1024B、512B（這意味著我們先建立4個(gè)只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)），這些內(nèi)存塊的指針存到MemBlockArray中，然后根據(jù)粒度大小和內(nèi)存塊大小把MemBucket相應(yīng)指針指到MemBlockArray中。 2）、動(dòng)態(tài)分配內(nèi)存方法（即malloc函數(shù)實(shí)現(xiàn)方法） a. 根據(jù)傳入?yún)?shù)中指定的大小來(lái)決定要分配多大的內(nèi)存粒度，當(dāng)分配大小剛好等于某個(gè)粒度大小時(shí)，則按該粒度大小來(lái)分配，如果找不到相應(yīng)大小粒度，則找一個(gè)比要分配的空間大小要大的最小粒度作為分配空間，例如要分配20字節(jié)空間，則分配一個(gè)粒度為32字節(jié)的空間。 b.　根據(jù)粒度大小在空閑鏈表中尋找相應(yīng)空閑空間：若找到則返回該空閑空間指針，并把相應(yīng)結(jié)點(diǎn)移入到已用鏈表中；若沒(méi)有找到，則找一個(gè)粒度更大一點(diǎn)的空閑塊，然后把該空閑塊進(jìn)行一半一半地分割，直到分割出得到所要的粒度大小為止，最后把被分割的空閑塊從鏈表中移出，并把該結(jié)點(diǎn)的指針都置為NULL，分割出來(lái)的空閑塊指針都存到MemBlockArray中，MemBlockArray中新增的數(shù)組單元內(nèi)容作為結(jié)點(diǎn)添加到MemBucket空閑鏈表中（按指針大小順序來(lái)添加），取分割出來(lái)的其中一個(gè)最小的空閑塊作為要返回的內(nèi)存塊，并把這個(gè)內(nèi)存塊移入到已用鏈表中。 3）、釋放內(nèi)存塊方法（即free函數(shù)實(shí)現(xiàn)方法） 搜索所有的已用鏈表，找出與傳入的指針大小一樣的結(jié)點(diǎn)，把該結(jié)點(diǎn)從已用鏈表中移出到空閑鏈表中，也是按順序插入到空閑鏈表中，如果發(fā)現(xiàn)相鄰結(jié)點(diǎn)為連續(xù)空間，而且相鄰結(jié)點(diǎn)都原來(lái)為從同一個(gè)較大的空閑內(nèi)存塊分割出來(lái)的（即為同一個(gè)父結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)），則合并這兩個(gè)內(nèi)存塊，把合并后的內(nèi)存塊移入到更大粒度的空閑鏈表中，如果在更大的粒度空閑鏈表中又發(fā)現(xiàn)有可合并內(nèi)存塊，則再進(jìn)行合并，依此方法，直到不能合并為止。 合并空閑內(nèi)存塊方法：把這兩個(gè)內(nèi)存塊結(jié)點(diǎn)都從空閑鏈表中移出，按內(nèi)存地址大小，把較小地址指針的結(jié)點(diǎn)移到更大粒度的空閑鏈表中，把較大地址指針的結(jié)點(diǎn)中所有指針值都置為NULL。 判斷兩個(gè)內(nèi)存塊是否是從同一個(gè)較大的空閑內(nèi)存塊分割出來(lái)的方法：如下圖 如果內(nèi)存塊1和內(nèi)存塊2都是從同一個(gè)較大的空閑內(nèi)存塊分割出來(lái)的，則滿(mǎn)足如下條件： （前面內(nèi)存塊＋內(nèi)存塊1）/內(nèi)存塊1的大小：這個(gè)結(jié)果為奇數(shù) （前面內(nèi)存塊＋內(nèi)存塊1+內(nèi)存塊2）/內(nèi)存塊2的大小：這個(gè)結(jié)果為偶數(shù) 3．該方法優(yōu)缺點(diǎn) 1）、優(yōu)點(diǎn)：實(shí)現(xiàn)方法較簡(jiǎn)單，產(chǎn)生的內(nèi)存碎片較少。 2）、缺點(diǎn)：內(nèi)存空間利用率不高，當(dāng)內(nèi)存分配中需要較多內(nèi)存塊時(shí)，由于要存儲(chǔ)內(nèi)存塊信息，要浪費(fèi)較大的內(nèi)存空間，而且存儲(chǔ)內(nèi)存塊信息的數(shù)組長(zhǎng)度為固定大小，則在具體應(yīng)用中可能需要調(diào)節(jié)該大小，較不靈活。

總結(jié)

以上是生活随笔為你收集整理的利用二叉树的思想来实现分配和释放内存方法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。