Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variables

ABSTRACT

Concurrent programs are notorious for containing errors that are difficult to reproduce and diagnose. A common kind of concurrency error is deadlock, which occurs when some threads are permanently blocked. This paper defines a run-time notion of potential deadlock in programs with locks, semaphores, and condition variables. Informally, an execution has potential for a deadlock if some feasible permutation of the execution results in a deadlock. Feasibility of a permutation is determined by ordering constraints amongst events in the execution. Previous work on run-time detection of potential deadlocks are for programs that use locks. This paper presents run-time algorithms to detect potential deadlocks in programs that use locks (block structured as well as non block structured), semaphores, and condition variables.

REFERENCES

• 1: R. Agarwal, L. Wang, and S. D. Stoller. Detecting potential deadlocks with static analysis and runtime monitoring. Technical Report DAR-05-25, Computer Science Department, SUNY at Stony Brook, Sept. 2005. Available at http://www.cs.sunysb.edu/.ragarwal/deadlock/.
• 2: R. Agarwal, L. Wang, and S. D. Stoller. Detecting potential deadlocks with static analysis and runtime monitoring. In Proceedings of the Parallel and Distributed Systems: Testing and Debugging (PADTAD) Track of the 2005 IBM Verification Conference volume 3875 of Lecture Notes in Computer Science pages 191--207. Springer-Verlag, 2006. Received the conference's Best Paper Award.
• 3: S. Bensalem and K. Havelund. Scalable deadlock analysis of multi-threaded programs. In Proceedings of the Parallel and Distributed Systems: Testing and Debugging (PADTAD) Track of the 2005 IBM Verification Conference Springer-Verlag, Nov. 2005.
• 4: Chandrasekhar Boyapati , Robert Lee , Martin Rinard, Ownership types for safe programming: preventing data races and deadlocks, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 5: F. Chen and G. Roşu. Predicting concurrency errors at runtime using sliced causality. Technical report, Computer Science at UIUC (No. UIUCDCS-R-2005-2660), 2005.
• 6: O. Edelstein, E. Farchi, E. Goldin, Y. Nir, G. Ratsaby, and S. Ur. Framework for testing multi-threaded Java programs. Concurrency and Computation: Practice and Experience 15(3-5) : 485--499, 2003.
• 7: Dawson Engler , Ken Ashcraft, RacerX: effective, static detection of race conditions and deadlocks, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 8: Eitan Farchi , Yarden Nir , Shmuel Ur, Concurrent Bug Patterns and How to Test Them, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.286.2, April 22-26, 2003
• 9: E. Farchi, Y. Nir-Buchbinder, and S. Ur. Cross-run lock discipline checker for java. Presentation at the 2005 IBM Verification Conference.
• 10: Cormac Flanagan , Stephen N Freund, Atomizer: a dynamic atomicity checker for multithreaded programs, Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.256-267, January 14-16, 2004, Venice, Italy
• 11: Jerry J. Harrow, Runtime Checking of Multithreaded Applications with Visual Threads, Proceedings of the 7th International SPIN Workshop on SPIN Model Checking and Software Verification, p.331-342, August 30-September 01, 2000
• 12: Klaus Havelund, Using Runtime Analysis to Guide Model Checking of Java Programs, Proceedings of the 7th International SPIN Workshop on SPIN Model Checking and Software Verification, p.245-264, August 30-September 01, 2000
• 13: D. Hovemeyer and W. Pugh. Finding concurrency bugs in java. In Proceedings of the PODC Workshop on Concurrency and Synchronization in Java Programs July 2005.
• 14: T. Li, C. S. Ellis, A. R. Lebeck, and D. J. Sorin. Pulse: A Dynamic Deadlock Detection Mechanism Using Speculative Execution. In Proceedings of the USENIX Annual Technical Conference pages 31--44, April 2005.
• 15: F. Mattern. Virtual time and global states of distributed systems. In M. Cosnard et. al, editor, Parallel and Distributed Algorithms: Proceedings of the International Workshop on Parallel and Distributed Algorithms pages 215--226. Elsevier Science Publishers B. V. , 1989.
• 16: Robert O'Callahan , Jong-Deok Choi, Hybrid dynamic data race detection, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 17: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multithreaded programs, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.391-411, Nov. 1997 [doi>10.1145/265924.265927]
• 18: Koushik Sen , Grigore Rosu , Gul Agha, Runtime safety analysis of multithreaded programs, Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, September 01-05, 2003, Helsinki, Finland
• 19: K. Sen, G. Roşu, and G. Agha. Online efficient predictive safety analysis of multithreaded programs. International Journal on Software Technology and Tools Transfer (STTT) (To Appear) 2005. Previous version appeared in TACAS'04, LNCS volumn 2988, pages 123--138.
• 20: W. Stallings. Operating Systems Prentice-Hall, 5th edition edition, 2005.
• 21: http://java.sun.com/docs/books/tutorial/essential/threads/waitAndNotify.html.
• 22: C. von Praun. Detecting Synchronization Defects in Multi-Threaded Object-Oriented Programs PhDthesis, ETH Zürich, 2004.
• 23: Christoph von Praun , Thomas R. Gross, Object race detection, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.70-82, October 14-18, 2001, Tampa Bay, FL, USA
• 24: Liqiang Wang , Scott D. Stoller, Accurate and efficient runtime detection of atomicity errors in concurrent programs, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122993]
• 25: Liqiang Wang , Scott D. Stoller, Runtime Analysis of Atomicity for Multithreaded Programs, IEEE Transactions on Software Engineering, v.32 n.2, p.93-110, February 2006 [doi>10.1109/TSE.2006.1599419]
• 26: A. Williams, W. Thies, and M. D. Ernst. Static deadlock detection for Java libraries. In Proc. 2005 European Conference on Object-Oriented Programming (ECOOP) Lecture Notes in Computer Science. Springer-Verlag, July 2005.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Reliability
      D.2.5 Testing and Debugging
          Subjects: Debugging aids; Testing tools (e.g., data generators, coverage testing)

General Terms:
Algorithms, Reliability

Keywords:
concurrent programs, deadlocks, testing