Efficient deterministic multithreading through schedule relaxation

摘要: Deterministic multithreading (DMT) eliminates many pernicious software problems caused by nondeterminism. It works constraining a program to repeat the same thread interleavings, or schedules, when given input. Despite much recent research, it remains an open challenge build both deterministic and efficient DMT systems for general programs on commodity hardware. To deterministically resolve data race, system must enforce schedule of shared memory accesses, mem-schedule, which can incur prohibitive overhead. By using schedules consisting only synchronization operations, sync-schedule, this overhead be avoided. However, sync-schedule is race-free programs, but most have races. Our key insight that races tend occur within minor portions execution, dominant majority execution still race-free. Thus, we resort mem-schedule "racy" otherwise, combining efficiency sync-schedules determinism mem-schedules. We call these combined hybrid schedules. Based insight, built Peregrine, system. When first runs input, Peregrine records trace. then relaxes trace into reuses future compatible inputs efficiently deterministically. further improves with two new techniques: determinism-preserving slicing generalize more while preserving determinism, schedule-guided simplification precisely analyze according specific schedule. evaluation diverse set shows efficient, frequently reuse half evaluated programs.