Efficient Race Condition Detection for Shared-Memory Programs with Post/Wait Synchronization.
Robert H. B. Netzer, Sanjoy Ghosh · 1992
Shared-memory parallel programs are often designed to be deterministic, both in their final results and intermediate states. However, debugging such programs requires a mechanism for locating race conditions or violations of the intended determinacy when they occur. This paper answers a previously open question by presenting the first precise, efficient algorithm for dynamically detecting race conditions in programs that use non-trivial synchronization. We address Post/Wait synchronization, the most powerful type of synchronization for which efficient race detection is possible. Our algorithm computes the order in which synchronization operations in the execution are guaranteed to have occurred. Using this information race conditions can be detected either postmortem or on-the-fly. Previous work has addressed either simpler types of synchronization, approximations to race detection, or a different (and easier to detect) type of race. INTRODUCTION Some parallel programs are designed t...