Gadara: dynamic deadlock avoidance for multithreaded programs
Yin Wang, Terence Kelly, Manjunath Kudlur, Stéphane Lafortune, Scott A. Mahlke · 2008
Deadlock is an increasingly pressing concern as the multicore revolution forces parallel programming upon the average programmer. Existing approaches to dead-lock 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 pro-grams. It employs whole-program static analysis to model programs, and Discrete Control Theory to synthe-size lightweight, decentralized, highly concurrent logic that controls them at runtime. Gadara is safe, and can be applied to legacy code with modest programmer ef-fort. Gadara is efficient because it performs expensive deadlock-avoidance computations offline rather than on-line. We have implemented Gadara for C/Pthreads pro-grams. 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%. 1