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

doi:10.11896/jsjkx.190700079

计算机科学 ›› 2020, Vol. 47 ›› Issue (10): 315-321.doi: 10.11896/jsjkx.190700079

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

李梦珂, 郑秋生, 王磊

中原工学院前沿信息技术研究院郑州450007
河南省网络舆情监测与智能分析重点实验室郑州450007

收稿日期:2019-07-10 修回日期:2019-12-09 出版日期:2020-10-15 发布日期:2020-10-16
通讯作者: 王磊(wl1167@163.com)
作者简介:2017007063@zzti.edu.cn
基金资助:
国家重点研发计划项目(2016QY07X1503,162300410190)

Dynamic Hybrid Data Race Detection Algorithm Based on Sampling Technique

LI Meng-ke, ZHENG Qiu-sheng, WANG Lei

Research Institute of Front Information Technology,Zhongyuan University of Technology,Zhengzhou 450007,ChinaHenan Key Laboratory on Public Opinion Intelligent Analysis,Zhengzhou 450007,China

Received:2019-07-10 Revised:2019-12-09 Online:2020-10-15 Published:2020-10-16
About author:LI Meng-ke,born in 1996,postgraduate.Her main research interests include high performance computing and so on.
WANG Lei,born in 1977,professor,master supervisor.His main research interests include research and development of high performance computing and domestic independent and controllable basic software.
Supported by:
National Key Research and Development Project (2016QY07X1503,162300410190)

摘要/Abstract

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

关键词: 多线程程序, 数据竞争检测, 锁模式, 预竞争检测

Abstract: 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.

Key words: Data race detection, Locking patterns, Multithreaded program, Preliminary data race

中图分类号:

TP311.53

李梦珂, 郑秋生, 王磊. 基于采样技术的动态混合数据竞争检测算法[J]. 计算机科学, 2020, 47(10): 315-321. https://doi.org/10.11896/jsjkx.190700079

LI Meng-ke, ZHENG Qiu-sheng, WANG Lei. Dynamic Hybrid Data Race Detection Algorithm Based on Sampling Technique[J]. Computer Science, 2020, 47(10): 315-321. https://doi.org/10.11896/jsjkx.190700079

参考文献

[1]LU S W,ZHOU Y.A study of interleaving co-verage criteria[C]//The 6th Joint Meeting on European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering:Companion Papers.ACM,2007:533-536.
[2]LU S.How to deal with concurrent bugs in multithreaded programs[J].Communication of China Computer Society,2013,9(2):20-27.
[3]LU S,PARK E,SEO,et al.Learning from mistake-s:A compre-hensive study on real world concurrency bug characteristics[C]//Proc. ASPLOS.2008:329-339.
[4]JACKSON J.Nasdaq’s Facebook glitch came from ‘RaceConditions’[EB/OL].[2012-03-24].https://www.computerworld.com/article/2504676/nasdaq-s-facebook-glitch-came-from--race-conditions-.html.
[5]JIMENEZ M,PAPADAKIS M,LE TRAON Y.Vulnerabilityprediction models:A case study on the Linux kernel[C]//2016 IEEE 16th International Working Conference on Source Code Analysis and Manipulation(SCAM).2016:1-10.
[6]ENGLER D,ASHCRAFT K.RacerX:effective,static detection of race conditions and deadlocks[J].ACM SIGOPS Operating Systems Review,2003,37(5):237-252.
[7]VOUNG J,JHALA R,LERNER S.RELAY:Static Race Detection on Millions of Lines of Code[C]//Joint Meeting of the European Software Engineering Conference & the ACM Sigsoft Symposium on the Foundations of Software Engineering.ACM,2007:205-214.
[8]POZNIANSKI E,SCHUSTER A.Efficient On-the-Fly DataRace Detection in Multithreaded C++ Programs[C]//International Parallel & Distributed Processing Symposium.IEEE,2003:179-190.
[9]CORMAC F S N F.FastTrack:Efficient and precise dynamicrace detection[J].ACM SIGPLAN Notices,2009,44(6):121-133.
[10]CAI Y,CHANW K.LOFT:Redundant Synchronization Event Removal for Data Race Detection[C]//IEEE International Symposium on Software Reliability Engineering.IEEE,2011:160-169.
[11]YANG Z,YU Z,SU X,et al.RaceTracker:Effec-tive and efficient detection of data races[C]//2016 17th IEEE/ACIS International Conference on Software Engineering,Artificial Intelligence,Networking and Parallel/Distributed Computing (SNPD).IEEE Computer Society,2016:293-300.
[12]XIE X,XUE J,ZHANG J.Acculock:Accurate and Efficient Detection of Data Races[C]//IEEE/ACM International Sympos-ium on Code Generation & Optimization.IEEE,2011:201-212.
[13]XIE X,XUE J,ZHANG J.Acculock:accurate and efficient de-tection of data races[J].Software:Practice and Experience,2013,43(5):543-576.
[14]YU M,YOO S K,BAED H.SimpleLock:Fast and Accurate Hybrid Data Race Detector[C]//International Conference onPa-rallel & Distributed Computing.IEEE,2014:50-56.
[15]YU M,LEE J,BAE D,et al.AdaptiveLock:Efficient Hybrid Data Race Detection Based on Real-World Locking Patterns[J].International Journal of Parallel Programming,2019,47(7):805-837.
[16]BIENIA C.Thesis:Benchmarking modern multiprocessors[D].Princeton University,2011.
[17]LAMPORT L.Time,clocks,and the orde-ring of events in a distributed system[J].Communications of the ACM,1978,21(7):558-565.
[18]GUO Y,CAI Y,YANG Z.AtexRace:across thread and execution sampling for in house race detection[C]//Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering.ACM,2017:315-325.
[19]MARINO D,MUSUVATHI M,NARAYANASAMY S.LiteRace:effective sampling for lightweight data race detection[C]//ACM Sigplan Notices.ACM,2009:134-143.
[20]BOND M D,COONS K E,MCKINLEY K S.PACER:proportional detection of data races[C]//ACM Sigplan Notices.ACM,2010:255-268.
[21]YU M,BAE D H.SimpleLock+:fast and accurate hybrid data race detection[J].The Computer Journal,2016,59(6):793-809.
[22]LUK C K,COHN R S,MUTH R,et al.Pin:Building Customized Program Analysis Tools with Dynamic Instrumentation[C]//ACM Sigplan Notices.ACM,2005:190-200.
[23]ZHANG Y,LIANG Y N,ZHANG D W,et al.An Effective Approach of Detecting Data Race in Concurrent Programs[J].Journal of Computer Applications,2019,39(1):67-71.
[24]WANG X F.Research on Dynamic Data Race Detection[D].Wuhan:Huazhong University of Science And Technology,2016.
[25]YU J,NARAYANASAMY S,PEREIRA C,et al.Maple:ACoverage-Driven Testing Tool for Multithreaded Programs[C]//Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications.ACM,2012:485-502.
[26]YU M,PARK S M,CHUN I,et al.Experimen-tal Performance Comparison of Dynamic Dat-a RaceDetectionTechniques[J].ETRI Journal,2017,39(1):124-134.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

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

Dynamic Hybrid Data Race Detection Algorithm Based on Sampling Technique

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

Metrics

本文评价

推荐阅读 0

[1]	杨璐,余守文,严建峰. 基于二型模糊逻辑的多线程数据竞争检测方法研究 Type-2 Fuzzy Logic Based Multi-threaded Data Race Detection 计算机科学, 2017, 44(12): 135-143. https://doi.org/10.11896/j.issn.1002-137X.2017.12.027
[2]	闫洁，徐恒阳，安虹，刘玉，王耀彬. Pview:一种基于PMU的支持并行程序性能分析的新方法 Pview: A Novel Implementation of Fundamental Supports for Parallel Programs Performance Monitoring Based on PMU 计算机科学, 2011, 38(2): 288-292.