A model for deadlock detection based on automata and languages theory

AbstractIn this paper, a model for solving the deadlock detection problem is introduced by using the formalism of the Automata and Languages Theory. The abstraction allows one to model the wait-for-relations between processes as a string of symbols. The set of wait-for-strings, which represent deadlock situations, is a regular language and it is accepted by a Finite Automaton (FA). The periodical algorithm for deadlock detection based on this FA has a linear time complexity O(N). This algorithm is extended to a non-periodical one by introducing, in the FA, the resource release operations of the processes. In this case, the detection time complexity is O(1)