What are race conditions?: Some issues and formalizations

ABSTRACT

In shared-memory parallel programs that use explicit synchronization, race conditions result when accesses to shared memory are not properly synchronized. Race conditions are often considered to be manifestations of bugs, since their presence can cause the program to behave unexpectedly. Unfortunately, there has been little agreement in the literature as to precisely what constitutes a race condition. Two different notions have been implicitly considered: one pertaining to programs intended to be deterministic (which we call general races) and the other to nondeterministic programs containing critical sections (which we call data races). However, the differences between general races and data races have not yet been recognized. This paper examines these differences by characterizing races using a formal model and exploring their properties. We show that two variations of each type of race exist: feasible general races and data races capture the intuitive notions desired for debugging and apparent races capture less accurate notions implicitly assumed by most dynamic race detection methods. We also show that locating feasible races is an NP-hard problem, implying that only the apparent races, which are approximations to feasible races, can be detected in practice. The complexity of dynamically locating apparent races depends on the type of synchronization used by the program. Apparent races can be exhaustively located efficiently only for weak types of synchronization that are incapable of implementing mutual exclusion. This result has important implications since we argue that debugging general races requires exhaustive race detection and is inherently harder than debugging data races (which requires only partial race detection). Programs containing data races can therefore be efficiently debugged by locating certain easily identifiable races. In contrast, programs containing general races require more complex debugging techniques.

REFERENCES

• 1: ALLEN, T. R., AND PADUA, D. A. Debugging Fortran in a shared memory machine. In Proceedings of the 1987 International Conference on Parallel Processing (St. Charles, IL, Aug. 1987), pp. 721-727.
• 2: Vasanth Balasundaram , Ken Kennedy, Compile-time detection of race conditions in a parallel program, Proceedings of the 3rd international conference on Supercomputing, p.175-185, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318809]
• 3: BERNSTEIN, A. J. Analysis of programs for parallel processing. IEEE Trans. Electronic Comput. EC-15 5 (Oct. 1966), 757-763.
• 4: 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]
• 5: Jong-Deok Choi , Sang Lyul Min, Race Frontier: reproducing data races in parallel-program debugging, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.145-154, April 21-24, 1991, Williamsburg, Virginia, United States
• 6: DINNING, A., AND SCHONBERG, E. The task recycling technique for detecting access anomalies on-the-fly. IBM Tech. Rep. RC 15385, Jan. 1990.
• 7: A. Dinning , E. Schonberg, An empirical comparison of monitoring algorithms for access anomaly detection, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.1-10, March 14-16, 1990, Seattle, Washington, United States
• 8: Anne Dinning , Edith Schonberg, Detecting access anomalies in programs with critical sections, Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, p.85-96, May 20-21, 1991, Santa Cruz, California, United States
• 9: Perry A. Emrath , David A. Padua, Automatic detection of nondeterminacy in parallel programs, ACM SIGPLAN Notices, v.24 n.1, p.89-99, Jan. 1989
• 10: P. A. Emrath , S. Chosh , D. A. Padua, Event synchronization analysis for debugging parallel programs, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.580-588, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76329]
• 11: HEMLBOLD, D. P., McDOWELL, C. E., AND WANG, J.-Z. Analyzing traces with anonymous synchronization. In Proceedings of the 1990 International Conference on Parallel Processing (St. Charles, IL, Aug. 1990), pp. 70-77.
• 12: Robert Hood , Ken Kennedy , John Mellor-Crummey, Parallel program debugging with on-the-fly anomaly detection, Proceedings of the 1990 conference on Supercomputing, p.74-81, October 1990, New York, New York, United States
• 13: G. M. Karam , C. M. Stanczyk , G. W. Bond, Critical Races in Ada Programs, IEEE Transactions on Software Engineering, v.15 n.11, p.1471-1480, November 1989 [doi>10.1109/32.41338]
• 14: LAMPORT, L. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Trans. Comput. C-28 9 (Sept. 1979), 690-691.
• 15: Leslie Lamport, The mutual exclusion problem: part I—a theory of interprocess communication, Journal of the ACM (JACM), v.33 n.2, p.313-326, April 1986 [doi>10.1145/5383.5384]
• 16: John Mellor-Crummey, On-the-fly detection of data races for programs with nested fork-join parallelism, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.24-33, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125861]
• 17: B. P. Miller , Jong-Deok Choi, A mechanism for efficient debugging of parallel programs, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.135-144, June 20-24, 1988, Atlanta, Georgia, United States
• 18: Sang L. Min , Jong-Deok Choi, An efficient cache-based access anomaly detection scheme, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.235-244, April 08-11, 1991, Santa Clara, California, United States
• 19: NETZER, R. H. B., AND MILLER, B.P. On the complexity of event ordering for shared-memory parallel program executions. In Proceedings of the 1990 International Conference on Parallel Processing (St. Charles, IL, Aug. 1990), pp. II-93-II-97.
• 20: Robert H. B. Netzer , Barton P. Miller, Improving the accuracy of data race detection, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.133-144, April 21-24, 1991, Williamsburg, Virginia, United States
• 21: Robert Harry Benson Netzer, Pace condition detection for debugging shared-memory parallel programs, University of Wisconsin at Madison, Madison, WI, 1992
• 22: NETZER, R. H. B., AND MILLER, B.P. Detecting data races in parallel program executions. In Advances in Languages and Compilers for Parallel Processing, A. Nicolau, D. Gelernter, T. Gross, and D. Padua, Eds. MIT Press 1991, 109-129.
• 23: NETZER, R. H. B., AND GHOSH, S. Efficient race condition detection for shared-memory programs with post/wait synchronization. In Proceedings of the 1992 International Conference on Parallel Processing (St. Charles, IL, Aug. 1992).
• 24: NUDLER, I., AND RUDOLPH, L. Tools for the efficient development of efficient parallel programs. In Proceedings of the 1st Israeli Conference on Computer System Engineering (1988).
• 25: B. Randell , P. Lee , P. C. Treleaven, Reliability Issues in Computing System Design, ACM Computing Surveys (CSUR), v.10 n.2, p.123-165, June 1978 [doi>10.1145/356725.356729]
• 26: Guy L. Steele, Jr., Making asynchronous parallelism safe for the world, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.218-231, December 1989, San Francisco, California, United States [doi>10.1145/96709.96731]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Syntax
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures
      D.3.4 Processors
          Subjects: Parsing
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency; Mutual exclusion; Synchronization

General Terms:
Design, Languages

Keywords:
critical sections, data races, debugging, nondeterminacy, parallel programs, race conditions