Probabilistic Models of Computer Deadlock ; CU-CS-041-74

As the number of processes and resources increase within a computer system, does the probability of that system’s encountering deadlock increase or decrease? The problem of deadlock in computer system and a model applicable to the investigation of this problem are presented. The model treats sequences of resource activity as potential members of the set of strings accepted by a probabilistic automation. This paper, after explaining the model as its application, describes a transformation on the automation which makes it amenable to calculations of the probability of deadlock. These calculations consist of: 1. Derivation of necessary and sufficient conditions for an automation to be well-behaved – formally described as accepting a normalized language, and 2. Usage of these conditions to yield closed-form equations of deadlock probability under several definitions thereof. Although the automation model used in these calculations is a probabilistic pushdown automation, it is indicated that the procedures described can also be applied to other types of probabilistic automata modeling other deadlock situations. Results of calculations on actual computer system models are also described, indicating that within the types of systems considered, the probability of deadlock increases