size_t requiredsize; /* 申请分配的大小*/

void *actualaddress; /* 实际地址*/

void *requiredaddress; /* 申请分配地址*/

⋯⋯}

通过内存管理器分配的内存结构可知, 返回给用户

的指针ptr 指向的是用户申请内存区域的起始位置。链

表节点, 前后检测区域均为内部使用, 用户是不可见的。

3.2 算法的改进

基于游戏引擎的特殊性, 如申请和释放内存十分

频繁。若采用传统的算法则肯定会降低系统的效率。

加之游戏是很讲究实时性的东西对于时间的要求自

然要比普通的程序来得高。为了解决上面所提到的链

表式的内存管理所带来的问题。我采用一种新的双向

链式哈希表数据结构, 并使用一个巧妙的方法来获取

哈希函数。

由于内存分配的地址是随机的, 经实验发现一个

32 位的地址的低40 位是随机变化概率最高的, 产生冲

突的概率也随之减小。于是我开辟了一个地址空间大

小为1024 的哈希表。把内存分配的地址与( 1024- 1) 相

与, 来获得哈希地址, 易知其值肯定在0～1024 之间。这

个哈希函数的特点在于, 构造简单方便, 利用了计算机

原有的特性从而简单了解决了地址冲突的问题。

函数原型如下:

int getHashIndex( void *address )

{return((unsignedint)address>>4)&(HASH_SIZE-1);}

当然, 我们知道一个游戏的内存分配可能远远超

过1024 个, 于是地址冲突又成了一个不可避免的问

题。为了解决这个问题, 采用双向链式哈希表, 其结构

如图1 所示。

图1 双向链式哈希表结构

Fig.1 configuration of double listed hash table

由于用链地址解决冲突构造的哈希表是个动态

结构, 故更适合在造表之前无法确定记录个数的情

况。对其进行性能分析可知, 链地址法的平均查找长

度在等概率的情况下为:

ASL=1- α

(2)

由上可知, 哈希表的平均查找长度不是记录数l

的函数, 而是装填系数α的函数。因此在设计哈希表

时, 可以选择α以控制其平均查找长度。α越小, 空间

冗余度越大, 产生冲突的机会就少; 但是α过小, 空间

浪费会过多。经过试验, 装填系数选择0.7, 比较符合

实际应用。

4 C++的具体实现

首先, 需要创建重载的new和delete 运算符。正如

前面指出的, 我们将记录请求内存分配的代码的文件

和行号。重载这些运算符的方式如下( 数组重载方式

类似) :

inline void*operator new(size_t,const char *file,int line);

inline void operator delete(void* address);

需要注意的是, 为确保正确运行, 必须对运算符

new和delete 的标准版本和数组版本都进行重载。虽然

这些声名不复杂, 但是我们现在需要解决的问题是: 让

所有将使用内存管理器的程序都无缝的将额外的参数

传递给new运算符。为此, 可以使用编译指令#define。

#define new new(__FILE__ , __LINE__)

#define delete predele (__FILE__ , __LINE__) ,

false ? predele( “”, 0) : delete

#define new 语句将把所有的new 调用替换为新

的new, 后者接收的参数并非仅仅是需要分配的内存

量, 还包括了文件和行号, 以便跟踪内存的分配情况。

宏#define delete 与#define new 基本相同。在不引起

语法问题的情况下, 无法将额外的参数传递给delete

运算符, 因此我们巧用“? : ”运算符来使得在调用

delete 之前先调用predele 函数来记录文件名和行号。

另外, 很重要的一点是, 应有条件的创建这些宏, 以避

免多行宏中常见的问题。最后, 出于完整性的考虑我

们还必须使用自己的方法来替换malloc ()、calloc()、

realloc()、free()等。

至此, 我们还需要一个类用来管理我们的内存管

理器, 即以后所有对内存的操作必须通过这个类的对

象进行调用。其中包括内存的分配和释放, 哈希表的插

入和删除等。下面的代码中仅列出了与此相关的成员:

class memorycontrol

{ // Hash 表操作部分

void insertMemoryNode ( MemoryNode *node );

// 向hash 表中插入一内存节点.

MemoryNode *removeMemoryNode(void *address );

// 内存的分配与删除

void deallocateMemory( MemoryNode *node );}

接下来就是该如何去分配内存了, 考虑到版面限

制, 这里仅给出allocatememory()的伪代码。

void *allocatememory ( const char *file, int line,

size_t size, ALLOC_TYPE type, void *address )

{//检查memorycontrol 是否已经被初试化;

//检查是否为0 分配, 若是0 分配的话当作1 分

配来看;

//判断分配类型, 若是realloc 分配, 则从hash 表

中删除这个节点并重新用realloc 命令来分配;

//若为其他类型的分配, 则建立一个内存节点;

//记录一些必要的信息报告, 分配内存并初始化;

//把节点插入hash 表, 返回内存分配地址; }

最后, 我们要解决的问题是: 确保内存管理器是

- 213 -

技

术

创

新

中文核心期刊《微计算机信息》( 管控一体化)2006 年第22 卷第5-3 期

360元/ 年邮局订阅号: 82-946 《现场总线技术应用200 例》

软件时空

第一个被创建的对象, 同时也是最后一个被释放的对

象。为解决这个问题, 需要做一下改进: 首先, 通过在

内存管理器的头文件中创建InitMemoryControl 对象,

确保它在任何静态对象声名之前被创建。Microsoft 指

出, 静态对象被创建的顺序与出现的顺序相同, 而被

释放的顺序则与此相反。其次, 为确保内存管理器始

终可用, 我们将在allocatememory()和deallocatememory

()中调用Initializememory(), 从而保证内存管理器出于

活动状态。最后, 为确保内存管理器是最后一个被释

放的对象, 我们将使用atexit()方法。因此, 必须对内存

管理器作出的唯一限制是, 它必须是第一个调用::exit

函数的方法。

5 实际应用

Shugine 游戏引擎是我们自主研发的一个游戏引

擎, 由于游戏开发资源量庞大。在游戏中需要不停的

分配内存空间, 这样对于内存的合理分配和回收就成

了我们必须考虑的一个重要问题。内存泄漏所引发的

一切意料之外的事件都会给玩家带来意想不到的后

果, 甚至将失去玩家。在这个庞大的工程中, 加入这个

内存管理器, 来跟踪我们分配出去的每一块内存, 在

游戏最后退出时, 打印出内存的分配情况以及未释放

的内存。整个内存管理器在引擎的编写中起到了重要

的作用, 并且收到了良好的效果。图2 是内存管理器

应用于游戏引擎的打印报告的统计部分, 其中详细列

出了内存的分配情况。

图2 部分内存管理报告

Fig.2 part of the memory management report

同样内存管理器也有缺点, 管理器分配、释放以

及查询内存以获得统计信息需要占用额外的时间。虽

然, 我们已经在算法上做了改进, 但是, 在最后创建游

戏时, 我们将不会启用该选项。为了消除这一缺陷, 我

们只在调试时或符号MEMORY_CONTROL_ON 被定

义时, 才启用内存管理器。

6 结语

这个内存管理器提供了一下功能及特点:

1 无缝的接口, 即代码可以嵌入任何的工程中。

2 跟踪所有的内存分配及释放。

3 统计并报告内存分配情况与内存泄漏和越界操

作。

4 用户自定义选项, 以便定制自己的内存管理器。

由于其改进了释放和搜索算法, 使得内存管理器

在游戏引擎编写中的效率得到了大幅的提高, 并且其

无缝的接口以及个性化的定制选项, 为代码的重用创

造了良好的条件。我们在游戏引擎的开发过程中, 由于

使用了内存管理, 也使得整个工程在推进的过程中避

免了不少内存泄漏的问题。并且这个内存管理器可用

于任何软件工程中, 可作为是程序员的必备工具之一。

参考文献：

[1]Microsoft Developer Network Library,

library/devprods/vs6/visualc/vccore/

core_memory_management_with_mfc.3a_.overview.htm

[2]沈被娜,刘祖照.计算机软件基础（第三版）[M].北京.清华大学

出版社.2000.89- 90

[3]杨雷,吴珏,陈汶滨.实时系统中动静结合的内存管理实现[J].微

计算机信息,2005,10- 2:15- 16

[4]McConnell,Steve,Code Complete [M],Microsoft Press.1993.

[5]MicrosoftDeveloperNetworkLibrary,

devprods/vs6/visualc/vclang/_pluslang_initializing_static_objects.htm

[6]CHANG J M,GEHRINGGER E.A high - performance memory

allocator for obiected - oriented system [J].IEEE Transactions on

Computers,1996,45(3):357- 366.

作者简介: 周政春( 1983.2～) , 男, 浙江余姚人, 硕士研究

生。专业: 通信与信息系统。主要研究方向: 互动数字媒

体, 多媒体信号处理,E- mail: zhouzhengchun@163.

com。万旺根( 1961.6～) , 男, 江西南昌人, 教授、博士生

导师, 博士学位。专业: 信号与信息处理。主要研究领

域: 互动数字媒体, 多媒体信号处理。

Author br ief introduction:Zhou,Zhengchun,was born in

Shanghai,China,on Feb 8,1983.He received the B.S.from

Shanghai University,China,in 2004.His research interests include

interactive digital media,multi- media signal processing.

通讯地址:

( 200072 上海市闸北区延长路149 号上海大学行健

楼1202 室) 周政春

(投稿日期:2005.9.23) (修稿日期:2005.10.28)

更正说明

本文发表在2005 年10 月第3 期" 基于IP 技术的

端对端通信网络安全模型分析设计"的作者林永和，将

文章正确信息更正如下：

1、第一页第三行"（湖南国防科技大学）林永和"应

该为"（广东警官学院）林永和"；

2、第一页倒数第二行"林永和：副教授"应改为"林

永和：讲师"；

3、第二页第二栏第十八行" 作者简介：林永和

（1966- ），男，副教授" 应改为" 作者简介：林永和

（1966- ），男，讲师"；

4、第二页第二栏第二十六行"（410073 湖南国防

科技大学五院博士生队）林永和"应改为"（510232 广州

广州市滨江东路500 号广东警官学院教务处）林永和" .

-214-