research-article

Grace: safe multithreaded programming for C/C++

Authors:

Emery D. Berger,

Gene NovarkAuthors Info & Claims

OOPSLA '09: Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications

Pages 81 - 96

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

Ji ZChen LSun YCai H(2024)Research on Parallel Reading and Drawing Techniques for Chemical Mechanical Polishing Simulation Data Based on Multi-ThreadElectronics10.3390/electronics1304070613:4(706)Online publication date: 9-Feb-2024
https://doi.org/10.3390/electronics13040706
Arora JWestrick SAcar U(2023)Efficient Parallel Functional Programming with EffectsProceedings of the ACM on Programming Languages10.1145/35912847:PLDI(1558-1583)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591284
Zhao QQiu ZShao SHui XKhan HJin GKloeckner AMoreira J(2022)Understanding and Reaching the Performance Limit of Schedule Tuning on Stable Synchronization DeterminismProceedings of the International Conference on Parallel Architectures and Compilation Techniques10.1145/3559009.3569669(223-238)Online publication date: 8-Oct-2022
https://dl.acm.org/doi/10.1145/3559009.3569669
Show More Cited By

Index Terms

Grace: safe multithreaded programming for C/C++

Recommendations

Grace: safe multithreaded programming for C/C++
OOPSLA '09

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 ...
Petrification: Software Model Checking for Programs with Dynamic Thread Management
Verification, Model Checking, and Abstract Interpretation
Abstract
We address the verification problem for concurrent program that dynamically create (fork) new threads or destroy (join) existing threads. We present a reduction to the verification problem for concurrent programs with a fixed number of threads. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

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

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

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 October 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

OOPSLA09

Sponsor:

SIGPLAN

OOPSLA09: ACM SIGPLAN Object Oriented Programming Systems and Applications Conference

October 25 - 29, 2009

Florida, Orlando, USA

Acceptance Rates

OOPSLA '09 Paper Acceptance Rate 25 of 144 submissions, 17%;

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

280
Total Citations
View Citations
1,625
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ji ZChen LSun YCai H(2024)Research on Parallel Reading and Drawing Techniques for Chemical Mechanical Polishing Simulation Data Based on Multi-ThreadElectronics10.3390/electronics1304070613:4(706)Online publication date: 9-Feb-2024
https://doi.org/10.3390/electronics13040706
Arora JWestrick SAcar U(2023)Efficient Parallel Functional Programming with EffectsProceedings of the ACM on Programming Languages10.1145/35912847:PLDI(1558-1583)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591284
Zhao QQiu ZShao SHui XKhan HJin GKloeckner AMoreira J(2022)Understanding and Reaching the Performance Limit of Schedule Tuning on Stable Synchronization DeterminismProceedings of the International Conference on Parallel Architectures and Compilation Techniques10.1145/3559009.3569669(223-238)Online publication date: 8-Oct-2022
https://dl.acm.org/doi/10.1145/3559009.3569669
Bozkurt E(2022)The usage of cybernetic in complex software systems and its application to the deterministic multithreadingConcurrency and Computation: Practice and Experience10.1002/cpe.737534:28Online publication date: 31-Oct-2022
https://doi.org/10.1002/cpe.7375
Hoseinzadeh MSwanson SSherwood TBerger EKozyrakis C(2021)Corundum: statically-enforced persistent memory safetyProceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3445814.3446710(429-442)Online publication date: 19-Apr-2021
https://dl.acm.org/doi/10.1145/3445814.3446710
Giebas DWojszczyk R(2021)Detection of Concurrency Errors in Multithreaded Applications Based on Static Source Code AnalysisIEEE Access10.1109/ACCESS.2021.30738599(61298-61323)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3073859
Lockerman EFeldmann ABakhshalipour MStanescu AGupta SSanchez DBeckmann NLarus JCeze LStrauss K(2020)LiviaProceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3373376.3378497(417-433)Online publication date: 9-Mar-2020
https://dl.acm.org/doi/10.1145/3373376.3378497
Majid ADonne CMaeng KColin AYildirim KLucia BPawełczak P(2020)Dynamic Task-based Intermittent Execution for Energy-harvesting DevicesACM Transactions on Sensor Networks10.1145/336028516:1(1-24)Online publication date: 4-Feb-2020
https://dl.acm.org/doi/10.1145/3360285
Giebas DWojszczyk R(2020)Multithreaded Application ModelDistributed Computing and Artificial Intelligence, 16th International Conference, Special Sessions10.1007/978-3-030-23946-6_11(93-103)Online publication date: 2020
https://doi.org/10.1007/978-3-030-23946-6_11
Utterback RAgrawal KLee IKulkarni M(2019)Processor-Oblivious Record and ReplayACM Transactions on Parallel Computing10.1145/33656596:4(1-28)Online publication date: 17-Dec-2019
https://dl.acm.org/doi/10.1145/3365659
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 Table of Contents