research-article

Detecting and tolerating asymmetric races

Authors:

Paruj Ratanaworabhan,

Martin Burtscher,

Darko Kirovski,

Karthik PattabiramanAuthors Info & Claims

PPoPP '09: Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming

Pages 173 - 184

https://doi.org/10.1145/1504176.1504202

Published: 14 February 2009 Publication History

Abstract

This paper introduces ToleRace, a runtime system that allows programs to detect and even tolerate asymmetric data races. Asymmetric races are race conditions where one thread correctly acquires and releases a lock for a shared variable while another thread improperly accesses the same variable. ToleRace provides approximate isolation in the critical sections of lock-based parallel programs by creating a local copy of each shared variable when entering a critical section, operating on the local copies, and propagating the appropriate copies upon leaving the critical section. We start by characterizing all possible interleavings that can cause races and precisely describe the effect of ToleRace in each case. Then, we study the theoretical aspects of an oracle that knows exactly what type of interleaving has occurred. Finally, we present two software implementations of ToleRace and evaluate them on multithreaded applications from the SPLASH2 and PARSEC suites. Our implementation on top of a dynamic instrumentation tool, which works directly on executables and requires no source code modifications, incurs an overhead of a factor of two on average. Manually adding ToleRace to the source code of these applications results in an average overhead of 6.4 percent.

References

[1]

M. Abadi, T. Harris and M. Mehrara, Transactional memory with strong atomicity using off-the-shelf memory protection hardware, Proceeding of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming Raleigh, NC, 2009.

Digital Library

[2]

S. V. Adve and M. D. Hill, Weak Ordering -- A New Definition, Proceedings of the 17th Annual International Symposium on Computer Architecture, 1990, pp. 2--14.

Digital Library

[3]

S. V. Adve, M. D. Hill, B. P. Miller and R. H. B. Netzer, Detecting data races on weak memory systems, ISCA '91: Proceedings of the 18th Annual International Symposium on Computer Architecture, ACM Press, New York, NY, USA, 1991, pp. 234--243.

Digital Library

[4]

S. V. Adve, V. S. Pai, P. Ranganathan and A.-S. H., Recent Advances in Memory Consistency Models for Hardware Shared-Memory Multiprocessors, Proceedings of the IEEE, special issue on distributed shared-memory, 87 (1999), pp. 445--455.

[5]

R. Agarwal, A. Sasturkar, L. Wang and S. Stoller, Optimized Run-Time Race Detection and Atomicity Checking Using Partial Discovered Types, Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering, 2005, pp. 233--242.

Digital Library

[6]

E. D. Berger and B. G. Zorn, DieHard: probabilistic memory safety for unsafe languages, ACM SIGPLAN Notices, 41 (2006), pp. 158--168.

Digital Library

[7]

C. Bienia, S. Kumar, J. Singh and K. Li, The PARSEC Benchmark Suite: Characterization and Architectural Implications, Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques, 2008.

Digital Library

[8]

C. Blundell, C. Lewis and M. Martin, Deconstructing Transactional Semantics: The Subtleties of Atomicity, Fourth Annual Workshop on Duplicating, Deconstructing, and Debunking, Madison, Wisconsin, 2005.

[9]

H. Boehm, Foundations of the C++ Concurrency Memory Model, Proceedings of the ACM SIGPLAN 2008 Conference on Programming Language Design and Implementation, 2008.

Digital Library

[10]

R. Callahan and J.-D. Choi, Hybrid Dynamic Data Race Detection, ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, ACM Press, New York, NY, 2003.

Digital Library

[11]

T. Elmas, S. Qadeer and S. Tasiran, Goldilocks: Efficiently Computing the Happens-Before Relation Using Locksets, in K. Havelund, N. Manuel, G. Rosu and B. Wolff, eds., FATES/RV, Springer, 2006, pp. 193--208.

Digital Library

[12]

D. R. Engler and K. Ashcraft, RacerX: effective, static detection of race conditions and deadlocks, SOSP '03: Proceedings of the 20th ACM Symposium on Operating Systems Principles, 2003, pp. 237--252.

Digital Library

[13]

C. Flanagan and S. N. Freund, Detecting race conditions in large programs, PASTE '01: Proceedings of the 2001 ACM SIGPLAN--SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, ACM Press, New York, NY, USA, 2001, pp. 90--96.

Digital Library

[14]

D. Grossman, Type-safe multithreading in cyclone, TLDI '03: Proceedings of the 2003 ACM SIGPLAN International Workshop on Types in Languages Design and Implementation, ACM Press, New York, NY, USA, 2003, pp. 13--25.

Digital Library

[15]

T. A. Henzinger, R. Jhala and R. Majumdar, Race checking by context inference, PLDI '04: Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, ACM Press, New York, NY, USA, 2004, pp. 1--13.

Digital Library

[16]

M. Herlihy and J. E. B. Moss, Transactional memory: architectural support for lock-free data structures, ISCA '93: Proceedings of the 20th Annual International Symposium on Computer Architecture, ACM Press, New York, NY, USA, 1993, pp. 289--300.

Digital Library

[17]

http://developers.sun.com/sunstudio/downloads/ssx/tha/.

[18]

http://www.intel.com/cd/software/products/asmo-na/eng/286406.htm.

[19]

D. Kirovski, B. Zorn, R. Nagpal and K. Pattabiraman, An Oracle for Tolerating and Detecting Asymmetric Races, Microsoft Research Technical Report MSR-TR-2007-122, Microsoft Research, 2007.

[20]

B. Krena, Z. Letko, R. Tzoref, S. Ur and T. Vojnar, Healing Data Races On-The-Fly, Proceedings of the 2007 ACM Workshop on Parallel and Distributed Systems: Testing and Debugging, London, UK, 2007.

Digital Library

[21]

M. Kulkarni, K. Pingali, B. Walter, G. Ramanarayanan, K. Bala and P. Chew, Optimistic Parallelism Requires Abstractions, Programming Language Design and Implementation, San Diego, CA, 2007.

Digital Library

[22]

L. Lamport, How to Make a Correct Multiprocess Program Execute Correctly on a Multiprocessor, IEEE Transactions on Computers, 46 (1997), pp. 779--782.

Digital Library

[23]

S. Lu, S. Park, E. Seo and Y. Zhou, Learning from Mistakes -- A Comprehensive Study on Real World Concurrency Bug Characteristics, The 13th International Conference on Architectural Support for Programming Languages and Operating Systems, Seattle, WA, 2008.

Digital Library

[24]

S. Lu, J. Tucek, F. Qin and Y. Zhou, AVIO: detecting atomicity violations via access interleaving invariants, ASPLOS-XII: Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems, ACM Press, New York, NY, USA, 2006, pp. 37--48.

Digital Library

[25]

B. Lucia, J. Devietti, K. Strauss and L. Ceze, Atom-Aid: Detecting and Surviving Atomicity Violations, The 35th International Symposium on Computer Architecture, Beijing, China, 2008.

Digital Library

[26]

C. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi and K. Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, In Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, Chicago, IL, USA, 2005.

Digital Library

[27]

M. Naik, A. Aiken and J. Whaley, Effective static race detection for Java, PLDI '06: Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, ACM Press, New York, NY, USA, 2006, pp. 308--319.

Digital Library

[28]

S. Narayanasamy, Z. Wang, J. Tigani, A. Edwards and B. Calder, Automatically Classifying Benign and Harmful Data Races Using Replay Analysis, International Conference on Programming Language Design and Implementation, 2007.

Digital Library

[29]

E. Pozniansky and A. Schuster, Efficient on-the-fly data race detection in multithreaded C++ programs, PPoPP '03: Proceedings of the 9th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, ACM Press, New York, NY, USA, 2003, pp. 179--190.

Digital Library

[30]

S. Rajamani, G. Ramalingam, V. Ranganath and K. Vaswani, ISOLATOR: Dynamically Ensuring Isolation in Concurrent Programs, Proceedings of the Symposium on Architectural Support for Programming Languages and Operating Systems, 2009.

Digital Library

[31]

S. Savage, M. Burrows, G. Nelson, P. Sobalvarro and T. E. Anderson, Eraser: A Dynamic Data Race Detector for Multi-Threaded Programs, SOSP, 1997, pp. 27--37.

Digital Library

[32]

M. Vaziri, F. Tip and J. Dolby, Associating Synchronization Constraints with Data in an Object-Oriented Language, The 33rd Annual Symposium on Principles of Programming Languages, Charleston, SC, 2006.

Digital Library

[33]

S. Woo, M. Ohara, E. Torrie, J. Singh and A. Gupta, The SPLASH-2 Programs: Characterization and Methodological Considerations, In Proceedings of the 22nd International Symposium on Computer Architecture, Santa Margherita Ligure, Italy, 1995.

Digital Library

[34]

Y. Yu, T. Rodeheffer and W. Chen, RaceTrack: efficient detection of data race conditions via adaptive tracking, SOSP '03: Proceedings of the 20th ACM Symposium on Operating Systems Principles, Brighton, UK, 2005, pp. 221--234.

Digital Library

Cited By

Zhai JJin YChen WZheng WZhai JJin YChen WZheng W(2023)Informed Memory Access MonitoringPerformance Analysis of Parallel Applications for HPC10.1007/978-981-99-4366-1_4(73-97)Online publication date: 19-Jun-2023
https://doi.org/10.1007/978-981-99-4366-1_4
Choi EKim TJun YLee SHan M(2022)On-the-Fly Repairing of Atomicity Violations in ARINC 653 SoftwareApplied Sciences10.3390/app1204201412:4(2014)Online publication date: 15-Feb-2022
https://doi.org/10.3390/app12042014
Cheung MShe JJunus ACao L(2016)Prediction of Virality Timing Using Cascades in Social MediaACM Transactions on Multimedia Computing, Communications, and Applications10.1145/297877113:1(1-23)Online publication date: 9-Dec-2016
https://dl.acm.org/doi/10.1145/2978771
Show More Cited By

Index Terms

Detecting and tolerating asymmetric races
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging
  2. Software notations and tools
    1. General programming languages
      1. Language types
        Parallel programming languages

Recommendations

Detecting and tolerating asymmetric races
PPoPP '09

This paper introduces ToleRace, a runtime system that allows programs to detect and even tolerate asymmetric data races. Asymmetric races are race conditions where one thread correctly acquires and releases a lock for a shared variable while another ...
Efficient Runtime Detection and Toleration of Asymmetric Races

We introduce ToleRace, a runtime system that allows programs to detect and even tolerate asymmetric data races. Asymmetric races are race conditions where one thread correctly acquires and releases a lock for a shared variable while another thread ...
Hardware support for enforcing isolation in lock-based parallel programs
ICS '12: Proceedings of the 26th ACM international conference on Supercomputing

When lock-based parallel programs execute on conventional multi-core hardware, faulty software can cause hard-to-debug race conditions in critical sections that violate the contract between locks and their protected shared variables. This paper proposes ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PPoPP '09: Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming

February 2009

322 pages

ISBN:9781605583976

DOI:10.1145/1504176

General Chair:
Daniel Reed
Microsoft Research, USA
,
Program Chair:
Vivek Sarkar
Rice University, USA

ACM SIGPLAN Notices Volume 44, Issue 4
PPoPP '09
April 2009
294 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1594835
Issue’s Table of Contents

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 February 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PPoPP09

Sponsor:

PPoPP09: ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

February 14 - 18, 2009

NC, Raleigh, USA

Acceptance Rates

Overall Acceptance Rate 202 of 830 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

89
Total Citations
View Citations
657
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhai JJin YChen WZheng WZhai JJin YChen WZheng W(2023)Informed Memory Access MonitoringPerformance Analysis of Parallel Applications for HPC10.1007/978-981-99-4366-1_4(73-97)Online publication date: 19-Jun-2023
https://doi.org/10.1007/978-981-99-4366-1_4
Choi EKim TJun YLee SHan M(2022)On-the-Fly Repairing of Atomicity Violations in ARINC 653 SoftwareApplied Sciences10.3390/app1204201412:4(2014)Online publication date: 15-Feb-2022
https://doi.org/10.3390/app12042014
Cheung MShe JJunus ACao L(2016)Prediction of Virality Timing Using Cascades in Social MediaACM Transactions on Multimedia Computing, Communications, and Applications10.1145/297877113:1(1-23)Online publication date: 9-Dec-2016
https://dl.acm.org/doi/10.1145/2978771
Biswas SZhang MBond MLucia B(2015)Valor: efficient, software-only region conflict exceptionsACM SIGPLAN Notices10.1145/2858965.281429250:10(241-259)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2858965.2814292
Biswas SZhang MBond MLucia BAldrich JEugster P(2015)Valor: efficient, software-only region conflict exceptionsProceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2814270.2814292(241-259)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2814270.2814292
Zhang MAldrich JEugster P(2015)SIRe: an efficient snapshot isolation-based memory model for detecting and tolerating region conflictsCompanion Proceedings of the 2015 ACM SIGPLAN International Conference on Systems, Programming, Languages and Applications: Software for Humanity10.1145/2814189.2815371(87-88)Online publication date: 25-Oct-2015
https://dl.acm.org/doi/10.1145/2814189.2815371
Bagherzadeh MRajan HFrance RGhosh SLeavens G(2015)Panini: a concurrent programming model for solving pervasive and oblivious interferenceProceedings of the 14th International Conference on Modularity10.1145/2724525.2724568(93-108)Online publication date: 16-Mar-2015
https://dl.acm.org/doi/10.1145/2724525.2724568
Liu PTripp OZhang X(2014)FlintACM SIGPLAN Notices10.1145/2714064.266021749:10(543-560)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2714064.2660217
Liu PTripp OZhang XBlack AMillstein T(2014)FlintProceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications10.1145/2660193.2660217(543-560)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2660193.2660217
Liu PTripp OZhang CCheung SOrso AStorey M(2014)Grail: context-aware fixing of concurrency bugsProceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering10.1145/2635868.2635881(318-329)Online publication date: 11-Nov-2014
https://dl.acm.org/doi/10.1145/2635868.2635881
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten