research-article

Futex based locks for C11's generic atomics

Author:

Jens GustedtAuthors Info & Claims

SAC '16: Proceedings of the 31st Annual ACM Symposium on Applied Computing

Pages 2004 - 2006

https://doi.org/10.1145/2851613.2851956

Published: 04 April 2016 Publication History

Get Access

Abstract

We present a new algorithm and implementation of a lock primitive that is based on Linux' native lock interface, the futex system call. It allows us to assemble compiler support for atomic data structures that can not be handled through specific hardware instructions. Such a tool is needed for C11's atomics interface because here an Atomic qualification can be attached to almost any data type. Our lock data structure for that purpose meets very specific criteria concerning its field of operation and its performance. By that we are able to outperform gcc's libatomic library by around 60%.

References

[1]

Alpine Linux. http://alpinelinux.org/

Google Scholar

[2]

Clang. http://clang.llvm.org/

Google Scholar

[3]

gcc. GNU Compiler Collection. https://gcc.gnu.org/

Google Scholar

[4]

glibc. GNU C library. https://www.gnu.org/software/libc/

Google Scholar

[5]

Jens Gustedt. 2015. Futex based locks for C11's generic atomics. INRIA RR-8818 https://hal.inria.fr/hal-01236734

Google Scholar

[6]

Darren Hart. 2009. A futex overview and update. LWN.net (2009). https://lwn.net/Articles/360699/

Google Scholar

[7]

Andrew J. Hutton et al. 2002. Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux. In Proceedings of the Ottawa Linux Symposium. 479--495.

Google Scholar

[8]

IBM 1983. IBM System/370 Extended Architecture, Principles of Operation. IBM. SA22-7085.

Google Scholar

[9]

JTC1/SC22/WG14 (Ed.). 2011. Programming languages --- C (cor. 1:2012 ed.). Number ISO/IEC 9899. ISO.

Google Scholar

[10]

Maged M. Michael. 2004. ABA Prevention Using Single-Word Instructions. Tech. Rep. RC23089. IBM Research.

Google Scholar

[11]

MUSL libc. http://musl-libc.org

Google Scholar

[12]

Robert H. B. Netzer and Barton P. Miller. 1992. What Are Race Conditions? Some Issues and Formalizations. ACM Lett. Program. Lang. Syst. 1, 1 (March 1992), 74--88.

Digital Library

Google Scholar

[13]

POSIX. 2009. ISO/IEC/IEEE Information technology -- Portable Operating Systems Interface (POSIX®) Base Specifications. Issue 7. ISO, Geneva, Switzerland.

Google Scholar

Cited By

View all

Liu CWang P(2021)A Concurrent Message Processing Mechanism for Internet of Vehicles2021 IEEE 2nd International Conference on Information Technology, Big Data and Artificial Intelligence (ICIBA)10.1109/ICIBA52610.2021.9687947(778-783)Online publication date: 17-Dec-2021
https://doi.org/10.1109/ICIBA52610.2021.9687947
Mishra RAhmad ISharma A(2020)A Dynamic Multi-Threaded Queuing Mechanism for Reducing the Inter-Process Communication Latency on Multi-Core Chips2020 3rd International Conference on Data Intelligence and Security (ICDIS)10.1109/ICDIS50059.2020.00008(12-19)Online publication date: Jun-2020
https://doi.org/10.1109/ICDIS50059.2020.00008

Index Terms

Futex based locks for C11's generic atomics
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Runtime environments
    2. General programming languages
      1. Language features
        Concurrent programming structures

Recommendations

AArch64 Atomics: Might They Be Harming Your Performance?
PPoPP '23: Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming

Atomic operations are indivisible operations guaranteed to execute as a whole. One of the most important and widely used atomic operations is "compare-and-swap" (CAS), which allows threads to perform concurrent read-modify-write operations on the same ...
Free atomics: hardware atomic operations without fences
ISCA '22: Proceedings of the 49th Annual International Symposium on Computer Architecture

Atomic Read-Modify-Write (RMW) instructions are primitive synchronization operations implemented in hardware that provide the building blocks for higher-abstraction synchronization mechanisms to programmers. According to publicly available documentation,...
Massive atomics for massive parallelism on GPUs
ISMM '14

One important type of parallelism exploited in many applications is reduction type parallelism. In these applications, the order of the read-modify-write updates to one shared data object can be arbitrary as long as there is an imposed order for the ...

Comments

Information & Contributors

Information

Published In

SAC '16: Proceedings of the 31st Annual ACM Symposium on Applied Computing

April 2016

2360 pages

ISBN:9781450337397

DOI:10.1145/2851613

Conference Chair:
Sascha Ossowski
University Rey Juan Carlos, Spain

Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 April 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SAC 2016

Sponsor:

SIGAPP

SAC 2016: Symposium on Applied Computing

April 4 - 8, 2016

Pisa, Italy

Acceptance Rates

SAC '16 Paper Acceptance Rate 252 of 1,047 submissions, 24%;

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25

Sponsor:
sigapp

The 40th ACM/SIGAPP Symposium on Applied Computing

March 31 - April 4, 2025

Catania , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
68
Total Downloads

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

Reflects downloads up to 21 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liu CWang P(2021)A Concurrent Message Processing Mechanism for Internet of Vehicles2021 IEEE 2nd International Conference on Information Technology, Big Data and Artificial Intelligence (ICIBA)10.1109/ICIBA52610.2021.9687947(778-783)Online publication date: 17-Dec-2021
https://doi.org/10.1109/ICIBA52610.2021.9687947
Mishra RAhmad ISharma A(2020)A Dynamic Multi-Threaded Queuing Mechanism for Reducing the Inter-Process Communication Latency on Multi-Core Chips2020 3rd International Conference on Data Intelligence and Security (ICDIS)10.1109/ICDIS50059.2020.00008(12-19)Online publication date: Jun-2020
https://doi.org/10.1109/ICDIS50059.2020.00008

View Options

Login options

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

Cited By

Index Terms

Recommendations

AArch64 Atomics: Might They Be Harming Your Performance?

Free atomics: hardware atomic operations without fences

Massive atomics for massive parallelism on GPUs