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

不恰当的最大安全推进时间(GALT)计算方法会影响系统整体运行,严重情况下可能导致系统死锁,使整个系统仿真无法向前推进。为此,分析经典时间推进Frederick算法中可能出现死锁的情况,给出死锁出现的原因,并对死锁产生的原因进行论证,在此基础上,设计一种基于该算法的改进无死锁时间管理GALT计算算法。分析结果表明,改进算法可以有效解决GALT计算产生的死锁问题。     

HLA中时间管理算法死锁问题的分析

RTI是HLA的核心,时间管理服务是RTI提供的六大类服务之一.GALT算法是时间管理服务能否实现的关键技术.不合理的GALT算法会导致死锁或破坏HLA时间管理的原则,从而导致整个仿真无法向前推进,或产生过去时刻的消息.分析了文献[7]中对死锁规律的描述,指出了其中存在的问题及身高测量法可能带来的问题.对原有的GALT算法做了改进,在保证不破坏HLA时间管理原则的前提下,解决了GALT算法的死锁问题,从而确保了时间管理服务的可靠实现.     

一种无死锁的时间管理算法

高层体系结构HLA(high level architecture)是美国国防部提出的建模和仿真的标准,时间管理服务是其重要的组成部分,而GALT(greatest available logical time)的计算是RTI(runtime infrastructure)时间管理服务实现的核心技术.GALT算法容易导致死锁,继而导致整个仿真无法推进.在Frederick Kuhl算法的基础上探讨了死锁产生时系统所特有的一些规律,得出了一些重要结论:如果系统处于死锁状态,则所有盟员的GALT和输出时间一定分别相等,并且GALT一定等于输出时间;所有Lookahead大于0的盟员一定处于NMR/NMRA推进状态而不会处于其他推进状态(TAR/TARA/FQR).最后提出了基于"身高测量法"的无死锁的GALT算法,"身高测量法"为RTI中时间管理模块的实现提供了可靠保证.     

Lookahead为零时的仿真

lookahead是HLA时间管理服务中的重要概念.lookahead值是在仿真执行过程中由用户自己设置的.Lookahead的值为零是一种特殊情况,它在实际仿真系统中会经常出现,IEEE标准专门为此做了规定.如果多个联邦成员都有lookahead为零,可能会造成逻辑时间推进的死锁状态.讨论了引入lookahcad的意义,并分析了lookahead为零时死锁的规律性,了解了这些规律后,就能有效地避免死锁,从而使仿真过程更加顺利地进行.     

Lookahead为零时的仿真

lookahead是HLA时间管理服务中的重要概念。looka-head值是在仿真执行过程中由用户自己设置的。Lookahead的值为零是一种特殊情况,它在实际仿真系统中会经常出现,IEEE标准专门为此做了规定。如果多个联邦成员都有lookahead为零,可能会造成逻辑时间推进的死锁状态。讨论了引入lookahead的意义,并分析了lookahead为零时死锁的规律性,了解了这些规律后,就能有效地避免死锁,从而使仿真过程更加顺利地进行。     

HLA中时间管理算法死锁的规律性

Frederick算法在通常情况下能够比较好地工作,并且完全符合HLA时间管理的原则。但在特殊情况下,该算法会造成死锁。研究表明,死锁是有规律的。文章分析了文献[5]中对Frederick算法死锁规律的描述,指出了其中存在的问题,并一一加以修正。最后给出了新的死锁规律。     

RTI时间管理的一种新型动态尺度标注算法

时间管理算法是决定RTI时间管理服务性能的关键。为解决时间管理中常用的Frederick算法计算GALT(greatest available logical time)时可能出现死锁以及仿真系统消息延迟等问题,定义了联邦成员尺度的概念,并结合时间前瞻量的动态调整思想,提出了动态尺度标注算法,并对其进行了分析。分析表明该算法不但减少了消息的延迟时间,还解决了时间管理中的死锁问题。通过在制导弹药飞行视景仿真系统上测试,表明算法改善了仿真效果,提高了仿真系统性能。     

协同作战仿真系统的时间同步机制研究

通过介绍基于HLA的协同作战仿真开发过程和HLA时间管理服务的相关概念,针对仿真系统的时间管理机制进行分析,提出了同步机制条件下的基于事件驱动的算法和基于步长的算法,用以解决协同作战过程中的联邦同步问题。     

RTI中时间推进机制的研究

作为高层体系结构HLA 的软件实现, RTI 按照HLA 接口规范的定义, 提供了支持分布式交互仿真实现的服务。其中时间管理是一类很重要的服务, 是为了保证正确地实现成员间仿真时间的协调推进和数据交换。通过一个具体的例子, 对RTI 中的保守时间推进机制进行了深入分析, 并研究了时间管理中的LBTS 的计算、避免死锁的策略等问题。     

基于HLA的潜艇作战仿真系统时间管理研究

时间管理服务是运行支撑系统(run-time infrastructure,RTI)提供的6类服务之一,它按照高层体系结构接口规范来管理各类消息的发送和接收,并协调不同的时间推进机制,以保证分布式仿真的逻辑正确性.针对仿真驱动的潜艇实装作战仿真训练系统,结合HLA时间管理常见问题,从开发基于HLA仿真应用的角度分析了时间管理机制,重点研究了潜艇作战仿真训练系统中的推演时间管理方法.     

一种改进的多重密钥共享的门限方案

给出一种改进的多重秘密共享的门限方案,在该方案中管理者可以安全有效地共享多个密钥,成员可以根据不同的共享密钥计算不同的子密钥。该方案采用知识签名的方法能够有效地抵御管理者欺骗和成员欺骗,具有良好的可扩展性,是安全且高效的。     

层次式多联盟结构框架及其时间管理服务的研究

随着仿真技术的发展，人们对大规模分布式仿真的应用需求越来越迫切。为了解决单联盟集中式RTI仿真规模受限的问题，AnthonyCramp等人提出了层次式多联盟的联盟集合的思想，并对分布式盟员代理(Distributed Federate Proxy DFP)结构的时间管理进行了简要描述，其描述是基于美国国防部HLA 1．3版本的；该文主要介绍了层次式多联盟的基本结构及主要数据流程，并重点给出了符合IEEE1516标准的层次式多联盟的时间管理算法，对分布式盟员代理部件(Distributed Federate Proxy Components DFPC)和仿真节点SN的最大可用逻辑时间(Greatest Available Logical Time GALT)的计算及其逻辑时间的推进过程进行了较为详尽的分析。     

A Two-Level Distributed Detection Algorithm of AND/OR Deadlocks

Numerous algorithms on distributed deadlock detection in distributed systems have been proposed for various deadlock models such as the AND model, OR model, and AND/OR model. This paper describes a new distributed algorithm for the AND/OR model by two levels of deadlock detection procedures. In every deadlock model, the existence of a cycle in a wait-for graph is a necessary condition. At the first level of our algorithm, a wait-for cycle is detected with a very simple operation. If no cycle is found, a deadlock does not exist. In this level, deadlocks consisting of AND-requested nodes are detected, and for the cycle of AND- and OR-requested nodes, an initiator is elected and the second-level algorithm is initiated by the initiator. The second-level algorithm uses the deadlock detection method of Herman and Chandy, but the communication cost is reduced even in the worst case because the second-level operation can be initiated by only qualified initiators.     

基于HLA/RTI的分布式交互仿真系统中的信息交换机制

基于HLA/RTI设计了一个顾客/服务员仿真系统，结合RTI 1.3提供的声明管理，对象管理和时间管理等服务，就对象类和交互类及其属性和参数等信息交换机制进行了分析，并讨论了基于HLA/RTI的分布式交互仿真系统中可能存在的一种死锁问题。     

Fast, centralized detection and resolution of distributed deadlocks in the generalized model

In the literature, only a few studies have been performed on the distributed deadlock detection and resolution problem in the generalized request model. Most of the studies are based on the diffusing computation technique where propagation of probes and backward propagation of replies are required to detect deadlock. The replies carry the dependency information between processes for the initiator of the algorithm to determine deadlock. Since fast detection of deadlock is critical, we take a centralized approach that removes the need of backward propagation of replies, but sends the dependency information directly to the initiator of the algorithm. This enables reduction of time cost for deadlock detection to half of that of the existing distributed algorithms. The algorithm is extended to handle concurrent executions in order to further improve deadlock detection time, whereas the current algorithms focus only on a single execution. Simulation experiments are performed to see the effectiveness of this centralized approach as compared to previous distributed algorithms. It is found that our algorithm shows better results in several performance metrics especially in deadlock latency and algorithm execution time.     

Deadlock detection in distributed database systems: a new algorithm and a comparative performance analysis

This paper attempts a comprehensive study of deadlock detection in distributed database systems. First, the two predominant deadlock models in these systems and the four different distributed deadlock detection approaches are discussed. Afterwards, a new deadlock detection algorithm is presented. The algorithm is based on dynamically creating deadlock detection agents (DDAs), each being responsible for detecting deadlocks in one connected component of the global wait-for-graph (WFG). The DDA scheme is a “self-tuning” system: after an initial warm-up phase, dedicated DDAs will be formed for “centers of locality”, i.e., parts of the system where many conflicts occur. A dynamic shift in locality of the distributed system will be responded to by automatically creating new DDAs while the obsolete ones terminate. In this paper, we also compare the most competitive representative of each class of algorithms suitable for distributed database systems based on a simulation model, and point out their relative strengths and weaknesses. The extensive experiments we carried out indicate that our newly proposed deadlock detection algorithm outperforms the other algorithms in the vast majority of configurations and workloads and, in contrast to all other algorithms, is very robust with respect to differing load and access profiles. Received December 4, 1997 / Accepted February 2, 1999     

符合IEEE1516规范的HLA/RTI时间管理

时间管理是HLA的一项关键服务。本文综合介绍了IEEE15 16规范中时间管理的主要内容 ,包括消息的排序传递以及仿真中逻辑时间的推进机制 ,然后结合RTI开发的工程实践 ,阐述了在设计和实现符合规范的时间管理服务时的具体做法 ,给出了基于CORBA的RTI时间管理服务的实现模型。