Reverse reachability analysis: A new technique for deadlock detection on communicating finite state machines

The communicating finite state machines can exchange messages over bounded FIFO channels. In this paper, a new technique, called reverse reachability analysis, is proposed to detect deadlocks on the communication between the communicating finite state machines. The technique is based on finding reverse reachable paths starting from possible deadlock states. If a reverse reachable path can reach the initial global state, then deadlock occurs. Otherwise the communication is deadlock-free. The effectiveness of the technique has been verified by some real protocols such as a specification of X.25 call establishment/clear protocol and Bartlet's alternating bit protocol.     

Model checker aided design of a controller for a wafer scanner

For a case-study of a wafer scanner from the semiconductor industry it is shown how model checking techniques can be used to compute (1) a simple yet optimal deadlock avoidance policy, and (2) an infinite schedule that optimizes throughput. in the absence of errors. Deadlock avoidance is studied based on a simple finite state model using Smv, and for throughput analysis a more detailed timed automaton model has been constructed and analyzed using the Uppaal tool. The Smv and Uppaal models are formally related through the notion of a stuttering bisimulation. The results were obtained within 2 weeks, which confirms once more that model checking techniques may help to improve the design process of realistic, industrial systems. Methodologically, the case study is interesting since two models were used to obtain results that could not have been obtained using only a single model. Supported by the European Community Project IST-2001-35304 (Ametist), http://ametist.cs.utwente.nl/.     

HIS系统维护中“死锁”现象的分析与解决

在我院HIS系统的维护工作中,死锁现象时有发生。通过分析“死锁”产生的机制．合理使用科学的手段预防和解决“死锁”问题,将会大大提高工作效率。     

A Polynomial Algorithm for Computing Elementary Siphons in a Class of Petri Nets

A set of elementary siphons plays a key role in the development of deadlock prevention policies for automated manufacturing systems. This paper addresses the computation problem for elementary siphons in a subclass of Petri nets which are basic systems of simple sequential processes with resources (BS³PR) and can model many automated manufacturing systems. An algorithm for enumerating elementary siphons is established by the one‐to‐one relationship between maximal perfect resource‐transition circuits (MPCs) and strict minimal siphons. A set of MPCs is first computed, followed by a set of elementary siphons in a BS³PR. The presented algorithm is proved to have polynomial‐time complexity. An example is used to illustrate the algorithm.     

GPU-OSDDA: a bit-vector GPU-based deadlock detection algorithm for single-unit resource systems

This article presents a GPU-based single-unit deadlock detection methodology and its algorithm, GPU-OSDDA. Our GPU-based design utilizes parallel hardware of GPU to perform computations and thus is able to overcome the major limitation of prior hardware-based approaches by having the capability of handling thousands of processes and resources, whilst achieving real-world run-times. By utilizing a bit-vector technique for storing algorithm matrices and designing novel, efficient algorithmic methods, we not only reduce memory usage dramatically but also achieve two orders of magnitude speedup over CPU equivalents. Additionally, GPU-OSDDA acts as an interactive service to the CPU, because all of the aforementioned computations and matrix management techniques take place on the GPU, requiring minimal interaction with the CPU. GPU-OSDDA is implemented on three GPU cards: Tesla C2050, Tesla K20c, and Titan X. Our design shows overall speedups of 6-595X over CPU equivalents.     

浅议SQL Server中死锁的产生和解决对策

针对SQL Server事务处理中出现的死锁现象进行了分析,并用一个实例构造出了死锁的情形,观察了SQL Server对死锁现象的处理。文中还提出了若干避免出现死锁现象的对策。     

柔性制造系统非阻塞监督控制器优化设计

针对一类含有并发执行装配过程的柔性制造系统G-systems,提出一种新的死锁预防策略保证该系统的非阻塞性,即在控制下,受控系统从任意可达状态都可以到达理想状态.首先对Petri网模型中基本信标实施控制,保证了基本信标的最大可控,然后通过线性规划算法求取所有从属信标满足可控性的条件,即获得基本信标的控制深度变量.与现有方法相比,该策略优点在于只需加入少量的控制库所,就可避免不必要的迭代过程;其次是提出控制器输出弧位置优化策略,得到了结构更为简单、许可行为更多的非阻塞Petri网控制器.     

A deadlock-free routing algorithm for dynamically reconfigurable Networks-on-Chip

We address routing in Networks-On-Chip (NoC) architectures that use irregular mesh topologies with Long-Range Links (LRL). These topologies create difficult conditions for routing algorithms, as standard algorithms assume a static, regular link structure and exploit the uniformity of regular meshes to avoid deadlock and maintain routability. We present a novel routing algorithm that can cope with these irregular topologies and adapt to run-time LRL insertion and topology reconfiguration. Our approach to accommodate dynamic topology reconfiguration is to use a new technique that decomposes routing relations into two stages: the calculation of output ports on the current minimal path and the application of routing restrictions designed to prevent deadlock. In addition, we present a selection function that uses local topology data to adaptively select optimal paths.The routing algorithm is shown to be deadlock-free, after which an analysis of all possible routing decisions in the region of an LRL is carried out. We show that the routing algorithm minimises the cost of sub-optimally placed LRL and display the hop savings available. When applied to LRLs of less than seven hops, the overall traffic hop count and associated routing energy cost is reduced. In a simulated 8 × 8 network the total input buffer usage across the network was reduced by 6.5%.     

多Agent系统中依赖关系的研究

多Ａｇｅｎｔ系统是分布式人工智能研究的一个重要分支。本文详细讨论了多Ａｇｅｎｔ系统中死锁依赖的性质以及三种解决死锁依赖的方法,为多Ａｇｅｎｔ系统中稳定性和活性的研究提供了有效的途径。