10/01/1990 09:00 AM
Computer Science
One of the fundamental problems encountered when debugging a parallel program is determining the potential race conditions in the program. A race condition exists when multiple tasks access shared data in an unconstrained order and at least one of the accesses is a write operation. The program\'s behavior can be unpredictable when race conditions are present. This paper describes techniques which automatically detect data races in parallel programs by analyzing program traces. We view a program execution as a partial ordering of events, and define which executions are consistent with a given trace. In general, it is not possible to determine which of the consistent executions occurred. Therefore we introduce the notion of ``safe orderings\'\' between events which are guaranteed to hold in every execution which is consistent with the trace. The main result of the paper is a series of algorithms which determine many of the ``safe orderings\'\'. An algorithm is also presented to distinguish unordered sequential events from concurrent events. A working trace analyzer has been implemented. The trace analyzer can report various data races in parallel programs by finding unordered pairs ofevents and variable access conflicts.
