一種基于VMIC網(wǎng)的內(nèi)存分配算法

李雨江

(湛江師范學(xué)院數(shù)學(xué)與計算科學(xué)學(xué)院，廣東湛江524048)

在分布式實時仿真系統(tǒng)中，為了彌補RTI在實時性方面的缺陷［1］，滿足系統(tǒng)對高實時性的需求，往往需要引入VMIC實時網(wǎng)。對于VMIC實時網(wǎng)而言，如何劃分VMIC的內(nèi)存空間，動態(tài)實現(xiàn)仿真數(shù)據(jù)的分配和釋放，為仿真任務(wù)提供準確的數(shù)據(jù)保障，是一個必須解決的問題。針對該問題，在此提出了一種基于鏈表［2，3］的動態(tài)內(nèi)存分配算法。

1 VMIC網(wǎng)原理

VMIC網(wǎng)主要是由VMIC板卡通過光纖等傳輸介質(zhì)連接而成的。VMIC網(wǎng)中的每個計算節(jié)點都安裝一塊VMIC板卡，且每個節(jié)點的VMIC板卡的存儲器中都有VMIC網(wǎng)上其他節(jié)點的共享數(shù)據(jù)拷貝。每個VMIC板卡都占有一段內(nèi)存空間，當(dāng)VMIC網(wǎng)中的任意計算節(jié)點向本地VMIC板卡寫入數(shù)據(jù)時，該數(shù)據(jù)和相應(yīng)的內(nèi)存地址將被廣播到網(wǎng)上所有其他VMIC板卡并存儲在相同的位置。在極短的時間內(nèi)，網(wǎng)上所有計算節(jié)點都可以訪問這個新數(shù)據(jù)。這樣，用戶對本地節(jié)點內(nèi)存的讀寫相當(dāng)于對全局內(nèi)存進行讀寫，而該全局內(nèi)存是所有分布節(jié)點都可共享的，從而實現(xiàn)了分布節(jié)點間的實時數(shù)據(jù)通信。

VMIC板卡使用簡單的讀寫方式，對于CPU來說就相當(dāng)于標(biāo)準的RAM，而且VMIC網(wǎng)傳輸是純硬件操作，不需考慮網(wǎng)絡(luò)的通信協(xié)議，幾乎不需要軟件操作，因此它與以太網(wǎng)相比具有更低的數(shù)據(jù)傳輸延遲、更快的傳輸速度，可以滿足實時系統(tǒng)快速反應(yīng)周期的要求。對低延遲、實時性要求高的分布式實時仿真系統(tǒng)來說，VMIC網(wǎng)是一個理想的解決方案［4］。

2 基于鏈表的動態(tài)內(nèi)存分配算法

2.1 相關(guān)數(shù)據(jù)定義

為給仿真系統(tǒng)提供充分的數(shù)據(jù)支持，本文將128 M的VMIC板卡劃分為3個部分:第1部分用于存儲系統(tǒng)時間和預(yù)估時間，占1 M內(nèi)存;第2部分用于存儲聯(lián)邦、聯(lián)邦成員和類實例數(shù)據(jù)，占126 M空間;剩下部分作為系統(tǒng)保留空間，用于日后擴展。根據(jù)仿真系統(tǒng)中數(shù)據(jù)之間的邏輯關(guān)系，本文將第2部分內(nèi)存的劃分為3個層次，如圖1所示。從圖1可知，VMIC板卡的第2部分內(nèi)存分為聯(lián)邦、聯(lián)邦成員和類實例3個層次。某個聯(lián)邦可以為其所屬的若干聯(lián)邦成員分配內(nèi)存空間，而某個聯(lián)邦成員同樣可以為其所屬的若干類實例分配空間。按照該邏輯關(guān)系，本文對相關(guān)數(shù)據(jù)作了如下若干定義。

圖1 VMIC板卡內(nèi)存劃分圖

2.1.1 符號定義

Fnum:聯(lián)邦的唯一編號，編號從0到9;fnum:聯(lián)邦成員的唯一編號，編號從10到99;Insnum:對象類實例或交互類實例(統(tǒng)稱類實例)的唯一編號，編號從100開始;O:塊空間在板卡上的起始位置;S:塊空間的大小。

2.1.2 關(guān)系定義

R1(Fnum，S):聯(lián)邦Fnum的空間大小為S;R2(Fnum，fnum，S):聯(lián)邦成員fnum的空間大小為S，它屬于聯(lián)邦Fnum;R3(Fnum，fnum，Insnum，S):對象類/交互類實例Insnum的空間大小為S，它屬于聯(lián)邦Fnum的聯(lián)邦成員fnum。

2.1.3 結(jié)構(gòu)體定義

聯(lián)邦的定義如下:

typedef struct federationNode{

int federationNum; ∥聯(lián)邦編號

int federationOffset; ∥聯(lián)邦偏移

int federationSize; ∥聯(lián)邦大小

struct federationNode* nextNode; ∥指向下一個聯(lián)邦的指針

}node;

聯(lián)邦成員的定義如下:

typedef struct federateNode{

int federationNum; ∥聯(lián)邦編號

int federateNum; ∥聯(lián)邦成員編號

int federateOffset; ∥聯(lián)邦成員偏移

int federateSize; ∥聯(lián)邦成員大小

struct federateNode* nextNode; ∥指向下一個聯(lián)邦成員的指針

}feNode;

類實例的定義如下:

typedef struct obj_inter_Node{

int federationNum; ∥聯(lián)邦編號

int federateNum; ∥聯(lián)邦成員編號

int obj_interNum; ∥類實例的編號

int obj_interOffset; ∥類實例的偏移

int obj_interSize; ∥類實例的大小

struct obj_inter_Node* nextNode; ∥指向下一個類實例的指針

}oiNode。

圖2 聯(lián)邦成員fnum i的空間分配流程

圖3 聯(lián)邦成員fnum i的空間釋放流程

2.1.4 鏈表定義

該內(nèi)存分配算法共維護了6條鏈表，分別如下:

聯(lián)邦閑鏈表:鏈表中的每一個節(jié)點表示可分配的聯(lián)邦空閑空間，每個節(jié)點均是node類型，freeHead是該鏈表的頭指針;

聯(lián)邦忙鏈表:鏈表中的每一個節(jié)點表示已經(jīng)占用的聯(lián)邦空間，每個節(jié)點均是為node類型，頭指針為busyHead;

聯(lián)邦成員閑鏈表:鏈表中的每一個節(jié)點表示可分配的聯(lián)邦成員空閑空間，每個節(jié)點均是為feNode類型，頭指針為feFreeHead;

聯(lián)邦成員忙鏈表:鏈表中的每一個節(jié)點表示已經(jīng)占用的聯(lián)邦成員空間，每個節(jié)點均是為feNode類型，頭指針為feBusyHead;

類實例閑鏈表:鏈表中的每一個節(jié)點表示可分配的類實例空閑空間，每個節(jié)點均是為oiNode類型，頭指針為oi_interFreeHead;

類實例忙鏈表:鏈表中的每一個節(jié)點表示已經(jīng)占用的類實例空間，每個節(jié)點均是為oiNode類型，頭指針為oi_interBusyHead。

2.2 算法描述

以聯(lián)邦成員的空間分配和釋放算法為例，描述基于VMIC內(nèi)存的動態(tài)分配和釋放過程。設(shè)聯(lián)邦成員滿足關(guān)系R2(Fnumi，fnumi，Si)，其空間分配算法的流程如圖2所示，聯(lián)邦成員fnumi的空間釋放算法的流程如圖3所示。

同樣地，仿照上述流程，實現(xiàn)了聯(lián)邦和類實例成員的內(nèi)存分配算法。

圖4 實驗驗證截圖

3 實驗驗證

實驗測試方式為測試者從鍵盤輸入要測試的次數(shù)，然后針對每一次測試，系統(tǒng)隨機生成本次的測試次數(shù)，在此基礎(chǔ)上，系統(tǒng)再隨機生成空間分配次數(shù)和釋放次數(shù)。圖4是針對聯(lián)邦成員內(nèi)存分配和釋放過程測試10次的截圖。

4 結(jié)束語

基于鏈表的動態(tài)內(nèi)存分配算法能夠較好地對VMIC板卡空間進行動態(tài)分配和釋放，能夠較好地處理在內(nèi)存分配和釋放過程中出現(xiàn)的異常。由于本文使用的是單向鏈表，在查找符合某種條件的空間結(jié)點時，須從鏈表頭部開始，依次往后遍歷查找，這樣的查找方式效率并不高。下一步要做的工作是改進該查找方式，以提高鏈表的查找效率。

［1］WUERFE R D，JOHNSTON C R.Real-Time Performance of RTI Version 1.3［C］.SIW，F(xiàn)all 1999

［2］嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)［M］.北京:清華大學(xué)出版社，2006

［3］譚浩強.C語言程序設(shè)計［M］.北京:清華大學(xué)出版社，2005

［4］顧穎彥.反射內(nèi)存網(wǎng)實時通信技術(shù)的研究［J］.計算機工程，2002(7):143-144