Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2015, Vol. 9 Issue (4) : 524-539    https://doi.org/10.1007/s11704-015-4042-0
RESEARCH ARTICLE
Understanding and identifying latent data races cross-thread interleaving
Long ZHENG,Xiaofei LIAO(),Song WU,Xuepeng FAN,Hai JIN
Services Computing Technology and System Laboratory, Cluster and Grid Computing Laboratory, School of Computer Science and Technology, Huazhong University of Science and Technology,Wuhan 430074, China
 Download: PDF(800 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

Data races are ubiquitous in multi-threaded applications, but they are by no means easy to detect. One of the most important reasons is the complexity of thread interleavings. A volume of research has been devoted to the interleaving-insensitive detection. However, all the previous work focuses on the uniform detection (unknown to the characteristics of thread interleavings), thereby making the detection defective in either reporting false positives or suffering from prohibitive overhead. To cope with the problem above, we propose an efficient, precise, and sound step-by-step resolution based on the characteristics of thread interleavings. We first try to tease apart the categories of thread interleavings from the several typical sources arising from the lock synchronizations. We then conduct a brief study and find a new and complex pattern the previous work cannot detect. It is also revealed that the simple pattern with the majority of thread interleavings can be resolved by a simple processing to achieve a big profit for the previous reordering-based design. Our final experimental results demonstrate the effectiveness of our empiricism-based approach, and show that 51.0% of execution time and 52.3% of trace size arising from the stateof-the-art reordering technique can be saved through a quick filtering of the simple pattern with a negligible (4.45%) performance overhead introduced on-the-fly.

Keywords data race      happens-before      thread interleaving     
Corresponding Author(s): Xiaofei LIAO   
Just Accepted Date: 09 March 2015   Issue Date: 07 September 2015
 Cite this article:   
Long ZHENG,Xiaofei LIAO,Song WU, et al. Understanding and identifying latent data races cross-thread interleaving[J]. Front. Comput. Sci., 2015, 9(4): 524-539.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-015-4042-0
https://academic.hep.com.cn/fcs/EN/Y2015/V9/I4/524
1 Netzer R H B, Miller B P. What are race conditions?: some issues and formalizations. ACM Letters on Programming Languages and Systems, 1992, 1(1): 74―88
https://doi.org/10.1145/130616.130623
2 Bond M D, Coons K E, McKinley K S. Pacer: proportional detection of data races. In: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 2010, 255―268
https://doi.org/10.1145/1806596.1806626
3 Flanagan C, Freund S N. FastTrack: efficient and precise dynamic race detection. In: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 2009, 121―133
https://doi.org/10.1145/1542476.1542490
4 Narayanasamy S, Wang Z, Tigani J, Edwards A, Calder B. Automatically classifying benign and harmful data races using replay analysis. In: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 2007, 22―31
5 Leslie L. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 1978, 21(7): 558―565
https://doi.org/10.1145/359545.359563
6 Chen F, Ro?u G. Parametric and sliced causality. In: Proceedings of the 19th International Conference on Computer Aided Verification. 2007, 240―253
https://doi.org/10.1007/978-3-540-73368-3_27
7 Smaragdakis Y, Evans J, Sadowski C, Yi J, Flanagan C. Sound predictive race detection in polynomial time. In: Proceedings of the 39th annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 2012, 387―400
https://doi.org/10.1145/2103656.2103702
8 Savage S, Burrows M, Nelson G, Sobalvarro P, Anderson T. Eraser: a dynamic data race detector for multithreaded programs. ACM Transactions on Computer Systems, 1997, 15(4): 391―411
https://doi.org/10.1145/265924.265927
9 Serebryany K, Iskhodzhanov T. ThreadSanitizer: data race detection in practice. In: Proceedings of the Workshop on Binary Instrumentation and Applications. 2009, 62―71
https://doi.org/10.1145/1791194.1791203
10 Jannesari A, Kaibin B, Pankratius V, Tichy W F. Helgrind+: an efficient dynamic race detector. In: Proceedings of the IEEE International Symposium on Parallel Distributed Processing. 2009, 1―13
https://doi.org/10.1109/ipdps.2009.5160998
11 Xie X, Xue J. Acculock: accurate and efficient detection of data races. In: Proceedings of the IEEE/ACM International Symposium on Code Generation and Optimization. 2011, 201―212
https://doi.org/10.1109/cgo.2011.5764688
12 Zheng L, Liao X, He B, Wu S, Jin H. On performance debugging of unnecessary lock contentions on multicore processors: a replay-based approach. In: Proceedings of the IEEE/ACM International Symposium on Code Generation and Optimization. 2015, 56―67
https://doi.org/10.1109/cgo.2015.7054187
13 Nethercote N, Seward J. How to shadow every byte of memory used by a program. In: Proceedings of the 3rd International Conference on Virtual Execution Environments. 2007, 65―74
https://doi.org/10.1145/1254810.1254820
14 Kyu Cho H, Wang Y, Liao H, Kelly T, Lafortune S, Mahlke S. Practical lock/unlock pairing for concurrent programs. In: Proceedings of the IEEE/ACM International Symposium on Code Generation and Optimization. 2013, 1―12
15 Lu S, Park S, Seo E, Zhou Y. Learning from mistakes: a comprehensive study on real world concurrency bug characteristics. In: Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems. 2008, 329―339
https://doi.org/10.1145/1346281.1346323
16 Voung J W, Jhala R, Lerner S. Relay: static race detection on millions of lines of code. In: Proceedings of the 6th Joint Meeting of the European Software Engineering Conference and the ACM Symposium on the Foundations of Software Engineering. 2007, 205―214
https://doi.org/10.1145/1287624.1287654
17 Engler D, Ashcraft K. RacerX: effective, static detection of race conditions and deadlocks. In: Proceedings of the 19th ACM Symposium on Operating Systems Principles. 2003, 237―252
https://doi.org/10.1145/945445.945468
18 Marino D, Musuvathi M, Narayanasamy S. LiteRace: effective sampling for lightweight data-race detection. In: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 2009, 134―143
https://doi.org/10.1145/1542476.1542491
19 Patil H, Pereira C, Stallcup M, Lueck G, Cownie J. PinPlay: a framework for deterministic replay and reproducible analysis of parallel programs. In: Proceedings of the IEEE/ACMInternational Symposium on Code Generation and Optimization. 2010, 2―11
https://doi.org/10.1145/1772954.1772958
[1] Supplementary Material-Highlights in 3-page ppt
Download
[1] Yang ZHANG,Xinyu FENG. An operational happens-before memory model[J]. Front. Comput. Sci., 2016, 10(1): 54-81.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed