Deadlock Immunity

Deadlock immunity is a property by which programs, once afflicted by a deadlock, develop resistance against future occurrences of that deadlock. We enable real applications to automatically achieve immunity against deadlock bugs involving mutex locks, semaphores, read-write locks, class initialization, and external synchronization, with no user intervention, and without changing the semantics of the applications. In other words, we provide transparent, non-intrusive immunization against deadlocks. Our deadlock immunity system, called Dimmunix, is available for Java applications, C/C++ applications using POSIX Threads, and Android OS. Java Dimmunix provides application-level immunity, i.e., deadlock immunity to individual Java applications. POSIX Threads Dimmunix provides library-level immunity, i.e., deadlock immunity to all the C/C++ applications using the POSIX Threads library. Android Dimmunix provides platform-level immunity, i.e., deadlock immunity to all the applications running within the Android OS. We also developed, on top of Java Dimmunix, a collaborative deadlock immunity framework called Communix, in which machines connected to the Internet collaborate to immunize each other against deadlocks. Since mutex locks are likely the most widely used synchronization construct, we focus on mutex deadlocks, i.e., deadlocks involving mutexes. The Java Dimmunix prototype is a complete implementation of Dimmunix; the other prototypes handle only mutex deadlocks. We heavily optimized the part of the Java Dimmunix prototype responsible for mutex deadlocks, in order to efficiently handle synchronization-intensive applications. Our prototype implementations are effective against deadlocks reported in real applications, like Limewire, MySQL JDBC, ActiveMQ, MySQL Server, and SQLite. The Java Dimmunix prototype for mutex deadlocks runs efficiently on synchronization-intensive applications, like JBoss and Eclipse, with millions of lines of code and hundreds of threads. We also show that Java Dimmunix for non-mutex deadlocks, POSIX Threads Dimmunix, Android Dimmunix, and Communix are efficient. Moreover, the Communix prototype manages to contain denial of service attacks that attempt to exploit the collaborative immunization framework.