Gadara: dynamic deadlock avoidance for multithreaded programs
Yin Wang, Terence Kelly, Manjunath Kudlur et al. · 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
Cited by 128 works. doi:10.5555/1855741.1855761
Authors
References
- Petri nets: Properties, analysis and applications
- Cooperating Sequential Processes
- Model checking
- Solution of a problem in concurrent programming control
- Model Checking
- Introduction to Discrete Event Systems
- Additional comments on a problem in concurrent programming control
- Prevention of system deadlocks
- Eraser
- Extended static checking for Java