基于SUIF2的静态死锁检测方法研究

死锁是并发程序中常见的错误之一,且由于并发程序运行的不确定性使得死锁难以检测。针对该问题,通过对C多线程程序死锁的分析,提出了一种基于SUIF2的静态死锁检测方法,设计了基于SUIF2的C多线程程序静态死锁检测的框架结构和锁集分析算法。最后通过一个实例说明了该检测方法的有效性。     

Distributed fault detection for interconnected second-order systems

In this paper, the existence of unknown input observers for networks of interconnected second-order linear time invariant systems is studied. Two classes of distributed control systems of large practical relevance are considered. It is proved that for these systems, one can construct a bank of unknown input observers, and use them to detect and isolate faults in the network. The result presents a distributed implementation. In particular, by exploiting the system structure, this work provides further insight into the design of UIO for networked systems. Moreover, the importance of certain network measurements is shown. Infeasibility results with respect to available measurements and faults are also provided, as well as methods to remove faulty agents from the network. Applications to power networks and robotic formations are presented. It is shown how the developed methodology apply to a power network described by the swing equation with a faulty bus. For a multi-robot system, it is illustrated how a faulty robot can be detected and removed.     

分布式系统死锁的预防、避免和检测

分布式系统涉及到资源和数据的高度共享,从而可能引发死锁。分布式系统的死锁是由于资源和通讯产生的。从分布式系统死锁产生的条件,解决策略,以及分布式系统中死锁预防、避免和检测的各种算法进行了具体阐述。     

分布式死锁检测算法中伪死锁率的研究和改进

死锁处理是分布式系统中的关键问题,其中处理死锁最主要的手段为死锁检测。在评价死锁检测算法性能时伪死锁率被视为一项重要指标,故降低伪死锁率对提高算法性能有着促进作用,而目前大多数算法改进对伪死锁率关注较少。本文阐述了伪死锁研究的意义,并对若干种死锁检测算法的伪死锁率进行研究和模拟实验,认为现有的死锁算法可分为两类:环内检测和环无关检测。并分别通过减少冗余消息和本地死锁解决两种改进方法来降低目前算法的伪死锁率,最终实验表明算法性能获得较大提高。     

数据库系统中并发事务死锁的解除与避免

本文利用Ｐｅｔｒｉ网作为工具，从提高事务进程并行性出发，建立数据库系统的并发事务进程竞争数据资源的模型。并由此推导出死锁和临界死锁的充分必要条件及提邮相应的避免死锁的控制机制。该控制机制是通过如何对关键的空闲数据资源进行控制分配来实现避免死锁。     

Algorithms for distributed termination detection

The termination problem for distributed computations is analyzed in the general context of asynchronous communication. In the underlying computational model it is assumed that messages take an arbitrary but finite time and do not necessarily obey the FIFO rule. Time diagrams are used as a graphic means of representing the overall communication scheme, giving a clear insight into the difficulties involved (e.g., lack of global state or time, inconsistent time cuts) and suggesting possible solutions.Several efficient algorithms for the solution of the termination problem are presented. They are all based on the idea of message counting but have a number of different characteristics. The methods are discussed and compared with other known solutions.Friedemann Matternreceived the Diploma in computer science from the University of Bonn, West Germany, in 1983.He is now a research scientist in the Department of Computer Science at the University of Kaiserslautern and is currently completing his Ph.D. His primary research interests include distributed algorithms, programming language design, and compiler construction. The author can be reached by electronic mail via mattern @ incas.uucp or mattern % uklirb.uucp @ Germany.csne.This work has been supported by the Deutsche Forschungsgemeinschaft (DFG) as part of the SFB124 research project VLSI-Design and Parallelism     

Distributed MST for constant diameter graphs

This paper considers the problem of distributively constructing a minimum-weight spanning tree (MST) for graphs of constant diameter in the bounded-messages model, where each message can contain at most B bits for some parameter B. It is shown that the number of communication rounds necessary to compute an MST for graphs of diameter 4 or 3 can be as high as and , respectively. The asymptotic lower bounds hold for randomized algorithms as well. On the other hand, we observe that O(log n) communication rounds always suffice to compute an MST deterministically for graphs with diameter 2, when B = O(log n). These results complement a previously known lower bound of for graphs of diameter Ω(log n). An extended abstract of this work appears in Proceedings of 20th ACM Symposium on Principles of Distributed Computing, August 2001.     

基于Petri网模型的FMS死锁结构

死锁是柔性制造系统中容易发生的异常现象，如不加以消除，将会导致整个系统的瘫痪。文中通过Petri网模型对FMS的结构分析，揭示出导致FMS死锁的结构元素和活性特征，在此基础上，提出了FMS的无死锁Petri网控制器算法，并举例说明这种控制器算法在FMS中的应用。     

基于初等运动的多机器人避碰及死锁预防

该文以一实际应用为背景提出了多移动机器人避碰及死锁预防算法,该算法将机器人的运行环境形式化地描述为初等运动集、冲突图、总任务集及机器人作业集,利用集合论、图论的有关方法及技术实现了多机器人间的避碰与死锁预防。当机器人的运行环境改变时,只需要对相应的集合描述文件进行修改,而不用对程序做任何屐改动。算法的另一个特点是利用避碰算法巧妙地完成了死锁预防。仿真和实际运行证明了该算法高效可靠。