ASN : A dynamic barrier-based approach to confirmation of deadlocks from warnings for large-scale multithreaded programs

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

13 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number6747310
Pages (from-to)13-23
Journal / PublicationIEEE Transactions on Parallel and Distributed Systems
Volume26
Issue number1
Publication statusPublished - 1 Jan 2015

Abstract

Many large-scale multithreaded programs incur deadlock bugs. Existing deadlock warning detection techniques only report warning scenarios, which may or may not be real deadlocks. Each warning should be further verified on whether it may manifest into a real deadlock. For this purpose, a number of active randomized testing schedulers have been developed to trigger them, and yet pervious experiments show that their deadlock confirmation probability can be low. This paper presents ASN, a novel barrier-based randomized scheduler that triggers real deadlocks with high probabilities. We exploit the insights that in a confirmation run, the threads involved in a real deadlock should properly acquire one or more sets of locks prior to deadlocking. ASN automatically identifies three interesting sets of such positions. It guides the threads participating in a given warning to stay at these position sets in turn. When all the threads are staying at the last position set, ASN checks whether any deadlock that matches with the given warning has been triggered. We have evaluated ASN on 15 deadlock bugs in a suite of real-world multithreaded programs. The results show that ASN either confirms more deadlocks from the benchmark suite or triggers the same deadlocks with significantly higher probabilities than existing schedulers.

Research Area(s)

  • deadlock triggering, Debugging, large-scale multithreaded programs, randomized testing

Citation Format(s)

ASN : A dynamic barrier-based approach to confirmation of deadlocks from warnings for large-scale multithreaded programs. / Cai, Yan; Jia, Changjiang; Wu, Shangru; Zhai, Ke; Chan, Wing Kwong.

In: IEEE Transactions on Parallel and Distributed Systems, Vol. 26, No. 1, 6747310, 01.01.2015, p. 13-23.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review