Generating Efficient Distributed Deadlock Avoidance Controllers

Abstract

We study how to generate efficient resource allocation controllers that implement distributed deadlock avoidance and are specific for a given application. We classify the solutions depending on the type and initial ammount of the resources handled. General solutions to deadlock avoidance in distributed systems are considered impractical due to the high communication overhead. In previous work, however, we showed that practical solutions exist when all possible sequences of resource requests are known a priori in the form of call graphs; in this case protocols can be constructed that involve no communication. These run-time protocols make use of annotations of the call-graph computed statically. If the annotations are acyclic, then deadlocks are unreachable. In this paper we first show that the algorithm that computes acyclic annotations is complete, in the sense that every optimal annotation can be generated. Second, we show that if the annotations are not acyclic, then checking whether deadlocks are reachable is NP-complete. Third, we study the problem of computing minimal annotations given constrainst in the system’s initial resources, and prove the complexity of this problem: if the restrictions are general the problem is NP-complete, while if the only restrictions are binary semaphores the problem becomes polynomial.