C11 Features on Concurrency

C11 Overview

C11 is an informal name for ISO/IEC 9899:2011. It includes multi-thread support, which enables us to use higher-level programming types to deal with concurrency. Now, let's see how to use the C11 features to design a lock-free data structure.

C11 Atomic Types

C11 defines a new _Atomic type specifier. Include the header with #include<stdatomic.h> when you are going to use the atomic type in your program.

The atomic declaration syntax is like _Atomic(type_name) or _Atomic type_name. For example, we could define an atomic integer like this:

_Atomic(int) a; // or
_Atomic int b; // both of them are the atomic integer

Notice that the type_name can not be an array or a function; and with the first syntax, it can not be an atomic type, or a qualified type. Refer to here for more information.

We could make a user-defined struct atomic, so that every element inside struct wil be manipulated atomically.

struct Node
{
    int data;
    struct Node *next;
};
_Atomic struct Node s; // s is also an atomic type

In addition to make user-defined type atomic, the _Atomic keyword makes it possible to use objects of all atomic types in nearly all the same expressions and contexts as their non-atomic counterparts.

_Atomic int a = 3; // initialize like a normal int type
a = a + 2;         // you can perform the atomic addition like this

Here is a simple example of using C11 atomic type:

atomic_type.c

#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>

_Atomic int acnt;
int cnt;
void *adding(void *input) {
    for (int i = 0; i < 10000; i++) {
        acnt++;
        cnt++;
    }
    pthread_exit(NULL);
}
int main() {
    pthread_t tid[10];
    for (int i = 0; i < 10; i++)
        pthread_create(&tid[i], NULL, adding, NULL);
    for (int i = 0; i < 10; i++)
        pthread_join(tid[i], NULL);

    printf("the value of acnt is %d\n", acnt);
    printf("the value of cnt is %d\n", cnt);
    return 0;
}

In order to compile C11 program, we need GCC 4.9 or later. We should specify the parameter to tell the gcc compiler that we would like to compile the program by using C11 standard. Use the following commands to check the GCC version and compile the program:

gcc --version
gcc -std=c11 -pthread -o atomic_type atomic_type.c

One of the possible outputs is:

the value of acnt is 100000 (correct)
the value of cnt is 89824 (wrong)

Atomic operations

C11 provides some functions for us to change the content of atomic types like a user-defined struct in an atomic way. Here We will introduce the CAS function, which we will use in lock-free data-struct design.

_Bool atmoic_compare_exchange_weak(volatile A *object, C *expected, C desired);

Description: Atomically, compares the value pointed to by object for equality with that in expected, and if true, replaces the value pointed to by object with desired, and if false, updates the value in expected with the value pointed to by object. (Here, A is the atomic type, while the C is the non-atomic counterpart of A. For example, if A is _Atomic int, then, C is int).

The volatile is a type qualifier like const, and is a property of the type. It indicates that a value may change between accesses (e.g. shared variable in multi-thread program), even if it does not appear to have been modified.

With the volatile keyword, the compiler knows a variable needs to be reread from memory upon each access. It prevents the compiler from performing optimization on code. For more information, please refer to this link.

atmoic_compare_exchange_weak() returns the result of the comparison, either true or false. Here, we use this function to implement a simple lock.

atomic_operation.c

#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>

_Atomic int lock = 0;
int lock_count = 0;
int unlock_count = 0;

void *counting(void *input) {
    int expected = 0;
    for (int i = 0; i < 100000; i++) {
        unlock_count++;
        while (!atomic_compare_exchange_weak(
            &lock, &expected, 1)) // if the lock is 0(unlock), then set it to 1(lock).
            expected = 0; // if the CAS fails, the expected will be set to 1, so we need
                          // to change it to 0 again.
        lock_count++;
        lock = 0;
    }
    pthread_exit(NULL);
}

int main() {
    pthread_t tid[10];
    for (int i = 0; i < 10; i++) {
        pthread_create(&tid[i], NULL, counting, NULL);
    }
    for (int i = 0; i < 10; i++)
        pthread_join(tid[i], NULL);

    printf("the value of lock_count is %d\n", lock_count);
    printf("the value of unlock_count is %d\n", unlock_count);
}

gcc -std=c11 -lpthread -o atomic_operation atomic_operation.c

One of the possible outputs is:

the value of lock_count is 1000000 (correct)
the value of unlock_count is 998578 (wrong)

For more information, please refer to http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf