Stable deterministic multithreading through schedule memoization
Heming Cui, Jingyue Wu, Chia-Che Tsai, Junfeng Yang · 2010
Adeterministicmultithreading(DMT)systemeliminates nondeterminism in thread scheduling, simplifying the development of multithreaded programs. However, existing DMT systems are unstable; they may force a program to (ad)venture into vastly different schedules even for slightly different inputs or execution environments, defeating many benefits of determinism. Moreover, few existingDMTsystemsworkwithserverprogramswhose inputs arrive continuously and nondeterministically. TERN is a stable DMT system. The key novelty in TERN is the idea of schedule memoization that memoizes past working schedules and reuses them on future inputs,makingprogrambehaviorsstableacrossdifferent inputs. A second novelty in TERN is the idea of windowingthatextendsschedulememoizationtoserverprograms by splitting continuous request streams into windows of requests. Our TERN implementation runs on Linux. It operates as user-space schedulers, requiring no changes to theOS and only afew lines of changes tothe application programs. We evaluated TERN on a diverse set of 14 programs (e.g., Apache and MySQL) with real and synthetic workloads. Our results show that TERN is easy to use, makes programs more deterministic and stable, and has reasonable overhead. 1