An Algorithm For Concurrency Bug Detection Based On Adaptive Randomized Scheduling

With the development of multi-core processors,multi-threaded programs are gradually being used widely.Although multithreaded programs have great performance and high efficiency,multithreaded programs often have erroneous behavior and cause concurrency defects due to unexpected interactions between threads.These concurrency defects are often difficult to find because they typically manifest under very specific thread schedules.The traditional randomized algorithms increase the probability of exploring infrequent interleaving by making randomized scheduling and improve the efficiency of detecting concurrency defects.However,they may generate redundant trials,especially for those hard-to-detect defects,the performance is not stable.In this work,we propose an adaptive randomized scheduling algorithm(ARS),which adaptively explores the search space and detects con-currency bugs more efficiently with less efforts.Our key idea is to adaptively guide thread scheduling,and to maximize the execution sequence that triggers the possibility of concurrent defects by distance comparison,so as to detect concurrent defects in the program quickly.We performed experimental verification and analysis the results on this algorithm using real multithreaded programs.The experimental verification mainly uses Java Pathfinder to apply the adaptive random scheduling algorithm to 18 Java programs with concurrency defects,and compares it with random searching and the state-of-the-art maximal causality reduction method.The experimental results show that our algorithm is effective in detecting concurrency defects and has good efficiency and stability.