Deadlock-free Supervisor Design for Robotic Manufacturing Cells With Uncontrollable and Unobservable Events

In this paper,a deadlock prevention policy for robotic manufacturing cells with uncontrollable and unobservable events is proposed based on a Petri net formalism.First,a Petri net for the deadlock control of such systems is defined.Its admissible markings and first-met inadmissible markings(FIMs)are introduced.Next,place invariants are designed via an integer linear program(ILP)to survive all admissible markings and prohibit all FIMs,keeping the underlying system from reaching deadlocks,livelocks,bad markings,and the markings that may evolve into them by firing uncontrollable transitions.ILP also ensures that the obtained deadlock-free supervisor does not observe any unobservable transition.In addition,the supervisor is guaranteed to be admissible and structurally minimal in terms of both control places and added arcs.The condition under which the supervisor is maximally permissive in behavior is given.Finally,experimental results with the proposed method and existing ones are given to show its effectiveness.     

Proving Total Correctness of Parallel Programs

An approach to proving paralel programs correct is presented. The steps are 1) model the paralel program, 2) prove partial correctness (proper synchronization), and 3) prove the absence of deadlock, livelock, and infinite loops. The parallel program model is based on KeUler's model. The main contributions of the paper are techniques for proving the absence of deadlock and livelock. A connection is made between Keler's work and Dijkstra's work with serial non-deterministic programs. It is shown how a variant function may be used to prove finite termination, even if the variant function is not strictly decreasing, and how finite termination can be used to prove the absence of livelock. Handling of the finite delay assumption is also discussed. The illustrative examples indude one which occurred in a commercial environment and a classic synchronization problem solved without the aid of special synchronization primitives.     

基于SMT的时钟约束语言CCSL的形式化分析方法与工具

时钟约束语言CCSL是一种用于描述实时嵌入式系统中事件之间约束的形式化语言.它是UML针对实时嵌入式系统建模的扩展包MARTE （Modeling and Analysis of Real-Time and Embedded systems）中用于对时间建模的一个子语言.给定一组由CCSL定义的时钟约束条件,需要判断是否存在某种调度策略满足约束,是否所有满足这些约束的行为都不会导致系统死锁等分析.针对CCSL的形式化分析目前已经有一定的研究工作,如基于状态迁移系统与时间自动机的方法等.但这些方法要么只针对某种特定的分析,要么只适用于部分CCSL约束,要么分析效率较低.本文提出一种基于SMT的统一且高效的CCSL形式化分析方法.统一性体现在其可用于有效性证明、迹分析、死锁检测、LTL模型检测等方面的验证与分析.基于该方法开发了原型工具同时支持上述四种验证功能.工具集成了当前最高效的SMT求解器Z3和CVC4.得益于SMT求解器的高效性,实验中大部分的验证可以在短时间内完成.     

Source Transformation for Concurrency Analysis

Concurrent programming poses a unique set of problems for quality assurance. These difficulties include the complexities of deadlock, livelock and divergence, which can be extremely difficult to detect and debug. A variety of tools have been developed to assist designers and developers of concurrent applications. Some of these tools, such as VeriSoft, are specific to particular implementation languages, such as C++.The Java Remote Method Invocation (Java RMI) package facilitates the implementation of concurrent applications, including those where processes reside on different hosts and communicate over networks. Unfortunately, it does not relieve the developer from the potential pitfalls of controlling concurrent access to remote objects, and may, in fact, make concurrency problems even more difficult to find.This paper presents an approach that allows the VeriSoft state exploration system to be used to analyze Java RMI programs for deadlock, livelock, divergence, and assertion violations. The system works by transforming Java RMI programs into C++ programs where Java syntax, structure, concurrency and memory management are replaced by C++ equivalents and Java RMI communication has been transformed to VeriSoft C++ inter-process communication. We present the details of this transformation and discuss preliminary results for a number of small examples.     

A deadlock and livelock free protocol for decentralized Internet resource coallocation

Computing over the Internet is becoming increasingly popular. With the emerging infrastructures such as computational grids and Web services, it is possible to develop applications that support various Internet-wide collaborations through seamlessly harnessing appropriate Internet resources. Yet, as Internet computing is becoming pervasive, it also presents a number of new challenges in designing efficient resource allocation protocol that provides clear directives on the acquisition of shared resources. In particular, the problem of coallocating distributed Internet resources that span multiple administrative domains is complicated by 1) the need for scalability, 2) the availability of alternative co-allocation schemes, 3) the possibility of deadlock and livelock, and finally 4) the lack of means for changing information between the independent Internet applications. Motivated by this, this paper develops a new scalable protocol for fast coallocation of Internet resources. The proposed protocol is free from deadlock and livelock, and seeks to effectively exploit the available alternative resource coallocation schemes through parallelization of requests for required resources. Experimental results demonstrate that the proposed protocol yields a significant performance improvement over the existing deadlock prevention protocol.     

Deadlock prevention in concurrent real-time systems

To meet consistency requirements found in concurrent applications, a process must be guaranteed that it will be able to use all resources in a set ofpassive resources (such as shared data structures). To provide predictable execution time required in real-time systems, a process also needs guaranteed access to at least one of a set ofactive resources (such as processors) associated with each passive resource. As such, a concurrent real-time-process has AND-OR resource requirements. If locking is used to provide exclusive access to resources, deadlock is possible since processes can request additional resources while holding other resources. Deadlock detection and recovery techniques and deadlock avoidance techniques typically involve preempting resources or terminating processes, and are therefore inappropriate for real-time systems that require the execution time of processes to be predictable. This paper describes a general resource request condition that we proveprevents deadlock in AND-OR systems. It also describes how we use this AND-OR deadlock prevention technique in a concurrent real-time system.This work is supported in part by the following grants: ONR N000014-89-J-1131 and ARO DAAG-29-84-k-0061.     

Deadlock prevention for flexible manufacturing system

Deadlock must be prevented via the shop controller during the flexible manufacturing system （FMS） performing. Various models have been tried for the analysis and design of shop controller. Petri net is suitable to describe the dynamic behavior of the discrete event system, such as concurrency, conflict and deadlock, however, the verification of the .system behavior needs structure analysis with complex theoretical proof method. Temporal logic model checking has important advantages over traditional theorem prover. It is flatly automatic and can produce possible counter-example which is particularly important in finding subtle error in complex transition systems. In this paper, a new method for the deadlock prevention based on Petri net and Temporal Logic model checking is presented. The specification in the Temporal Logic is expressed according to some result of structure analysis of the Petri net. The model checking is employed to execute the formal verification, which will conduct an exhaustive exploration of all possible behaviors. Finally, an example is presented to demonstrate how the method works.     

Deadlock p revention f or flexible manufacturing system

Deadlock must be prevented via the shop controller during the flexible manufacturing system (FMS) performing. Various models have been tried for the analysis and design of shop controller. Petri net is suitable to describe the dynamic behavior of the discrete event system , such as concurrency , conflict and deadlock , however , the verification of the system behavior needs ructure analysis with complex theoretical proof method. Temporal logic model checking has important advantages over traditional theorem prover. It is fully automatic and can produce possible unter- example which is particularly important in finding subtle error in complex transition systems. In this paper ,a new method for the deadlock prevention based on Petri net and Temporal Logic model checking is presented. The specification in the Temporal Logic is expressed according to some result of structure analysis of the Petri net . The model checking is employed to execute the formal verification ,which will conduct an exhaustive exploration of all possible behaviors. Finally ,an example is presented to demonstrate how the method works.     

Modeling in the design of a KBS validation system

We describe and illustrate the modeling issues in the design of a system for validation of knowledge based systems (KBSs). the domain of such a validation system is “KBSs and their validation problems.” the basic idea in our solution is the following. Since different KBSs may use different knowledge representation languages, we first represent the target KBS (i.e., the KBS to be validated) in a general formal model of KBS, and then validate it in this form. the advantage of this strategy is that validation problem solving needs only to refer to the common language of the general formal model. We present a set of possible conceptual abstraction levels in such a model, and argue that each level is associated with a related view on validation problems. Since high level characterizations are difficult to abstract from current knowledge representation languages, we consider the formal aspects of modeling mainly at the “lowest” level, the so-called inference primitive level. We illustrate the approach by formalizing a solution for selected modeling issues at this level.     

Model Checking Semi-Continuous Time Models Using BDDs

The verification of timed systems is extremely important, but also extremely difficult. Several methods have been proposed to assist in this task, including extensions to symbolic model checking. One possible use of model checking to analyze timed systems is by modeling passage of time as the number of taken transitions and applying quantitative algorithms to determine the timing parameters of the system. The advantage of this method is its simplicity and efficiency. In this paper we extend this technique in two ways. First, we present new quantitative algorithms that are more efficient than their predecessors. The new algorithms determine the number of occurrences of events in all paths between a set of starting states and a set of final states. We then use these algorithms to introduce a new model of time, in which the passage of time is dissociated from the occurrence of events. With this new model it is possible to verify systems that were previously thought to require dense time models. We use the new method to verify two such examples previously analyzed by the HyTech tool: a steam boiler example and a fuel injection controller.     

Comparing digraph and Petri net approaches to deadlock avoidance inFMS

Flexible manufacturing systems (FMSs) are modern production facilities with easy adaptability to variable production plans and goals. These systems may exhibit deadlock situations occurring when a circular wait arises because each piece in a set requires a resource currently held by another job in the same set. Several authors have proposed different policies to control resource allocation in order to avoid deadlock problems. These approaches are mainly based on some formal models of manufacturing systems, such as Petri nets (PNs), directed graphs, etc. Since they describe various peculiarities of the FMS operation in a modular and systematic way, PNs are the most extensively used tool to model such systems. On the other hand, digraphs are more synthetic than PNs because their vertices are just the system resources. So, digraphs describe the interactions between jobs and resources only, while neglecting other details on the system operation. The aim of this paper is to show the tight connections between the two approaches to the deadlock problem, by proposing a unitary framework that links graph-theoretic and PN models and results. In this context, we establish a direct correspondence between the structural elements of the PN (empty siphons) and those of the digraphs (maximal-weight zero-outdegree strong components) characterizing a deadlock occurrence. The paper also shows that the avoidance policies derived from digraphs can be implemented by controlled PNs.     

Starvation and critical race analyzers for Ada

Starvation and critical race analysis tools for Ada designs are described. These tools are part of a temporal analysis toolset that includes an operational specification language, a language interpreter, and a deadlock analyzer for Ada. The starvation analyzer is based on a set-theoretic model of starvation. It uses a proof tree produced by the deadlock analyzer to define the possible computation space of the design. A preprocessing phase of the starvation tool optimizes the analysis so that the resulting analysis is efficient. Unlike livelock analysis in state machines, the starvation analyzer does not require a priori specification of home states to discern liveness. The critical race analysis tool provides semiautomatic proof of critical races by identifying nondeterministic rendezvous (races) from the proof tree generated by the deadlock analyzer, and then assisting the human operator in identifying which of these constitute critical races. Several design examples are used to demonstrate the capabilities of the two analysis methods     

E-2D Torus网络结构中的无死锁路由算法

研究了太比特路由器核心交换网络拓扑的一种新结构-E-2Dtorus网络.该网络具有简单,对称,可扩展等优势.提出了适用于该网络结构的两种路由算法NPN(NoPositivetoNegative)和IDO(ImprovedDimensionOrder).部分自适应的NPN和确定性的IDO都是无死锁,无活锁且最短的路由算法.同时给出了无死锁无活锁的证明.最后,在8×8的E-2Dtorus网络上对路由算法进行仿真,结果表明E-2Dtorus是一种有潜力的网络拓扑结构,两种路由算法具有良好的性能.     

A deadlock avoidance approach for nonsequential resource allocation systems

The paper concentrates on the deadlock-avoidance problem for a class of resource allocation systems modeling manufacturing systems. In these systems, a set of production orders have to be executed in a concurrent way. To be executed, each step of each production order needs a set of reusable system resources. The competition for the use of these resources can lead to deadlock problems. Many solutions, from different perspectives, can be found in the literature for deadlock-related problems when the production orders have a sequential nature [sequential resource allocation systems (S-RAS)]. However, in the case in which the involved processes have a nonsequential nature [nonsequential resource allocation systems (NS-RAS)], the problem becomes more complex. In this paper, we propose a deadlock avoidance algorithm for this last class of systems. We also show the usefulness of the proposed solution by means of its application to a real system.     

Minimizing the cardinality of an events set for supervisors ofdiscrete-event dynamical systems

In this paper we study sufficient observation and work spaces for supervisors of a class of discrete-event dynamical systems (DEDS). We use finite state automata to model a DEDS. The finite automata generates a formal language defined over the set of events in the DEDS. A supervisor is a feedback system that observes a generated trace of events and dynamically disables (or enables) a subset of controllable events such that the closed-loop system behaves as desired. We model the desired behavior of the DEDS by a sublanguage defined over the set of events. A sufficient observation space is a collection of events whose observation by a supervisor is enough to realize a given desired behavior. A sufficient work space is a sufficient observation space such that the control action of the supervisor is limited to only the controllable elements of the work space. We construct algorithms to evaluate a sufficient work (or observation) space. The reduction of work (or observation) spaces results in reducing the number of event detectors, communication, and command channels between the supervisor and the plant     

New Controllability Condition for Siphons in Ws3PR Nets

Existing policies for deadlock control are mainly based on siphons due to their ability to indicate deadlocks, and can be used as a powerful tool to deal with deadlock situations in flexible manufacturing systems. In order to avoid deadlocks, researchers often add monitors to control siphons. This may result in redundant monitors, unnecessary cost, and restriction of the behavior permissiveness. For example, for a system of sequential systems with shared resources (S⁴R), the existing deadlock control policies based on max, max′ or max′′‐controlled siphons tend to overly restrict the behavior of a controlled system. To ensure maximal permissive behavior of controlled systems, a new concept of siphon controllability named W‐control is defined and then a sufficient and necessary condition under which a WS³PR is live if all its siphons are W‐controlled. Examples are given to demonstrate them.     

带时间标记的鉴别协议的验证

对等实体鉴别服务是网络安全体系结构中的一项重要服务。本文介绍了计算机网络通信环境中的带时间标记的鉴别协议，该协议具有对称性，事件的时序是任意的。根据该协议的状态转称图，本文应用可达性分析技术，验证了该协议的完整性，无死锁，无活锁，终止性，有界性以及在不存任何不可执行的交互作用等重要性质。     

An expressive event-based language for representing user behavior patterns

In-depth analysis of user interactions with applications in large systems is widely adopted as a means to understand user’s behavior for strategic purposes such as fraud detection, system security, weblog analysis, social networking, and customer relationship management. Overall, the user behavior presents characteristics, relationships, structures, and effects of a sequence of actions in a specific application domain. The interaction of users with applications at the business-level generates events that make the elements of the user behavior. Formal modelling and representation of complex patterns of user actions using expressive languages are critical aspects of behavior analysis. We present a model to describe the behavior elements and their relationships. The model also provides a systematic mechanism for describing and presenting events, sequence of events, and complex behavior patterns. A behavior pattern can be defined as a sequence of typed events that occur during specific time intervals. An event consists of a tuple of attributes whose values represent an observation of the behavior. In this paper, first we define a semantic model of the user behavior to address the issues around the user behavior representation, and then we present syntax and semantics of a generic Behavior Pattern Language (BPL), which enables the analysts to define a variety of complex behavior patterns in a declarative manner. We present the feasibility of the approach through several examples of complex behavior patterns expressed using the proposed language.     

Networks on which hot-potato routing does not livelock

Summary. Hot-potato routing is a form of synchronous routing which makes no use of buffers at intermediate nodes. Packets must move at every time step, until they reach their destination. If contention prevents a packet from taking its preferred outgoing edge, it is deflected on a different edge. Two simple design principles for hot potato routing algorithms are minimum advance, that advances at least one packet towards its destination from every nonempty node (and possibly deflects all other packets), and maximum advance, that advances the maximum possible number of packets. Livelock is a situation in which packets keep moving indefinitely in the network without any packet ever reaching its destination. It is known that even maximum advance algorithms might livelock on some networks. We show that minimum advance algorithms never livelock on tree networks, and that maximum advance algorithms never livelock on triangulated networks. Received: March 1999 / Accepted: August 1999     

Verification and conformance test generation of communication protocol for railway signaling systems

Verification and testing are complementary techniques that are used to increase the level of confidence in the correct functioning of communication systems as prescribed by their specifications. This paper presents an experience of model checking for Korean railway signaling protocol specified in LTS (Labeled Transition System). This formal approach checks deadlock, livelock and reachability for the state and action to verify whether properties expressed in modal logic are true on specifications. We also propose a formal method for semi-automated test case generation for Korean railway signaling protocol described in I/O FSM (Input/Output Finite State Machine). This enables the generation of more complete and consistent test sequence for conformance testing. The above functions are implemented by C++ language and included within RSPVTE (Railway Signaling Protocol Verification and Testing Environment) in the MS-windows environment.