Efficient Deterministic Replay of Multithreaded Executions in a Managed Language Virtual Machine ∗

Shared-memory parallel programs are inherently nondeterministic, making it difficult to diagnose rare bugs and to achieve determin-istic execution. Existing multithreaded record & replay approaches have serious limitations such as relying on custom hardware, han-dling only data-race-free executions, or slowing programs by an or-der of magnitude. Furthermore, language virtual machines (VMs) such as Java VMs (JVMs) introduce various sources of nondeter-minism that thwart demonstrating deterministic replay. This paper introduces an approach for multithreaded record & replay based on tracking and reproducing shared-memory depen-dences accurately and efficiently. Building on prior work that intro-duces an efficient dependence recorder, we develop a new analysis for replaying dependences. To demonstrate multithreaded record & replay, we modify a JVM to support a new methodology that enables demonstrating and evaluating replay in the inherently non-deterministic JVM. Overall, the performance of both recorded and replayed executions compares favorably with performance reported by prior work for competing record & replay approaches