An Efficient and Flexible Deterministic Framework for Multithreaded Programs

• Published in: Journal of computer science and technology 2015, Vol.30 (1), p.42-56
• Main Author: 卢凯 周旭 王小平 Tom Bergan 陈沉
• Format: Article
• Language: English
• Subjects: Artificial Intelligence; Computer Science; Computer simulation; Consistency; Data Structures and Information Theory; Debugging; Determinism; DMT系统; Information Systems Applications (incl.Internet); Libraries; Locks; Mathematical models; Regular Paper; Replay systems; Software; Software Engineering; State of the art; Studies; Theory of Computation; 一致性模型; 内存; 多线程程序; 框架; 重放系统; 非确定性系统
• ISSN: 1000-9000; 1860-4749
• DOI: 10.1007/s11390-015-1503-8

Determinism is very useful to multithreaded programs in debugging, testing, etc. Many deterministic ap- proaches have been proposed, such as deterministic multithreading （DMT） and deterministic replay. However, these sys- tems either are inefficient or target a single purpose, which is not flexible. In this paper, we propose an efficient and flexible deterministic framework for multithreaded programs. Our framework implements determinism in two steps： relaxed determinism and strong determinism. Relaxed determinism solves data races eificiently by using a proper weak memory consistency model. After that, we implement strong determinism by solving lock contentions deterministically. Since we can apply different approaches for these two steps independently, our framework provides a spectrum of deterministic choices, including nondeterministic system （fast）, weak deterministic system （fast and conditionally deterministic）, DMT system, and deternfinistic replay system. Our evaluation shows that the DMT configuration of this framework could even outperform a state-of-the-art DMT system.