Decomposition Approach of Banker's Algorithm: Design and Concurrency Analysis

Hoon OH  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E87-D   No.1   pp.183-195
Publication Date: 2004/01/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Software Systems
Keyword: 
deadlock,  concurrency,  heuristic algorithm,  decomposition,  

Full Text: PDF(1.8MB)>>
Buy this Article




Summary: 
Concurrency in the computing systems using a deadlock avoidance strategy varies largely according to the way that resource usage plan of process is used in testing the possibility of deadlocks. If a detailed resource usage plan of process is to be taken into account, the deadlock avoidance problem is known to be NP-complete. A decomposition model to manage resources is proposed, where process is logically partitioned into a number of segments each of which uses at least one resource. It is shown that one of our deadlock avoidance algorithms achieves the best concurrency among the polynomial-bounded algorithms. We also present a heuristic algorithm that achieves concurrency close to the optimal one. Finally, we analyze concurrency of various algorithms.