2019/09/07 by Martin Sulzmann, Sulzmann, Martin, Kai Stadtmüller +1
Computer Science · #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques #Programming Languages (cs.PL) #Software System Performance and Reliability
paper · pdf · doi:10.48550/arxiv.1909.03289
openalex publication_date 2019/09/07 · openalex created_date 2019/09/12 · openalex updated_date 2026/07/28
We consider the problem of data race prediction where the program's behavior is represented by a trace. A trace is a sequence of program events recorded during the execution of the program. We employ the schedulable happens-before relation to characterize all pairs of events that are in a race for the schedule as manifested in the trace. Compared to the classic happens-before relation, the schedulable happens-before relations properly takes care of write-read dependencies and thus avoids false positives. The challenge is to efficiently identify all (schedulable) data race pairs. We present a refined linear time vector clock algorithm to predict many of the schedulable data race pairs. We introduce a quadratic time post-processing algorithm to predict all remaining data race pairs. This improves the state of the art in the area and our experiments show that our approach scales to real-world examples. Thus, the user can systematically examine and fix all program locations that are in a race for a particular schedule.