高層體系結構中時間管理算法研究及改進

王 月，李宏偉，孫黎陽

(1.中國人民解放軍65635部隊，遼寧 錦州 121017；2.解放軍理工大學工程兵工程學院，南京 210094；3.中國電子科技集團公司第二十八研究所，南京 210007)

1 概述

高層體系結構(High Level Architecture, HLA)[1]是美國國防部提出的關于分布式仿真的一個標準，其主要目的是實現(xiàn)各類仿真的互操作和重用。在典型的分布式仿真應用中，由于成員(Federate)方的計算量、處理器的計算速度及網(wǎng)絡延遲等因素的影響，因此成員之間的消息傳遞存在不確定性，而消息的先后次序對整個仿真是非常重要的。

時間管理服務是 HLA的重要組成部分，其主要目的是保證成員能夠按照正確的順序接收消息，從而保證仿真的正確執(zhí)行。HLA支持2類時間推進機制，即保守成員的時間推進機制和樂觀成員的時間推進機制。

保守成員可采用TAR(Time Advance Request)、TARA(Time Advance Request Available)、NMR(Next Message Request)(IEEE 1516中的NMR/NMRA對應于 HLA1.3中的 NER/NERA)和 NMRA(Next Message Request Available)等 4種 HLA標準服務進行時間推進；樂觀成員可采用FQR(Flush Queue Request)服務進行時間推進。時間管理服務是基于HLA標準實現(xiàn) RTI(Runtime Infrastructure)軟件的重點和難點，而GALT(Greatest Available Logical Time)(IEEE 1516中的 GALT相當于 HLA1.3中的 LBTS(Lower Bound Time Stamp))。IEEE 1516去掉了 LBTS，而增加GALT和LITS(Least Incoming Time Stamp)的計算問題則是 RTI中時間管理模塊實現(xiàn)的關鍵。GALT是IEEE 1516標準提出的新概念，在此之前，GALT被稱為LBTS。

本文遵循 IEEE1516標準，統(tǒng)一采用 GALT名稱。GALT計算應該綜合考慮各種時間推進方式，許多學者對此進行了卓有成效的研究，但考慮得不夠全面。文獻[2]對RTI中保守時間推進機制進行了分析，討論了如何避免死鎖，但主要針對死鎖檢測機制進行研究。文獻[3]對HLA中保守和樂觀時間推進機制進行了比較和分析，但未涉及死鎖問題。文獻[4-5]都對HLA中的時間管理進行研究，特別 是文獻[5]對Lookahead為0時的情況進行了詳細研究。文獻[6]和文獻[7]對 HLA時間管理進行了優(yōu)化，目的在于提高 HLA運行性能，但并未對死鎖進行更深入研究。文獻[8]對HLA時間管理算法中時間推進策略進行了研究與實現(xiàn)，文獻[9]則對HLA的實時性進行了研究。縱觀上述研究，雖然都對HLA時間管理進行了研究，但是并未均涉及死鎖問題，而就算討論了時間管理中的死鎖問題，也并未從根本上找出死鎖產(chǎn)生的原因并解決之。

目前筆者暫未發(fā)現(xiàn)任何 RTI開發(fā)商公布其軟件中的GALT算法，但是，文獻[10]卻描述了一個簡單、實用的 GALT算法(當時使用的名稱是 LBTS)。作為HLA的參與者和制訂者，他們的算法應當具有可信性和權威性。該算法在通常情況下能夠較好地工作，但在特殊情況下會造成死鎖。

本文探討了HLA中TAR、TARA、NMR、NMRA 4種推進機制，解釋了死鎖出現(xiàn)的原因，分析Frederick算法在某種特殊情況下會出現(xiàn)死鎖的條件，提出了一種改進的時間管理算法，并驗證該改進算法可以避免死鎖。

2 時間推進機制及算法

2.1 基本術語

定義 1 GALT是指成員能夠推進的最大邏輯時間。

在保守時間推進機制下，HLA規(guī)范要求一個成員在仿真的任何時刻都不能接收到一個過時(即比成員的當前邏輯時間小)的消息。因此，在成員推進時，RTI必須確保成員的時間推進不能超過GALT這個時間上界，否則，在未來的邏輯時間里有可能接收到過時的消息。

定義2 LETS(Least Existent Time Stamp)是指成員消息隊列中已有消息的最小時標。

LETS不是IEEE 1516規(guī)范中的定義，而是為了敘述方便在本文中引進的。

定義3 LITS是指成員有可能接收到的最小消息的時標。

通過計算GALT和LETS，RTI能夠確定成員的LITS。LITS可取GALT和LETS的最小值。LITS和LETS的區(qū)別在于，LETS是那些已經(jīng)接收到的放在成員TSO隊列中的所有消息的最小時標；而LITS還可能包括那些仍在網(wǎng)絡中傳輸甚至還沒有發(fā)出的小時標的消息。

定義4 輸出時間(Output Time)是指 RTI計算出的成員能夠發(fā)送的消息時標的最大下界。

成員只能發(fā)送不小于輸出時間的消息，否則，其他成員有可能接收到一個過時的消息。據(jù)此，RTI在計算成員的 GALT時可由其他成員的輸出時間來得到。

定義5 掛起(Pending)是指成員在請求時間推進時因為沒有得到RTI的允許而處于暫停狀態(tài)。

定義6 死鎖(Deadlock)是指系統(tǒng)中有相互約束關系的成員均處于掛起狀態(tài)。

不同系統(tǒng)對死鎖的定義會有所不同，本文的死鎖是由計算GALT引起的。一個成員的時間推進狀態(tài)將直接影響其他成員的GALT計算，一個處于掛起狀態(tài)的成員需要其他成員 GALT的增加才有可能被解除掛起狀態(tài)而進入Grant狀態(tài)。如果有相互約束關系的成員都因為期望其他成員能夠增加 GALT而解除掛起狀態(tài)，那么這些成員就會處于互相等待狀態(tài)而形成死鎖。

本文所有定理和算法都以參加仿真的所有成員間既相互控制又相互受限為前提條件，且只針對保守情況下的時間推進方法，樂觀推進機制在此不做研究。

2.2 時間推進方式

HLA中時間推進方式分為獨立的時間推進方式和協(xié)商的時間推進方式兩大類。在獨立的時間推進方式下，RTI不參與成員時間推進的管理，各成員根據(jù)自己的仿真需要獨立、盡快地推進自己的邏輯時間，各成員的時間是相對獨立的。在協(xié)商時間推進方式下，RTI協(xié)調成員的時間推進，以確保聯(lián)邦執(zhí)行能保持系統(tǒng)中事件先后順序，保守協(xié)商推進機制包括TAR、TARA、NMR、NMRA 4種。

步進的時間推進(TAR、TARA)、基于事件的時間推進(NMR、NMRA)都是在RTI協(xié)調下進行的。在RTI頭文件中分別為不同推進類型定義了其函數(shù)原型：timeAdvanceRequest()，nextEventRequest()。聯(lián)邦成員調用相應的函數(shù)請求推進到希望的邏輯時間theTime，RTI根據(jù)聯(lián)邦成員的請求完成消息的 傳遞和處理后，采用回調函數(shù) timeAdvanceGrant()通知聯(lián)邦成員時間推進完成，成員在收到 timeAdvance-Grant()回調函數(shù)后就可以進入下一個時間推進過程。若請求推進的時間是不安全的，該聯(lián)邦成員將被掛起，被掛起的成員處于暫停狀態(tài)。當所有成員均被掛起后，系統(tǒng)出現(xiàn)死鎖。

3 Frederick算法及其死鎖問題

3.1 Frederick算法

對于任意成員i，其GALT計算公式為：

Frederick算法將成員的 GALT取值為其他成員輸出時間的最小值。算法的關鍵在于計算成員的輸出時間，輸出時間取決于成員的當前狀態(tài)、邏輯時間、Lookahead和LETS多個因素。

成員的輸出時間可按照下式計算：

其中，T(i)為成員i請求推進的時間；L(i)為成員i當前的Lookahead值；LETS(i)為成員i的消息隊列中最小消息的時標；GALT(i)為成員i的GALT值。

3.2 Frederick算法的死鎖問題

在討論 GALT計算的諸多文獻中，都著重于Grant、TAR、TARA狀態(tài)，而 Frederick算法較好地解決了成員使用 NMR、NMRA請求時間推進時的GALT計算問題，并且在絕大多數(shù)情況下非常實用和有效，但是該算法卻不能避免死鎖。

假設在一次仿真中只有A和B 2個成員參加，它們的Lookahead均為0.5。由于只有2個成員，因此一個成員的輸出時間就是另外一個成員的GALT。

Frederick算法中的死鎖情況如圖1所示。在墻上時間w1時刻，A和B均處于Grant狀態(tài)，它們的輸出時間均為t+0.5，GALT也同樣為t+0.5；在w2時刻處，成員A使用NMR請求推進到t+1，但因為此時它的GALT仍為t+0.5，所以成員A的請求被掛起；在w3時刻處，成員B使用NMR請求推進到t+2，這時在計算B的GALT時就會出現(xiàn)2種情況：

(1)由于B的GALT等于A的輸出時間，因此可取w3時刻之前的A的輸出時間t+0.5作為B的GALT，由于t+0.5小于B的請求時間t+2，因此B也被掛起，出現(xiàn)了死鎖。

(2)在 w3處，重新計算 A的輸出時間，但根據(jù)Frederick算法，A的輸出時間依賴于B的GALT，而B的GALT正是要求的結果，這樣在計算GALT或輸出時間時算法本身也會出現(xiàn)死鎖，即無法計算GALT或輸出時間。

圖1 Frederick算法中的死鎖

4 Frederick算法的改進

前面討論的死鎖問題本質上是因 GALT的算法不完善造成的，一個好的算法是不會造成死鎖的。下面介紹一種基于“身高測量法”的無死鎖算法[11]。

身高(stature)可定義為：

其中，H(i)表示成員i的身高；T(i)表示成員i的邏輯時間或請求推進的邏輯時間；L(i)表示成員 i的Lookahead；LETS(i)表示成員 i消息隊列中的最小消息的時標。

這里再次對FQR請求進行必要的說明，由于FQR請求總能夠得到滿足，因此在具體的RTI實現(xiàn)中可以把該請求視為原子動作，成員在請求前后均為 Grant狀態(tài)。但是在實現(xiàn) RTI時需要注意的是，F(xiàn)QR請求可能導致其他成員的GALT增加，從而引起其他成員從掛起狀態(tài)進入Grant狀態(tài)。

身高測量法：對于任意成員i，其GALT取決于其他成員的身高，公式為：

Frederick算法會導致GALT計算的死鎖，其根本原因是在計算輸出時間時增加了對 GALT的比較。身高測量法本質上是對 Frederick算法的改進，最重要的改進之處在于用身高代替了輸出時間，在身高中不再增加對 GALT的比較。在圖 1的 w3時刻，H(A)= (t+1)+0.5=t+1.5=GALT(B)，H(B)=(t+2)+0.5=t+2.5= GALT(A)，這樣，A的GALT大于A的請求時間，所以，A的推進請求得到滿足，死鎖被解開。身高測量法的特點可通過如下定理來體現(xiàn)：

定理 1 如果一個成員請求時間推進時的身高最矮，則該成員的請求總能夠得到滿足。

證明：設成員 A的身高最矮，即H(A)最小。由身高測量法可知：

GALT(A)=min{H(i)}≥H(A), i≥A

(1)如成員的請求為 TAR/TARA，則 GALT(A)≥T(A)+L(A)>T(A)，請求能夠滿足。

(2)如果請求為 NMR/NMRA，則 GALT(A)≥min{T(A)+L(A), LETS(A)}。若 LETS(A)>T(A)，則GALT(A)>T(A)，請求能滿足。下面討論LETS(A)≤T(A)的情形，此時H(A)=LETS(A)。又因對任意成員i(i≠A)而言，RTI同意其推進的時間一定≥H(A)，因此可知：成員 i能夠發(fā)送的消息的時標≥H(A)+L(i)>H(A)=LETS(A)，因此，成員A再也不會收到LETS(A)的消息，RTI同意成員A推進到LETS(A)。

(3)如果成員的請求為FQR，則請求總能夠滿足。

在一個聯(lián)盟中，可能有多個身高最矮的成員，但是只要它們處于時間推進狀態(tài)，則RTI總能夠滿足其時間推進請求。

定理2 身高測量法不會導致死鎖。

證明：用反證法證明。假設系統(tǒng)存在死鎖，則n個成員的身高構成一個集合Y={h(1),h(2),…,h(n)}。在有窮集Y中，一定存在最小值，即系統(tǒng)中一定存在身高最矮的成員A，由定理1可知，成員A的請求總能夠滿足，與死鎖矛盾。

5 結束語

時間管理是分布式仿真技術的核心，一個好的時間管理算法可以有效提高系統(tǒng)運行效率，避免系統(tǒng)出現(xiàn)死鎖。本文探討 HLA中幾種時間推進機制，解釋了時間管理推進過程出現(xiàn)死鎖的原因。針對著名的Frederick算法，分析了其在某種特殊情況下出現(xiàn)死鎖的條件。為解決死鎖問題，提出一種改進的Frederick算法——身高測量法。該算法能夠運用在C4ISR系統(tǒng)仿真推進中，有效避免死鎖，提高仿真效率，使仿真運行更完善。下階段將針對大規(guī)模仿真中的時間管理相關問題，對身高測量法做進一步改進，以適應大規(guī)模層次式仿真。

[1]IEEE Org..1516-2000 IEEE Standard for Modeling and Simulation(M&S) High Level Architecture(HLA)[S].2000.

[2]張亞崇, 孫國基, 嚴海蓉, 等.RTI中時間推進機制的研究[J].計算機應用研究, 2005, 28(1): 104-110.

[3]歐陽伶俐, 宋 星, 卿杜政, 等.HLA 時間管理與PDES仿真算法研究[J].系統(tǒng)仿真學報, 2000, 12(3):237-240.

[4]Fujimoto R M.Time Management in the High Level Architecture[J].Simulation, 1999, 71(6): 388-400.

[5]王召福, 金士堯.HLA仿真系統(tǒng)中Lookahead的分析與動態(tài)調整策略[J].計算機仿真, 2003, 20(4): 78-81.

[6]張亞崇, 孫國基, 嚴海蓉, 等.HLA/RTI中的時間管理算法[J].吉林大學學報: 工學版, 2004, 34(7): 306-309.

[7]Fujimoto R M.Zero Lookahead and Repeatability in the High Level Architecture[EB/OL].(2005-08-08).http://www.cc.gatech.edu/computing/pds/papers.html.

[8]華偉亮, 孫少斌.HLA/RTI中時間管理機制及實現(xiàn)[J].系統(tǒng)仿真技術, 2009, 5(3): 208-213.

[9]徐大勇, 蔣曉原, 張義宏.HLA 的實時性擴展[J].計算機仿真, 2006, 23(9): 124-128.

[10]Kuhl F, Weatherly R, Dahmann J.Creating Computer Simulation Systems: An Introduction to the High Level Architecture[EB/OL].(1997-10-25).http://www.phptr.com.

[11]劉步權, 王懷民, 姚益平.一種無死鎖的時間管理算法[J].軟件學報, 2003, 14(9): 1515-1522.