分布仿真系統(tǒng)中的動(dòng)態(tài)內(nèi)存分配算法

李雨江

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

分布仿真系統(tǒng)中的動(dòng)態(tài)內(nèi)存分配算法

李雨江

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

針對(duì)分布仿真系統(tǒng)中的內(nèi)存分配問(wèn)題，提出了一種基于VMIC的內(nèi)存分配算法，利用向量和映射相結(jié)合的方式對(duì)VMIC板卡的內(nèi)存空間進(jìn)行動(dòng)態(tài)分配和釋放。試驗(yàn)表明，該算法能夠準(zhǔn)確地為仿真數(shù)據(jù)分配和釋放空間，處理內(nèi)存分配和釋放過(guò)程中出現(xiàn)的異常，且能夠及時(shí)合并空閑空間以減少內(nèi)存碎片，從而滿足分布仿真系統(tǒng)對(duì)大量數(shù)據(jù)的存取需求。

分布仿真系統(tǒng)；VMIC；內(nèi)存分配；向量；映射

當(dāng)前的分布仿真系統(tǒng)主要基于HLA/RTI平臺(tái)搭建。由于RTI在實(shí)時(shí)性方面的缺陷［1］，使其難以滿足對(duì)實(shí)時(shí)性要求很高的半實(shí)物仿真系統(tǒng)，因此，往往需要引入VMIC實(shí)時(shí)網(wǎng)，從網(wǎng)絡(luò)方面擴(kuò)展分布仿真系統(tǒng)的實(shí)時(shí)性［2］。在這樣的異構(gòu)網(wǎng)絡(luò)環(huán)境中，如何分配和釋放VMIC板卡的內(nèi)存空間，為分布仿真系統(tǒng)提供有力數(shù)據(jù)支持，是一個(gè)需要解決的重要問(wèn)題。本文提出了一種利用向量和映射實(shí)現(xiàn)的動(dòng)態(tài)內(nèi)存分配算法。

1 VMIC實(shí)時(shí)網(wǎng)原理

VMIC實(shí)時(shí)網(wǎng)主要是由VMIC板卡通過(guò)光纖等傳輸介質(zhì)連接而成的。實(shí)時(shí)網(wǎng)中的每個(gè)計(jì)算節(jié)點(diǎn)都安裝一塊VMIC卡。每塊卡上都有自己獨(dú)立的局部?jī)?nèi)存，它通過(guò)局部?jī)?nèi)存映射將網(wǎng)卡上的局部?jī)?nèi)存映射到主機(jī)內(nèi)存，用戶讀寫網(wǎng)卡上的數(shù)據(jù)就如同讀寫主機(jī)內(nèi)存上的數(shù)據(jù)一樣快速、方便。此外，每塊VMIC反射內(nèi)存卡通過(guò)網(wǎng)絡(luò)內(nèi)存映射，將分布在節(jié)點(diǎn)卡上的局部?jī)?nèi)存，映射到一個(gè)虛擬的全局內(nèi)存，即每個(gè)節(jié)點(diǎn)在寫入本地節(jié)點(diǎn)卡的數(shù)據(jù)同時(shí)也寫入所有其他節(jié)點(diǎn)卡的內(nèi)存，這樣，用戶對(duì)本地節(jié)點(diǎn)內(nèi)存的讀寫相當(dāng)于對(duì)全局內(nèi)存進(jìn)行讀寫，而這個(gè)全局內(nèi)存是所有分布節(jié)點(diǎn)都可共享的，從而實(shí)現(xiàn)了分布節(jié)點(diǎn)間的實(shí)時(shí)數(shù)據(jù)通信［3］。

VMIC反射內(nèi)存網(wǎng)可以達(dá)到數(shù)十兆字節(jié)的傳輸率和百納秒級(jí)的數(shù)據(jù)傳輸延遲，且這種網(wǎng)絡(luò)的傳輸延遲是確定和可以預(yù)期的，這是傳統(tǒng)網(wǎng)絡(luò)難以達(dá)到的［4］。因此，對(duì)低延遲、實(shí)時(shí)性要求高的分布式仿真系統(tǒng)來(lái)說(shuō)，VMIC網(wǎng)是一個(gè)理想的解決方案。

2 算法設(shè)計(jì)

2.1 VMIC反射內(nèi)存的層次劃分

本文將內(nèi)存為128M的VMIC板卡劃分為三個(gè)部分:第一部分用于存儲(chǔ)系統(tǒng)時(shí)間和預(yù)估時(shí)間，占1M空間；第二部分用于存儲(chǔ)聯(lián)邦、聯(lián)邦成員和類實(shí)例數(shù)據(jù)，占126M空間；剩下部分作為系統(tǒng)保留空間，用于日后擴(kuò)展。根據(jù)仿真系統(tǒng)中數(shù)據(jù)之間的邏輯關(guān)系，進(jìn)一步將第二部分內(nèi)存分為三個(gè)層次，如圖1所示。

從圖1可知，VMIC板卡的第二部分內(nèi)存分為聯(lián)邦、聯(lián)邦成員和類實(shí)例三個(gè)層次。第一層次為聯(lián)邦所占用的空間和相應(yīng)剩余空間，第二層次是在聯(lián)邦內(nèi)部進(jìn)行的劃分，分為某聯(lián)邦所屬聯(lián)邦成員所占的空間和相應(yīng)剩余空間，第三層次是在聯(lián)邦成員內(nèi)部進(jìn)行的劃分，分為某聯(lián)邦成員所屬類實(shí)例所占的空間和相應(yīng)剩余空間。

2.2 關(guān)鍵問(wèn)題的解決方案

2.2.1 使用最佳適應(yīng)算法分配內(nèi)存

最佳適應(yīng)算法［5］是指每次為作業(yè)分配內(nèi)存時(shí)，總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”。為了加速尋找，該算法要求將所有的空閑分區(qū)按從小到大的順序排成一空閑分區(qū)鏈。這樣，第一次找到的能滿足要求的空閑區(qū)，必然是最佳的。

圖1 VMIC卡第二部分內(nèi)存空間的劃分情況

根據(jù)最佳適應(yīng)算法的思想，當(dāng)聯(lián)邦、聯(lián)邦成員和類實(shí)例申請(qǐng)空間時(shí)，如果閑空間中有恰好滿足申請(qǐng)者所要求的空閑塊，則將該塊分配給申請(qǐng)者，否則選擇滿足要求且為最小的空閑塊，對(duì)其進(jìn)行分割，將申請(qǐng)者所要求的空間分配給申請(qǐng)者，剩余部分仍舊留在閑空間。

2.2.2 減少內(nèi)存碎片

內(nèi)存碎片是因?yàn)樵诜峙湟粋€(gè)內(nèi)存塊后，使之空閑，但不將空閑內(nèi)存歸還給最大內(nèi)存塊而產(chǎn)生的。內(nèi)存的分配和釋放都有可能產(chǎn)生內(nèi)存碎片。內(nèi)存分配時(shí)，空閑塊分割的剩余部分仍舊留在閑空間，如果剩余部分小于請(qǐng)求的內(nèi)存大小，那么該部分便成了內(nèi)存碎片。內(nèi)存釋放時(shí)，如果被釋放的內(nèi)存塊小于請(qǐng)求的內(nèi)存大小，該內(nèi)存塊也成了內(nèi)存碎片。

塊移動(dòng)的辦法可以使每次空閑的內(nèi)存與最大內(nèi)存塊相連接（這種方法可以徹底避免內(nèi)存碎片問(wèn)題），即將已占用塊移動(dòng)到相鄰位置，空閑塊移動(dòng)到相鄰位置并連接。但這種方式的算法實(shí)現(xiàn)既復(fù)雜又耗時(shí)，而且每次所釋放的內(nèi)存往往并不剛好和最大內(nèi)存塊相鄰，那么，往往每釋放一空閑塊，就要進(jìn)行一次移動(dòng)工作。因此，這種方式難以應(yīng)用在實(shí)際的內(nèi)存分配程序中。

即使一個(gè)內(nèi)存分配程序不能保證返回的內(nèi)存能與最大內(nèi)存塊相連接，但可以設(shè)法控制并限制內(nèi)存碎片。本文采取了減少被分割內(nèi)存塊的數(shù)量和連接相鄰空閑內(nèi)存塊的辦法。在內(nèi)存分配過(guò)程中，假設(shè)申請(qǐng)者請(qǐng)求的內(nèi)存大小為k，為盡量避免內(nèi)存塊的分割，優(yōu)先尋找大小為k的空閑塊將其分配給申請(qǐng)者，如果當(dāng)前不存在大小為k的空閑塊，再考慮對(duì)大小大于k的空閑塊進(jìn)行分割。當(dāng)內(nèi)存釋放時(shí)，和該內(nèi)存相鄰的內(nèi)存塊將被合并以形成一個(gè)更大的空閑內(nèi)存塊，這樣減少了空閑塊的數(shù)量，有助于減少內(nèi)存碎片。

2.2.3 異常處理

在內(nèi)存的分配和釋放過(guò)程中都有可能產(chǎn)生異常。所謂異常是指程序執(zhí)行過(guò)程中發(fā)生的特殊事件，可能是錯(cuò)誤（例如:除數(shù)為0），也可能是程序員自定義的某一需要注意的情況（例如:執(zhí)行刪除操作時(shí)彈出的警告對(duì)話框）［6］。當(dāng)異常產(chǎn)生后，程序要及時(shí)進(jìn)行異常處理。

內(nèi)存分配主要考慮內(nèi)存不足和重復(fù)分配內(nèi)存兩種情況:當(dāng)聯(lián)邦、聯(lián)邦成員和類實(shí)例申請(qǐng)空間時(shí)，如果當(dāng)前所有空閑塊均不能滿足申請(qǐng)者所要求的空間，分配程序應(yīng)停止分配操作，提示空間不足，返回0值表示分配失敗；當(dāng)已經(jīng)分配了空間的聯(lián)邦、聯(lián)邦成員和類實(shí)例未進(jìn)行內(nèi)存釋放操作，又再次申請(qǐng)空間時(shí)，分配程序應(yīng)停止分配操作，提示重復(fù)分配，返回0值表示分配失敗。

內(nèi)存釋放主要考慮對(duì)并不存在的聯(lián)邦、聯(lián)邦成員和類實(shí)例釋放內(nèi)存的情況。在這種情況下，釋放程序應(yīng)停止釋放操作，提示所要釋放的聯(lián)邦、聯(lián)邦成員和類實(shí)例并不存在，釋放程序直接結(jié)束。

2.3 流程描述

VMIC實(shí)時(shí)網(wǎng)能從硬件方面保證分布仿真系統(tǒng)的實(shí)時(shí)性，系統(tǒng)對(duì)動(dòng)態(tài)內(nèi)存分配算法的基本要求就是準(zhǔn)確性，因此沒必要采用通用操作系統(tǒng)中完善但卻復(fù)雜的內(nèi)存分配策略，只要能夠準(zhǔn)確地為聯(lián)邦、聯(lián)邦成員和類實(shí)例分配空間以及釋放空間即可。以聯(lián)邦的空間分配為例，描述該算法的空間分配過(guò)程。數(shù)據(jù)結(jié)構(gòu)方面，聯(lián)邦忙空間用向量表示，向量中的每個(gè)元素都是指向某個(gè)聯(lián)邦的指針；聯(lián)邦閑空間用映射表示，映射中的每一key-value對(duì)表示某空閑塊的起始地址和大小。假設(shè)聯(lián)邦Fnumi的大小為Si，其空間分配和釋放的流程分別如圖2、圖3所示。

圖2 聯(lián)邦Fnumi的內(nèi)存分配流程

圖3 聯(lián)邦Fnumi的內(nèi)存釋放流程

3 測(cè)試結(jié)果

按照上述流程，實(shí)現(xiàn)了聯(lián)邦內(nèi)存分配函數(shù)federationMalloc和聯(lián)邦內(nèi)存釋放函數(shù)federationFree。本文利用白盒測(cè)試工具BullseyeCoverage對(duì)這兩個(gè)函數(shù)進(jìn)行了測(cè)試，測(cè)試用例的內(nèi)容為:1）為聯(lián)邦1和0分別分配空間1 024k、13 004 8k（空間不足異常），再次為聯(lián)邦1分配1 000k空間（空間重復(fù)分配異常），分別為聯(lián)邦2至聯(lián)邦7分配空間1 098k、1 002k、5 000k、6 102k、4 506k、1 608k；2）釋放聯(lián)邦2的空間，為聯(lián)邦8分配1 098k空間，再依次釋放聯(lián)邦8、1（右相鄰）、3（左相鄰）、5、7、6（左右相鄰）的空間，最后釋放聯(lián)邦1的空間（釋放并不存在的聯(lián)邦導(dǎo)致異常）。

BullseyeCoverage的測(cè)試結(jié)果和控制臺(tái)的顯示信息分別如圖4、圖5所示。其中，圖4中的第一行分別表示函數(shù)名稱、函數(shù)覆蓋率、未覆蓋的函數(shù)數(shù)量、條件/判定覆蓋率、未覆蓋條件/判定的數(shù)目（該函數(shù)所含有的條件/判定數(shù)目減去已經(jīng)覆蓋的條件/判定數(shù)目）。圖5中虛線的上部分是執(zhí)行測(cè)試用例1）后聯(lián)邦閑空間和忙空間的情況，虛線以下部分是執(zhí)行測(cè)試用例2）后聯(lián)邦閑空間和忙空間的情況。

圖4 BullseyeCoverag的測(cè)試結(jié)果

從圖4可知，這兩個(gè)函數(shù)覆蓋率和條件/判定覆蓋率均為100%，這意味著函數(shù)中的所有獨(dú)立的路徑都被執(zhí)行過(guò)，每一個(gè)判定分支的真假值都被執(zhí)行過(guò)，且每條判定分支中的每個(gè)子表達(dá)式的真假值也都被執(zhí)行過(guò)。從圖5可以看出，這兩個(gè)函數(shù)的測(cè)試結(jié)果和實(shí)際情況是完全一致的，也就是說(shuō)聯(lián)邦內(nèi)存分配函數(shù)和釋放函數(shù)能夠正確處理正常情況和異常情況下的內(nèi)存分配及釋放需求。

圖5 控制臺(tái)的顯示信息

4 結(jié)語(yǔ)

該動(dòng)態(tài)內(nèi)存分配算法能夠?yàn)榉植挤抡嫦到y(tǒng)中的各類仿真數(shù)據(jù)準(zhǔn)確地分配和釋放內(nèi)存空間，及時(shí)合并空閑內(nèi)存空間以處理內(nèi)存分配和釋放過(guò)程中的出現(xiàn)的異常，提升了系統(tǒng)的空間利用率和健壯性。由于本文使用向量存放各類仿真數(shù)據(jù)已經(jīng)分配的空間，當(dāng)查找符合特定條件的空間結(jié)點(diǎn)時(shí)，須從向量頭部開始，依次往后遍歷查找，逐一判斷，直至找到符合特定條件的空間節(jié)點(diǎn)為止或是遍歷完整個(gè)向量得出不存在該特定空間節(jié)點(diǎn)的結(jié)論，這種查找方式的時(shí)間效率不夠高，下一步工作是建立索引以加快查詢速度。

［1］ 胡良兵，杜承烈，尤濤，等.基于RTX和VMIC的虛擬試驗(yàn)聯(lián)邦支撐環(huán)境研究［J］.計(jì)算機(jī)測(cè)量與控制，2011，19（5）:11-13.

［2］ 侯兵強(qiáng)，杜承烈，尤濤，等.VMIC下基于聯(lián)邦范型的虛擬試驗(yàn)支撐環(huán)境研究［J］.計(jì)算機(jī)測(cè)量與控制，2010（2）:385-388.

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

［4］ 陳杰，宋李彬，朱小娟，等.基于VMIC實(shí)時(shí)網(wǎng)的網(wǎng)絡(luò)管理研究［J］.信息化研究，2009，35（11）:20-23.

［5］ 湯小丹，梁紅兵，哲鳳屏，等.計(jì)算機(jī)操作系統(tǒng)［M］.三版.西安:西安電子科技大學(xué)，2013:124.

［6］ 郭國(guó)弟，雷冠軍，閆娜.程序語(yǔ)言中的異常處理機(jī)制［J］.科技信息，2008（19）:407-408.

Dynamic Memory Allocation Algorithm inDistributed Simulation System

LIYu.jiang
（School of Mathematics and Computation Science，Zhanjiang Mormal University，Zhanjiang 524048，China）

According to the memory allocation problem in distributed simulation system，a dynamic memory allocation algorithm is proposed based on VMIC，which allocates and frees the memory space dynamically by vector and map.The test indicates that the algorithm is able to allocate memory and free memory for simulation data accurately，deal with the exceptions during memory allocation and release，and combine free memory together timely to reduce memory fragments aswell，thus satisfying the access requirements of huge data in distributed simulation system.

distributed simulation system；VMIC；memory allocation；vector；map

TP391.9

A

1009-0312（2014）01-0057-04

2013-10-09

李雨江（1985—），女，廣東湛江人，助教，碩士，主要從事分布式仿真研究。