Technical Reports
HPL-2009-200
Click here for full text:
Gadara: Dynamic Deadlock Avoidance for Multithreaded Programs
Wang, Yin; Kelly, Terence; Kudlur, Manjunath; Lafortune, Stephane; Mahlke, Scott
HP Laboratories
HPL-2009-200
Keyword(s): deadlock avoidance, discrete control theory, multithreaded software, concurrent programming
Abstract: Deadlock is an increasingly pressing concern as the multicore revolution forces parallel programming upon the average programmer. Existing approaches to deadlock impose onerous burdens on developers, entail high runtime performance overheads, or offer no help for unmodified legacy code. Gadara automates dynamic deadlock avoidance for conventional multithreaded programs. It employs whole-program static analysis to model programs, and Discrete Control Theory to synthesize lightweight, decentralized, highly concurrent logic that controls them at runtime. Gadara is safe, and can be applied to legacy code with modest programmer effort. Gadara is efficient because it performs expensive deadlock-avoidance computations offline rather than online. We have implemented Gadara for C/Pthreads programs. In benchmark tests, Gadara successfully avoids injected deadlock faults, imposes negligible to modest performance overheads (at most 18%), and outperforms a software transactional memory system. Tests on a real application show that Gadara identifies and avoids both previously known and unknown deadlocks while adding performance overheads ranging from negligible to 10%.
14 Pages
Additional Publication Information: Published in Operating Systems Design & Implementation (OSDI), Dec 2008.
External Posting Date: August 21, 2009 [Fulltext]. Approved for External Publication
Internal Posting Date: August 21, 2009 [Fulltext]