Title :
A novel parallel deadlock detection algorithm and architecture
Author :
Shiu, Pun H. ; Tan, Yudong ; Moone, Vincent J.
Author_Institution :
Electr. & Comput. Eng., Georgia Inst. of Technol., Atlanta, GA, USA
Abstract :
A novel deadlock detection algorithm and its hardware implementation are presented in this paper. The hardware deadlock detection algorithm has a run time complexity of Ohw(min(m,n)), where m and n are the number of processors and resources, respectively. Previous algorithms based on a resource allocation graph have Osw(m×n) run time complexity for the worst case. We simulate a realistic example in which the hardware deadlock detection unit is applied, and demonstrate that the hardware implementation of the novel deadlock detection algorithm reduces deadlock detection time by 99.5%. Furthermore, in a realistic example, total execution time is reduced by 68.9%
Keywords :
computational complexity; concurrency control; hardware-software codesign; network operating systems; parallel algorithms; parallel architectures; resource allocation; system recovery; hardware implementation; parallel deadlock detection algorithm; resource allocation graph; run time complexity; Computer architecture; Detection algorithms; Hardware; Marine vehicles; Operating systems; Permission; Programming profession; Real time systems; Resource management; System recovery;
Conference_Titel :
Hardware/Software Codesign, 2001. CODES 2001. Proceedings of the Ninth International Symposium on
Conference_Location :
Copenhagen
Print_ISBN :
1-58113-364-2
DOI :
10.1109/HSC.2001.924654
