Deadlock detection and solution method of reachable graph based on petri network

Abstract

The invention relates to a reachable graph deadlock detection and solution method based on a petri network, which comprises the following steps of: 1, constructing a petri net corresponding to a codeto be detected, and constructing a reachable tree of the petri net; 2, constructing a reachable graph according to the constructed reachable tree; 3, judging whether leaf nodes exist in the reachablegraph, if yes, judging that the to-be-detected code has deadlock, turning to the next step, and if not, judging that the to-be-detected code does not have deadlock; 4, constructing a fault tree corresponding to the petri network, and obtaining a minimum cut set through fault diagnosis; and 5, judging according to the minimum cut set and the reachability graph to obtain a fault position, and improving the petri network and the to-be-detected code according to the fault position. According to the method, the activity of the system is judged through the reachability graph of the Petri net, the problem points causing inactivity of the Petri net are determined by combining the reachability graph and fault diagnosis positioning, and the deadlock problem can be effectively solved through improvement of directed arcs of the problem points.

Description

technical field [0001] The invention belongs to the field of deadlock detection methods, in particular to a deadlock detection and resolution method based on reachable graphs of petri nets. Background technique [0002] The report shows that close to 3% (6500 / 198000) of program defects are caused by deadlocks. Deadlock is one of the fatal problems of applications. Deadlock will prevent processes from using system resources and prevent other jobs from executing, resulting in reduced utilization of system resources and even system crashes. It is very important to study the cause of deadlock and solve it to improve the reliability of software. [0003] Insufficient system resources, wrong progress sequence, and unreasonable resource allocation are the three main causes of deadlocks. Deadlock detection and deadlock removal can improve system stability. At present, the research on deadlock detection at home and abroad mainly focuses on three aspects: static deadlock, dynamic de...

AI Technical Summary

Problems solved by technology

[0006] 1) The path when the program is running is part of the possible execution path, and the dynamic deadlock detection technology cannot discover the potential deadlock of the program;

[0007] 2) Static deadlock uses a conservative method to estimate variable values, lacks precise operating information, and has a high false positive rate and low false positive rate in detection results

[0008] The path is part of the executable path when the program is running, and the dynamic detection technology cannot discover the potential deadlock of the program

Images