Hybrid dynamic data race detection
Authors:
Open Access
- 11 June 2003
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 38 (10) , 167-178
Abstract
We present a new method for dynamically detecting potential data races in multithreaded programs. Our method improves on the state of the art in accuracy, in usability, and in overhead. We improve accuracy by combining two previously known race detection techniques -- lockset-based detection and happens-before-based detection -- to obtain fewer false positives than lockset-based detection alone. We enhance usability by reporting more information about detected races than any previous dynamic detector. We reduce overhead compared to previous detectors -- particularly for large applications such as Web application servers -- by not relying on happens-before detection alone, by introducing a new optimization to discard redundant information, and by using a "two phase" approach to identify error-prone program points and then focus instrumentation on those points. We justify our claims by presenting the results of applying our tool to a range of Java programs, including the widely-used Web application servers Resin and Apache Tomcat. Our paper also presents a formalization of locksetbased and happens-before-based approaches in a common framework, allowing us to prove a "folk theorem" that happens-before detection reports fewer false positives than lockset-based detection (but can report more false negatives), and to prove that two key optimizations are correct.Keywords
This publication has 13 references indexed in Scilit:
- Efficient and precise datarace detection for multithreaded object-oriented programs2002
- A parameterized type system for race-free Java programs2001
- Guava2000
- Type-based race detection for Java2000
- Barrier inference1998
- Detecting data races in Cilk programs that use locks1998
- Detecting access anomalies in programs with critical sections1991
- Concerning the size of logical clocks in distributed systemsInformation Processing Letters, 1991
- Structure preserving reductions among convex optimization problemsJournal of Computer and System Sciences, 1980
- Time, clocks, and the ordering of events in a distributed systemCommunications of the ACM, 1978