140. C11 threads, atomic operations and OpenMP

POSIX threads are a standard of the operating system, not of the language. C11 added three things to the language itself: threads in <threads.h>, atomic types in <stdatomic.h> and the _Thread_local storage class. The first is a thin wrapper over pthread, the second is what every lock is built on, the third gives a thread its own data without any functions. Plus OpenMP: a way to parallelize a loop with one line, without writing a single create or join. Everything is in the experiments in _verify/sys140/, stm-sys:1, gcc 12.

Atomic operations are the same topic as in section 124 on interrupts in a microcontroller; here they are examined from another side: how a lock is built on them and what memory order means with several cores.

Terms used in the documentation

Term	Meaning
thrd_t, mtx_t, cnd_t	C11 thread, mutex, condition variable
atomic operation	an operation other threads cannot see half-done
lock-free	works without a lock
compare-and-swap (CAS), compare-exchange	compare a value and swap it in one step
memory order	the order in which other threads see memory accesses
relaxed, acquire, release, seq_cst	no ordering, acquire, release, a single total order
memory fence	an ordering barrier without a variable
thread-local	a separate copy in each thread
reentrant	can be called again before the previous call has finished
thread-safe	can be called from several threads at once
reduction	combining the threads' partial results

140.1 C11 threads

The same concepts as in pthread, with other names and error codes thrd_success/thrd_error instead of errno:

    for (long k = 0; k < 4; k++)
        if (thrd_create(&th[k], worker, (void *)k) != thrd_success) { puts("thrd_create"); return 1; }
    for (int k = 0; k < 4; k++) { thrd_join(th[k], &res); printf("thrd_join поток %d вернул %d\n", k, res); }

A mutex is created with mtx_init(&mx, mtx_plain); mtx_timed allows mtx_timedlock, mtx_recursive allows nested locking. In glibc it is the same 40 bytes as pthread_mutex_t. In the container the threads.h header is present (glibc since 2.28) and builds with -std=c11 -lpthread. C11 has no thread attributes (stack, priority), no cancellation, no barriers and no rwlock — when you need them, use pthread.

140.2 Atomic types

_Atomic int or atomic_int is a variable on which every operation is indivisible: ++, +=, assignment and reading — and two threads will not lose an increment. How this is done depends on the processor. On x86-64 ++ is a single instruction with the lock prefix (lock addl), and a read is a plain mov. On Cortex-M3 and M4 it is an LDREX/STREX loop (section 124.5). The Cortex-M0 has no such instructions, and ++ becomes a library call: with GCC, __atomic_fetch_add_4, with armclang, __sync_fetch_and_add_4. The libraries do not provide ready-made atomicity for a bare chip: GCC and armclang's microlib do not have this function at all, and armclang's standard library asks for __user_cmpxchg_4 instead. The firmware writes the missing part itself, by disabling interrupts. The explicit functions are atomic_load, atomic_store, atomic_fetch_add, atomic_fetch_or, atomic_exchange, atomic_compare_exchange_*. Four threads, 200 000 times each:

        atomic_fetch_add_explicit(&acnt, 1, memory_order_relaxed);   /* атомарно */
        plain++;                                                       /* гонка */
        mtx_lock(&mx); guarded++; mtx_unlock(&mx);                     /* мьютекс C11 */
        while (atomic_flag_test_and_set_explicit(&spin, memory_order_acquire)) ;   /* спин */
        spin_guarded++;
        atomic_flag_clear_explicit(&spin, memory_order_release);

atomic 800000, мьютекс 800000, спин 800000, без защиты 789678 (потеряно 10322), mine в main 0
atomic_int lock-free: 1; sizeof mtx_t 40

atomic_is_lock_free tells whether a type is implemented with a processor instruction (1) or with a hidden lock (0): atomic_int on x86-64 is lock-free, a 32-byte structure is not. atomic_flag is the only type that must be lock-free everywhere; the four-line spin lock above is written on it.

_Thread_local is the same as __thread in section 139: each thread has its own copy of mine, and in main it stayed zero.

140.3 Compare-and-swap: how a lock works

All mutexes, semaphores and lock-free queues rest on one instruction: compare and swap. atomic_compare_exchange_weak(&v, &expected, desired) atomically checks whether v equals expected; if it does, it writes desired and returns true; if not, it puts the value it found into expected and returns false. The lock:

        int expected = 0;
        while (!atomic_compare_exchange_weak(&lock, &expected, 1))   /* если lock == 0 — ставим 1 */
            expected = 0;                                            /* иначе expected стал 1 — сбросить и повторить */
        lock_count++;                                                /* критическая секция */
        atomic_store(&lock, 0);

CAS-замок: 10 потоков × 100000 = 1000000

Ten threads, a million entries into the critical section, not a single one lost. weak may return false spuriously (on some architectures), so it sits in a loop; strong has no spurious failures but costs more. Reference counters, the lock-free stack and futex in glibc are built the same way: the fast path is a CAS in user mode, and the kernel is entered only when the lock is taken.

140.4 Memory order

A single core always shows a program its own accesses in order. But the compiler reorders ordinary memory accesses even on a single-core microcontroller, and other bus masters — DMA and peripherals — may see the writes in a different order: on a Cortex-M7 because of the write buffer and the cache (section 124.6). On a multicore machine the processor itself reorders too: a write made earlier in the code may become visible to another core later. Hence the second parameter of the atomic functions — the memory order:

Passing a message through a flag: the writer stores the data, then raises the flag with release; the reader waits for the flag with acquire and only then reads the data:

        payload = i;
        atomic_store_explicit(&ready, 1, memory_order_release);                 /* всё до этого видно после acquire */

release/acquire: 200000 сообщений, испорчено 0

A counter that nobody reads together with other data is relaxed: the cheapest, and sufficient (as in the first experiment). A "data ready" flag is a release/acquire pair. Everything else is seq_cst: it is the default and it is not a mistake, only more expensive on ARM and on weak memory models; on x86-64 acquire/release are free, while seq_cst costs an mfence instruction on a write. A barrier without a variable is atomic_thread_fence(order). In section 124 the same barriers stood before starting DMA: __DMB is atomic_thread_fence in Cortex-M terms.

140.5 Reentrancy and thread safety

A function is reentrant if it can be called again while the previous call has not finished — from a signal handler or an interrupt. A function is thread-safe if several threads can call it at the same time. These are different properties: malloc is thread-safe (it has a mutex inside) but not reentrant — a call from a signal handler in the middle of malloc runs into a locked mutex. Static buffers make functions non-reentrant: strtok, localtime, getenv in their old form; their _r variants (strtok_r, localtime_r) get the buffer from the caller. POSIX lists the functions that may be unsafe for threads; everything else in the standard library must be safe.

140.6 OpenMP: a parallel loop with one directive

OpenMP is a set of #pragma omp directives plus a library; the compiler itself creates the threads and splits the loop between them. The switch is -fopenmp; the version in the container is _OPENMP 201511 (OpenMP 4.5):

    #pragma omp parallel for reduction(+:r)          /* у каждого потока своя копия r, в конце сложение */
    for (long i = 0; i < TOTAL; i++) r += sqrt((double)i);

последовательно: 46 мс
parallel for reduction: 10 мс, потоков 24, ускорение 4.5, сумма та же: да
без reduction: cnt = 666665 из 4000000
с omp atomic: cnt = 4000000

reduction(+:r) is the key word: without it r is shared, and the threads create the same race as everywhere else: a counter without reduction, in the worst of 20 runs, reached 666 665 out of 4 000 000. The race does not show up every time: if the threads happened to finish their chunks one after another, nothing is lost — that is why the experiment is repeated. #pragma omp atomic before cnt++ fixes this at the cost of speed; #pragma omp critical is a section under a mutex. The number of threads is set by the OMP_NUM_THREADS variable or num_threads(3) in the directive; omp_get_thread_num and omp_get_num_threads tell who I am and how many of us there are. With four threads the speedup is 3.9 — as with the hand-made threads in section 139; with 24 threads on the same task it is only 4.5, even though the experiment's machine has 24 cores and no hyperthreading. A 46 ms task is small: for 24 threads that means chunks of 2 ms, and starting the threads, waiting for the slowest one and neighbouring processes eat a noticeable share. Repeated runs show this: 8 threads give a speedup of 6.5–7, 24 give 6.4–7.3, while 12 and 16 jump around from 4 to 12 times. Speedup is measured on a longer task, taking the best of several runs.

OpenMP fits computational loops over arrays — signal processing, matrices, images; a server with connections needs ordinary threads or event descriptors (section 141).

140.7 Pitfalls

140.8 Summary

• C11: thrd_*, mtx_*, cnd_*, call_once, tss_* — a wrapper over pthread, without attributes, cancellation or rwlock.
• _Atomic: 800 000 out of 800 000 versus losses without protection; atomic_flag is always lock-free; atomic_is_lock_free checks a type.
• CAS lock: 10 × 100 000 = 1 000 000; weak goes in a loop.
• Memory order: relaxed for counters, release/acquire for a flag, seq_cst by default.
• Reentrancy ≠ thread safety: malloc has the second, not the first.
• OpenMP: parallel for reduction, atomic, critical; without reduction there is a race.

Full sources

c11_threads.c — C11 threads, mutexes and atomic operations, _Thread_local, a spin lock.

/* Раздел 140: потоки и мьютексы C11 (<threads.h>), атомарные операции (<stdatomic.h>),
   _Thread_local, спин-блокировка на compare-and-exchange, thrd_sleep. */
#include <stdio.h>
#include <stdlib.h>
#include <threads.h>
#include <stdatomic.h>
#include <time.h>

#define N 200000
static atomic_int acnt;
static int plain;
static mtx_t mx;
static int guarded;
static _Thread_local int mine;                       /* своя копия у каждого потока */
static atomic_flag spin = ATOMIC_FLAG_INIT;
static int spin_guarded;

static int worker(void *arg)
{
    for (int i = 0; i < N; i++) {
        atomic_fetch_add_explicit(&acnt, 1, memory_order_relaxed);   /* атомарно */
        plain++;                                                       /* гонка */
        mtx_lock(&mx); guarded++; mtx_unlock(&mx);                     /* мьютекс C11 */
        while (atomic_flag_test_and_set_explicit(&spin, memory_order_acquire)) ;   /* спин */
        spin_guarded++;
        atomic_flag_clear_explicit(&spin, memory_order_release);
        mine++;
    }
    printf("поток %d: _Thread_local mine = %d\n", (int)(long)arg, mine);
    return (int)(long)arg * 10;
}

int main(void)
{
    thrd_t th[4]; int res;
    mtx_init(&mx, mtx_plain);
    for (long k = 0; k < 4; k++)
        if (thrd_create(&th[k], worker, (void *)k) != thrd_success) { puts("thrd_create"); return 1; }
    for (int k = 0; k < 4; k++) { thrd_join(th[k], &res); printf("thrd_join поток %d вернул %d\n", k, res); }
    printf("atomic %d, мьютекс %d, спин %d, без защиты %d (потеряно %d), mine в main %d\n",
           atomic_load(&acnt), guarded, spin_guarded, plain, 4 * N - plain, mine);
    printf("atomic_int lock-free: %d; sizeof mtx_t %zu\n", atomic_is_lock_free(&acnt), sizeof(mtx_t));
    struct timespec t0, t1;
    timespec_get(&t0, TIME_UTC);
    thrd_sleep(&(struct timespec){ .tv_nsec = 200000000 }, NULL);
    timespec_get(&t1, TIME_UTC);
    printf("thrd_sleep 200 мс: прошло %ld мс\n", (t1.tv_sec - t0.tv_sec) * 1000 + (t1.tv_nsec - t0.tv_nsec) / 1000000);
    mtx_destroy(&mx);
    return 0;
}

cas_order.c — a lock on compare-and-exchange and the release/acquire memory order versus relaxed.

/* Раздел 140: compare-and-exchange (CAS) как основа блокировок без ядра, и порядок памяти:
   передача данных через флаг с release/acquire против relaxed. */
#include <stdio.h>
#include <stdatomic.h>
#include <threads.h>

static atomic_int lock;
static int lock_count;

static int locker(void *a)
{
    (void)a;
    for (int i = 0; i < 100000; i++) {
        int expected = 0;
        while (!atomic_compare_exchange_weak(&lock, &expected, 1))   /* если lock == 0 — ставим 1 */
            expected = 0;                                            /* иначе expected стал 1 — сбросить и повторить */
        lock_count++;                                                /* критическая секция */
        atomic_store(&lock, 0);
    }
    return 0;
}

/* Передача сообщения через флаг: писатель кладёт данные, потом поднимает флаг;
   читатель ждёт флага и читает данные. С relaxed порядок не гарантирован. */
static int payload;
static atomic_int ready;
static long bad;

static int writer(void *a) { (void)a; for (int i = 1; i <= 200000; i++) {
        while (atomic_load_explicit(&ready, memory_order_acquire)) ;            /* ждём, пока читатель заберёт */
        payload = i;
        atomic_store_explicit(&ready, 1, memory_order_release);                 /* всё до этого видно после acquire */
    } return 0; }
static int reader(void *a) { (void)a; for (int i = 1; i <= 200000; i++) {
        while (!atomic_load_explicit(&ready, memory_order_acquire)) ;
        if (payload != i) bad++;
        atomic_store_explicit(&ready, 0, memory_order_release);
    } return 0; }

int main(void)
{
    thrd_t t[10];
    for (int k = 0; k < 10; k++) thrd_create(&t[k], locker, NULL);
    for (int k = 0; k < 10; k++) thrd_join(t[k], NULL);
    printf("CAS-замок: 10 потоков × 100000 = %d\n", lock_count);
    thrd_t w, r;
    thrd_create(&w, writer, NULL); thrd_create(&r, reader, NULL);
    thrd_join(w, NULL); thrd_join(r, NULL);
    printf("release/acquire: 200000 сообщений, испорчено %ld\n", bad);
    printf("порядки: relaxed %d, acquire %d, release %d, acq_rel %d, seq_cst %d\n",
           memory_order_relaxed, memory_order_acquire, memory_order_release, memory_order_acq_rel, memory_order_seq_cst);
    return 0;
}

Next: section 141 — non-blocking I/O and epoll.