Concurrency, Threads and Shared Memory

A thread is a separate line of execution inside a process.

Learning Objectives

Distinguish processes and threads; describe thread stacks, thread-local storage and the shared address space.

Create and join threads; explain scheduling and context switching for threads.

Define race conditions, data races and critical sections; use mutexes, semaphores, condition variables and read-write locks correctly.

Use atomics, compare-and-swap and memory orders (relaxed, acquire, release, sequentially consistent) and the happens-before relation.

Recognise and prevent deadlock, livelock and starvation; avoid false sharing.

Know lock-free and wait-free concepts, producer-consumer patterns, thread-safe allocation and re-entrancy.

Handle interrupt/task shared state on embedded systems; explain volatile versus atomics; detect races with ThreadSanitizer; shut down safely.

Plain-Language Explanation

A thread is a separate line of execution inside a process. Threads share everything except their stacks and registers — the same globals, the same heap. That makes communication easy and mistakes easy too: if two threads update the same counter at the same time, some updates get lost, because "add one" is really "read, add, write", and the steps can interleave. Synchronisation — locks, atomic operations, condition variables — makes such updates happen one at a time and makes one thread's writes visible to another in a predictable order.

Precise Technical Explanation

Process versus thread shared with other threads of the process Stack, registers high (page tables, descriptors) Thread stacks and thread-local storage

Each thread gets its own stack (glibc default: 8 MiB virtual, from RLIMIT_STACK, with a guard page; Windows: 1 MiB) and its own copy of _Thread_local variables, located through a per-thread base register (%fs on x86-64 Linux, TPIDR_EL0 on AArch64).

Shared heap and address space Every thread can access every heap object and global — no protection between threads. Ownership and synchronisation are matters of program design.

Thread creation and termination concepts POSIX: pthread_create(&t, attr, fn, arg), pthread_join(t, &result), pthread_detach. C11: thrd_create/thrd_join. C++: std::thread, std::jthread (joins automatically, supports stop tokens). A thread ends when its function returns; its resources are released when it is joined or, if detached, when it ends.

Scheduling and context switching The OS schedules threads, not processes. A switch between threads of the same process skips the address-space change (cheaper, no TLB flush). Threads may run truly in parallel on different cores, or interleave on one.

The program's outcome depends on the relative timing of threads — e.g. two threads both see "seat available" and both book it.

In C and C++, a data race — two conflicting accesses (at least one write) to the same memory location from different threads without happens-before ordering, and not both atomic — is undefined behavior. Even "benign" races can be miscompiled.

Code that must not be executed by two threads at once because it accesses shared state. Keep critical sections short.

Mutexes and locks A mutex allows one owner at a time: pthread_mutex_lock/unlock, std::mutex with std::lock_guard/std::scoped_lock (RAII). Locking also provides memory ordering: everything written before unlock is visible after the next lock of the same mutex.

A counter with atomic wait (decrement, blocking at zero) and post (increment): sem_t, std::counting_semaphore. Used to limit concurrency (a pool of N resources) and for signalling, including from interrupt handlers in RTOSes.

Let a thread sleep until another thread signals that a condition *may* have changed. Always wait in a loop around the predicate, while holding the associated mutex (spurious wake-ups are allowed):

Many concurrent readers or one writer (pthread_rwlock_t, std::shared_mutex). Helpful when reads dominate and critical sections are long; otherwise a plain mutex is often faster.

Operations that are indivisible and race-free by definition: _Atomic/<stdatomic.h> in C11, std::atomic<T> in C++11, Interlocked/Volatile in C#, java.util.concurrent.atomic, AtomicU64 in Rust. Compiled to lock-prefixed instructions, LL/SC loops or LSE atomics (Module 11).

atomic_compare_exchange_weak(&obj, &expected, desired): if obj == expected, store desired and succeed; otherwise load the current value into expected and fail. Loops around CAS implement any atomic read-modify-write (maximum, push onto a lock-free stack).

Memory ordering: relaxed, acquire, release, sequential consistency atomicity only; no ordering with other memory operations acquire (loads) later reads/writes cannot move before it release (stores) earlier reads/writes cannot move after it both, for read-modify-write seq_cst (default) acquire/release plus a single total order of all seq_cst operations

If a release store is read by an acquire load, everything sequenced before the store happens-before everything after the load: the reader sees the writer's earlier writes. Locks, thread creation/join and condition variables establish happens-before too. Without it, there is no guarantee another thread ever sees your writes.

Deadlocks, livelocks and starvation Deadlock — threads wait for each other forever (A holds L1 and wants L2; B holds L2 and wants L1). Prevent by a global lock order, std::scoped_lock (deadlock-avoiding multi-lock), try-lock with back-off, or fewer locks.

Livelock — threads keep reacting to each other without progress (both back off and retry in lockstep).

Starvation — a thread never gets the resource (unfair locks, priority inversion — the RTOS simulator in Electronics shows priority inheritance).

Module 13 measured it: separate per-thread written data onto different cache lines.

Lock-free and wait-free overview Lock-free: some thread always makes progress even if others are suspended (CAS loops). Wait-free: every thread completes in a bounded number of steps. They avoid lock convoys and priority inversion but are hard to get right — especially memory reclamation (the ABA problem; hazard pointers, epochs, RCU — Module 19). Use proven libraries.

Producers put work in a bounded queue; consumers take it out. Implement with a mutex + two condition variables (not full / not empty), semaphores, or a lock-free SPSC ring buffer (Module 8). Bounded queues provide back-pressure.

malloc is thread-safe in every modern C library, using per-thread caches (glibc tcache, jemalloc/tcmalloc thread caches) and arenas to avoid lock contention. Freeing a block on another thread than the one that allocated it is allowed but can be slower.

Thread-safe ≠ re-entrant: a function that takes a lock is thread-safe but not re-entrant from a signal handler or ISR that interrupts the lock holder (it would deadlock). Interrupt handlers may only use re-entrant, non-blocking code.

Interrupt/task shared state in embedded systems An ISR and the main loop (or an RTOS task) share data. Options: disable interrupts briefly around multi-word updates; use single-word atomic accesses (volatile for the "must read memory" part *plus* knowledge that aligned word accesses are atomic on the core); use C11 atomics where supported; or use RTOS queues/semaphores with FromISR variants.

volatile versus atomics Every access performed Ordering with other variables no (only with other volatiles, by the compiler) yes, per memory order Inter-thread visibility guarantees MMIO registers, signal flags data shared between threads Thread sanitizers and race detection

ThreadSanitizer instruments memory accesses and synchronisation and reports races with both stacks (demonstration below). Also: Helgrind and DRD (Valgrind), Intel Inspector, the Go and Rust (via loom, Miri) race tools.

Safe shutdown and resource lifetime Signal threads to stop (atomic flag, stop token, closing a queue), wake sleepers (pthread_cond_broadcast), join every thread *before* destroying the objects they use, and never let a detached thread outlive data it references.

Concurrency debugging exercises See the exercises below and Lab 17 in Module 20.

pthread_mutex_lock(&m);
while (!ready) pthread_cond_wait(&cv, &m);   /* atomically unlocks, sleeps, relocks */
pthread_mutex_unlock(&m);

Why It Matters in Real Systems

Every server, GUI, game engine and RTOS application is concurrent. Data races produce the hardest bugs to reproduce — they appear under load, on other CPUs, or after a compiler upgrade. Correct synchronisation is also a performance question: too little is wrong, too much is slow.

Key Terms

Independent execution path sharing its process's address space

Unsynchronised conflicting accesses; UB in C/C++ Code that must run under mutual exclusion Mutex / semaphore / condition variable

Lock / counter / wait-for-condition primitives Indivisible operation with defined concurrent semantics

Ordering guarantees of an atomic operation Ordering relation that makes writes visible Deadlock / livelock / starvation

No progress / busy no progress / one thread never progresses Lock-free / wait-free Progress guarantees without locks

Memory Layout and Execution Flow

flowchart LR
  subgraph Process[one process, one address space]
    G[globals + heap: shared]
    T1[thread 1: own stack, registers, TLS]
    T2[thread 2: own stack, registers, TLS]
    T1 --> G
    T2 --> G
  end

Syntax

#include <pthread.h>
#include <stdatomic.h>
pthread_t t;
pthread_create(&t, NULL, worker, arg);
pthread_join(t, NULL);
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&m); /* critical section */ pthread_mutex_unlock(&m);
atomic_long counter = 0;
atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);
atomic_store_explicit(&ready, 1, memory_order_release);
while (!atomic_load_explicit(&ready, memory_order_acquire)) { }

Complete Runnable Example

A lost-update race, then two correct versions. GCC 11.2 -O2 -pthread, 8 hardware threads.

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

#define THREADS 4
#define ITERS 1000000

static volatile long racy;               /* volatile does NOT make ++ atomic */
static long locked;
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
static atomic_long atomic_count;

static void *work(void *unused)
{
    (void)unused;
    for (int i = 0; i < ITERS; ++i) {
        racy = racy + 1;                                   /* data race: lost updates */
        pthread_mutex_lock(&lock);
        ++locked;                                           /* protected */
        pthread_mutex_unlock(&lock);
        atomic_fetch_add_explicit(&atomic_count, 1, memory_order_relaxed);   /* indivisible */
    }
    return NULL;
}

int main(void)
{
    pthread_t t[THREADS];
    for (int i = 0; i < THREADS; ++i) pthread_create(&t[i], NULL, work, NULL);
    for (int i = 0; i < THREADS; ++i) pthread_join(t[i], NULL);
    printf("expected      %d\n", THREADS * ITERS);
    printf("racy volatile %ld\n", racy);
    printf("mutex         %ld\n", locked);
    printf("atomic        %ld\n", (long)atomic_count);
    return 0;
}

Line-by-Line Explanation

racy = racy + 1 compiles to load, add, store; two threads can load the same value and both store value + 1 — one increment lost. volatile forces the memory accesses but does not make the sequence indivisible.

The mutex makes ++locked a critical section; unlock/lock also orders memory between threads.

atomic_fetch_add is one indivisible instruction (lock add); relaxed suffices because only the final count matters and pthread_join provides the happens-before for reading it.

(The racy counter is undefined behavior; it is here, in an isolated variable, purely to show the symptom.)

Expected Output

Output (one real run — the racy value changes every run):

expected      4000000
racy volatile 3979284
mutex         4000000
atomic        4000000

Step-by-Step Execution Trace

A lost update, two threads, racy = 10:

racy in memory 11 (one increment lost)

Interactive Visualization

The lifetime visualizer's "shared object" example shows two owners and the hazards of releasing an object while another thread still uses it; the cache simulator shows why per-thread data should not share lines.

Common Mistakes and Failure Modes

Using volatile (or nothing) for inter-thread flags and counters.

Checking a condition variable's predicate with if instead of while.

Locking in different orders in different places (deadlock).

Holding a lock while calling unknown code (callbacks, I/O).

Destroying objects while other threads still use them; detached threads outliving main's data.

Double-checked locking with plain variables.

ThreadSanitizer finds the race in the first example automatically:

Output (one real run):

Two real-world lessons in one output. First, the tool itself has platform constraints: GCC 11's ThreadSanitizer predates the larger address-space randomisation of recent kernels (vm.mmap_rnd_bits), so the plain run aborts with "unexpected memory mapping". Running that single process without ASLR (setarch -R), lowering vm.mmap_rnd_bits, or using a newer GCC/Clang fixes it. Second, the report names both conflicting accesses — a read and a previous write by two different threads, both on line 9 (shared++) — the variable (global 'shared') and where each thread was created. Note that the program printed the "right" total of 2000 this time: races do not always produce wrong results, which is exactly why a detector is needed.

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

static long shared;

static void *work(void *unused)
{
    (void)unused;
    for (int i = 0; i < 1000; ++i) shared++;     /* unsynchronised read-modify-write */
    return NULL;
}

int main(void)
{
    pthread_t a, b;
    pthread_create(&a, NULL, work, NULL);
    pthread_create(&b, NULL, work, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("shared = %ld\n", shared);
    return 0;
}

gcc -std=c17 -g -O1 -fsanitize=thread -pthread m14_tsan_src.c -o m14_tsan_bin
echo "--- plain run ---"
./m14_tsan_bin 2>&1 | head -n 1 || true
echo "--- with ASLR disabled for this one process (setarch -R) ---"
setarch "$(uname -m)" -R ./m14_tsan_bin 2>&1 | grep -v '^$' || true

--- plain run ---
FATAL: ThreadSanitizer: unexpected memory mapping 0x63ac6b52b000-0x63ac6b52c000
--- with ASLR disabled for this one process (setarch -R) ---
==================
WARNING: ThreadSanitizer: data race (pid=32)
  Read of size 8 at 0x555555558018 by thread T2:
    #0 work m14_tsan_src.c:9 (m14_tsan_bin+0x1263)
  Previous write of size 8 at 0x555555558018 by thread T1:
    #0 work m14_tsan_src.c:9 (m14_tsan_bin+0x128d)
  Location is global 'shared' of size 8 at 0x555555558018 (m14_tsan_bin+0x000000004018)
  Thread T2 (tid=37, running) created by main thread at:
    #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:969 (libtsan.so.0+0x605b8)
    #1 main m14_tsan_src.c:17 (m14_tsan_bin+0x1301)
  Thread T1 (tid=36, finished) created by main thread at:
    #0 pthread_create ../../../../src/libsanitizer/tsan/tsan_interceptors_posix.cpp:969 (libtsan.so.0+0x605b8)
    #1 main m14_tsan_src.c:16 (m14_tsan_bin+0x12e7)
SUMMARY: ThreadSanitizer: data race m14_tsan_src.c:9 in work
==================
ThreadSanitizer: reported 1 warnings
shared = 2000

Corrected / Safe Pattern

A bounded producer-consumer queue with a mutex and two condition variables, a message passed with release/acquire, and a CAS loop:

How the split between consumers varies run to run, the total does not — the queue never loses or duplicates an item, and shutdown (closed + broadcast) lets both consumers exit cleanly.

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

#define CAP 4
static int queue[CAP];
static int head, tail, count;
static bool closed;
static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t not_full = PTHREAD_COND_INITIALIZER, not_empty = PTHREAD_COND_INITIALIZER;

static void put(int v)
{
    pthread_mutex_lock(&m);
    while (count == CAP) pthread_cond_wait(&not_full, &m);   /* loop: spurious wake-ups */
    queue[tail] = v; tail = (tail + 1) % CAP; ++count;
    pthread_cond_signal(&not_empty);
    pthread_mutex_unlock(&m);
}

static bool take(int *v)
{
    pthread_mutex_lock(&m);
    while (count == 0 && !closed) pthread_cond_wait(&not_empty, &m);
    if (count == 0) { pthread_mutex_unlock(&m); return false; }   /* closed and drained */
    *v = queue[head]; head = (head + 1) % CAP; --count;
    pthread_cond_signal(&not_full);
    pthread_mutex_unlock(&m);
    return true;
}

static void *consumer(void *out)
{
    long sum = 0; int v;
    while (take(&v)) sum += v;
    *(long *)out = sum;
    return NULL;
}

static int payload;                       /* plain data ... */
static atomic_bool published;             /* ... pub
…

producer-consumer: total 500500 (expected 500500)
release/acquire message: reader saw 42
CAS-based atomic max: 99

Debugging and Diagnostic Techniques

Threads really do have separate stacks and separate thread-local variables:

Output (one real run):

The two thread stacks are about 8 MiB apart — each thread got its own mmap'ed 8 MiB stack plus a guard page — and each thread's tls_value lives at a different address.

Further tools: debuggers' thread views (info threads, thread apply all bt), perf lock, perf c2c, Visual Studio Concurrency Visualizer, RTOS-aware trace (Tracealyzer, SystemView).

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

static _Thread_local int tls_value;
static int shared_global;

struct Report { int id; uintptr_t stack_addr, tls_addr; int tls_seen; };

static void *probe(void *arg)
{
    struct Report *r = arg;
    int local = 0;
    tls_value = r->id * 100;              /* each thread writes its own copy */
    r->stack_addr = (uintptr_t)&local;
    r->tls_addr = (uintptr_t)&tls_value;
    r->tls_seen = tls_value;
    return NULL;
}

int main(void)
{
    pthread_attr_t attr;
    size_t stack_size = 0;
    pthread_attr_init(&attr);
    pthread_attr_getstacksize(&attr, &stack_size);
    printf("default thread stack size: %zu KiB\n", stack_size / 1024);

    struct Report r[2] = {{.id = 1}, {.id = 2}};
    pthread_t t[2];
    for (int i = 0; i < 2; ++i) pthread_create(&t[i], NULL, probe, &r[i]);
    for (int i = 0; i < 2; ++i) pthread_join(t[i], NULL);
    for (int i = 0; i < 2; ++i)
        printf("thread %d: local at 0x%lx, tls_value at 0x%lx = %d\n",
               r[i].id, (unsigned long)r[i].stack_addr, (unsigned long)r[i].tls_addr, r[i].tls_seen);
    printf("main: tls_value = %d (its own copy), &shared_global = %p (one copy for al
…

default thread stack size: 8192 KiB
thread 1: local at 0x7c583fdfee3c, tls_value at 0x7c583fdff63c = 100
thread 2: local at 0x7c583f5fde3c, tls_value at 0x7c583f5fe63c = 200
main: tls_value = 0 (its own copy), &shared_global = 0x5e048a78e014 (one copy for all)
distance between the two thread stacks: 8196 KiB

Performance Implications

Uncontended mutexes cost tens of nanoseconds; contended ones microseconds (sleep/wake). Atomics on a shared line serialize all cores on that line. Scale by partitioning data per thread and combining results, using read-mostly data, batching, and avoiding false sharing. More threads than cores add context-switch overhead for CPU-bound work.

Security and Safety Implications

Races can break security checks (TOCTOU), corrupt memory (use-after-free across threads) and cause intermittent failures in safety systems. RTOS designs must bound blocking (priority inheritance, ceiling protocols) to meet deadlines. Use TSan in CI, design ownership so most data is not shared, and prefer message passing.

Platform and Language Caveats

POSIX threads on Linux/macOS; Win32 threads, SRWLOCK, CONDITION_VARIABLE on Windows; C11 <threads.h> support varies.

The x86 memory model hides many ordering bugs that appear on Arm and RISC-V.

Java and C# have their own memory models (JSR-133, ECMA-335): volatile there *does* have acquire/release semantics — unlike C/C++.

CPython's GIL serialises bytecode (until free-threaded 3.13+ builds), but races between Python operations still occur; JavaScript is single-threaded per realm, with SharedArrayBuffer + Atomics for workers.

Rust's Send/Sync traits make data races compile-time errors in safe code.

Real-World Application

Web servers use thread pools and work queues; databases use reader-writer and fine-grained locks plus lock-free logs; the Linux kernel uses spinlocks, RCU and per-CPU data; game engines use job systems; firmware shares data between ISRs and tasks through queues and critical sections.

Best Practices Checklist

[ ] Minimise shared mutable state; prefer message passing and immutable data.

[ ] Protect every shared mutable object with one documented lock or make it atomic.

[ ] Use RAII locks (std::scoped_lock) and a global lock order.

[ ] Wait on condition variables in a while loop.

[ ] Use atomics, not volatile, for inter-thread communication; default to seq_cst until you can prove a weaker order is correct.

[ ] Join threads before destroying what they use.

[ ] Run ThreadSanitizer in CI; test on weakly ordered hardware.

Exercises

E1 · Beginner. Why can count++ on a shared int lose updates even on a single-core CPU?

Answer: It is load, add, store; a context switch between the load and the store lets another thread update count, and the first thread then overwrites that update with its stale value + 1.

E2 · Intermediate. Two threads lock mutexes A and B in opposite orders. Show a deadlocking interleaving and two ways to fix it.

Answer: T1 locks A, T2 locks B, T1 waits for B, T2 waits for A — forever. Fixes: always lock A before B everywhere; or lock both with a deadlock-avoiding call (std::scoped_lock(a, b) / std::lock), or use try-lock and back off.

E3 · Advanced challenge. In the release/acquire example, what could the reader print if both operations used memory_order_relaxed, and on which hardware would you be likely to observe it?

Answer: It could print 0: without release/acquire there is no happens-before, so the store to payload may become visible after published. On x86 (TSO) the hardware does not reorder these stores, so it rarely shows up (the compiler still could reorder); on Arm or RISC-V it can be observed in practice — and in any case the program has a data race on payload, which is undefined behavior.

Quiz

? Why did the volatile counter end below 4,000,000?
- volatile makes the compiler skip some increments. :: It forces every access.
+ The read-add-write sequences of different threads interleaved and overwrote each other. :: volatile is not atomic.
- The threads did not all run. :: All four were joined.
- long overflowed. :: 4,000,000 fits easily.

? What does a release store paired with an acquire load guarantee?
+ The reader sees all writes the writer made before the release store. :: That is the happens-before edge.
- Both threads run on the same core. :: Unrelated to placement.
- The store is visible instantly. :: Visibility timing is not specified; ordering is.
- Mutual exclusion. :: That needs a lock or RMW protocol.

? Which prevent deadlock? (select all that apply)
+ A single global lock-acquisition order :: Cycles in the wait-for graph become impossible.
+ std::scoped_lock(a, b) for multiple mutexes :: Uses a deadlock-avoidance algorithm.
- Using volatile for the mutex :: Irrelevant.
+ Try-lock with back-off and retry :: Breaks hold-and-wait (watch for livelock).

? In C/C++, which is true of a data race?
- It is harmless if the variable is an int. :: Any data race is undef
…

Summary

Threads share an address space but have private stacks, registers and thread-local storage. Unsynchronised conflicting accesses are data races — undefined behavior. Mutexes, condition variables, semaphores and atomics with memory orders provide mutual exclusion and visibility; happens-before is the rule that makes writes visible. Avoid deadlock with lock ordering, false sharing with padding, and volatile for threads altogether. Detect races with ThreadSanitizer and shut down by signalling and joining.

References and Further Reading

Anthony Williams, *C++ Concurrency in Action*, 2nd ed.

Herb Sutter, "atomic<> Weapons" (C++ and Beyond 2012).

Hans Boehm, "Threads Cannot Be Implemented as a Library" (PLDI 2005).

Maurice Herlihy & Nir Shavit, *The Art of Multiprocessor Programming*.

Paul McKenney, *Is Parallel Programming Hard, And, If So, What Can You Do About It?*