A theory of data race detection

Abstract

This paper presents a rigorous mathematical theory for the detection of data races in threaded programs. After creating a structure with precise definitions and theorems, it goes on to develop four algorithms with the goal of detecting at least one race in the situation where the history kept on previous memory accesses is limited. The algorithms demonstrate the tradeoff between the amount of access history kept and the kinds of data races that can be detected. One of these algorithms is a reformulation of a previously known algorithm; the other three are new. One of the new ones is actually used in the tool called Intel® Thread Checker.