一种基于VMIC网的内存分配算法

李雨江

(湛江师范学院数学与计算科学学院，广东湛江524048)

在分布式实时仿真系统中，为了弥补RTI在实时性方面的缺陷［1］，满足系统对高实时性的需求，往往需要引入VMIC实时网。对于VMIC实时网而言，如何划分VMIC的内存空间，动态实现仿真数据的分配和释放，为仿真任务提供准确的数据保障，是一个必须解决的问题。针对该问题，在此提出了一种基于链表［2，3］的动态内存分配算法。

1 VMIC网原理

VMIC网主要是由VMIC板卡通过光纤等传输介质连接而成的。VMIC网中的每个计算节点都安装一块VMIC板卡，且每个节点的VMIC板卡的存储器中都有VMIC网上其他节点的共享数据拷贝。每个VMIC板卡都占有一段内存空间，当VMIC网中的任意计算节点向本地VMIC板卡写入数据时，该数据和相应的内存地址将被广播到网上所有其他VMIC板卡并存储在相同的位置。在极短的时间内，网上所有计算节点都可以访问这个新数据。这样，用户对本地节点内存的读写相当于对全局内存进行读写，而该全局内存是所有分布节点都可共享的，从而实现了分布节点间的实时数据通信。

VMIC板卡使用简单的读写方式，对于CPU来说就相当于标准的RAM，而且VMIC网传输是纯硬件操作，不需考虑网络的通信协议，几乎不需要软件操作，因此它与以太网相比具有更低的数据传输延迟、更快的传输速度，可以满足实时系统快速反应周期的要求。对低延迟、实时性要求高的分布式实时仿真系统来说，VMIC网是一个理想的解决方案［4］。

2 基于链表的动态内存分配算法

2.1 相关数据定义

为给仿真系统提供充分的数据支持，本文将128 M的VMIC板卡划分为3个部分:第1部分用于存储系统时间和预估时间，占1 M内存;第2部分用于存储联邦、联邦成员和类实例数据，占126 M空间;剩下部分作为系统保留空间，用于日后扩展。根据仿真系统中数据之间的逻辑关系，本文将第2部分内存的划分为3个层次，如图1所示。从图1可知，VMIC板卡的第2部分内存分为联邦、联邦成员和类实例3个层次。某个联邦可以为其所属的若干联邦成员分配内存空间，而某个联邦成员同样可以为其所属的若干类实例分配空间。按照该逻辑关系，本文对相关数据作了如下若干定义。

图1 VMIC板卡内存划分图

2.1.1 符号定义

Fnum:联邦的唯一编号，编号从0到9;fnum:联邦成员的唯一编号，编号从10到99;Insnum:对象类实例或交互类实例(统称类实例)的唯一编号，编号从100开始;O:块空间在板卡上的起始位置;S:块空间的大小。

2.1.2 关系定义

R1(Fnum，S):联邦Fnum的空间大小为S;R2(Fnum，fnum，S):联邦成员fnum的空间大小为S，它属于联邦Fnum;R3(Fnum，fnum，Insnum，S):对象类/交互类实例Insnum的空间大小为S，它属于联邦Fnum的联邦成员fnum。

2.1.3 结构体定义

联邦的定义如下:

typedef struct federationNode{

int federationNum; ∥联邦编号

int federationOffset; ∥联邦偏移

int federationSize; ∥联邦大小

struct federationNode* nextNode; ∥指向下一个联邦的指针

}node;

联邦成员的定义如下:

typedef struct federateNode{

int federationNum; ∥联邦编号

int federateNum; ∥联邦成员编号

int federateOffset; ∥联邦成员偏移

int federateSize; ∥联邦成员大小

struct federateNode* nextNode; ∥指向下一个联邦成员的指针

}feNode;

类实例的定义如下:

typedef struct obj_inter_Node{

int federationNum; ∥联邦编号

int federateNum; ∥联邦成员编号

int obj_interNum; ∥类实例的编号

int obj_interOffset; ∥类实例的偏移

int obj_interSize; ∥类实例的大小

struct obj_inter_Node* nextNode; ∥指向下一个类实例的指针

}oiNode。

图2 联邦成员fnum i的空间分配流程

图3 联邦成员fnum i的空间释放流程

2.1.4 链表定义

该内存分配算法共维护了6条链表，分别如下:

联邦闲链表:链表中的每一个节点表示可分配的联邦空闲空间，每个节点均是node类型，freeHead是该链表的头指针;

联邦忙链表:链表中的每一个节点表示已经占用的联邦空间，每个节点均是为node类型，头指针为busyHead;

联邦成员闲链表:链表中的每一个节点表示可分配的联邦成员空闲空间，每个节点均是为feNode类型，头指针为feFreeHead;

联邦成员忙链表:链表中的每一个节点表示已经占用的联邦成员空间，每个节点均是为feNode类型，头指针为feBusyHead;

类实例闲链表:链表中的每一个节点表示可分配的类实例空闲空间，每个节点均是为oiNode类型，头指针为oi_interFreeHead;

类实例忙链表:链表中的每一个节点表示已经占用的类实例空间，每个节点均是为oiNode类型，头指针为oi_interBusyHead。

2.2 算法描述

以联邦成员的空间分配和释放算法为例，描述基于VMIC内存的动态分配和释放过程。设联邦成员满足关系R2(Fnumi，fnumi，Si)，其空间分配算法的流程如图2所示，联邦成员fnumi的空间释放算法的流程如图3所示。

同样地，仿照上述流程，实现了联邦和类实例成员的内存分配算法。

图4 实验验证截图

3 实验验证

实验测试方式为测试者从键盘输入要测试的次数，然后针对每一次测试，系统随机生成本次的测试次数，在此基础上，系统再随机生成空间分配次数和释放次数。图4是针对联邦成员内存分配和释放过程测试10次的截图。

4 结束语

基于链表的动态内存分配算法能够较好地对VMIC板卡空间进行动态分配和释放，能够较好地处理在内存分配和释放过程中出现的异常。由于本文使用的是单向链表，在查找符合某种条件的空间结点时，须从链表头部开始，依次往后遍历查找，这样的查找方式效率并不高。下一步要做的工作是改进该查找方式，以提高链表的查找效率。

［1］WUERFE R D，JOHNSTON C R.Real-Time Performance of RTI Version 1.3［C］.SIW，Fall 1999

［2］严蔚敏，吴伟民.数据结构［M］.北京:清华大学出版社，2006

［3］谭浩强.C语言程序设计［M］.北京:清华大学出版社，2005

［4］顾颖彦.反射内存网实时通信技术的研究［J］.计算机工程，2002(7):143-144