On-the-fly race detection in multi-threaded programs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

On-the-fly race detection in multi-threaded programs

Full text

Pdf (1.89 MB)

Source

International Symposium on Software Testing and Analysis archive
Proceedings of the 6th workshop on Parallel and distributed systems: testing, analysis, and debugging table of contents

Seattle, Washington

Article No.: 6

Year of Publication: 2008

ISBN:978-1-60558-052-4

Authors

Ali Jannesari	University of Karlsruhe, Karlsruhe, Germany
Walter F. Tichy	University of Karlsruhe, Karlsruhe, Germany

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 154, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1390841.1390847 What is a DOI?

ABSTRACT

Multi-core chips enable parallel processing for general purpose applications. Unfortunately, parallel programs may contain synchronization defects. Such defects are difficult to detect due to nondeterministic interleavings of parallel threads. Current tools for detecting these defects produce numerous false alarms, thereby concealing the true defects. This paper describes an extended race detection technique based on a combination of lockset analysis and the happens-before relation. The approach provides more accurate warnings and significantly reduces the number of false positives, while limiting the number of false negatives. The technique is implemented in Helgrind⁺, an extension of the open source dynamic race detector Helgrind. Experimental results with several applications and benchmarks demonstrate a significant reduction in false alarms at a moderate runtime increase.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	The SPLASH-2 Programs: Characterization and Methodological Considerations, Santa Margherita Ligure, Italy, 1995.
	2	C. Bienia, S. Kumar, J. P. Singh, and K. Li. The PARSEC benchmark suite: Characterization and architectural implications. Technical report, January 2008.
	3	Jong-Deok Choi , Barton P. Miller , Robert H. B. Netzer, Techniques for debugging parallel programs with flowback analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.491-530, Oct. 1991 [doi>10.1145/115372.115324]
	4	Jong-Deok Choi , Sang Lyul Min, Race Frontier: reproducing data races in parallel-program debugging, ACM SIGPLAN Notices, v.26 n.7, p.145-154, July 1991
	5	Mark Christiaens , Koen De Bosschere, TRaDe, a topological approach to on-the-fly race detection in java programs, Proceedings of the 2001 Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.15-15, April 23-24, 2001, Monterey, California
	6	Edmund M. Clarke , Orna Grumberg , Somesh Jha , Yuan Lu , Helmut Veith, Counterexample-Guided Abstraction Refinement, Proceedings of the 12th International Conference on Computer Aided Verification, p.154-169, July 15-19, 2000
	7	Anne Dinning , Edith Schonberg, Detecting access anomalies in programs with critical sections, ACM SIGPLAN Notices, v.26 n.12, p.85-96, Dec. 1991
	8	Orit Edelstein , Eitan Farchi , Yarden Nir , Gil Ratsaby , Shmuel Ur, Multithreaded Java program test generation, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.181, June 2001, Palo Alto, California, United States [doi>10.1145/376656.376848]
	9	Dawson Engler , Ken Ashcraft, RacerX: effective, static detection of race conditions and deadlocks, ACM SIGOPS Operating Systems Review, v.37 n.5, December 2003
	10	J. Gilchrist. Parallel bzip2 (pbzip2):data compression software, 2007.
	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	Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
	13	Shan Lu , Joseph Tucek , Feng Qin , Yuanyuan Zhou, AVIO: Detecting Atomicity Violations via Access-Interleaving Invariants, IEEE Micro, v.27 n.1, p.26-35, January 2007 [doi>10.1109/MM.2007.5]
	14	F. Mattern. Virtual time and global states of distributed systems. In Parallel and Distributed Algorithms: proceedings of the International Workshop on Parallel and Distributed Algorithms.
	15	N. Nethercote. Dynamic Binary Analysis and Instrumentation. PhD thesis, University of Cambridge, UK, 2004.
	16	N. Nethercote and J. Seward. Valgrind: A program supervision framework. 2003.
	17	Nicholas Nethercote , Julian Seward, Valgrind: a framework for heavyweight dynamic binary instrumentation, ACM SIGPLAN Notices, v.42 n.6, June 2007
	18	Robert H. B. Netzer , Barton P. Miller, What are race conditions?: Some issues and formalizations, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.74-88, March 1992 [doi>10.1145/130616.130623]
	19	Hiroyasu Nishiyama, Detecting data races using dynamic escape analysis based on read barrier, Proceedings of the 3rd conference on Virtual Machine Research And Technology Symposium, p.10-10, May 06-07, 2004, San Jose, California
	20	Robert O'Callahan , Jong-Deok Choi, Hybrid dynamic data race detection, ACM SIGPLAN Notices, v.38 n.10, October 2003
	21	Victor Pankratius , Christoph Schaefer , Ali Jannesari , Walter F. Tichy, Software engineering for multicore systems: an experience report, Proceedings of the 1st international workshop on Multicore software engineering, May 11-11, 2008, Leipzig, Germany [doi>10.1145/1370082.1370096]
	22	Eli Pozniansky , Assaf Schuster, MultiRace: efficient on-the-fly data race detection in multithreaded C++ programs: Research Articles, Concurrency and Computation: Practice & Experience, v.19 n.3, p.327-340, March 2007 [doi>10.1002/cpe.v19:3]
	23	Brad Richards , James R. Larus, Protocol-based data-race detection, Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, p.40-47, August 03-04, 1998, Welches, Oregon, United States [doi>10.1145/281035.281040]
	24	Michiel Ronsse , Koen De Bosschere, RecPlay: a fully integrated practical record/replay system, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.133-152, May 1999 [doi>10.1145/312203.312214]
	25	Paul Sack , Brian E. Bliss , Zhiqiang Ma , Paul Petersen , Josep Torrellas, Accurate and efficient filtering for the Intel thread checker race detector, Proceedings of the 1st workshop on Architectural and system support for improving software dependability, p.34-41, October 21-21, 2006, San Jose, California [doi>10.1145/1181309.1181315]
	26	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]
	27	J. Seward. bzip2: A free data compressor, 2007.
	28	Valgrind-project. Helgrind: a data-race detector, 2007.
	29	Christoph von Praun , Thomas R. Gross, Object race detection, ACM SIGPLAN Notices, v.36 n.11, p.70-82, 11/01/2001
	30	Yuan Yu , Tom Rodeheffer , Wei Chen, RaceTrack: efficient detection of data race conditions via adaptive tracking, ACM SIGOPS Operating Systems Review, v.39 n.5, December 2005