Virtual time and its application to data race detection

Abstract:

Aiming at applying virtual time mechanism to data race detection, a model is proposed to uniformly describe different implementation forms of virtual time. We firstly establish an abstract model for a distributed execution. Based on this model, we give a unified description on virtual time’s three basic implementation forms: scalar time system, vector time system and matrix time system. Furthermore, we take vector time system and matrix time system for examples to illustrate four optimization techniques for virtual time. At last, we discuss the problems to be solved when applying virtual time to data races detection in shared-memory concurrent systems and four application examples. The model proposed in this paper unifies different implementation forms of virtual time and reduces the difficulty of applying virtual time to data race detection.