Research On Concurrency Bug Detection And Avoidance

The prevalent multi-core architecture today brings ubiquitous potential of parallel.To benefit from the parallel power of hardware,concurrent programming is becoming the mainstream programming model.Comparing with sequential programs,concurrent programs are characterized by concurrency and non-determinism.These two natures make concurrent programs prone to suffering from concurrency bugs which are hard to expose,detect,debug and repair.Under traditional testing,many concurrency bugs are not detected and still lie in programs until manifesting themselves in production runs,which may lead to grave accidents or financial losses.To remove the threaten of concurrency bugs to program correctness,two contrary measures can be taken: one tries to quickly expose concurrency bugs and accurately detect them with identification of their ingredients to benefit debugging and fixing,while the other allows the existence of concurrency bugs and attempts to avoid them dynamically by intentionally scheduling execution flows.The former focuses on bug detection,while the latter focuses on bug avoidance.Therefore,researching on accurate detection and effective avoidance of concurrency bugs has great significance in theory and application for enhancing the quality and runtime reliability of concurrent programs.In this dissertation,firstly we classify concurrency bugs into 4 categories,namely deadlock,data race,atomicity violation and order violation,and explore correlations among them.Secondly for each category of concurrency bugs,we make analyses,comparisons and summarizations on previous researches about how to expose,detect and avoid them.From these investigations,we draw 4 scientific questions which need further study:how to strengthen the ability of deadlock detection,how to reduce the false positive and negative rates of data race detection,how to enhance the ability and efficiency of deadlock avoidance,and how to strengthen the ability of general concurrency bug avoidance meanwhile decreasing its human involvement degree.At last,we conduct intensive study on these 4 questions and give research schema,implementation step and experimental result to each of them.Current deadlock detection techniques have weak detection ability for they can only detect mutex deadlocks.To detect all possible 5 kinds of deadlocks caused by mutexes or rwlocks,a mixed deadlock detection method based on lock allocation graphs is proposed.This method first introduces the concept of mixed deadlocks,and gives the definition and construction means of Multiple-type Lock Allocation Graph(MLAG).Then by instrumenting all lock/unlock operations on mutexes and rwlocks,this method dynamically constructs and real-time updates a MLAG to reflect the synchronization state of the target program.At last the method detects deadlock bugs by detecting cycles on the MLAG and checking whether or not a cycle is a deadlock cycle.If a deadlock is detected,the method outputs information about that bug to assist debugging.Experimental results show that this method is strong in detection ability,incurs only slight overhead to target programs and scales well with increasing number of threads.Current static race detection techniques have high false positive rate while current dynamic race detection techniques have high false negative rate.To decrease both false positive rate and false negative rate,a combined static and dynamic data race detection method is proposed.Firstly by static analysis,this method founds out all potential racy access pairs and identifies all potential customized synchronization primitives.Then by dynamic analysis,it monitors behaviors of the target program at racy accesses and controls thread scheduling to try to manifest races.It also integrates lockset algorithm and happens-before algorithm to verify covered races in a detection way.At last the method dynamically confirms real synchronization primitives and use the information to remove false and benign races.Experimental results show that this method has high accuracy,low false positive/negative rates as well as overhead and scalability not worse than existing methods.Current dynamic techniques for deadlock avoidance have four main drawbacks: limited ability,passive or blind avoiding strategies,large performance overhead and no guarantee of correctness of target programs.To solve these problems,a combined static and dynamic avoidance method based on future lockset is proposed.The key idea is that,for a lock operation,if none of its future locks are occupied,then it makes sure that executing this lock operation won't lead the current thread to trap into a deadlock state.The future lockset of a lock operation is a set of locks that will be requested by the current thread before the corresponding unlock operation is reached.Firstly,this method computes lock effects for lock operations and functions call operations and inserts them before and after the corresponding operations.Then it dynamically intercepts lock operations and computes its future lockset using lock effects inserted by static analysis.It permits a lock operation to be execute if and only if all locks of its lockset are not held by any other threads.Otherwise,the lock operation waits until the condition is satisfied.Experimental results show that this method can efficiently avoid multiple types of deadlocks in an active,intelligent,scalable and correctness-guaranteed way.Current general concurrency bug avoidance techniques has weak avoidance ability and needs high degree of human involvement.To solve these problems,a software transactional memory based concurrency bug avoidance method is proposed.It can automatically transactionalize target programs to equip them with avoidance ability against deadlocks,data races,atomicity violations and order violations.It can also supports transactional I/O and handle condition variables properly.By turning threads into processes,leveraging virtual memory protection and customizing memory allocation/deallocation,this method makes memory transactional.By intercepting inter-thread operations and designating codes among them as transactions in each thread,this method transparently makes target programs transactionalized.By saving/restoring stack frames and CPU registers on beginning/aborting a transaction,this method makes execution revocable.By maintaining virtual file systems and redirecting I/O operations onto them,this method makes I/O transactional.By converting lock/unlock operations to no-ops,customizing condition variable operations and committing memory as well as I/O changes transactionally,this method makes deadlocks,data races,atomicity violations and order violations impossible.Experimental results show that this method is strong in avoidance ability and needs no human interference.However,it may incurs larger overhead to the target program.In conclusion,this thesis provides new ideas and methods for solving the following scientific questions: how to strengthen the ability of deadlock detection,how to reduce the false positive and negative rates of data race detection,how to enhance the ability and efficiency of deadlock avoidance,and how to strengthen the ability of general concurrency bug avoidance meanwhile decreasing its human involvement degree.