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.
- 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.Google Scholar
- 2 BALASUNDARAM, V., AND KENNEDY, K. Compile-time detection of race conditions in a parallel program. In Proceedings of the 3rd International Conference on Supercomputing (Crete, Greece, June 1989), pp. 175-185. Google ScholarDigital Library
- 3 BERNSTEIN, A. J. Analysis of programs for parallel processing. IEEE Trans. Electronic Comput. EC-15 5 (Oct. 1966), 757-763.Google ScholarCross Ref
- 4 CHoI, J.-D., MILLER, B. P., AND NETZER, R. H. B. Techniques for debugging parallel programs with fiowback analysis. ACM Trans. Program. Lang. Syst. 13, 4 (Oct. 1991), 491-530. Google ScholarDigital Library
- 5 CHOI, J.-D., AND MIN, S. L. Race frontier: Reproducing data races in parallel program debugging. In Proceedings of the 3rd A CM Symposium on Principles and Practice of Parallel Programming (Williamsburg, VA, Apr. 1991), pp. 145-154. Google ScholarDigital Library
- 6 DINNING, A., AND SCHONBERG, E. The task recycling technique for detecting access anomalies on-the-fly. IBM Tech. Rep. RC 15385, Jan. 1990.Google Scholar
- 7 DINNING, A., AND SCHONBERG, E. An empirical comparison of monitoring algorithms for access anomaly detection. In Proceedings of the 2nd A CM Symposium on Principles and Practice of Parallel Programming (Seattle, WA, Mar. 1990), pp. 1-10. Google ScholarDigital Library
- 8 DINNING, A., AND SCHONBERG, E. Detecting access anomalies in programs with critical sections. In Proceedings of the ACM/ ONR Workshop on Parallel and Distributed Debugging (Santa Cruz, CA, May 1991), pp. 79-90. Google ScholarDigital Library
- 9 EMRATH, P. A., AND PADUA, D. A. Automatic detection of nondeterminacy in parallel programs. In Proceedings of the SIGPLAN/SIGOPS Workshop on Parallel and Distributed Debugging (Madison, WI, May 1988), pp. 89-99. Also appears in SIGPLAN Notices 24, 1 (Jan. 1989). Google ScholarDigital Library
- 10 EMRATH, P. A., GHOSH, S., AND PADUA, D.A. Event synchronization analysis for debugging parallel programs. In Proceedings of Supercomputing '89 (Reno, NV, Nov. 1989), pp. 580-588. Google ScholarDigital Library
- 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.Google Scholar
- 12 HooD, R., KENNEDY, K., AND MtgLLOI~-CRUMMEY, J Parallel program debugging with on-the-fly anomaly detection. In Proceedings of Supercomputing '90 (New York, NY, Nov. 1990), pp. 74-81. Google ScholarDigital Library
- 13 KARAM, G. M., STANCZYK, C. M., AND BOND, G.W. Critical races in Ada programs. IEEE Trans. Softw. Eng. 15, 11 (Nov. 1989), 1471-1480. Google ScholarDigital Library
- 14 LAMPORT, L. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Trans. Comput. C-28 9 (Sept. 1979), 690-691.Google ScholarDigital Library
- 15 LAMPORT. L. The mutual exclusion problem: Part I--A theory of interprocess communication. J. ACM 33, 2 (Apr. 1986), 313-326. Google ScholarDigital Library
- 16 MELLOR-CRUMMEY, J. M. On-the-fly detection of data races for programs with nested fork-join parallelism. In Proceedings of Supercomputing '91 (Albuquerque, NM, Nov. 1991), 24-33. Google ScholarDigital Library
- 17 MILLER, B. P., AND CHOI, J.-D. A mechanism for efficient debugging of parallel programs. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation (Atlanta, GA, June 1988), 135-144. Also appears in SIGPLAN Notices 23, 7 (July 1988). Google ScholarDigital Library
- 18 MIN, S. L., AND CHO}{, J.-D. An efficient cache-based access anomaly detection scheme. In Proceedings of the 4th International Conference on Architectural Support for Programming Languages and Operating Systems (Palo Alto, CA, Apr. 1991), 235-244. Google ScholarDigital Library
- 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.Google Scholar
- 20 NETZER, R. H. B., AND MILLER, B. P. Improving the accuracy of data race detection. In Proceedings of the 3rd A CM Symposium on Principles and Practice of Parallel Programming (Williamsburg, VA, Apr. 1991), pp. 133-144. Google ScholarDigital Library
- 21 NETZER, R. H. B. Race condition detection for debugging shared-memory parallel programs. Computer Sciences Dept. Tech. Rep. #1039 (Ph.D. Thesis), Univ. of Wisconsin-Madison, Aug. 1991. Google ScholarDigital Library
- 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.Google Scholar
- 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).Google Scholar
- 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).Google Scholar
- 25 RANDELL, B., LEE, P. A., AND TRELEAVEN, P. C. Reliability issues in computing system design. Comput. Surv. 10, 2 (June 1978), 123-165. Google ScholarDigital Library
- 26 STEELE, G.L. Making asynchronous parallelism safe for the world. In Proceedings of the 17th Annual ACM Symposium on Principles of Programming Languages (San Francisco, CA, Jan. 1990), pp. 218-231. Google ScholarDigital Library
Index Terms
- What are race conditions?: Some issues and formalizations
Recommendations
On-the-fly race detection in multi-threaded programs
PADTAD '08: Proceedings of the 6th workshop on Parallel and distributed systems: testing, analysis, and debuggingMulti-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 ...
Runtime race detection for multi-threaded C++ server applications
SE'07: Proceedings of the 25th conference on IASTED International Multi-Conference: Software EngineeringMulti-threaded programming is becoming more important, because physical limits prevent further speedup by increasing clock speed. Therefore, it is required to make use of multiple processors. Unfortunately, multi-threading is error-prone and hard to ...
Dynamic race detection for C++11
POPL '17: Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming LanguagesThe intricate rules for memory ordering and synchronisation associated with the C/C++11 memory model mean that data races can be difficult to eliminate from concurrent programs. Dynamic data race analysis can pinpoint races in large and complex ...
Comments