skip to main content
10.5555/962289.962332dlproceedingsArticle/Chapter ViewAbstractPublication PagescasconConference Proceedingsconference-collections
Article
Free access

Efficient event generation for detecting races

Published: 24 October 1993 Publication History

Abstract

A data race is a situation during the execution of a parallel program where a variable is accessed concurrently by two independent threads and at least one of the accesses is a write operation. Races are a common cause of errors in parallel programs, so detecting them is an essential debugging task.A brute-force strategy used in many postmortem race detection methods involves instrumenting the program to record each inter-thread synchronization and each shared variable access in a log file. Races are then located by analyzing this event log after execution. The problem with this method is the volume of information involved: the time and space required to generate and store events can be prohibitive, even for fairly small programs.This paper describes a technique for using static program analysis to greatly reduce the number and size of events that are generated at run time. We focus on the program instrumentation phase of any post-mortem race detection method rather than actual race detection. The analysis technique involves extending a language grammar with four attributes and adding rules to each grammar production describing the interaction between these attributes. The parse tree is traversed during the compilation phase, and attribute values are computed at each node. These attribute values are then used to instrument the program far more sparsely than the brute-force strategy. A static-log file maintains the list of variables accessed between synchronization points. The result is that far fewer events, in conjuction with the static-log file, suffice to locate races.

References

[1]
Alfred V. Aho, Ravi Sethi, and Jeffery D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley Publishing Company, 1986.
[2]
Gregory R. Andrews. Synchronizing resources. ACM Transactions on Programming Languages and Systems, 3(4): 405--430, October 1981.
[3]
Gregory R. Andrews and Ronald A. Olsson. The SR Programming Language. The Benjamin/Cummings Publishing Company, Inc., 1992.
[4]
David Callahan and Jaspal Subhlok. Static analysis of low-level synchronization. In Workshop of Parallel and Distributed Debugging: Proceedings, pages 100--111, May 1988. SIGPLAN Notices, Volume 24, Number 1.
[5]
Jong-Deok Choi and Sang Lyul Min. RACE FRONTIER: Reproducing data races in parallel-program debugging. In Third ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming, pages 145--154, April 1991. SIGPLAN Notices, Volume 26, Number 7.
[6]
E. W. Dijkstra. The structure of the THE multiprogramming system. Communications of the ACM, 11(5):341--346, May 1965.
[7]
Anne Dinning and Edith Schonberg. Anempirical comparison of monitoring algorithms for access anomaly detection. In Second ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming, pages 1--10, March 1990. SIGPLAN Notices, Volume 25, Number 3.
[8]
Perry A. Emrath, Sanjoy Ghosh, and David Padula. Event synchronization analysis for debugging parallel programs. In Supercomputing '89, November 1989.
[9]
Perry A. Emrath, Sanjoy Ghosh, and David Padula. Detecting nondeterminacy in parallel programs. IEEE Software, 9(1):69--77, January 1992.
[10]
Perry A. Emrath and David A. Padua. Automatic detection of nondeterminacy in parallel programs. In Workshop of Parallel and Distributed Debugging: Proceedings, pages 89--99, May 1988. SIGPLAN Notices, Volume 24, Number 1.
[11]
Robert Hood, Ken Kennedy, and John Mellor-Crummey. Parallel program debugging with on-the-fly anomaly detection. Supercomputing '90, pages 74--81, November 1990.
[12]
Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7), July 1978.
[13]
John M. Mellor-Crummey. On-the-fly detection of data races for programs with nested fork join parallelism. In Proc. of Supercomputing '91, pages 24--33, Albuquerque, NM, November 1991.
[14]
John M. Mellor-Crummey. Compile-time support for efficient data race detection in shared-memory parallel programs. In Proc. ACM/ONR Workshop on Parallel and Distributed Debugging, San Diego, CA, May 1993.
[15]
Barton P. Miller and Jong-Deok Choi. A mechanism for efficient debugging of parallel programs. In Workshop on Parallel and Distributed Debugging: Proceedings, pages 141--150, May 1988. SIGPLAN Notices, Volume 24, Number 1.
[16]
Robert H. B. Netzer. Race Condition Detection for Debugging Shared-Memory Parallel Programs. PhD thesis, University of Wisconsin-Madison, 1991.
[17]
Robert H. B. Netzer and Barton P. Miller. Detecting data races in parallel program executions. Advances in Languages and Compilers for Parallel Processing, pages 109--129, 1991.
[18]
Robert H. B. Netzer and Barton P. Miller. Improving the accuracy of data race detection. In Third ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming, pages 133--144, April 1991. SIGPLAN Notices, Volume 26, Number 7.
[19]
Edith Schonberg. On-the-fly detection of access anomalies. In SIGPLAN Conference on Programming Language Design and Implementation, pages 285--297, June 1989. SIGPLAN Notices, Volume 24, Number 7.
[20]
Richard N. Taylor. A general-purpose algorithm for analyzing concurrent programs. Communications of the ACM, 26(5):362--376, May 1983.
[21]
Richard N. Taylor. Analysis of concurrent software by cooperative application of static and dynamic techniques. In Software Validation, pages 73--93, 1984.
[22]
Richard N. Taylor and Leon J. Osterweil. Anomaly detection in concurrent software by static data flow analysis. IEEE Transactions on Software Engineering, 6(3):265--277, May 1980.
[23]
Michael Young and Richard N. Taylor. Combining static concurrency analysis with symbolic execution. IEEE Transactions on Software Engineering, 14(10):1499--1511, October 1988.
[24]
R. Scotte Zinn. Efficient event generation for race detection. Master's thesis, University of Waterloo, June 1993.

Recommendations

Comments

Information & Contributors

Information

Published In

cover image DL Hosted proceedings
CASCON '93: Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: software engineering - Volume 1
October 1993
12 pages

Sponsors

  • IBM Centre for Advanced Studies (CAS)
  • NRC: National Research Council - Canada

Publisher

IBM Press

Publication History

Published: 24 October 1993

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 24 of 90 submissions, 27%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 129
    Total Downloads
  • Downloads (Last 12 months)27
  • Downloads (Last 6 weeks)11
Reflects downloads up to 10 Feb 2025

Other Metrics

Citations

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media