research-article

Detecting and tolerating asymmetric races

Authors:

Paruj Ratanaworabhan,

Martin Burtscher,

Darko Kirovski,

Karthik PattabiramanAuthors Info & Claims

ACM SIGPLAN Notices, Volume 44, Issue 4

Pages 173 - 184

https://doi.org/10.1145/1594835.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

Didehban MShrivastava A(2018)A Compiler Technique for Processor-Wide Protection From Soft Errors in Multithreaded EnvironmentsIEEE Transactions on Reliability10.1109/TR.2018.279309867:1(249-263)Online publication date: Mar-2018
https://doi.org/10.1109/TR.2018.2793098
Fu HWang ZChen XFan X(2018)A systematic survey on automated concurrency bug detection, exposing, avoidance, and fixing techniquesSoftware Quality Journal10.1007/s11219-017-9385-326:3(855-889)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s11219-017-9385-3
Tchamgoue GKim KJun Y(2016)EventHealerJournal of Systems and Software10.1016/j.jss.2016.02.051118:C(208-220)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.jss.2016.02.051
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: Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming

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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

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

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

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 February 2009

Published in SIGPLAN Volume 44, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

89
Total Citations
View Citations
657
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Didehban MShrivastava A(2018)A Compiler Technique for Processor-Wide Protection From Soft Errors in Multithreaded EnvironmentsIEEE Transactions on Reliability10.1109/TR.2018.279309867:1(249-263)Online publication date: Mar-2018
https://doi.org/10.1109/TR.2018.2793098
Fu HWang ZChen XFan X(2018)A systematic survey on automated concurrency bug detection, exposing, avoidance, and fixing techniquesSoftware Quality Journal10.1007/s11219-017-9385-326:3(855-889)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s11219-017-9385-3
Tchamgoue GKim KJun Y(2016)EventHealerJournal of Systems and Software10.1016/j.jss.2016.02.051118:C(208-220)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.jss.2016.02.051
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
Kim YSong SJun Y(2014)VORDInternational Journal of Parallel Programming10.1007/s10766-013-0257-642:6(900-930)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1007/s10766-013-0257-6
Roy AHand SHarris T(2012)Weak atomicity for the x86 memory consistency modelJournal of Parallel and Distributed Computing10.1016/j.jpdc.2012.06.00172:10(1306-1317)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1016/j.jpdc.2012.06.001
Chen QWang LGuo PHuang H(2011)Analyzing Concurrent Programs Title for Potential Programming ErrorsModern Software Engineering Concepts and Practices10.4018/978-1-60960-215-4.ch016(380-415)Online publication date: 2011
https://doi.org/10.4018/978-1-60960-215-4.ch016
Yu JNarayanasamy S(2010)Tolerating Concurrency Bugs Using Transactions as LifeguardsProceedings of the 2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture10.1109/MICRO.2010.56(263-274)Online publication date: 4-Dec-2010
https://dl.acm.org/doi/10.1109/MICRO.2010.56
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.

Media

Figures

Other

Tables

View Issue’s Table of Contents