內存管理 - 動態開辟內存
作者：孫靖(Jig) 時間：2006 - 12 - 26
若要轉貼或使用本文章介紹的技術，請在你發布的文章或作品中注明出處。
關于內存管理，以前我在PC機上研究系統內核時接觸過。那要求在把CPU設置為32位后統一給內存做影射，而我們今天要討論的內存管理比那是要簡單多了。
前兩天拿朋友的51單片機開發板玩（用的Keil），突然萌發做個貪食蛇的想法，經過考慮我打算用鏈表來做（當然，結果證明用鏈表做很不值得）可在快完工的時候我傻眼啦，蛇在吃了食物后整個屏幕都花啦（用的LCD12864的液晶屏）。本來蛇每吃一個食物其實就是動態再開辟一段蛇身。這樣看來顯然是動態開辟內存失敗，導致繪制蛇身函數在逐個查找鏈表的每個節點的時候有一環被破壞沒有連接到下一環。
再追查下去，應該就是 malloc() 函數沒有發揮作用，可是很納悶 Keil 編譯器并沒有報告錯誤。現在問題找到了，可要解決這個問題那就必須自己能構造一個 malloc() 函數。后來我查看了 malloc() 函數，具體實現如下：
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 */
}
在這我們可以看到其實他就是利用一個鏈表在內存中去搜索一段連續的空閑內存，并把首地址傳回。可為什么他在我使用的51單片機開發板上沒有發揮作用呢？經過分析，我恍然大悟。大家試想一下如果讓你去分配一段內存，那么我們就必須有個紀錄哪些內存在使用哪些內存空閑的機制。拿TC或VC在PC機上實驗一下使用 malloc() 函數看看？它作用發揮良好，看來這個機制是由OS來完成的，而在我們那51單片機的裸機上有個毛的OS啊，也難怪 malloc() 函數不能成功的分配內存。現在找到問題的本質，那我們就來自己構造 malloc() 函數。
建立自己的數據類型：
文件名：MY_Type.h
內容：
/* 自定義類型，方便書寫與在不同平臺進行移植 */
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;*/
總體具體分析：
為了能有效果的對內存進行管理，我們必須保證內存時時刻刻都能被指定并被紀錄是否空閑，那么最好的做法就是先開辟好一定空間再統一管理。當然這段內存空間也必須是全局的。然后我們必須建立一個紀錄列表，紀錄下內存的使用狀態，以便管理。
建立管理機制：
我們可以構造一個結構，將紀錄列表和實際使用內存綁定起來。具體代碼如下：
#define MEM_COUNT 40 /* 實際使用內存40個字節 */
#define MEM_LIST MEM_COUNT >> 3 /* 管理列表 40/8 = 5個字節 */
typedef struct
{
UINT8 list[MEM_LIST]; /* 管理列表共40位與實際使用內存一一對應，1表示使用中，0表示空閑 */
INT8 mem[MEM_COUNT]; /* 實際使用內存40個字節 */
}MEM; /* 管理機制結構 */
MEM Mem; /* 管理機制數據 */
到此我們就把內存管理機制的核心部分建立起來了，我們可以作這樣一個表來說明他的工作方式：
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個字節共40位，與 Mem.mem 的40個字節一一對應，我們就是通過檢查 Mem.list 各位的狀態來確定哪些內存在使用哪些內存空閑。
初始化管理系統：
這個很簡單，初始化即是內存全部可用，Mem.list 全部置0，具體實現函數：
void Init_mem(void);
void Init_mem()
{
UINT8 i;
for (i = 0; i < MEM_LIST; i++)
{
Mem.list[i] = 0; /* 管理列表共40位全部置0，表示內存可用 */
}
}
經過此函數，Mem.mem 的40個字節內存被標記為可使用。
動態開辟內存：
即像 malloc() 函數那樣，分配指定字節的內存，具體實現函數：
void Set_bit(UINT8 Bit, UINT8 mode); /* 設置管理列表的第Bit位為mode */
void *Malloc(UINT8 Size); /* 分配Size字節大小的內存，返回首地址 */
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; /* 內存開辟失敗，返回空指針 */
}
/* i, j 兩層for循環用于查找管理列表目前的空閑內存 */
for (i = 0; i < MEM_LIST; i++)
{
Enter = 128;
for (j = 0; j < 7; j++)
{
if ((Mem.list[i] & Enter) != Enter) /* 查找管理列表，直至查早到空閑內存 */
{
for (k = (i<<3)+j; k < (i<<3)+j+Size; k++)
{
Set_bit(k, 1); /* 從空閑內存首地址開始按Size大小設置被使用的內存 */
}
return &Mem.mem[(i << 3) + j]; /* 內存開辟成功，返回首地址 */
}
Enter >>= 1;
}
}
return NULL; /* 內存開辟失敗，返回空指針 */
}
此函數通過檢查管理列表，找到空閑內存的啟始地址，并把管理列表對應的位置1，并返回空閑內存啟始地址。
釋放內存：
void Free(UINT8 *Mem1, UINT8 Size); /* 釋放開辟的內存 */
void Free(UINT8 *Mem1, UINT8 Size)
{
UINT8 i;
/* Mem1 - &Mem.mem[0] 計算出Mem1指向的地址為Mem.mem的第幾元素 */
for (i = (Mem1 - &Mem.mem[0]); i < (Mem1 - &Mem.mem[0] + Size); i++)
{
Set_bit(i, 0); /* 從指定內存首地址開始按Size大小設置被內存空閑 */
}
}
此函數可以“釋放”掉被開辟的內存空間。當然，這個釋放不是真正意義上的釋放，只是把管理列表的相對應位設置為0，表示內存空閑。
好了，到此這個內存管理技術全部介紹完畢。他全部也就四個函數，我們可以做個小實驗。
#include <stdio.h>
#include "MY_Mem.h"
int main()
{
INT32 *i;
UINT8 *j;
Init_mem(); /* 初始化內存管理機制 */
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編譯的結果是：
30 1121
30 1121
6789324 1122
1122
用不同的編譯器結構可能有點不同，但 j = &Mem.mem[0], i = &Mem.mem[1];卻是絕對成立的，這說明我們的內存管理機制起作用了，我們成功的實現內存的統一管理，并實現了動態開辟內存。
總結：
以上闡述的思路，其實很簡單。也許大家在看到這時就覺得這個很小兒科了。我也承認這的確很小兒科。說到底，其實就是先開辟好內存然后再來使用，但作為一個思路我希望對您有一定啟發和幫助，同時也希望和大家共同交流和探討。當然，任何事物和方法都有兩面性，這個內存管理也不列外。
缺點：由于要開辟一個列表來紀錄內存的使用狀態，所以增大了內存的開銷，如上所示，40個字節的內存就需要5個字節的管理列表。
優點：這個方法簡單方便，在單片機這樣的平臺上你想像在PC機上那樣花大力氣去做內存的影射嗎？而且那樣做內存的額外開銷也不一定比此方法的少。并且是按字節大小以順序方式開辟內存，不存在什么所謂的內存碎片。
當然，大家在使用著套方法的時候一定主要將Malloc()和Free()函數配套使用，并且要保證里面的Size參數一樣。當然你也可以進一步改進此方法，讓他使用的更合理更安全。