内存管理 - 动态开辟内存
作者：孙靖(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参数一样。当然你也可以进一步改进此方法，让他使用的更合理更安全。
[此贴子已经被作者于2006-12-26 14:32:11编辑过]
