Hardware/Software Deadlock Detection Algorithm and Implementation

This report introduces a new theorem and its proof about the problem of deadlock detection. First, we examine how to represent the problem of deadlock with a directed graph. Then, translation from a directed graph into a matrix is elaborated. The theorem and its proof are based on this matrix representation. By applying this theorem, we present a novel parallel deadlock detection algorithm, which we hypothesize has a run-time complexity of O[subscript hw](min(m,n)) in a parallel hardware implementation, where m, n are the number of processors and resources involved in deadlock detection respectively