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中时间管理模块的实现提供了可靠保证.     

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

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

基于动态滑模的无死锁时间管理算法

基于新一代仿真体系结构HLA的IEEE1516新标准中的最大有效逻辑时间关键值,讨论最大有效逻辑时间在HLA时间管理中的重要意义,分析其在常规时间推进算法中的实现及死锁的产生,研究并证明HLA时间推进中的4个产生死锁的充分条件,即互斥条件、请求保持条件、不剥夺条件和环路等待条件,提出动态滑模的概念,设计了基于动态滑模的无死锁时间管理算法,对Lookahead的合理设置进行了分析。     

容错的分布式系统通用死锁模型检测解除算法

分布式系统技术为采用低成本购建高性能系统提供了有效的途径,但是由于资源的分配与需求可能产生冲突,造成系统中发生死锁,导致系统运行陷入停滞.在不可靠的分布式系统中,故障会干扰正常的死锁检测,但现有的死锁检测算法不具有容错功能.对失效形式进行了归类,提出一个容错的死锁检测解除算法.算法建立在通用的AND-OR模型基础上,采用扩散计算和集中规约方式,不仅能够检测到死锁,而且能给出死锁环的全部成员.若死锁拓扑处于静态且为环状,算法的消息复杂度的上限为e n-1,时间复杂度为d,其中e为死锁等待图中边的个数,n和d为构成死锁环的节点的个数,分析表明算法性能等于或优于同类算法.     

一种基于优先级扩展的时间自动机模型中DBM减法算法的改进

本文介绍一种具有优先级扩展的时间自动机模型,并对一种计算DBM减法算法进行改进。这种减法是DBM上操作中的一种,它会产生需要用DBM集来表示的非凸集合。DBM的数量影响符号模型检测的性能,我们的减法算法是有效的,因为它产生的DBM的数量相对于最初算法具有较大程度的约减。DBM减法操作扩展了具有优先级的时间自动机理论,它对对于具有紧急行为的变换描述、死锁检测、时间博弈等问题具有非常重要的作用。     

一种基于预测的大学课表调度算法

本文通过对大学课程调度中出现死锁原因的分析,将死锁分为不可避免死锁和可避免死锁。同时提出一种算法,根据对时间和场地死锁的静态和动态的预测与调整,实现了计算机对大学课程的辅助调度。     

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

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

基于任务-资源图的AGVS循环死锁搜索算法的改进研究

针对AGVS中循环死锁搜索算法研究中存在的不能搜索全部的循环死锁的问题,利用任务-资源图提出一个改进算法.改进算法如下:首先,根据AGV的相对位置关系和执行任务的情况,利用任务-资源图(Task-Resource graph,T-R图)对AGVS进行建模,然后根据循环死锁的T-R图特征,在每一个状态时刻下的T-R图使用图的强连通分支理论搜索循环死锁.当访问完所有状态时刻下的T-R图,也就找到了AGVS中的所有循环死锁.算例验证与理论分析均说明改进算法可以搜索到全部类型的循环死锁,解决了原算法存在的不足.根据改进算法开发的控制规则,可以有效避免新循环死锁的产生.同时指出,对改进算法稍加修改,可以找到AGVS中所有的循环死锁和非循环死锁.     

基于集束搜索和银行家算法的柔性制造系统无死锁调度

本文提出了一种基于启发式规则的无死锁调度算法,该算法基于集束搜索方法,局部评价函数和全局评价函数,在无缓冲区的情况下,采用单步前瞻的银行家算法来避免死锁。该算法可以迅速解决复杂制造系统的死锁和调度问题,折衷了计算时间的消耗和调度结果的质量。     

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

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

A deadlock recovery strategy for unified automated material handling systems in 300 mm wafer fabrications

A key issue emerging from the unified automated material handling systems (UAMHSs) in 300 mm wafer fabrications is the system deadlock. This paper addresses the deadlock recovery strategy of unified automated material handling systems (UAMHSs) with limited buffers. A formal model for UAMHSs deadlock detection is proposed. Sufficient conditions for system deadlocks based on actual UAMHS characteristics are defined along with a novel deadlock recovery strategy. Moreover, an effective heuristic algorithm is proposed for parallel resolving UAMHS deadlocks. The performances are evaluated in simulation by monitoring indexes reflecting efficiency of the material handling system. Results of the simulation experiments show that the novel deadlock recovery strategy is superior to the benchmark strategy in reducing deadlock time and improving tools’ utilization. Furthermore, the proposed algorithm features real-time operation and large scale cases, and is suitable for practical applications.     

基于Petri网并行程序通信死锁的检测和预防

无死锁是并行程序正确性的主要条件之一,已有研究成果关注于死锁检测,但对死锁预防研究较少。该文在对消息传递模式并行程序各种通信过程进行分类介绍的基础上,借助Petri网进行建模,提出程序死锁与Petri网死标识的对应关系,给出通信死锁检测算法,进而针对2种引起通信死锁的原因提出了3种预防方法,通过比较提出最佳方案。该方法既有较好的通用性,又可用于并行算法设计阶段的死锁预防以提高并行编程效率。     

Robust Deadlock Avoidance Policy for Automated Manufacturing System With Multiple Unreliable Resources

This work studies the robust deadlock control of automated manufacturing systems with multiple unreliable resources. Our goal is to ensure the continuous production of the jobs that only require reliable resources. To reach this goal, we propose a new modified Banker's algorithm(MBA) to ensure that all resources required by these jobs can be freed. Moreover,a Petri net based deadlock avoidance policy(DAP) is introduced to ensure that all jobs remaining in the system after executing the new MBA can complete their processing smoothly when their required unreliable resources are operational. The new MBA together with the DAP forms a new DAP that is robust to the failures of unreliable resources. Owing to the high permissiveness of the new MBA and the optimality of the DAP, it is tested to be more permissive than state-of-the-art control policies.     

广义预测控制和PID控制在混凝投药中的应用

针对水处理过程中混凝投药的非线性和时滞特点,分析了其混凝投药的工作原理,采用传统的控制方法难以实现很好的控制效果.提出了一个混凝投药的方案,把广义预测控制算法和PID (proportion-integralderivative)控制算法结合起来,通过预测被控系统的若干个时刻的未来输出值,得到一个新的性能优化函数,通过实时优化被控对象的控制参数,计算出一个合理的混凝投药量.最后,采用Visual Basic软件编程完成该控制方案,并通过对混凝投药自动化控制的现场实验,得到较好的输出控制结果,从而验证了该控制方案的可行性.     

面向多机器人动态任务分配的事件驱动免疫网络算法

为实现多机器人系统的动态任务分配与协作,提出了一种面向多机器人动态任务分配的事件驱动免疫网络算法。将生物免疫网络的工作机理应用到多机器人动态任务分配算法中,借鉴Jerne的独特型免疫网络假说和Farmer提出的抗体激励动态方程,设计了多机器人任务分配与自主协作模型;基于事件驱动机制,设计了多机器人动态任务分配算法,并引入焦躁模型来解决任务死锁问题。仿真和实际多机器人系统实验结果表明,基于本文算法的多机器人系统在动态任务场景中具有较强的适应性和自主规划协调能力。     

基于Petri网的指挥信息系统死锁防治算法

多兵种联合作战指挥信息系统死锁防治是保障系统安全可靠的根本问题,也是有待解决的难点之一。该文提出一种描述指挥信息系统的形式化方法——Petri网模型,以抽取某级通信指挥系统与筹划作战方案的智能运作模型为实例,系统归纳了模型抽取方法,进而提出其死锁防治算法DLPCA,它能够防止系统出现的死锁等弊端,为组建一体化信息系统提供可靠的理论基础。经彷真试验,算法是有效可行的,在系统较长时间的工作中,可将死锁的次数减少50％左右。