Search

The Go programming language is acquiring momentum in the development of concurrent software. Even though Go supports the shared-memory model, the message-passing alternative is the favoured idiomatic approach. Naturally, this practice is not exempt of the usual difficulties: programs may deadlock and the language run-time has only very basic support for deadlock detection. Previous research on deadlock detection mainly focused on shared-memory concurrency models. For mainstream languages, tools and approaches specific to the message-passing paradigm are scarce and incipient. There is however a large body of work on models of concurrency that only recently started to be applied to languages like Go. Since the Go run-time lets many deadlocks pass unnoticed, and the existing solutions provided by third party tools detect many deadlocks but only try to fix a limited set of specific patterns, imposing severe conditions to do so, there is a clear need for more general deadlock resolution strategies, going beyond prevention and avoidance. To gain insight on real-world deadlock bugs, we first built and categorized a collection of bugs sourced from high-profile open-source Go projects. Next, we extended and implemented an algorithm that takes an abstraction of the communication behaviour of the program and, when all the communication operations on channels necessary for progress are present, but a deadlock is possible, presents the problem and offers a possible resolution for the error. The extensions allows our approach to analyse a much wider range of real world programs. We conclude with an evaluation, comparing with two other state-of-the-art solutions. A linguagem de programação Go tem ganhado tração no desenvolvimento de software concorrente. Apesar de o Go suportar o modelo de partilha de memória, o modelo alternativo de partilha de mensagens é a abordagem idiomática. Naturalmente, esta prática não está isenta das dificuldades usuais: os programas podem bloquear e o runtime da linguagem só possui um suporte muito básico para a deteção destes bloqueios. Investigação anterior na deteção de bloqueios focou principalmente no modelo de partilha de memória. Para linguagens convencionais, ferramentas e abordagens dedicadas ao paradigma de passagem de mensagens são escassas e incipientes. No entanto, existe um grande conjunto de trabalhos sobre modelos de concorrência que só recentemente começou a ser aplicado em linguagens como o Go. Visto que o run-time do Go deixa muitos bloqueios passar despercebidos e as soluções existentes detetam muitos bloqueios, mas só tentam resolver um conjunto muito pequeno de padrões. De modo a ganhar conhecimento sobre erros de bloqueio reais, nós começámos por construir e categorizar uma coleção de erros obtidos a partir de projetos Go open-source de alto perfil. De seguida, nós estendemos e implementámos um algoritmo que recebe uma abstração do comportamento da comunicação de um programa e quando todas as operações de comunicação nos canais necessários para o progresso estão presentes, mas um bloqueio é possível, apresenta o erro e oferece uma possível resolução do erro. A nossa extensão permite analisar um conjunto muito maior de programas reais. Concluímos com uma avaliação, comparando com duas outras soluções do estado da arte.

It has been an active research area to develop robust supervisory control policies for production systems with unreliable resources. So far, most methods for robust deadlock resolution apply only to systems without flexible routes, where each processing step of any part type requires a unique prespecified resource. In this paper, we address deadlock avoidance control problem in production systems with both failure-prone resources and flexible routings, which allow that a part has options when deciding the resource acquisition at each step. This paper presents properties that a controller with robustness must satisfy. Specifically, at any system reachable state, neither the failed resources nor part instances trapped in these resources should have too much detrimental effect on the other portions of the system. Thus, the full range of part types’ production could be assured at all time. After defining the notions of reduced system and reduced state with respect to unreliable resources, we identify and prove conditions for determining whether or not the state resulting from the occurrence of an event is feasible. Subsequently, we develop a method for robust deadlock avoidance, which uses the solutions to state safety checking problem for the reduced production system with only reliable resources. An illustrative example shows the effectiveness of this method. Finally, we conduct a comparison investigation of some representative approaches in the literature about robust supervisory control for deadlock resolution in resource allocation systems with routing flexibility.

It is no longer possible to improve CPU performance by increasing clock speeds and cache sizes, at the rate it once was, due to heat generation becoming too high. Thus, CPU manufacturers resorted to improving performance through others means such as hyper- threading and multi-core architectures. The use of concurrent programming has been on a steady rise to make full use of modern hardware. However, concurrent program- ming is considerably harder to grasp than its sequential counterpart. Humans naturally think sequentially, which makes this method of programming notoriously difficult. At a sufficiently large scale, it is hard to reason about interaction between processes, often leading to the introduction of errors that are hard to detect. This results in programs being unknowingly unsafe. A particular case of concurrency errors are deadlocks, which occur when a program reaches a state where two or more threads prevent each other from accessing a shared resource, effectively blocking the program permanently. Deadlocks are hard to debug because their cause may not be easily identified, and because it is difficult to reliably reproduce them, due to the wide range of execution possibilities. Despite being difficult to develop and debug concurrent programs, there is a lack of tools and mechanisms to help the user detect and fix deadlocks. Go, a programming language that employs a message passing concurrency model, in addition to a shared memory model, can detect, at runtime, cases where all the threads are blocked. However, it does not auto- matically fix the error or provide a suggestion of a solution. To the best of our knowledge, there are no automatic deadlock resolution tools for Go, despite there being multiple deadlock detection tools. As such, to bridge this gap, this work proposes a proof of con- cept tool that statically detects deadlocks in Go and automatically fixes some of them. It uses another existing tool to extract the communication protocol of a Go program, which is then translated to CCS processes and solved. To do this, existing deadlock detection and resolution algorithms were extended and implemented. Já não é possível melhorar o desempenho de CPU através do aumento de velocidades de clock e tamanho de caches ao ritmo que anteriormente era possível, devido à geração de calor se tornar demasiado elevada. Assim, os fabricantes de CPU recorreram à melho- ria de desempenho por outros meios, como hyperthreading e arquiteturas multi-core. O uso de programação concorrente tem sido preeminente para aproveitar ao máximo o hard- ware moderno. No entanto, programação concorrente é consideravelmente mais difícil de compreender do que o homólogo sequencial. Os humanos pensam sequencialmente por natureza, o que torna este método de programação especialmente difícil. Numa es- cala suficientemente grande, é difícil perceber a interação entre processos, o que leva a que erros difíceis de detetar sejam introduzidos. Isto resulta em programas inadvertida- mente inseguros. Um caso particular de erros de concorrência são bloqueios, que ocorrem quando um programa chega a um estado em que dois ou mais threads não permitem que os outros acedam a um recurso partilhado, efetivamente bloqueando o programa permanentemente. Bloqueios são difíceis de depurar por a sua causa não ser facilmente identificável, e porque é difícil de os reproduzir consistentemente, devido à variedade de caminhos de execução. Apesar de ser difícil de programar e depurar programas con- correntes, há uma falta de ferramentas e mecanismos que ajudem o utilizador a detetar e resolver bloqueios. Go, uma linguagem de programação que emprega um modelo de concorrência de passagem de mensagens, para além de um modelo de memória parti- lhada, consegue detetar situações em que todas as threads estão bloqueadas, em tempo de execução. No entanto, não consegue automaticamente resolver o erro ou sugerir uma solução. Tanto quanto sabemos, não existe nenhuma ferramenta de resolução automática de bloqueios para Go, apesar de haver várias ferramentas de deteção de bloqueios. Para endereçar esta situação, este trabalho propõe uma ferramenta que deteta bloqueios em Go e automaticamente resolve alguns. Esta usa outra ferramenta para extrair o protocolo de comunicação de um programa Go, que é traduzido para processos CCS e resolvido. Para isso, algoritmos de deteção e resolução de bloqueios existentes foram modificados.

Deadlock resolution strategies based on siphon control are widely investigated. Their computational efficiency largely depends on siphon computation. Mixed-integer programming &#x0028 MIP &#x0029 can be utilized for the computation of an emptiable siphon in a Petri net &#x0028 PN &#x0029 . Based on it, deadlock resolution strategies can be designed without requiring complete siphon enumeration that has exponential complexity. Due to this reason, various MIP methods are proposed for various subclasses of PNs. This work proposes an innovative MIP method to compute an emptiable minimal siphon &#x0028 EMS &#x0029 for a subclass of PNs named S4PR. In particular, many particular structural characteristics of EMS in S4PR are formalized as constraints, which greatly reduces the solution space. Experimental results show that the proposed MIP method has higher computational efficiency. Furthermore, the proposed method allows one to determine the liveness of an ordinary S4PR.

An interconnection network forms the communication backbone in both on-chip and off-chip systems. In networks, congestion causes packets to be blocked. Indefinite blocking can occur if cyclic dependencies exist, leading to deadlock. All modern networks devote resources to either avoid deadlock by eliminating cyclic dependences or to detect and recover from it. Conventional buffered flow control does not allow a blocked packet to move forward unless the buffer at the next hop is guaranteed to be free. We introduce SWAP, a novel mechanism for enabling a blocked packet to perform an in-place swap with a buffered packet at the next hop. We prove that in-place swaps are sufficient to break any deadlock and are agnostic to the underlying topology or routing algorithm. This makes SWAP applicable across homogeneous or heterogeneous on-chip and off-chip topologies. We present a lightweight implementation of SWAP that reuses conventional router resources with minor additions to enable these swaps. The additional path diversity provided by SWAP provides 20-80% higher throughput with synthetic traffic patterns across regular and irregular topologies compared to baseline escape VC based solutions, and consumes 2-8× lower network energy compared to deflection and global-synchronization based solutions.

Deadlock resolution is a classic problem faced by operating and database systems. It not only affects the utilization of system resources, but also may bring unpredictable consequences to the events corresponding to deadlock processes. Spiking neural P systems (SN P systems) are neural networks built upon membrane computing models inspired by neuron communication via excitatory and inhibitory spikes. We explore the application of SN P systems to the optimal revocation of deadlock processes in order to overcome deficiencies in traditional deadlock resolution methods such as exhaustive method and time cost method. Our system determines the optimal order of revocation by calculating the time cost associated with the deadlock release process. Compared to the exhaustive method and time cost method, our system significantly reduces the time complexity of the deadlock revocation process, improving deadlock resolution efficiency and offering more opportunities for parallelism.

Purpose This paper aims to propose and formulate a complicated routing/scheduling problem for multiple automated guided vehicles (AGVs) in a manufacturing system. Design/methodology/approach Considering the due date of AGVs requiring for material handling among shops in a jobshop layout, their earliness and tardiness are significant in satisfying the expected cycle time and from an economic view point. Therefore, the authors propose a mathematical program to minimize the penalized earliness and tardiness for a conflict-free and just-in-time production. Findings The model considers a new concept of turning point for deadlock resolution. As the mathematical program is difficult to solve with a conventional method, an optimization method in two stages, namely, searching the solution space and finding optimal solutions are proposed. The performance of the proposed mathematical model is tested in a numerical example. Practical implications A case study in real industrial environment is conducted. The findings lead the decision-makers to develop a user interface decision support as a simulator to plan the AGVs’ movement through the manufacturing network and help AGVs to prevent deadlock trap or conflicts. The proposed decision support can easily be commercialized. Originality/value The benefits of such commercialization are increase in the quality of material handling, improve the delivery time and prevent delays, decrease the cost of traditional handling, capability of computerized planning and control, intelligent tracking and validation experiments in simulation environment.

In real-time distributed transaction processing, deadlocks must be detected and resolved. Timeouts are not a viable option because they lead to lost work and missed deadlines. We have proposed a suite of deadlock detection protocols and a resolution protocol which carry a varying degree of (generally low) overhead. The protocols behave differently under varying load conditions and transaction characteristics. Further, the invocation period of these protocols can be controlled to improve performance when the overhead tends to become large. The performance of these protocols has been demonstrated using a distributed real-time transaction processing simulator which provides an interactive interface to set parameters, and also has provisions to select from a variety of concurrency control, priority assignment, workload distribution and other protocols. The impact of transaction workload, underlying system configuration, resource availability, detection rates, and congestion on each of the proposed protocols is observed and presented. In general, the multi-cycle detection protocol demonstrated the most superior performance over a broad range of parameters. The results presented in this paper were obtained from over 147,000 simulations.

In the near future mobile robots, such as personal robots or mobile manipulators, will share the workspace with other robots and humans. We present a method for mission and motion planning that applies to small teams of robots performing a task in an environment with moving obstacles, such as humans. Given a mission specification written in linear temporal logic, such as patrolling a set of rooms, we synthesize an automaton from which the robots can extract valid strategies. This centralized automaton is executed by the robots in the team at runtime, and in conjunction with a distributed motion planner that guarantees avoidance of moving obstacles. Our contribution is a correct-by-construction synthesis approach to multi-robot mission planning that guarantees collision avoidance with respect to moving obstacles, guarantees satisfaction of the mission specification and resolves encountered deadlocks, where a moving obstacle blocks the robot temporally. Our method provides conditions under which deadlock will be avoided by identifying environment behaviors that, when encountered at runtime, may prevent the robot team from achieving its goals. In particular, (1) it identifies deadlock conditions; (2) it is able to check whether they can be resolved; and (3) the robots implement the deadlock resolution policy locally in a distributed manner. The approach is capable of synthesizing and executing plans even with a high density of dynamic obstacles. In contrast to many existing approaches to mission and motion planning, it is scalable with the number of moving obstacles. We demonstrate the approach in physical experiments with walking humanoids moving in 2D environments and in simulation with aerial vehicles (quadrotors) navigating in 2D and 3D environments., Boeing Company, United States. Office of Naval Research. Multidisciplinary University Research Initiative. SMARTS (N00014-09-1051), United States. Office of Naval Research (N00014-12-1-1000), National Science Foundation (U.S.). Expeditions in Computer Augmented Program Engineering

One of the major challenges from both a theoretical and practical perspectives, for effectively establishing unattended operation of automated manufacturing systems (AMSs), is to resolve the deadlock. In the existing methods on deadlock problem, most of them are focused on the models with either flexible routes or assembly operations, whereas few method investigates them with both. Furthermore, applying these methods into large-scale systems is usually nontrivial, primarily because of the fact that they generally require the enumeration of all the states or siphons. The work presented in this paper proposes a Petri net-based model which can deal with both features and develops an innovative distributed strategy that provides an online and dynamic mechanism for deadlock resolution. Each step's execution depends on a search-based procedure that seeks to determine whether there exists a feasible event sequence bringing the currently-active process or sub-processes to the nearest global critical place when other processes stagnate. By taking our approach, system can benefit from minimal communication amount among different processes, better toleration to many contingencies like resource failure, and improved system performance like throughput.

The occurrence of deadlocks should be controlled effectively by their detection and resolution, but may sometimes lead to a serious system failure. After implying an efficient detection algorithm the deadlock is resolved by a deadlock resolution algorithm whose primary step is to either select the victim then to abort the victim transaction or cause it to rollback. This step resolves deadlock but is not efficient one. This paper proposes a new deadlock resolution algorithm which doesn‟t cause any aborts /roll backs in fact it is based on the mutual cooperation of transactions and a random number representing time duration for which the process holding the resource will be suspended.

Deadlock prevention, deadlock detection and deadlock avoidance strategies are used to solve the deadlock problems of flexible manufacturing systems (FMSs). The conventional prevention policies were always attempt to prevent the system entering the deadlocked situation by using a few control places. On can know that one prohibits the deadlocked markings, some dead markings will be sacrificed. Therefore, the reachability states will become less than the initial net. However, our goal is to preserve all the reachability states of the initial net. Under our control policy, the deadlocks or deadlock zone will be channelized to live markings such that all the dead markings in reachability states will be conserved. Finally, an example is performed and can obtain the maximal permissiveness of a Petri net model. The other examples are all getting the same result. To our knowledge, this is the first work that employs the channelized method to prevent the deadlock problem for FMSs.

Since the 1980s, Petri nets (PN) have been widely used to model automated manufacturing systems (AMS) for analysis, performance evaluation, simulation, and control. They are mostly based on process-oriented modeling methods and thus termed as process-oriented PN (POPN) in this paper. The recent study of deadlock avoidance problems in AMS led to another type of PN called resource-oriented PN (ROPN). This paper, for the first time, compares these two modeling methods and resultant models in terms of modeling power, model complexity for analysis and control, and some critical properties. POPN models the part production processes straightforwardly, while ROPN is more compact and effective for deadlock resolution. The relations between these two models are investigated. Several examples are used to illustrate them. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society

The work presented in this paper seeks 1) to correct and generalize some previously published results regarding the siphon control in PT-ordinary Petri nets (PNs) and, subsequently, 2) to employ this generalized framework in order to provide an alternative explanation of the way in which certain methodologies that have been proposed in the past enforce the liveness of a particular class of PT-ordinary PN-modeling resource allocation. The derived characterizations provide a unifying framework for analyzing and interpreting the aforementioned methodologies, and also, they reveal that approaches that have been considered as disparate in the current literature can actually be "mixed" toward the development of an ever richer set of liveness-enforcing supervisory-control policies for the considered class of PNs

Although the storage capacity is rapidly increasing, the size of datasets is also ever-growing, especially for those workflows in HPC that perform the parameter sweep studies. Consequently, the deadlock caused by the storage competition between concurrent workflow instances is still a major pragmatic concern and storage management remains important for high performance and throughput computing. In practice, there are various ways to this issue, ranging from admission control to deadlock resolution. Despite being a simple solution, the admission control is conservative and not space efficient to storage utilization. Therefore, in this paper, we study the performance of the deadlock resolution approach by proposing a resource allocation algorithm which is performance resilient to the workflows characterized by different features. The algorithm is designed based on our previous result, called DDS, which takes advantages of the dataflow information of the workflow to resolve deadlock based on detection&recovery principle. We improve DDS to allow it to not only resolve the deadlock but also overcome the performance anomaly, a not yet investigated problem in our previous studies. We thus called the improved algorithm performance-resilience algorithm, denoted as DDS+. The studies in this paper can be viewed as a follow-up research on DDS and show the performance behavior of the improved algorithm in various conditions. Therefore, the results in this paper are more useful to adapt DDS+ to the workflows with different characteristics in reality while keeping the performance stable.

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.

Automated manufacturing systems (AMSs) can process different parts according to operation sequences sharing a finite number of resources. In these systems, deadlock situations can occur so that the flow of parts is permanently inhibited, and the processing of jobs is partially or completely blocked. Hence, one of the tasks of the control system is ruling resource allocation to prevent such situations from occurring. A large part of the existing literature focused on systems in which every operation is performed by only one resource. This paper proposes a deadlock strategy to avoid deadlock conditions in more complex systems where multiple resource acquisitions are allowed to complete a working operation conjunctive resource service system (CRSS). The AMS structure and dynamics is described by a colored timed Petri net model, suitable for following resource changes and working procedure updating. Moreover, digraphs characterize the complex interactions between resources and jobs so that the conditions for the deadlock occurrence are derived. Finally, an event-based controller is defined to avoid deadlock in CRSSs on the basis of the system state knowledge and of the given priority law ruling the concurrent job selection.

Deadlocks in the OR model are usually resolved by aborting a deadlocked process. Prior algorithms for the same model sometimes abort nodes needlessly wasting computing resources. This paper presents a new deadlock resolution algorithm for the OR model that satisfies the following correctness criteria: (Safety) the algorithm does not resolve false deadlocks; (Liveness) the algorithm resolves all deadlocks in finite time. The communication cost of the algorithm is similar to that of previous nonsafe proposals. The theoretical cost has been validated by simulation. In addition, different algorithm initiation alternatives have been analyzed in order to reduce the latency of deadlocks.

This work introduces a duplication-based deadlock resolution (DBDR) scheme in clustered directed acyclic graphs using three methods for duplicating a task. The scheme can be embedded within any clustering technique for handling synchronous communication with an added cost of O(|E| + (|V|)2). The main objective of task duplication, besides to resolving deadlocks, has been the reduction of communication cost and the improvement in the program computation to communication ratio. The embedding of the DBDR scheme within a clustering technique is shown along with the analysis of its complexity. A comparison between deadlock resolution strategy using the DBDR and deadlock avoidance strategy using the same clustering technique is given.

This paper revisits the problem of selecting an optimal deadlock resolution strategy, when the selection criterion is the maximization of the system throughput, and the system is Markovian in terms of its timing and routing characteristics. This problem was recently addressed in some of our previous work, that (i) provided an analytical formulation for it, (ii) introduced the notion of randomized deadlock avoidance as a generalization of the more traditional approaches of deadlock prevention/avoidance, and detection and recovery, and (iii) provided a methodology for selecting the optimal randomized deadlock avoidance policy for a given resource allocation system (RAS) configuration. An issue that remained open in the problem treatment of that past work, was whether the proposed policy randomization is essential, i.e., whether there exist any RAS configurations for which a randomized deadlock avoidance policy is superior to any other policy that does not employ randomization. The work presented in this paper establishes that for the basic problem formulation where the only concern is the (unconstrained) maximization of the system throughput—or the other typical performance objectives of minimizing the system work-in-process and mean sojourn time—randomization of the deadlock resolution strategy is not essential. However, it is also shown that, sometimes, it can offer an effective mechanism for accommodating additional operational constraints, like the requirement for production according to a specified product mix. Furthermore, the undertaken analysis provides an analytical characterization of the dependence of the aforementioned performance measures on the transition rates relating to the various events of the underlying state space, which can be useful for the broader problem of synthesizing efficient scheduling policies for the considered class of resource allocation systems.