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

fYear

2001

fDate

2001

Firstpage

73

Lastpage

78

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 O_hw(min(m,n)), where m and n are the number of processors and resources, respectively. Previous algorithms based on a resource allocation graph have O_sw(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;

fLanguage

English

Publisher

ieee

Conference_Titel

Hardware/Software Codesign, 2001. CODES 2001. Proceedings of the Ninth International Symposium on

Conference_Location

Copenhagen

Print_ISBN

1-58113-364-2

Type

conf

DOI

10.1109/HSC.2001.924654

Filename

924654