摘要：基于新一代仿真体系结构HLA的IEEE1516新标准中的最大有效逻辑时间关键值，讨论最大有效逻辑时间在HLA时间管理中的重要意义，分析其在常规时间推进算法中的实现及死锁的产生，研究并证明HLA时间推进中的4个产生死锁的充分条件，即互斥条件、请求保持条件、不剥夺条件和环路等待条件，提出动态滑模的概念，设计了基于动态滑模的无死锁时间管理算法，对Lookahead的合理设置进行了分析。
关键词：时间管理；死锁；动态滑模；最大有效逻辑时间
1概述
基于仿真部件互操作和重用思想，1995年10月美国国防部提出了新一代仿真体系结构HLA(High Level Archi-tecture)，其内容由规则(Rules)、对象模型模板(Object ModelTemplate,OMT)和接口规范说明(interface specification)3部分组成[1-3]。其中时间管(TimeManagement,TM)是接口规范中6种服务之一，它描述的是联邦运行过程中联邦成员仿真时间的推进机制，且该时间推进机制必须与其他联邦成员的数据交换相协调，以确保联邦成员发送与接收消息在时间上的一致性及逻辑上的正确性。
HLA中一个联邦成员通过调用以下标准服务来推进他的逻辑时间：时间推进请求(Time Advance Request,TAR)，时间推进请求有效(Time Advance Request Available,TARA)，下一消息请求(Next Message Request,NMR)，下一消息请求有效(Next Message Request vailable,NMRA)和直接队列请求(Flush Queue Request,FQR)。其中前4种为保守联邦成员的时间推进机制，而FQR为乐观联邦成员的时间推进机制。RTI(Runtime Infrastructure)时间管理作为HLA标准的难点和重点，其最大有效逻辑时间(Greatest Available Logical Time,GALT)、时间预测量Lookahead的计算与设置以及最终如何预防或者缓解死锁都是技术的关键。
本文基于IEEE1516技术标准，假设源点与终点之间的消息传递具有队列特性，遵循先入先出(FIFO)原则，具体设置可参看文献[4,7-8]。在假设基础上，从常用的GALT算法引出死锁产生的原因，并重点分析了死锁产生的充分条件，提出动态滑模法以预防或缓解计算GALT的死锁问题，最后讨论了时间预测量Lookahead的有效设置方法。
2基本术语及算法
2.1基本术语
IEEE1516标准对HLA的以前各版本有些概念进行了修正与补充[1]，下面简述将用到的概念。
定义1逻辑时间(logical time)指联邦成员在HLA仿真中被指定的基于HLA仿真时间轴的时间，是一个当前时间点。
定义2 GALT指联邦成员能够推进的最大有效逻辑时间。每个联邦成员均有GALT值，使得RTI保证在没有其他联邦成员在等待时间推进的情况下授予权利予以时间推进。在TAR或NMR条件下，联邦成员在其逻辑时间小于GALT值时被授权予以时间推进，而在TARA,NMRA或FQR情况下，仅仅是联邦成员逻辑时间小于或等于GALT值时才可以进行时间推进。
定义3 LITS(Least Incoming Time Stamp)指联邦成员可能接收到TSO(Time Stamp Order)消息时的最小时间戳。联邦成员的LITS可以通过GALT,RTI和被其他联邦成员接受的队列顺序所共同决定。如果一个联邦成员的GALT值不定且无队列TSO消息，则LITS值不能确定。
定义4死锁Deadlock指联邦成员间的时间推进序列由于竞争消息通道而造成的僵局(Dead-Embrace)，若无外界调节机制，这些联邦成员都将无法向前推进时间序列，从而使得仿真停滞。
定义5有效逻辑时间ELT(Effect Logical Time)表示联邦成员可以发送消息时间戳的最大下界。
2.2 GALT常规算法及不足
RTI确保TSO消息以时间戳顺序传输给联邦成员，并保证其时间戳小于当前逻辑时间[8-9]。
2.3算法中死锁的产生
假设在一次仿真中只有2个联邦成员A和B参加，它们的Lookahead均为相同的定值0.5。由于只有2个联邦成员，因此由上述算法可知一个联邦成员的输出时间就是另外一个联邦成员的GALT值。
3死锁规律性研究
由于GALT算法可虑因素众多，且各时间推进服务的不同及物理时间与仿真时间的差异，很容易产生死锁[8]，因此必须研究在GALT算法中的死锁规律以解除之。引理1如果所有联邦成员均由请求的时间推进而处于死锁状态，那么所有联邦成员的GALT相等。引理2如果所有联邦成员均由请求的时间推进而处于死锁状态，那么所有联邦成员能够发送消息时戳的最大下界相等。
引理3如果系统中至少有一个联邦成员因TAR/TARA请求而处于挂起状态，那么系统中至少存在一个处于Grant状态的联邦成员。
定理3如果所有联邦成员均因为请求时间推进而处于死锁状态，则所有联邦成员的请求为不可剥夺条件。证明从定理1和定理2及引理可知，在请求结束之前的有限时段内，各联邦成员的请求条件必须保持才可以进行有序可靠的信息传输，但互斥条件使得自身只有在自己满足条件时才能解除死锁，所有联邦成员的以上2点共性造成每个成员的要求不可剥夺，造成死锁。定理4如果所有联邦成员均因为请求时间推进而处于死锁状态，那么所有成员的请求必出现环路等待。
4动态滑模法
下面对动态滑模法产生死锁的4个充分条件进行讨论：
(1)互斥条件：由于滑模窗口的范围限制，在时间推进过程中模态限制时间链路的时间段，使用大于或等于它的不予满足，因此在请求中以窗口由小到大渐增消除了条件的互斥。
(2)请求保持：由于在死锁中死锁的产生，各请求处于保持状态，而滑模窗口总能找到一个值最小的满足时间推进的请求，因此死锁迎刃而解。
(3)不剥夺条件：由于滑模总能找到一个适合窗口大小的满足授予时间推进权利，从而阻止其他成员提出新的要求并不给予满足。此时，便认为是摒弃了不剥夺条件。
(4)环路等待：方法是在假设先进先出的队列消息传递情况下进行。滑模在时间轴上的瞬时推动，最低时序被滑模窗口占据，这样保证在某一时刻固定的滑窗下避免环路等待。
5 Lookahead设置方法
从前面的分析可以看出，Lookahead值设置非常关键，在IEEE1516中，Lookahead的定义是[1]“Lookahead is anonnegative value that establishes a lower value on the timestamps that can be sent in TSO messages by time-regulatingjoined federates”。且联邦一旦建立，各联邦成员的Lookahead值仅能通过Modify Lookahead Service来进行更新[1,10-11]。
一个时间控制(time regulating)的联邦成员的Lookahead=0必须考虑其他约束条件。如果这样的联邦成员通过TAR/NMR来推进其逻辑时间，将不会发送那些时戳小于或等于其逻辑时间的TSO消息。另外GALT等时间推进的关键值计算都需要正确合理地设置Lookahead值。Modify Lookahead Service在Time Advancing状态中不能改变Lookahead值。如果要求的值大于或等于联邦成员的实际Lookahead值，请求立刻被接受并且实施；否则需逐步改变其逻辑时间而更新。
6结束语
HLA中时间管理为其接口规范说明的6大管理中的重点和难点。由于时间的推进不当造成了死锁以致仿真无法进行。文章从IEEE1516新标准提出的GALT出发研究了导致死锁6结束语的充分条件，指出了死锁的出现是由于在仿真时间推进中出现了互斥条件，请求保持条件不可剥夺以及环路等待。本文提出一个动态滑模法以较好地消除死锁，最后对GALT算法中Lookahead值的设定加以讨论。
|
