引言

内存分配算法是计算机中的基本算法，不论是操作系统还是应用软件中都必须用到。各种内存分配算法都有它的优缺点，一个理想的内存算法应该满足以下要求：

◇ 能分配任意大小的内存；

◇ 能有效地管理内存，即无限地分配下去，直到系统的内存耗光为止；

◇ 释放的内存能重新被分配；

◇ 内存碎片要尽量少；

◇ 分配速度要快；

◇ 内存管理消耗的辅助空间要尽量小。

1动态等尺寸内存分配算法简介和分析

动态等尺寸分配算法把连续的大块内存按分区来管理，每个分区中有相同大小的内存块。每个分区中的空闲内存块用链表相连,其数据结构如图1所示。要使用内存块时，从分区中取一个内存块，使用完后再把内存块放回该分区。一个系统可以有多个内存分区，这样应用程序就可以从不同的内存分区中得到大小不同的内存块。μC/OSII就是采用了这种内存管理算法。

图1动态等尺寸内存分配算法的数据结构

这种内存管理算法具有以下优点：

① 时间效率高，每次分配所花费的时间为常量；

② 内存管理的辅助开销为0，已被分配节点的内存全部使用，不需要为内存管理保留；

③ 内存性能好，不存在内存碎片的问题，便于大规模使用；

④ 算法实现简单。

但是当不小心对一个申请到的内存块进行非法越界写操作，或者应用任务在申请内存块中产生了非法指针，并指向空闲内存块的指针区（空闲内存块的头4个字节）时，可能破坏它指向下一个空闲内存快的指针，空闲内存块链表也就可能会被破坏。因此，必须将控制信息与用户使用的空闲块分开来。内存块的控制信息属于系统数据，必须对其进行保护，这样即使发生了越界写操作，或者应用程序申请到的内存块中产生了指向空闲内存块指针区（空闲内存块的头4个字节）的非法指针，也不会破坏空闲内存控制链表。

2改进算法的描述与实现

改进算法采用类似μC/OSII就绪表的内存分配表，并且对就绪表进行了一定的改造，使其一次可以管理512个内存块。下面介绍其具体实现。

2．1内存控制块

typedef struct os_mem{

INT8U*OSMemAddr;//内存分区首地址

INT8UOSMemGrp;

INT8UOSMemTbl[8];

INT8UOSMemGrid[8][8];

INT32UOSMemBlkSize;//内存块大小

INT32UOSMemNBlks;//每个分区内存块的数目

INT32UOSMemNFree;//当前可分配内存块的数目

struct os_mem *next;//用来连接内存控制块(MCB)

}OS_MEM;

类似μC/OSII就绪表，OSMemGrid[][]的每一位对应一个内存块，为0表示内存块已被分配，为1则表示内存块为可用的空闲块，未被分配。OSMemTbl[]的每一位对应8个内存块，为0表示这8个内存块全部被分配出去了，为1表示至少还有1个内存块未被分配。OSMemGrp每一位对应64个内存块，只要这64个内存块中有1个空闲可用的，该位就置1，否则置0。

2．2创建一个内存分区

创建一个内存分区，需要初始化内存控制块的信息：

pmem>OSMemGrp = 0xff;

for(i =0 ;i<8;i++){

pmem>OSMemTbl[i] = 0xff;

}

for(i=0;i<8;i++){

for(j=0;j<8;j++){

pmem>OSMemGrid[i][j] = 0xff;

}

}

2.3申请一个内存块

申请一个内存块通过调用函数OSMemGet()来完成，函数的定义为：

INT8U *OSMemGet(OS_MEM *pmem,INT8U *err)；

其中，pmem为内存控制块，err为错误信息，该函数返回申请到内存块的首地址。

申请一个内存块，总是按地址由低到高的顺序，低地址的空闲内存先被分配。由于每个内存块都与内存分配表中的1位对应，所以当要分配内存块时，可以使用类似于就绪表的方法来计算得到要分配的内存块的编号。具体实现如下：

y2 = OSUnMapTbl[(INT8U)(pmem>OSMemGrp)];

y1 = OSUnMapTbl[(INT8U)(pmem>OSMemTbl1[y2])];

x1=OSUnMapTbl[(INT8U)(pmem>OSMemGrid[y2][y1])];

blknum = (y2<<6)+(y1<<3) + x1;

同时修改内存分配表：

if((pmem > OSMemGrid[y2][y1] &= ~OSMapTbl[x1])==0){

pmem > OSMemTbl1[y2] &= ~OSMapTbl[y1];

}

if(pmem > OSMemTbl1[y2] ==0x00){

pmem > OSMemGrp &= ~OSMapTbl[y2];

}

最后，可以根据得到的内存块编号计算出分配内存的首地址：

pblk =(INT8U *)pmem﹥OSMemAddr + blknum*pmem﹥OSMemBlkSize;

pblk就是该函数的返回值。

2．4释放一个内存块

释放一个内存块通过调用OSMemPut（）函数来完成。该函数定义如下：

INT8U OSMemPut(OS_MEM*pmem,INT8U*pblk)；

其中，pmem表示内存控制块，pblk表示要释放内存块的首地址。

释放一个内存块，要先计算出内存块编号，可通过该内存块的首地址实现：

blknum = (pblk (INT8U *)pmem>OSMemAddr )/pmem>OSMemBlkSize;

然后修改内存分配表：

x1=(INT8U)blknum & 0x07;

y1=(INT8U)(blknum >>3)&0x07;

y2=(INT8U)(blknum >>6)&0x07;

pmem>OSMemGrp|= OSMapTbl[y2];

pmem>OSMemTbl1[y2] |= OSMapTbl[y1];

pmem>OSMemGrid[y2][y1] |= OSMapTbl[x1];

3改进后内存管理算法的优缺点

改进后的内存管理算法，取消了用链表来连接分区内空闲内存块的做法，采用的是内存分配表。每个内存块不需要包含指针信息，完全是用户的信息，这样完全不必担心由于越界写操作，或应用任务的非法指针指向空闲内存块指针区，而引起空闲内存块链表被破坏的状况发生。

但是改进后的内存管理算法仅支持每个分区最多为512个空闲内存块。对于这个问题，可以创建两个或者两个以上内存分区的办法，然后用内存控制块的next成员把它们连接起来，组成逻辑上的一个分区。

结语

本文介绍了动态等尺寸的内存管理算法，并提出了一种改进算法，解决了可能由越界写操作，或应用任务非法指针引起的空闲内存块链表被破坏的问题，提高了内存管理的安全性，具有一定的实际意义。