Deadlock Detection Based on the Parallel Graph Theory Algorithm
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.
deadlock detection parallel computing resource allocation graph loop detection SIMD-CC
Xiaorui Wang Qingxian Wang Yudong Guo Jianping Lu
China National Digital Switching System Engineering and Technological Research Center Zhengzhou,Chin Chongqing Communication Institute Chongqing,China
国际会议
杭州
英文
709-714
2013-03-22（万方平台首次上网日期，不代表论文的发表时间）