基于采样技术的动态混合数据竞争检测算法

Dynamic Hybrid Data Race Detection Algorithm Based on Sampling Technique

数据竞争是多线程程序并发错误的主要来源,目前已有许多静态和动态程序分析技术用于检测数据竞争,但这些检测器或者会产生巨大的检测开销,或者会漏掉许多真实的数据竞争错误。文中提出了一种基于优化的FastTrack算法和锁模式的动态混合数据竞争检测算法AsampleLock。该算法利用采样技术,监控同一时刻同时运行的来自并发线程的函数对,通过预竞争检测获得真正涉及数据竞争的内存访问对,从而减小竞争检测分析开销;为了减弱线程调度对算法相关性能的影响,AsampleLock算法采用nolock-hb关系来判断访问事件的并发关系;采用map记录所有共享变量的读写信息,并采用锁模式进行动态数据竞争检测,降低漏报率和误报率。基于上述方法实现了原型系统AsampleLock,选择基准测试集Parsec对该系统进行评估,并与FastTrack算法、LiteRace算法和Multilock-HB算法进行对比。实验结果表明,AsampleLock算法与FastTrack算法相比整体时间开销平均降低了8%;AsampleLock算法的数据竞争检测率与LiteRace算法和FastTrack算法相比分别增加了39%和27%。

Data race is a major source of concurrency bugs.Numerous static and dynamic program analysis techniques have been proposed to detect data races.However,some of detectors may cause a large detection overhead and some of detectors may miss lots of true races.In this paper,a dynamic hybrid data race detection algorithm AsampleLock is proposed,which is based on the optimized FastTrack algorithm and lock mode.It uses the sampling technique,monitoring the function pairs from concurrent threads running simultaneously at the same time,and obtains memory access pairs that really involve data race through the preliminary data race detection,thereby reducing analysis overhead of race detection.In order to reduce the influence of the algorithm on thread scheduling,AsampleLock adopts nolock-hb relation to judge the concurrency relationship of access events,adopts map to record read and write informations of shared variables,and adopts the locking patterns to perform dynamic data race detection,thereby reducing false positives and false negatives.On the basis of the above methods,this paper implements the prototype system,named AsampleLock,and chooses the Parsec benchmark suite to evaluate the race detectors.Experiments compared to FastTrack algorithm,LiteRace algorithm and Multilock-HB algorithm.The results show that the time overhead of AsampleLock algorithm is reduced by 8%compared with FastTrack algorithm.Compared with LiteRace algorithm and FastTrack algorithm,the data race detection rate of AsampleLock algorithm is increased by 39%and 27%,respectively.