內(nèi)存管理 - 動(dòng)態(tài)開(kāi)辟內(nèi)存
作者：孫靖(Jig) 時(shí)間：2006 - 12 - 26
若要轉(zhuǎn)貼或使用本文章介紹的技術(shù)，請(qǐng)?jiān)谀惆l(fā)布的文章或作品中注明出處。
關(guān)于內(nèi)存管理，以前我在PC機(jī)上研究系統(tǒng)內(nèi)核時(shí)接觸過(guò)。那要求在把CPU設(shè)置為32位后統(tǒng)一給內(nèi)存做影射，而我們今天要討論的內(nèi)存管理比那是要簡(jiǎn)單多了。
前兩天拿朋友的51單片機(jī)開(kāi)發(fā)板玩（用的Keil），突然萌發(fā)做個(gè)貪食蛇的想法，經(jīng)過(guò)考慮我打算用鏈表來(lái)做（當(dāng)然，結(jié)果證明用鏈表做很不值得）可在快完工的時(shí)候我傻眼啦，蛇在吃了食物后整個(gè)屏幕都花啦（用的LCD12864的液晶屏）。本來(lái)蛇每吃一個(gè)食物其實(shí)就是動(dòng)態(tài)再開(kāi)辟一段蛇身。這樣看來(lái)顯然是動(dòng)態(tài)開(kāi)辟內(nèi)存失敗，導(dǎo)致繪制蛇身函數(shù)在逐個(gè)查找鏈表的每個(gè)節(jié)點(diǎn)的時(shí)候有一環(huán)被破壞沒(méi)有連接到下一環(huán)。
再追查下去，應(yīng)該就是 malloc() 函數(shù)沒(méi)有發(fā)揮作用，可是很納悶 Keil 編譯器并沒(méi)有報(bào)告錯(cuò)誤?，F(xiàn)在問(wèn)題找到了，可要解決這個(gè)問(wèn)題那就必須自己能構(gòu)造一個(gè) malloc() 函數(shù)。后來(lái)我查看了 malloc() 函數(shù)，具體實(shí)現(xiàn)如下：
struct __mem__
{
struct __mem__ _MALLOC_MEM_ *next; /* single-linked list */
unsigned int len; /* length of following block */
};
typedef struct __mem__ __memt__;
typedef __memt__ _MALLOC_MEM_ *__memp__;
#define HLEN (sizeof(__memt__))
extern __memt__ _MALLOC_MEM_ __mem_avail__ [];
#define AVAIL (__mem_avail__[0])
#define MIN_BLOCK (HLEN * 4)
void _MALLOC_MEM_ *malloc (unsigned int size)
{
__memp__ q; /* ptr to free block */
__memp__ p; /* q->next */
unsigned int k; /* space remaining in the allocated block */
q = &AVAIL;
while (1)
{
if ((p = q->next) == NULL)
{
return (NULL); /* FAILURE */
}
if (p->len >= size)
break;
q = p;
}
k = p->len - size; /* calc. remaining bytes in block */
if (k < MIN_BLOCK) /* rem. bytes too small for new block */
{
q->next = p->next;
return (&p[1]); /* SUCCESS */
}
k -= HLEN;
p->len = k;
q = (__memp__ ) (((char _MALLOC_MEM_ *) (&p [1])) + k);
q->len = size;
return (&q[1]); /* SUCCESS */
}
在這我們可以看到其實(shí)他就是利用一個(gè)鏈表在內(nèi)存中去搜索一段連續(xù)的空閑內(nèi)存，并把首地址傳回?？蔀槭裁此谖沂褂玫?1單片機(jī)開(kāi)發(fā)板上沒(méi)有發(fā)揮作用呢？經(jīng)過(guò)分析，我恍然大悟。大家試想一下如果讓你去分配一段內(nèi)存，那么我們就必須有個(gè)紀(jì)錄哪些內(nèi)存在使用哪些內(nèi)存空閑的機(jī)制。拿TC或VC在PC機(jī)上實(shí)驗(yàn)一下使用 malloc() 函數(shù)看看？它作用發(fā)揮良好，看來(lái)這個(gè)機(jī)制是由OS來(lái)完成的，而在我們那51單片機(jī)的裸機(jī)上有個(gè)毛的OS啊，也難怪 malloc() 函數(shù)不能成功的分配內(nèi)存?，F(xiàn)在找到問(wèn)題的本質(zhì)，那我們就來(lái)自己構(gòu)造 malloc() 函數(shù)。
建立自己的數(shù)據(jù)類型：
文件名：MY_Type.h
內(nèi)容：
/* 自定義類型，方便書(shū)寫與在不同平臺(tái)進(jìn)行移植 */
typedef char INT8;
typedef int INT16;
long INT32;
/*typedef float F32;
typedef double F64;*/
typedef unsigned char UINT8;
typedef unsigned int UINT16;
typedef unsigned long UINT32;
/*typedef unsigned float UF32;
typedef unsigned double UF64;*/
總體具體分析：
為了能有效果的對(duì)內(nèi)存進(jìn)行管理，我們必須保證內(nèi)存時(shí)時(shí)刻刻都能被指定并被紀(jì)錄是否空閑，那么最好的做法就是先開(kāi)辟好一定空間再統(tǒng)一管理。當(dāng)然這段內(nèi)存空間也必須是全局的。然后我們必須建立一個(gè)紀(jì)錄列表，紀(jì)錄下內(nèi)存的使用狀態(tài)，以便管理。
建立管理機(jī)制：
我們可以構(gòu)造一個(gè)結(jié)構(gòu)，將紀(jì)錄列表和實(shí)際使用內(nèi)存綁定起來(lái)。具體代碼如下：
#define MEM_COUNT 40 /* 實(shí)際使用內(nèi)存40個(gè)字節(jié) */
#define MEM_LIST MEM_COUNT >> 3 /* 管理列表 40/8 = 5個(gè)字節(jié) */
typedef struct
{
UINT8 list[MEM_LIST]; /* 管理列表共40位與實(shí)際使用內(nèi)存一一對(duì)應(yīng)，1表示使用中，0表示空閑 */
INT8 mem[MEM_COUNT]; /* 實(shí)際使用內(nèi)存40個(gè)字節(jié) */
}MEM; /* 管理機(jī)制結(jié)構(gòu) */
MEM Mem; /* 管理機(jī)制數(shù)據(jù) */
到此我們就把內(nèi)存管理機(jī)制的核心部分建立起來(lái)了，我們可以作這樣一個(gè)表來(lái)說(shuō)明他的工作方式：
Mem.list[0] ... ... Mem.list[5]
┏━┳━┳━┳┻┳━┳━┳━┓ ┏━┳━┳━┳┻┳━┳━┳━┓
位 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃
Mem.mem[] 0 1 2 3 4 5 6 7 32 33 34 35 36 37 38 39 （表一）
從上表一可以很直觀的理解 Mem.list 的5個(gè)字節(jié)共40位，與 Mem.mem 的40個(gè)字節(jié)一一對(duì)應(yīng)，我們就是通過(guò)檢查 Mem.list 各位的狀態(tài)來(lái)確定哪些內(nèi)存在使用哪些內(nèi)存空閑。
初始化管理系統(tǒng)：
這個(gè)很簡(jiǎn)單，初始化即是內(nèi)存全部可用，Mem.list 全部置0，具體實(shí)現(xiàn)函數(shù)：
void Init_mem(void);
void Init_mem()
{
UINT8 i;
for (i = 0; i < MEM_LIST; i++)
{
Mem.list[i] = 0; /* 管理列表共40位全部置0，表示內(nèi)存可用 */
}
}
經(jīng)過(guò)此函數(shù)，Mem.mem 的40個(gè)字節(jié)內(nèi)存被標(biāo)記為可使用。
動(dòng)態(tài)開(kāi)辟內(nèi)存：
即像 malloc() 函數(shù)那樣，分配指定字節(jié)的內(nèi)存，具體實(shí)現(xiàn)函數(shù)：
void Set_bit(UINT8 Bit, UINT8 mode); /* 設(shè)置管理列表的第Bit位為mode */
void *Malloc(UINT8 Size); /* 分配Size字節(jié)大小的內(nèi)存，返回首地址 */
void Set_bit(UINT8 Bit, UINT8 mode)
{
UINT8 Enter = 128;
Enter >>= (Bit % 8);
if (mode)
{
Mem.list[Bit >> 3] |= Enter; /* 將管理列表的第Bit位置1，表示已被使用 */
}
else
{
Mem.list[Bit >> 3] ^= Enter; /* 將管理列表的第Bit位置0，表示處于空閑 */
}
}
void *Malloc(UINT8 Size)
{
UINT8 i, j, k, Enter;
if (Size > MEM_COUNT || Size < 1)
{
return NULL; /* 內(nèi)存開(kāi)辟失敗，返回空指針 */
}
/* i, j 兩層for循環(huán)用于查找管理列表目前的空閑內(nèi)存 */
for (i = 0; i < MEM_LIST; i++)
{
Enter = 128;
for (j = 0; j < 7; j++)
{
if ((Mem.list[i] & Enter) != Enter) /* 查找管理列表，直至查早到空閑內(nèi)存 */
{
for (k = (i<<3)+j; k < (i<<3)+j+Size; k++)
{
Set_bit(k, 1); /* 從空閑內(nèi)存首地址開(kāi)始按Size大小設(shè)置被使用的內(nèi)存 */
}
return &Mem.mem[(i << 3) + j]; /* 內(nèi)存開(kāi)辟成功，返回首地址 */
}
Enter >>= 1;
}
}
return NULL; /* 內(nèi)存開(kāi)辟失敗，返回空指針 */
}
此函數(shù)通過(guò)檢查管理列表，找到空閑內(nèi)存的啟始地址，并把管理列表對(duì)應(yīng)的位置1，并返回空閑內(nèi)存啟始地址。
釋放內(nèi)存：
void Free(UINT8 *Mem1, UINT8 Size); /* 釋放開(kāi)辟的內(nèi)存 */
void Free(UINT8 *Mem1, UINT8 Size)
{
UINT8 i;
/* Mem1 - &Mem.mem[0] 計(jì)算出Mem1指向的地址為Mem.mem的第幾元素 */
for (i = (Mem1 - &Mem.mem[0]); i < (Mem1 - &Mem.mem[0] + Size); i++)
{
Set_bit(i, 0); /* 從指定內(nèi)存首地址開(kāi)始按Size大小設(shè)置被內(nèi)存空閑 */
}
}
此函數(shù)可以“釋放”掉被開(kāi)辟的內(nèi)存空間。當(dāng)然，這個(gè)釋放不是真正意義上的釋放，只是把管理列表的相對(duì)應(yīng)位設(shè)置為0，表示內(nèi)存空閑。
好了，到此這個(gè)內(nèi)存管理技術(shù)全部介紹完畢。他全部也就四個(gè)函數(shù)，我們可以做個(gè)小實(shí)驗(yàn)。
#include <stdio.h>
#include "MY_Mem.h"
int main()
{
INT32 *i;
UINT8 *j;
Init_mem(); /* 初始化內(nèi)存管理機(jī)制 */
j = (UINT8 *)Malloc(sizeof(UINT8));
i = (INT32 *)Malloc(sizeof(INT32));
*j = 30;
*i = 6789324;
printf("%d %d\n", *j, j); /* 打印j所指向地址存放的元素和j */
printf("%d %d\n", Mem.mem[0], &Mem.mem[0]); /* 打印Mem.mem[0]和Mem.mem[0]的地址 */
printf("%ld %d\n", *i, i); /* 打印i所指向地址存放的元素和i */
printf("%d", &Mem.mem[1]); /* 打印Mem.mem[1]的地址 */
Free(j, sizeof(UINT8));
Free(i, sizeof(UINT8));
getch();
}
你可以用TC或VC編譯，我用TC編譯的結(jié)果是：
30 1121
30 1121
6789324 1122
1122
用不同的編譯器結(jié)構(gòu)可能有點(diǎn)不同，但 j = &Mem.mem[0], i = &Mem.mem[1];卻是絕對(duì)成立的，這說(shuō)明我們的內(nèi)存管理機(jī)制起作用了，我們成功的實(shí)現(xiàn)內(nèi)存的統(tǒng)一管理，并實(shí)現(xiàn)了動(dòng)態(tài)開(kāi)辟內(nèi)存。
總結(jié)：
以上闡述的思路，其實(shí)很簡(jiǎn)單。也許大家在看到這時(shí)就覺(jué)得這個(gè)很小兒科了。我也承認(rèn)這的確很小兒科。說(shuō)到底，其實(shí)就是先開(kāi)辟好內(nèi)存然后再來(lái)使用，但作為一個(gè)思路我希望對(duì)您有一定啟發(fā)和幫助，同時(shí)也希望和大家共同交流和探討。當(dāng)然，任何事物和方法都有兩面性，這個(gè)內(nèi)存管理也不列外。
缺點(diǎn)：由于要開(kāi)辟一個(gè)列表來(lái)紀(jì)錄內(nèi)存的使用狀態(tài)，所以增大了內(nèi)存的開(kāi)銷，如上所示，40個(gè)字節(jié)的內(nèi)存就需要5個(gè)字節(jié)的管理列表。
優(yōu)點(diǎn)：這個(gè)方法簡(jiǎn)單方便，在單片機(jī)這樣的平臺(tái)上你想像在PC機(jī)上那樣花大力氣去做內(nèi)存的影射嗎？而且那樣做內(nèi)存的額外開(kāi)銷也不一定比此方法的少。并且是按字節(jié)大小以順序方式開(kāi)辟內(nèi)存，不存在什么所謂的內(nèi)存碎片。
當(dāng)然，大家在使用著套方法的時(shí)候一定主要將Malloc()和Free()函數(shù)配套使用，并且要保證里面的Size參數(shù)一樣。當(dāng)然你也可以進(jìn)一步改進(jìn)此方法，讓他使用的更合理更安全。