research-article

Grace: safe multithreaded programming for C/C++

Authors:

Emery D. Berger,

Gene NovarkAuthors Info & Claims

ACM SIGPLAN Notices, Volume 44, Issue 10

Pages 81 - 96

https://doi.org/10.1145/1639949.1640096

Published: 25 October 2009 Publication History

Abstract

The shift from single to multiple core architectures means that programmers must write concurrent, multithreaded programs in order to increase application performance. Unfortunately, multithreaded applications are susceptible to numerous errors, including deadlocks, race conditions, atomicity violations, and order violations. These errors are notoriously difficult for programmers to debug.

This paper presents Grace, a software-only runtime system that eliminates concurrency errors for a class of multithreaded programs: those based on fork-join parallelism. By turning threads into processes, leveraging virtual memory protection, and imposing a sequential commit protocol, Grace provides programmers with the appearance of deterministic, sequential execution, while taking advantage of available processing cores to run code concurrently and efficiently. Experimental results demonstrate Grace's effectiveness: with modest code changes across a suite of computationally-intensive benchmarks (1-16 lines), Grace can achieve high scalability and performance while preventing concurrency errors.

References

[1]

M. Abadi, A. Birrell, T. Harris, and M. Isard. Semantics of transactional memory and automatic mutual exclusion. In POPL '08: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 63--74, New York, NY, USA, 2008. ACM.

Digital Library

[2]

D. F. Bacon and S. C. Goldstein. Hardware-assisted replay of multiprocessor programs. In PADD '91: Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, pages 194--206, New York, NY, USA, 1991. ACM.

Digital Library

[3]

E. D. Berger, K. S. McKinley, R. D. Blumofe, and P. R. Wilson. Hoard: A scalable memory allocator for multithreaded applications. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX), pages 117--128, New York, NY, USA, Nov. 2000. ACM.

Digital Library

[4]

E. D. Berger, B. G. Zorn, and K. S. McKinley. Composing high-performance memory allocators. In Proceedings of the 2001 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2001), pages 114--124, New York, NY, USA, June 2001. ACM.

Digital Library

[5]

R. D. Blumofe, C. F. Joerg, B. C. Kuszmaul, C. E. Leiserson, K. H. Randall, and Y. Zhou. Cilk: an efficient multithreaded runtime system. J. Parallel Distrib. Comput., 37(1):55--69, 1996.

Digital Library

[6]

C. Blundell, E. C. Lewis, and M. M. K. Martin. Deconstructing transactions: The subtleties of atomicity. In WDDD '05: 4th Workshop on Duplicating, Deconstructing, and Debunking, June 2005.

[7]

J. B. Carter, J. K. Bennett, and W. Zwaenepoel. Implementation and performance of Munin. In SOSP '91: Proceedings of the Thirteenth ACM Symposium on Operating Systems Principles, pages 152--164, New York, NY, USA, 1991. ACM.

Digital Library

[8]

G.-I. Cheng, M. Feng, C. E. Leiserson, K. H. Randall, and A. F. Stark. Detecting data races in cilk programs that use locks. In SPAA '98: Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, pages 298--309, New York, NY, USA, 1998. ACM.

Digital Library

[9]

J. Dean and S. Ghemawat. MapReduce: simplified data processing on large clusters. In OSDI'04: Proceedings of the 6th conference on Symposium on Opearting Systems Design&Implementation, pages 10--10, Berkeley, CA, USA, 2004. USENIX Association.

Digital Library

[10]

J. Devietti, B. Lucia, L. Ceze, and M. Oskin. DMP: deterministic shared memory multiprocessing. In ASPLOS '09: Proceedings of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 85--96, New York, NY, USA, 2009. ACM.

Digital Library

[11]

D. Dice, O. Shalev, and N. Shavit. Transactional locking ii. In S. Dolev, editor, DISC, volume 4167 of Lecture Notes in Computer Science, pages 194--208. Springer, 2006.

Digital Library

[12]

C. Ding, X. Shen, K. Kelsey, C. Tice, R. Huang, and C. Zhang. Software behavior oriented parallelization. In PLDI '07: Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, pages 223--234, New York, NY, USA, 2007. ACM.

Digital Library

[13]

M. Feng and C. E. Leiserson. Efficient detection of determinacy races in cilk programs. In SPAA '97: Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, pages 1--11, New York, NY, USA, 1997. ACM.

Digital Library

[14]

C. Flanagan and S. Qadeer. A type and effect system for atomicity. In PLDI '03: Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, pages 338--349, New York, NY, USA, 2003. ACM.

Digital Library

[15]

T. Harris and K. Fraser. Language support for lightweight transactions. In OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, pages 388--402, New York, NY, USA, 2003. ACM.

Digital Library

[16]

J. W. Havender. Avoiding deadlock in multitasking systems. IBM Systems Journal, 7(2):74--84, 1968.

Digital Library

[17]

M. Herlihy and J. E. B. Moss. Transactional memory: architectural support for lock-free data structures. In ISCA '93: Proceedings of the 20th annual international symposium on Computer architecture, pages 289--300, New York, NY, USA, 1993. ACM.

Digital Library

[18]

K. Huang. Data-race detection in transactions-everywhere parallel programming. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, June 2003.

[19]

R. L. Hudson, B. Saha, A.-R. Adl-Tabatabai, and B. C. Hertzberg. Mcrt-malloc: a scalable transactional memory allocator. In ISMM '06: Proceedings of the 5th International Symposium on Memory Management, pages 74--83, New York, NY, USA, 2006. ACM.

Digital Library

[20]

M. Isard and A. Birrell. Automatic mutual exclusion. In HotOS XI: 11th Workshop on Hot Topics in Operating Systems, Berkeley, CA, May 2007.

Digital Library

[21]

R. L. B. Jr., V. S. Adve, D. Dig, S. Adve, S. Heumann, R. Komuravelli, J. Overbey, P. Simmons, H. Sung, and M. Vakilian. A type and effect system for deterministic parallel Java. In OOPSLA '09: Proceedings of the 24th ACM SIGPLAN Conference on Object-oriented Programming Systems, Languages, and Applications, New York, NY, USA, 2009. ACM.

Digital Library

[22]

P. Keleher, A. L. Cox, S. Dwarkadas, and W. Zwaenepoel. Treadmarks: Distributed shared memory on standard workstations and operating systems. In WTEC'94: Proceedings of the USENIX Winter 1994 Technical Conference, pages 10--10, Berkeley, CA, USA, 1994. USENIX Association.

Digital Library

[23]

J. R. Larus and R. Rajwar. Transactional Memory. Morgan&Claypool, 2006.

[24]

D. Lea. A Java fork/join framework. In JAVA '00: Proceedings of the ACM 2000 conference on Java Grande, pages 36--43, New York, NY, USA, 2000. ACM.

Digital Library

[25]

S. Lu, S. Park, C. Hu, X. Ma, W. Jiang, Z. Li, R. A. Popa, and Y. Zhou. MUVI: automatically inferring multi-variable access correlations and detecting related semantic and concurrency bugs. In SOSP '07: Proceedings of the Twenty-First ACM SIGOPS Symposium on Operating Systems Principles, pages 103--116, New York, NY, USA, 2007. ACM.

Digital Library

[26]

S. Lu, S. Park, E. Seo, and Y. Zhou. Learning from mistakes: a comprehensive study on real world concurrency bug characteristics. In ASPLOS XIII: Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, pages 329--339, New York, NY, USA, 2008. ACM.

Digital Library

[27]

B. Lucia, J. Devietti, K. Strauss, and L. Ceze. Atom-Aid: Detecting and surviving atomicity violations. In ISCA '08: Proceedings of the 35th Annual International Symposium on Computer Architecture, New York, NY, USA, June 2008. ACM Press.

Digital Library

[28]

C.-K. 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 PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, pages 190--200, New York, NY, USA, 2005. ACM.

Digital Library

[29]

C. E. McDowell and D. P. Helmbold. Debugging concurrent programs. ACM Comput. Surv., 21(4):593--622, 1989.

Digital Library

[30]

R. H. B. Netzer and B. P. Miller. What are race conditions?: Some issues and formalizations. ACM Lett. Program. Lang. Syst., 1(1):74--88, 1992.

Digital Library

[31]

Y. Ni, A. Welc, A.-R. Adl-Tabatabai, M. Bach, S. Berkowits, J. Cownie, R. Geva, S. Kozhukow, R. Narayanaswamy, J. Olivier, S. Preis, B. Saha, A. Tal, and X. Tian. Design and implementation of transactional constructs for C/C++. In OOPSLA '08: Proceedings of the 23rd ACM SIGPLAN Conference on Object-oriented Programming Systems, Languages, and Applications, pages 195--212, New York, NY, USA, 2008. ACM.

Digital Library

[32]

M. Olszewski, J. Ansel, and S. Amarasinghe. Kendo: efficient deterministic multithreading in software. In ASPLOS '09: Proceedings of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 97--108, New York, NY, USA, 2009. ACM.

Digital Library

[33]

S. Rajamani, G. Ramalingam, V. P. Ranganath, and K. Vaswani. ISOLATOR: dynamically ensuring isolation in comcurrent programs. In ASPLOS '09: Proceeding of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 181--192, New York, NY, USA, 2009. ACM.

Digital Library

[34]

C. Ranger, R. Raghuraman, A. Penmetsa, G. Bradski, and C. Kozyrakis. Evaluating MapReduce for multi-core and multiprocessor systems. In Proceedings of the 13th Intl. Symposium on High-Performance Computer Architecture (HPCA), feb 2007.

Digital Library

[35]

J. Reinders. Intel Threading Building Blocks: Outfitting C++ for Multi-core Processor Parallelism. O'Reilly Media, Inc., 2007.

Digital Library

[36]

N. Shavit and D. Touitou. Software transactional memory. In PODC '95: Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, pages 204--213, New York, NY, USA, 1995. ACM.

Digital Library

[37]

T. Shpeisman, V. Menon, A.-R. Adl-Tabatabai, S. Balensiefer, D. Grossman, R. L. Hudson, K. F. Moore, and B. Saha. Enforcing isolation and ordering in S™. In PLDI '07: Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, pages 78--88, New York, NY, USA, 2007. ACM.

Digital Library

[38]

C. von Praun, L. Ceze, and C. Caşcaval. Implicit parallelism with ordered transactions. In PPoPP '07: Proceedings of the 12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 79--89, New York, NY, USA, 2007. ACM.

Digital Library

[39]

A. Welc, S. Jagannathan, and A. Hosking. Safe futures for Java. In OOPSLA '05: Proceedings of the 20th annual ACM SIGPLAN Conference on Object oriented Programming, Systems, Languages, and applications, pages 439--453, New York, NY, USA, 2005. ACM.

Digital Library

[40]

A. Welc, B. Saha, and A.-R. Adl-Tabatabai. Irrevocable transactions and their applications. In SPAA '08: Proceedings of the Twentieth Annual Symposium on Parallelism in Algorithms and Architectures, pages 285--296, New York, NY, USA, 2008. ACM.

Digital Library

Cited By

Semenova SKo SLiu YZiarek LDantu K(2024)A Comprehensive Study of Systems Challenges in Visual Simultaneous Localization and Mapping SystemsACM Transactions on Embedded Computing Systems10.1145/367731724:1(1-31)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.1145/3677317
Song H(2021)A Study on Optimized Multi-Thread Porgramming : Information and The Use of Unitiy DOTSJournal of Digital Contents Society10.9728/dcs.2021.22.11.171522:10(1715-1719)Online publication date: 31-Oct-2021
https://doi.org/10.9728/dcs.2021.22.11.1715
Yu ZZuo YZhao Y(2020)Convoider: A Concurrency Bug Avoider Based on Transparent Software Transactional MemoryInternational Journal of Parallel Programming10.1007/s10766-019-00642-148:1(32-60)Online publication date: 1-Feb-2020
https://dl.acm.org/doi/10.1007/s10766-019-00642-1
Show More Cited By

Index Terms

Grace: safe multithreaded programming for C/C++

Recommendations

Grace: safe multithreaded programming for C/C++
OOPSLA '09: Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications

The shift from single to multiple core architectures means that programmers must write concurrent, multithreaded programs in order to increase application performance. Unfortunately, multithreaded applications are susceptible to numerous errors, ...
Adding Concurrency to Smart Contracts
PODC '17: Proceedings of the ACM Symposium on Principles of Distributed Computing

Modern cryptocurrency systems, such as Ethereum, permit complex financial transactions through scripts called smart contracts. These smart contracts are executed many, many times, always without real concurrency. First, all smart contracts are serially ...
Nested parallelism in transactional memory
PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming

This paper investigates adding transactions with nested parallelism and nested transactions to a dynamically multithreaded parallel programming language that generates only series-parallel programs. We describe XConflict, a data structure that ...

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 10

OOPSLA '09

October 2009

554 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1639949

Issue’s Table of Contents

OOPSLA '09: Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications
October 2009
590 pages
ISBN:9781605587660
DOI:10.1145/1640089
General Chair:
Shail Arora
Adayana, Inc.
,
Program Chair:
Gary Leavens
University of Central Florida

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: 25 October 2009

Published in SIGPLAN Volume 44, Issue 10

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

280
Total Citations
View Citations
1,618
Total Downloads

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

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Semenova SKo SLiu YZiarek LDantu K(2024)A Comprehensive Study of Systems Challenges in Visual Simultaneous Localization and Mapping SystemsACM Transactions on Embedded Computing Systems10.1145/367731724:1(1-31)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.1145/3677317
Song H(2021)A Study on Optimized Multi-Thread Porgramming : Information and The Use of Unitiy DOTSJournal of Digital Contents Society10.9728/dcs.2021.22.11.171522:10(1715-1719)Online publication date: 31-Oct-2021
https://doi.org/10.9728/dcs.2021.22.11.1715
Yu ZZuo YZhao Y(2020)Convoider: A Concurrency Bug Avoider Based on Transparent Software Transactional MemoryInternational Journal of Parallel Programming10.1007/s10766-019-00642-148:1(32-60)Online publication date: 1-Feb-2020
https://dl.acm.org/doi/10.1007/s10766-019-00642-1
Yu ZZuo YXiong W(2019)Concurrency Bug Avoiding Based on Optimized Software Transactional MemoryScientific Programming10.1155/2019/94043232019Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1155/2019/9404323
Schardl TMoses WLeiserson C(2019)TapirACM Transactions on Parallel Computing10.1145/33656556:4(1-33)Online publication date: 17-Dec-2019
https://dl.acm.org/doi/10.1145/3365655
Khan TZhao YPokam GMozafari BKasikci BMcKinley KFisher K(2019)Huron: hybrid false sharing detection and repairProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314644(453-468)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314644
Lau P(2019)Static Detection of Event-Driven Races in HTML5-Based Mobile AppsVerification and Evaluation of Computer and Communication Systems10.1007/978-3-030-35092-5_3(32-46)Online publication date: 12-Nov-2019
https://doi.org/10.1007/978-3-030-35092-5_3
(2018)ReferencesThe Continuing Arms Race10.1145/3129743.3129753(261-281)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1145/3129743.3129753
Coppens BDe Sutter BVolckaert S(2018)Multi-variant execution environmentsThe Continuing Arms Race10.1145/3129743.3129752(211-258)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1145/3129743.3129752
Jin YSullivan DArias OSadeghi ADavi L(2018)Hardware control flow integrityThe Continuing Arms Race10.1145/3129743.3129751(181-210)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1145/3129743.3129751
Show More Cited By

View Options

Get Access

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