Optimal prediction of synchronization-preserving races
Optimal prediction of synchronization-preserving races
复制标题
同步保持竞争的最佳预测
DOI：
10.1145/3434317
复制
发表时间：
2021
影响因子：
--
通讯作者：
Viswanathan, Mahesh
中科院分区：
文献类型：
--
作者：
Mathur, Umang;Pavlogiannis, Andreas;Viswanathan, Mahesh
并发程序很难正确编写，这是出了名的，因为调度不确定性引入了难以检测和重现的细微错误。最常见的并发错误是(数据)争用，这是在并发执行内存冲突操作时发生的。因此，已经做出了相当大的努力来开发用于种族检测的有效技术。最常见的方法是动态竞争预测：给定一个并发程序的观察到的、无竞争的踪迹σ，任务是决定σ的事件是否可以被正确地重新排序为见证隐藏在σ中的竞争的踪迹σ*。在σ中，当存在见证σ*，其中同步操作(例如，获取和释放锁)以与σ中相同的顺序出现时，就会发生保持同步的竞争。这是一个宽泛的定义，严格地包含了著名的比赛前发生的概念。我们的主要结果如下。首先，我们开发了一个完善的算法来预测保持同步的比赛。对于像线程数这样的中等参数值，该算法在(N)时间和空间内运行，其中N是跟踪σ的长度。其次，我们证明了该问题有一个Ω(N/log2N)空间下界，因此我们的算法本质上是时间和空间最优的。第三，我们证明了即使只有一次两个同步操作的反向操作预测比赛也是NP完全的，甚至当被线程数量参数化时是W1困难的。因此，同步保持准确地表征了种族预测的可驯化边界，并且我们的算法对于易驯服的一侧几乎是最优的。我们的实验表明，我们的算法在实践中是快速的，而同步保持是最先进的方法经常错过的比赛的特征。
Concurrent programs are notoriously hard to write correctly, as scheduling nondeterminism introduces subtle errors that are both hard to detect and to reproduce. The most common concurrency errors are (data) races, which occur when memory-conflicting actions are executed concurrently. Consequently, considerable effort has been made towards developing efficient techniques for race detection. The most common approach is dynamic race prediction: given an observed, race-free trace σ of a concurrent program, the task is to decide whether events of σ can be correctly reordered to a trace σ*that witnesses a race hidden in σ.In this work we introduce the notion of sync(hronization)-preserving races. A sync-preserving race occurs in σ when there is a witness σ*in which synchronization operations (e.g., acquisition and release of locks) appear in the same order as in σ. This is a broad definition that strictly subsumes the famous notion of happens-before races. Our main results are as follows. First, we develop a sound and complete algorithm for predicting sync-preserving races. For moderate values of parameters like the number of threads, the algorithm runs in Õ(N) time and space, whereNis the length of the trace σ. Second, we show that the problem has a Ω(N/log2N) space lower bound, and thus our algorithm is essentially time and space optimal. Third, we show that predicting races with even just a single reversal of two sync operations is NP-complete and even W1-hard when parameterized by the number of threads. Thus, sync-preservation characterizes exactly the tractability boundary of race prediction, and our algorithm is nearly optimal for the tractable side. Our experiments show that our algorithm is fast in practice, while sync-preservation characterizes races often missed by state-of-the-art methods.
登录
查看更多内容
DOI：
10.1145/3373376.3378475
发表时间：
2020-01
期刊：
Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems
影响因子：
--
作者：
Umang Mathur;Mahesh Viswanathan
通讯作者：
Umang Mathur;Mahesh Viswanathan
多线程 Java Grande 基准测试套件
DOI：
--
发表时间：
2001
期刊：
影响因子：
--
作者：
Lorna Smith;J. M. Bull
通讯作者：
J. M. Bull
DOI：
10.1007/978-3-319-89884-1_4
发表时间：
2018
期刊：
影响因子：
--
作者：
Joaquín Aguado;Michael Mendler;Marc Pouzet;Partha S. Roop;Reinhard von Hanxleden
通讯作者：
Reinhard von Hanxleden
DOI：
--
发表时间：
2009
期刊：
International Conference on Tools and Algorithms for Construction and Analysis of Systems
影响因子：
--
作者：
Azadeh Farzan;P. Madhusudan
通讯作者：
P. Madhusudan