A Featherweight Deadlock Detection and Prevention System for Production Software

Date

2017

Authors

Zhou, Jinpeng

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Deadlock is a critical problem that halts parallel programs with no further progress. Pro- grammers may need to make tremendous efforts to achieve deadlock-free, because it requires pro- found understanding of synchronization logic especially when the program is highly concurrent with many threads or processes. Existing detection tools suffer from significant recording per- formance overhead and excessive memory overhead. Furthermore, they may introduce numerous false alarms, which requires tremendous manual efforts to confirm and fix these deadlocks.

This thesis proposes a novel library-based runtime system, named as UNDEAD, for defeating resource deadlocks related to mutex locks in production software. Different from existing detection tools, UNDEAD imposes negligible runtime performance overhead (2% on average), and 14% memory overhead, based on our evaluation on PARSEC benchmarks and seven real applications, including MySQL, Apache, SQLite, Memcached, Aget, Pbzip2 and Pfscan.

Based on the detection results, UNDEAD automatically strengthens erroneous programs with the capability to prevent future occurrences of all detected deadlocks, which is similar to the ex- isting work—Dimmunix. However, UNDEAD exceeds Dimmunix with several orders of magni- tude lower performance overhead, and eliminates numerous false positives. The advantages in- cluding extremely low overhead, bounded memory/storage overhead, automatic prevention make UNDEAD an convenient, always-on detection and a "band-aid" prevention system for production software.

In this thesis, we also provide a case study, then extract some basic definitions and properties from our case study for detecting communication deadlocks related to conditional variables. Fur- thermore, We design a prototype which can be easily integrated into UNDEAD as an enhancement.

Description

This item is available only to currently enrolled UTSA students, faculty or staff. To download, navigate to Log In in the top right-hand corner of this screen, then select Log in with my UTSA ID.

Keywords

Deadlock, Deadlock Detection, Deadlock Prevention

Citation

Department

Computer Science