Research For Type-2Fuzzy Logic Based Deadlock And Data Race Detection

Multithreading technique has been widely used in these days because of that it can improve computational efficiency, share data and save resource. However, with the growing complexity of multi-threaded programs, software programmers are facing a lot of concurrent problems, especially the deadlock and data race in program design. Many institutes at home and abroad have done a lot of researches in this area and got many achievements. At present, the approaches of detecting the deadlock and data race can be divided into static detection and dynamic detection. However, the static detection has the problem of low-precision and false positives, while the dynamic detection has the trouble of low coverage rate and omissions. Besides, both two ways do not take the uncertainty of the time sequence into consideration. And they cannot calculate the probability of deadlock and data race, and generate a priority list based on the probability.On account of these problems, we present an effective deadlock and data race detection approach based on Type-2fuzzy logic for multithread programs. The steps of our approach are as follows:(1) In order to build a rule library, the statements which can statically confirm the thread time sequence will be recorded. A time sequence graph can be generated by statically scanning the program according to the library rule.(2) We provide a pretreatment step by using static analysis to get the positions of the potential deadlocks and data races according to the TSG.(3) We use the interval type-2fuzzy logic hidden Markov model to get the probability of time sequences of dotted pairs of the potential deadlocks and data race positions in the target program.(4) We evaluate the deadlocks and data races based on the probability. This step will calculate the probability of these deadlocks and data races and generate a priority list to suggest software developers first handle the deadlocks and data races with higher probability. We implement a deadlock detection tool named DLdetector and a data race detection tool named DRdetector. We apply them to two groups of multi-threaded case studies. The experiment results show that our approach can not only improve the accuracy of the deadlock and data race detection, but also decrease the false positives. Besides, it can provide a priority list. Our approach is a new exploration in this area and a significant supplement of the related works.