Abstract:

Atomicity violation is one of the concurrency bugs in concurrency software development. Since the interaction of the threads is random, if the corresponding synchronization is not used, it is very likely that the atomic violation will occur. Aiming at the problems that the application traces of the existing off-line atomicity violation detection are large and redundant, and the running speed of detection algorithm is slow, this paper proposes a concurrency detection algorithm for two kinds of atomicity violations based on thread communication invariant. Firstly, the algorithm extracts the original traces from the program and removes the redundancy, then uses the hash table based on the unordered map to classify the traces. Secondly, the algorithm uses the stack to extract the thread invariant which can tag thread communication, and uses the multiprocess technology to realize the concurrency of the algorithm. At last, the efficiency and effectiveness of the bug detection algorithm are analyzed by experiment.

Key words: concurrency bug detection, atomicity violation, invariant, concurrency algorithm

摘要：

原子性违例错误是并发软件开发中多发的并发错误之一，由于并发程序运行时线程的交互是随机的，若没有相应的同步措施，极有可能导致原子性违例错误的发生。针对现有的离线原子性违例错误检测算法踪迹记录大、冗余多和运行速度较慢等问题，对于两类特定的原子性违例错误提出了一种基于交互不变量的原子性违例错误并发检测算法。该算法首先提取程序的原始踪迹并去除冗余，并利用基于无序映射的散列表对踪迹进行分类；然后用栈提取的线程交互不变量标记线程交互，并利用多进程技术实现算法的并发；最后通过实验比较和分析了错误检测算法的效率和有效性。

关键词: 并发错误检测, 原子性违例, 不变量, 并发算法