李雨江

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

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

李雨江

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

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

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

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

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

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

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

2 算法設(shè)計

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

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

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

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

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

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

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

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

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

內(nèi)存碎片是因為在分配一個內(nèi)存塊后，使之空閑，但不將空閑內(nèi)存歸還給最大內(nèi)存塊而產(chǎn)生的。內(nèi)存的分配和釋放都有可能產(chǎn)生內(nèi)存碎片。內(nèi)存分配時，空閑塊分割的剩余部分仍舊留在閑空間，如果剩余部分小于請求的內(nèi)存大小，那么該部分便成了內(nèi)存碎片。內(nèi)存釋放時，如果被釋放的內(nèi)存塊小于請求的內(nèi)存大小，該內(nèi)存塊也成了內(nèi)存碎片。

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

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

2.2.3 異常處理

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

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

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

2.3 流程描述

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

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

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

3 測試結(jié)果

按照上述流程，實現(xiàn)了聯(lián)邦內(nèi)存分配函數(shù)federationMalloc和聯(lián)邦內(nèi)存釋放函數(shù)federationFree。本文利用白盒測試工具BullseyeCoverage對這兩個函數(shù)進行了測試，測試用例的內(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的測試結(jié)果和控制臺的顯示信息分別如圖4、圖5所示。其中，圖4中的第一行分別表示函數(shù)名稱、函數(shù)覆蓋率、未覆蓋的函數(shù)數(shù)量、條件/判定覆蓋率、未覆蓋條件/判定的數(shù)目（該函數(shù)所含有的條件/判定數(shù)目減去已經(jīng)覆蓋的條件/判定數(shù)目）。圖5中虛線的上部分是執(zhí)行測試用例1）后聯(lián)邦閑空間和忙空間的情況，虛線以下部分是執(zhí)行測試用例2）后聯(lián)邦閑空間和忙空間的情況。

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

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

圖5 控制臺的顯示信息

4 結(jié)語

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

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

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

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

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

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

［6］ 郭國弟，雷冠軍，閆娜.程序語言中的異常處理機制［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—），女，廣東湛江人，助教，碩士，主要從事分布式仿真研究。