Systems and Means of Informatics

2014, Volume 24, Issue 2, pp 114-130

DATA RACE DETECTION IN JAVA PROGRAMS USING SYNCHRONIZATION CONTRACTS

D. Tsitelov
V. Trifanov

Abstract

Data race occurs in a multithreaded program when several threads simultaneously access the same memory location and at least one of them has a write access. Data races are hardly reproducible and can damage global data structures; so, research in the area of automatic race detection methods has been carried out for more than 20 years. This article focuses on the issue of improving performance of dynamic race detection in Java programs without loss of precision. Synchronization contracts - partial specifications of multithreaded behavior - are introduced for solving this problem. Using contracts allows excluding parts of application's code that are not interesting from the race detection perspective (e. g., external libraries). The paper also covers advantages and restrictions of the approach, the contracts specification language, and some implementation details.

[+] References (18)

Netzer, R., and B.Miller. 1992.What are race conditions? Some issues and formalizations. ACM Lett. Programming Languages Syst. 1(1):74-88.
Leino, K., G. Nelson, and J. Saxe. 2001. ESC/Java user's manual: SRC Technical note 2000-002. Available at: http://www.hpl.hp.com/techreports/Compaq- DEC/SRC-TN-2000-002.pdf (accessed March 28, 2014).
Engler, D., and K. Ashcraft. 2003. RacerX: Effective, static detection of race conditions and deadlocks. 19th ACM Symposium on Operating Systems Principles Proceedings. New York, NY, USA: ACM. 237-252.
Naik, M., A. Aiken, and J.Whaley. 2006. Effective static race detection for Java. 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation Proceedings. New York, NY, USA: ACM. 308-319.
Savage, S., M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. 1997. Eraser: A dynamic data race detector for multithreaded programs. ACM Trans. Comput. Syst. 15(4):391-411.
Christiaens,M., andK.Brosschere. 2001. TRaDe:Atopological approach to on-the-fly race detection in Java programs. 2001 Symposium on Java Virtual Machine Research and Technology Symposium Proceedings. Berkley, CA, USA: USENIX Association. 1:105-116.
Choi, J.,K. Lee, A. Loginov,R.O'Callahan, V. Sarkar, andM. Sridharan. 2002. Efficient and precise data-race detection for multithreaded object-oriented programs. ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation Proceedings. New York, NY, USA: ACM. 258-269.
Pozniansky, E., and A. Schuster. 2003. Efficient on-the-fly data race detection in multithreaded C++ programs. 9th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming Proceedings. New York, NY, USA: ACM. 179-190.
Elmas, T., S. Qadeer, and S. Tasiran. 2007. Goldilocks: A race and transaction-aware Java runtime. 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'07) Proceedings. New York, NY, USA: ACM. 245-255.
Flanagan, C., and S. Freund. 2009. FastTrack: Efficient and precise dynamic race detection. ACM Conference on Programming Language Design and Implementation. New York, NY, USA: ACM. 121-133.
Qi, Y., R. Das, Z. Luo, and M. Trotter. 2011. Multicore SDK: A practical and efficient data race detector for real-world applications. Software Testing, Verification and Validation (ICST) Proceedings. Los Alamitos, CA, USA: IEEE. 309-318.
ThreadSanitizer for Java: A run-time detector of data races. Available at: http:// code.google.com/p/java-thread-sanitizer/ (accessed March 28, 2014).
Lamport, L. 1978. Time, clocks and the ordering of events in a distributed system. Commun. ACM 21(7):558-565.
Java language specification. 3rd ed. Threads and locks. Happens-before order. Available at: http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.5 (accessed March 28, 2014).
Mattern, F. 1989. Virtual time and global states of distributed systems. Workshop on Parallel and Distributed Algorithms Proceedings. Eds. M. Cosnard, P. Quinton, M. Raynal, and Y. Robert. Amsterdam: Elsevier. 215-226.
Trifanov, V.Yu., and D. I. Tsitelov. 2011. Dinamicheskie sredstva obnaruzheniya gonok v parallel'nykh programmakh [Dynamic data race detectors for parallel programs]. Komp'yuternye Instrumenty v Obrazovanii [Computer Instruments in Education] 5:3-15.
Trifanov, V.Yu., and D. I. Tsitelov. 2011. Staticheskie i post-mortem sredstva obnaruzheniya gonok v parallel'nykh programmakh [Static and post-mortem data race detectors for parallel programs]. Komp'yuternye Instrumenty v Obrazovanii [Computer Instruments in Education] 6:3-13.
Package java.util.concurrent: Utility classes commonly useful in concur- rent programming. Documentation of java.util.concurrent package. Available at: http://download.oracle. com/javase/6/docs/api/java/util/concurrent/packagesummary. html (accessed March 28, 2914).

[+] About this article