高层体系结构中时间管理算法研究及改进

王 月，李宏伟，孙黎阳

(1.中国人民解放军65635部队，辽宁 锦州 121017；2.解放军理工大学工程兵工程学院，南京 210094；3.中国电子科技集团公司第二十八研究所，南京 210007)

1 概述

高层体系结构(High Level Architecture, HLA)[1]是美国国防部提出的关于分布式仿真的一个标准，其主要目的是实现各类仿真的互操作和重用。在典型的分布式仿真应用中，由于成员(Federate)方的计算量、处理器的计算速度及网络延迟等因素的影响，因此成员之间的消息传递存在不确定性，而消息的先后次序对整个仿真是非常重要的。

时间管理服务是 HLA的重要组成部分，其主要目的是保证成员能够按照正确的顺序接收消息，从而保证仿真的正确执行。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标准实现 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中时间管理模块实现的关键。GALT是IEEE 1516标准提出的新概念，在此之前，GALT被称为LBTS。

本文遵循 IEEE1516标准，统一采用 GALT名称。GALT计算应该综合考虑各种时间推进方式，许多学者对此进行了卓有成效的研究，但考虑得不够全面。文献[2]对RTI中保守时间推进机制进行了分析，讨论了如何避免死锁，但主要针对死锁检测机制进行研究。文献[3]对HLA中保守和乐观时间推进机制进行了比较和分析，但未涉及死锁问题。文献[4-5]都对HLA中的时间管理进行研究，特别 是文献[5]对Lookahead为0时的情况进行了详细研究。文献[6]和文献[7]对 HLA时间管理进行了优化，目的在于提高 HLA运行性能，但并未对死锁进行更深入研究。文献[8]对HLA时间管理算法中时间推进策略进行了研究与实现，文献[9]则对HLA的实时性进行了研究。纵观上述研究，虽然都对HLA时间管理进行了研究，但是并未均涉及死锁问题，而就算讨论了时间管理中的死锁问题，也并未从根本上找出死锁产生的原因并解决之。

目前笔者暂未发现任何 RTI开发商公布其软件中的GALT算法，但是，文献[10]却描述了一个简单、实用的 GALT算法(当时使用的名称是 LBTS)。作为HLA的参与者和制订者，他们的算法应当具有可信性和权威性。该算法在通常情况下能够较好地工作，但在特殊情况下会造成死锁。

本文探讨了HLA中TAR、TARA、NMR、NMRA 4种推进机制，解释了死锁出现的原因，分析Frederick算法在某种特殊情况下会出现死锁的条件，提出了一种改进的时间管理算法，并验证该改进算法可以避免死锁。

2 时间推进机制及算法

2.1 基本术语

定义 1 GALT是指成员能够推进的最大逻辑时间。

在保守时间推进机制下，HLA规范要求一个成员在仿真的任何时刻都不能接收到一个过时(即比成员的当前逻辑时间小)的消息。因此，在成员推进时，RTI必须确保成员的时间推进不能超过GALT这个时间上界，否则，在未来的逻辑时间里有可能接收到过时的消息。

定义2 LETS(Least Existent Time Stamp)是指成员消息队列中已有消息的最小时标。

LETS不是IEEE 1516规范中的定义，而是为了叙述方便在本文中引进的。

定义3 LITS是指成员有可能接收到的最小消息的时标。

通过计算GALT和LETS，RTI能够确定成员的LITS。LITS可取GALT和LETS的最小值。LITS和LETS的区别在于，LETS是那些已经接收到的放在成员TSO队列中的所有消息的最小时标；而LITS还可能包括那些仍在网络中传输甚至还没有发出的小时标的消息。

定义4 输出时间(Output Time)是指 RTI计算出的成员能够发送的消息时标的最大下界。

成员只能发送不小于输出时间的消息，否则，其他成员有可能接收到一个过时的消息。据此，RTI在计算成员的 GALT时可由其他成员的输出时间来得到。

定义5 挂起(Pending)是指成员在请求时间推进时因为没有得到RTI的允许而处于暂停状态。

定义6 死锁(Deadlock)是指系统中有相互约束关系的成员均处于挂起状态。

不同系统对死锁的定义会有所不同，本文的死锁是由计算GALT引起的。一个成员的时间推进状态将直接影响其他成员的GALT计算，一个处于挂起状态的成员需要其他成员 GALT的增加才有可能被解除挂起状态而进入Grant状态。如果有相互约束关系的成员都因为期望其他成员能够增加 GALT而解除挂起状态，那么这些成员就会处于互相等待状态而形成死锁。

本文所有定理和算法都以参加仿真的所有成员间既相互控制又相互受限为前提条件，且只针对保守情况下的时间推进方法，乐观推进机制在此不做研究。

2.2 时间推进方式

HLA中时间推进方式分为独立的时间推进方式和协商的时间推进方式两大类。在独立的时间推进方式下，RTI不参与成员时间推进的管理，各成员根据自己的仿真需要独立、尽快地推进自己的逻辑时间，各成员的时间是相对独立的。在协商时间推进方式下，RTI协调成员的时间推进，以确保联邦执行能保持系统中事件先后顺序，保守协商推进机制包括TAR、TARA、NMR、NMRA 4种。

步进的时间推进(TAR、TARA)、基于事件的时间推进(NMR、NMRA)都是在RTI协调下进行的。在RTI头文件中分别为不同推进类型定义了其函数原型：timeAdvanceRequest()，nextEventRequest()。联邦成员调用相应的函数请求推进到希望的逻辑时间theTime，RTI根据联邦成员的请求完成消息的 传递和处理后，采用回调函数 timeAdvanceGrant()通知联邦成员时间推进完成，成员在收到 timeAdvance-Grant()回调函数后就可以进入下一个时间推进过程。若请求推进的时间是不安全的，该联邦成员将被挂起，被挂起的成员处于暂停状态。当所有成员均被挂起后，系统出现死锁。

3 Frederick算法及其死锁问题

3.1 Frederick算法

对于任意成员i，其GALT计算公式为：

Frederick算法将成员的 GALT取值为其他成员输出时间的最小值。算法的关键在于计算成员的输出时间，输出时间取决于成员的当前状态、逻辑时间、Lookahead和LETS多个因素。

成员的输出时间可按照下式计算：

其中，T(i)为成员i请求推进的时间；L(i)为成员i当前的Lookahead值；LETS(i)为成员i的消息队列中最小消息的时标；GALT(i)为成员i的GALT值。

3.2 Frederick算法的死锁问题

在讨论 GALT计算的诸多文献中，都着重于Grant、TAR、TARA状态，而 Frederick算法较好地解决了成员使用 NMR、NMRA请求时间推进时的GALT计算问题，并且在绝大多数情况下非常实用和有效，但是该算法却不能避免死锁。

假设在一次仿真中只有A和B 2个成员参加，它们的Lookahead均为0.5。由于只有2个成员，因此一个成员的输出时间就是另外一个成员的GALT。

Frederick算法中的死锁情况如图1所示。在墙上时间w1时刻，A和B均处于Grant状态，它们的输出时间均为t+0.5，GALT也同样为t+0.5；在w2时刻处，成员A使用NMR请求推进到t+1，但因为此时它的GALT仍为t+0.5，所以成员A的请求被挂起；在w3时刻处，成员B使用NMR请求推进到t+2，这时在计算B的GALT时就会出现2种情况：

(1)由于B的GALT等于A的输出时间，因此可取w3时刻之前的A的输出时间t+0.5作为B的GALT，由于t+0.5小于B的请求时间t+2，因此B也被挂起，出现了死锁。

(2)在 w3处，重新计算 A的输出时间，但根据Frederick算法，A的输出时间依赖于B的GALT，而B的GALT正是要求的结果，这样在计算GALT或输出时间时算法本身也会出现死锁，即无法计算GALT或输出时间。

图1 Frederick算法中的死锁

4 Frederick算法的改进

前面讨论的死锁问题本质上是因 GALT的算法不完善造成的，一个好的算法是不会造成死锁的。下面介绍一种基于“身高测量法”的无死锁算法[11]。

身高(stature)可定义为：

其中，H(i)表示成员i的身高；T(i)表示成员i的逻辑时间或请求推进的逻辑时间；L(i)表示成员 i的Lookahead；LETS(i)表示成员 i消息队列中的最小消息的时标。

这里再次对FQR请求进行必要的说明，由于FQR请求总能够得到满足，因此在具体的RTI实现中可以把该请求视为原子动作，成员在请求前后均为 Grant状态。但是在实现 RTI时需要注意的是，FQR请求可能导致其他成员的GALT增加，从而引起其他成员从挂起状态进入Grant状态。

身高测量法：对于任意成员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的推进请求得到满足，死锁被解开。身高测量法的特点可通过如下定理来体现：

定理 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能够发送的消息的时标≥H(A)+L(i)>H(A)=LETS(A)，因此，成员A再也不会收到LETS(A)的消息，RTI同意成员A推进到LETS(A)。

(3)如果成员的请求为FQR，则请求总能够满足。

在一个联盟中，可能有多个身高最矮的成员，但是只要它们处于时间推进状态，则RTI总能够满足其时间推进请求。

定理2 身高测量法不会导致死锁。

证明：用反证法证明。假设系统存在死锁，则n个成员的身高构成一个集合Y={h(1),h(2),…,h(n)}。在有穷集Y中，一定存在最小值，即系统中一定存在身高最矮的成员A，由定理1可知，成员A的请求总能够满足，与死锁矛盾。

5 结束语

时间管理是分布式仿真技术的核心，一个好的时间管理算法可以有效提高系统运行效率，避免系统出现死锁。本文探讨 HLA中几种时间推进机制，解释了时间管理推进过程出现死锁的原因。针对著名的Frederick算法，分析了其在某种特殊情况下出现死锁的条件。为解决死锁问题，提出一种改进的Frederick算法——身高测量法。该算法能够运用在C4ISR系统仿真推进中，有效避免死锁，提高仿真效率，使仿真运行更完善。下阶段将针对大规模仿真中的时间管理相关问题，对身高测量法做进一步改进，以适应大规模层次式仿真。

[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].系统仿真学报, 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仿真系统中Lookahead的分析与动态调整策略[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中时间管理机制及实现[J].系统仿真技术, 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.