Why Are Race Conditions So Difficult to Detect?

Detecting race conditions in a threaded program can be done at runtime, which is referred to as a dynamic detection. Or, it can be done at compile time by scanning a source program and reporting race conditions without actually running the program. This is referred to as a static detection. Unfortunately, statically detecting race conditions in programs using multiple semaphores is NP-hard (Netzer and Miller 1990), meaning an efficient solution is unlikely. If the synchronization mechanism is weaker than semaphores, an exact and efficient algorithm does exist (Netzer and Ghosh 1992); otherwise, only heuristic algorithms are available (Choi and Min 1991, and Dinning and Schonberg 1991). The problem of heuristic algorithms is that they can only report potential race conditions, meaning the detection program may report many race conditions that are actually not race conditions. However, since race condition detection is NP-hard, one never knows whether these potential race conditions are real race conditions. This is the reason that not very many useful tools exist that can pinpoint race conditions accurately. How about runtime detection? This is impractical because we need to examine every memory access and it is too late when one is detected.

References

  1. Jong-Deok Choi and Sang Lyul Min, RACE FRONTIER: Reproducing Data Races in Parallel-Program Debugging, Third ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming (PPOPP), April 1991, pp. 145-154.
  2. Anne Dinning and Edith Schonberg, Detecting Access Anomalies in Programs with Critical Sections, Proceeding of the ACM/ONR Workshop on Parallel and Distributed Debugging, May 1991, pp. 85-96.
  3. Robert H. B. Netzer and S. Ghosh, Efficient Race Condition Detection for Shared-Memory Programs with Post/Wait Synchronization, International Conference on Parallel Processing, August 1992, pp. II242-II246.
  4. Robert H. B. Netzer and Barton P. Miller, On the Complexity of Event Ordering for Shared-Memory Parallel Program Execution, International Conference on Parallel Processing, August 1990, pp. II93-II97.
  5. Robert H. B. Netzer and Barton P. Miller, What Are Race Conditions? Some Issues and Formalization, ACM Letters on Programming Languages and Systems, Vol. 1 (1992), No. 1 (March), pp. 74-88.
Materials of this section are taken from the following paper: