For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Decomposition Approach of Banker's Algorithm: Design and Concurrency Analysis
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2004/01/01
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Software Systems
deadlock, concurrency, heuristic algorithm, decomposition,
Full Text: PDF(1.8MB)>>
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.