A Local Deadlock Detection and Resolution Algorithm for Process Networks
Wei Huang, Deyu Qi · 2008
Kahn Process Network (KPN) is a popular model for data streaming applications. Since it is impractical to implement an idealized KPN model with unbounded channel capacities, a bounded scheduling policy has been proposed by T. M. Parks. However, this policy would lead to artificial deadlocks in PN. Several deadlock detection mechanisms have been proposed to address this problem. In this paper, we propose an efficient deadlock detection algorithm which extends M. Prietopsilas algorithm for PN using message cooperation. It achieves a message complexity of O(n) and finds the bottleneck channel to resolve the artificial deadlock.