An O(NIN(M,N)) Parallel Deadlock Detection Algorithm

Abstract

This paper presents a novel Parallel Deadlock Detection Algorithm (PDDA) and its hardware implementation, Deadlock Detection Unit (DDU). PDDA uses simple boolean representations of request, grant and no activity so that the hardware implementation of PDDA becomes easier and operates faster. We prove that the DDU has a worst-case run-time of 2 x min(m, n) - O(min(m,n)), where m is the number of resources and n is the number of processes. Previous algorithms in software, by contrast, have O(m x n) run-time complexity. We also prove the correctness of PDDA and the DDU. The DDU reduces deadlock detection time by 99.9%, (i.e., 1000X) or more compared to software implementations of deadlock detection algorithms. An experiment involving a practical situation that employs the DDU showed that the time measured from application initialization to deadlock detection was reduced by 46% compared to detecting deadlock in software.