Proc. IEEE Conference on Acoustics, Speech, and Signal
April 16-20, 2007, Honululu, HI USA,
accepted for publication.
A Distributed Deadlock Detection and Resolution
Algorithm for Process Networks
Gregory E. Allen,
Paul E. Zucknick, and
Brian L. Evans
Electrical and Computer Engineering,
The University of Texas at Austin,
Austin, TX 78712 USA
Process Networks Research
at UT Austin
In the Process Network (PN) model, multiple concurrent processes
communicate over unidirectional FIFO queues. PN is useful for
modeling signal processing systems of streaming data, and naturally
captures parallelism in these systems. PN provides formal execution
properties to alleviate the difficulties of threaded and distributed
programming, and naturally maps onto parallel and distributed
targets. For a large class of PN, clever run-time scheduling can
permit execution in bounded memory. In general, PN termination and
boundedness cannot be statically determined, so correct bounded
scheduling of PN requires run-time deadlock detection. We present the
first algorithm that correctly performs dynamic deadlock detection
and resolution for bounded scheduling of PN. The proposed algorithm
is a modification of a distributed deadlock detection algorithm by
Mitchell and Merritt.
COPYRIGHT NOTICE: All the documents on this server
have been submitted by their authors to scholarly journals or conferences
as indicated, for the purpose of non-commercial dissemination of
The manuscripts are put on-line to facilitate this purpose.
These manuscripts are copyrighted by the authors or the journals in which
they were published.
You may copy a manuscript for scholarly, non-commercial purposes, such
as research or instruction, provided that you agree to respect these
Last Updated 12/12/12.