Advanced Search
    Yu Zhen, Su Xiaohong, Qiu Jing. Dynamically Detecting Multiple Types of Deadlocks Using Lock Allocation Graphs[J]. Journal of Computer Research and Development, 2017, 54(7): 1557-1568. DOI: 10.7544/issn1000-1239.2017.20160369
    Citation: Yu Zhen, Su Xiaohong, Qiu Jing. Dynamically Detecting Multiple Types of Deadlocks Using Lock Allocation Graphs[J]. Journal of Computer Research and Development, 2017, 54(7): 1557-1568. DOI: 10.7544/issn1000-1239.2017.20160369

    Dynamically Detecting Multiple Types of Deadlocks Using Lock Allocation Graphs

    • Deadlock bugs are hard to expose, reproduce and diagnose. Once happening, they will cause increasing response time, decreasing throughput, or even crash to the target multithreaded programs. However, current deadlock detection techniques can detect only one mutex-caused deadlock at a time. In order to detect all possible deadlocks one time caused by multiple threads and multiple mutexes or rwlocks, this paper proposes the concept of multiple-type lock allocation graph (MLAG) and its construction method. Then a MLAG-based dynamic detection algorithm to detect multiple types of deadlocks is proposed. By instrumenting all lockunlock operations on mutexes and rwlocks, our method dynamically constructs and real-time updates a MLAG which reflects the synchronization state of the target program. Our method detects deadlock bugs by detecting cycles on the MALG and checking whether or not a cycle is a deadlock cycle. When a deadlock is detected, the method outputs information about that bug to assist debugging. The experimental results on benchmarks show that our method is strong in deadlock detection for successfully detecting all 13 deadlock bugs with 5 types, and has a slight impact on target programs for incurring at most 10.15% slowdown to openldap-2.2.20’s performance, and is scalable because the overhead increase gently along with an exponentially increasing number of threads.
    • loading

    Catalog

      Turn off MathJax
      Article Contents

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return