Research On Deadlock Detection In Multi-thread Based On Petri Net

With the rapid development of multi-core processors and multi-threaded programs, the application of multi-threading technology use more widely. However, when the multi-threaded programs run in inappropriate order, it could cause a deadlock. Deadlocks can cause a system breakdown, or even software crashes. Therefore, how to effectively detect deadlocks is an important research topic in the field of software testing and development. Currently static deadlock detection methods including data flow analysis and based on concurrency model analysis. The data flow analysis could cause false retrieval due to the Conservative analysis. The model analysis could not well support how to build the multi-thread programing. And most of current studies focus on Java programs deadlock detection, the research on Posix threads is not much enough.This paper research the deadlock detection for C multi-thread programs. Based on the researches about the exsiting static programs analysis and deadlock detection algorithms, a new deadlock detection method based on Petri net model is presented, which method support two or more threads. This paper mainly discusses the following works:1) First, we preprocess the posix program using GCC compiler to obtain the CFG, the programs in Static Single Assignment form and the function dependencies, then we use the pointer alias analysis to get the possible values of function and lock pointer, which also get the function call graph of all threads.2) Secondly. We mainly discuss how to translate the multi-threaded program into Petri nets, including model the CFG, lock operations function and function call graphs into Petri net. We also optimize the functions and CFG to reduce the size of the program Petri nets. After that, we use the lockset analysis to roughly recognize the unsafe functions and use stub code to modify those functions, which makes concurrency semantics equivalent to the Petri nets model as possible.3) Thirdly, we discuss the relationship between Petri net deadlock and program deadlock. Then we define a special Petri nets to describe the operation of mutex lock, spin lock and read-writer lock in multi-thread program, and analyze the dynamic nature of this particular Petri nets. Based on this we propose a deadlock detection algorithm based on Mixed Integer Programming(MIP), which result tell us whether the program exists deadlock. It is proved that if the algorithm has a solution then the program exists deadlock.4) Finally, we use Apache, OpenLDAP, FastDFS, SQLite and Pfscan to analysis and test. The experimental results show that our method can effectively detect deadlock in those programs. Compared with the previous studies, our method take smaller time and suitable for handling large-scale multi-threaded programs.