Deadlock Detection Based on the Parallel Graph Theory Algorithm

DOI

10.2991/iccsee.2013.180How to use a DOI?

Keywords

deadlock detection, parallel computing, resource allocation graph, loop detection, SIMD-CC

Abstract

Deadlock detection and release is an important means to maintain the concurrency of task in operating system, the relationship between system process and resources is usually described by means of resource allocation graph, the core of the deadlock detection is to determine whether there is a loop in the resource allocation graph and simplify the resource allocation graph. If using the traditional serial method to process the resource allocation graph, it will cause delay in the system even impossible to unlock in condition of a large number of processes exist in the system. This paper introduces the parallel processing of graph for deadlock detection, including two aspects: using the transitive closure algorithm on SIMD-CC model for loop detection in resource allocation graph, using the parallel P-BFS algorithm for Simplification of resource allocation graph. By parallel processing on the serial detection process, efficiency of the system in dealing with deadlock has been improved.

Copyright

© 2013, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Xiaorui Wang
AU  - Qingxian Wang
AU  - Yudong Guo
AU  - Jianping Lu
PY  - 2013/03
DA  - 2013/03
TI  - Deadlock Detection Based on the Parallel Graph Theory Algorithm
BT  - Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering (ICCSEE 2013)
PB  - Atlantis Press
SP  - 709
EP  - 714
SN  - 1951-6851
UR  - https://doi.org/10.2991/iccsee.2013.180
DO  - 10.2991/iccsee.2013.180
ID  - Wang2013/03
ER  -