This paper presents a practical solution for detecting data races in parallel programs. The solution consists of a combination of execution replay (RecPlay) with automatic on-the-fly data race detection. This combination enables us to perform the data race detection on an unaltered execution (almost no probe effect). Furthermore, the usage of multilevel bitmaps and snooped matrix clocks limits the amount of memory used. As the record phase of RecPlay is highly efficient, there is no need to switch it off, hereby eliminating the possibility of Heisenbugs because tracing can be left on all the time.
Although much theoretical work has been done in the field of data race detection @cite_19 @cite_25 @cite_10 @cite_17 few implementations for general systems have been proposed. Tools proposed in the past had limited capabilities: they were targeted at programs using one semaphore @cite_11 , programs using only post wait synchronisation @cite_22 or programs with nested fork-join parallelism @cite_10 @cite_21 . The tools that come closest to our data race detection mechanism, apart from @cite_26 for a proprietary system, is an on-the-fly data race detection mechanism for the CVM (Concurrent Virtual Machine) system @cite_24 . The tool only instruments the memory references to distributed shared data (about 1 unable to perform reference identification: it will return the variable that was involved in a data race, but not the instructions that are responsible for the reference.
@cite_26 @cite_22 @cite_21 @cite_17 @cite_24 @cite_19 @cite_10 @cite_25 @cite_11
2168171401 32942804 2162446957 2147506153 2170200862 2088270410
We describe an integrated approach to support debugging of nondeterministic concurrent programs. Our tool provides reproducible program behavior and incorporates mechanisms to identify synchronization bugs commonly termed data races or access anomalies. Both features are based on partially ordered event logs captured at run time. Our mechanism identifies a race condition that is guaranteed to be unaffected by other races in the considered execution. Data collection and analysis for race detection has no impact on the original computation since it is done in replay mode. The race detection and execution replay mechanisms are integrated in the MOSKITO operating system. This paper presents results on the complexity of computing event orderings for sharedmemory parallel program executions. Given a program execution, we formally define the problem of computing orderings that the execution must have exhibited or could have exhibited, and prove that computing such orderings is an intractable problem. We present a formal model of a shared-memory parallel program execution on a sequentially consistent processor, and discuss event orderings in terms of this model. Programs are considered that use fork join and either counting semaphores or event style synchronization. We define a feasible program execution to be an execution of the program that performs the same events as an observed execution, but which may exhibit different orderings among those events. Any program execution exhibiting the same data dependences among the shared data as the observed execution is feasible. We define several relations that capture the orderings present in all (or some) of these feasible program executions. The happened-before, concurrent-with, and ordered-with relations are defined to show events that execute in a certain order, that execute concurrently, or that execute in either order but not concurrently. Each of these ordering relations is defined in two ways. In the must-have sense they show the orderings that are guaranteed to be present in all feasible program executions, and in the could-have sense they show the orderings that could potentially occur in at least one feasible program execution due to timing variations. We prove that computing any of the must-have ordering relations is a co-NP-hard problem and that computing any of the could-have ordering relations is an NP-hard problem. For shared-memory systems, the most commonly assumed programmer’s model of memory is sequential consistency. The weaker models of weak ordering, release consistency with sequentially consistent synchronization operations, data-race-free-O, and data-race-free-1 provide higher performance by guaranteeing sequential consistency to only a restricted class of programs - mainly programs that do not exhibit data races. To allow programmers to use the intuition and algorithms already developed for sequentially consistent systems, it is impontant to determine when a program written for a weak system exhibits no data races. In this paper, we investigate the extension of dynamic data race detection techniques developed for sequentially consistent systems to weak systems. A potential problem is that in the presence of a data race, weak systems fail to guarantee sequential consistency and therefore dynamic techniques may not give meaningful results. However, we reason that in practice a weak system will preserve sequential consistency at least until the “first” data races since it cannot predict if a data race will occur. We formalize this condition and show that it allows data races to be dynamically detected. Further, since this condition is already obeyed by all proposed implementations of weak systems, the full performance of weak systems can be exploited. Detecting data races in shared-memory parallel programs is an important debugging problem. This paper presents a new protocol for run-time detection of data races in ex­ ecutions of shared-memory programs with nested fork-join parallelism and no other inter-thread synch ronization. This protocol has signifi cantly smaller worst-case run-time over­ head than previous techniques. The worst-case space re­ quired by our protocol when monitoring an execution of a program P is O(V N), where V is the number of shared variables in P, and N is the maximum dynamic nesting of parallel constructs in P's execution. The worst-case time required to perform any monitoring operation is O(N). We formally prove that our new protocol always reports a non­ empty subset of the data races in a monitored program ex­ ecution and describe how this property leads to an effective debugging strategy. For shared-memory parallel programs that use explicit synchronization, data race detection is an important part of debugging. A data race exists when concurrently executing sections of code access common shared variables. In programs intended to be data race free, they are sources of nondeterminism usually considered bugs. Previous methods for detecting data races in executions of parallel programs can determine when races occurred, but can report many data races that are artifacts of others and not direct manifestations of program bugs. Artifacts exist because some races can cause others and can also make false races appear real. Such artifacts can overwhelm the programmer with information irrelevant for debugging. This paper presents results showing how to identify nonartifact data races by validation and ordering. Data race validation attempts to determine which races involve events that either did execute concurrently or could have (called feasible data races). We show how each detected race can either be guaranteed feasible, or when insufficient information is available, sets of races can be identified within which at least one is guaranteed feasible. Data race ordering attempts to identify races that did not occur only as a result of others. Data races can be partitioned so that it is known whether a race in one partition may have affected a race in another. The first partitions are guaranteed to contain at least one feasible data race that is not an artifact of any kind. By combining validation and ordering, the programmer can be directed to those data races that should be investigated first for debugging. hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh Research supported in part by National Science Foundation grant CCR-8815928, Office of Naval Research grant N00014-89-J-1222, and a Digital Equipment Corporation External Research Grant. To appear in Proc. of the Third ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Williamsburg, VA, April 1991.