Concurrency, Synchronization & Deadlock Questions

Direct answer

A single-producer single-consumer (SPSC) ring buffer needs no lock because each index has exactly one writer: the producer writes head, the consumer writes tail. Use free-running indices (they only ever increase and wrap naturally), a power-of-two capacity so the slot is index & (CAP - 1), empty when head == tail and full when head - tail == CAP, which uses all CAP slots without a reserved gap. The ordering that makes it correct: the producer writes the slot, then publishes head with a release store; the consumer loads head with an acquire load, then reads the slot. Symmetrically the consumer reads the slot, then releases tail, and the producer acquires tail before reusing a slot. On weakly ordered hardware (Arm, Power) without those pairs the consumer can see the new head but stale slot data.

Terms

A release store guarantees every write the thread made before it is visible to a thread that sees that stored value with an acquire load of the same variable. Weakly ordered hardware may make a thread's writes visible to others in a different order than the program wrote them. False sharing is two threads writing different variables that sit on the same cache line, which makes the line bounce between cores.

Step by step

1. push: read own head (relaxed, no one else writes it); acquire-load tail; if head - tail == CAP the ring is full; plain-write the slot at head & MASK; release-store head + 1.
2. pop: read own tail (relaxed); acquire-load head; if equal the ring is empty; plain-read the slot; release-store tail + 1.
3. Subtraction on unsigned indices stays correct across wraparound as long as CAP divides the index range, which a power of two always does (and the mask replaces a slow modulo). Small trace with CAP = 4: after four pushes and no pops head = 4, tail = 0, so head - tail = 4 = CAP and the ring is full (slots 0 to 3 all hold items); after two pops tail = 2, head - tail = 2, so a push is allowed and writes slot 4 & 3 = 0; when head = tail = 4 the ring is empty. To see wraparound in small numbers, use 8-bit unsigned indices, which count 0 to 255 and then wrap to 0: with tail = 254 and head having wrapped to 2 (four pushes since tail), 2 - 254 wraps to 4 (-252 plus 256), so the subtraction still says 4 items in flight and the ring is full, and both indices point at slot 2 (254 & 3 = 2, 2 & 3 = 2) as they should. With a capacity of 3 the slot would be index % 3, index 255 maps to slot 0, but the next index after wrapping is 0 and also maps to slot 0, skipping slot 1: that is why CAP must divide the range. The real code uses size_t (64 bits), which takes far longer to wrap but follows the same rule.
4. Each call has no loop and no retry, so each operation finishes in a bounded number of steps: it is wait-free, which is why this design is used for latency-sensitive paths. Full and empty are reported to the caller, who decides whether to spin, drop or block.

Worked example: tested implementation

The two indices and the buffer each get their own 64-byte aligned region so the producer's writes to head do not invalidate the cache line the consumer is writing tail on. (64 bytes is a common cache line size; confirm it for your target.) The BROKEN switch turns every ordering into relaxed (atomic, but with no ordering against other reads and writes), to show what the pairs are for.

#include <atomic>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <thread>

#ifndef BROKEN
#define BROKEN 0
#endif
constexpr auto PUB_ORDER = BROKEN ? std::memory_order_relaxed : std::memory_order_release;
constexpr auto OBS_ORDER = BROKEN ? std::memory_order_relaxed : std::memory_order_acquire;

template <typename T, size_t CAP>            // CAP must be a power of two
class SpscRing {
    static_assert((CAP & (CAP - 1)) == 0, "capacity must be a power of two");
    static constexpr size_t MASK = CAP - 1;
public:
    bool push(const T& v) {                  // producer thread only
        size_t h = head_.load(std::memory_order_relaxed);        // only the producer writes head_
        size_t t = tail_.load(OBS_ORDER);                         // see the consumer's freed slots
        if (h - t == CAP) return false;                           // full: CAP items in flight
        buf_[h & MASK] = v;                                       // plain write into the slot
        head_.store(h + 1, PUB_ORDER);                            // publish the slot
        return true;
    }
    bool pop(T& out) {                       // consumer thread only
        size_t t = tail_.load(std::memory_order_relaxed);         // only the consumer writes tail_
        size_t h = head_.load(OBS_ORDER);                         // see the producer's published slots
        if (h == t) return false;                                 // empty
        out = buf_[t & MASK];                                     // plain read of the slot
        tail_.store(t + 1, PUB_ORDER);                            // hand the slot back
        return true;
    }
    static void print_layout() {
        printf("sizeof=%zu alignof=%zu offsetof(head_)=%zu offsetof(tail_)=%zu offsetof(buf_)=%zu\n",
               sizeof(SpscRing), alignof(SpscRing), offsetof(SpscRing, head_), offsetof(SpscRing, tail_), offsetof(SpscRing, buf_));
    }
private:
    alignas(64) std::atomic<size_t> head_{0};   // written by producer, own cache line
    alignas(64) std::atomic<size_t> tail_{0};   // written by consumer, own cache line
    alignas(64) T buf_[CAP];
};

int main() {
    static SpscRing<uint32_t, 1024> ring;
    SpscRing<uint32_t, 1024>::print_layout();
    constexpr uint32_t N = 2'000'000;
    std::thread prod([&] { for (uint32_t i = 0; i < N; ++i) while (!ring.push(i)) {} });
    uint32_t bad = 0, got = 0, v;
    std::thread cons([&] { while (got < N) if (ring.pop(v)) { if (v != got) ++bad; ++got; } });
    prod.join(); cons.join();
    printf("received %u items, out-of-order or corrupted: %u\n", got, bad);
}

g++ -std=c++20 -O2 -g -Wall -Wextra -fsanitize=thread spsc.cpp -o s && ./s (g++ 14.4.0, 64-bit Arm Linux container; also run at -O2 without TSan, same output):

sizeof=4224 alignof=64 offsetof(head_)=0 offsetof(tail_)=64 offsetof(buf_)=128
received 2000000 items, out-of-order or corrupted: 0

Reading the layout line: each alignas(64) member starts on a 64-byte boundary, so head_ sits at offset 0, tail_ at offset 64 and the slot array at offset 128. The two indices therefore live on different cache lines (the chunk of memory cores pass between their caches), which is the point of the padding, and alignof=64 is the strictest alignment of any member. The total checks out: 128 bytes of two padded indices plus 1,024 x 4 bytes of slots is 4,224, which is 66 x 64, a whole number of cache lines. With TSan (a data race detector) the correct version reports nothing. Compiling with -DBROKEN=1 -fsanitize=thread makes TSan report a data race between the producer's slot write in push and the consumer's slot read in pop: the first lines were WARNING: ThreadSanitizer: data race, Read of size 4 ... pop, Previous write of size 4 ... push. That is the missing release/acquire edge, found mechanically.

Other producer and consumer contexts

• Interrupt-handler producer, task consumer (embedded). An interrupt service routine (ISR) pushes, a task pops. On a single core the hardware does not reorder what the ISR and task see, but the compiler still may, so the index handoff must be an atomic or at least a volatile access (a qualifier telling the compiler every access must really happen as written; it gives no atomicity and no CPU ordering) plus a compiler barrier (an instruction to the compiler, not the CPU, not to move memory accesses across that point); std::atomic with release/acquire is a safe superset. If direct memory access (DMA, a hardware engine that copies memory without involving the CPU) or a second core is involved, hardware ordering matters again. No microcontroller was used here: the logic ran on the host only.
• Multiple producers. Two producers that both read head and write the same slot corrupt it, and a consumer can read a half-written entry. The fix is a different structure: each slot carries a sequence number (a counter stored beside the slot) that says "free for round k" or "full for round k"; producers claim an index with a CAS and publish by writing the sequence number with release; the consumer waits for the sequence number before reading. Fixed-size slots keep each claim independent.
• Latency tuning. Beyond padding: cache the other side's index locally and re-read it only when the ring looks full (or empty), so the shared line is touched rarely.

Pitfalls

Capacity not a power of two with a mask (silent wrong slot); using head == tail for both empty and full without a count or spare slot (here avoided by free-running indices); relaxed ordering that passes on x86-64 hardware and fails on Arm; padding omitted so false sharing hides in the benchmark; and sharing one ring between two producers because "it worked in the test".

Direct answer

A memory barrier (or fence) is a point that stops the compiler, the CPU, or both from moving memory accesses across it, so accesses before it become visible before accesses after it. It comes in two kinds: a compiler barrier (only constrains the compiler's reordering) and a hardware fence (the instruction that constrains the CPU, such as mfence on x86 or dmb on Arm; C++ gives a portable form, std::atomic_thread_fence). volatile is not a substitute because it only tells the compiler that each access is a visible side effect: the access must happen, as written, and cannot be merged or removed. It provides no atomicity (a 64-bit value can be torn on a 32-bit core: another thread or an interrupt sees half old, half new bits), no ordering against ordinary variables, and no CPU fence. volatile is needed for memory-mapped I/O registers (device control registers that appear as ordinary memory addresses, where reading or writing talks to hardware) and for same-thread signal/interrupt flags (flags set by a signal handler, a function the OS runs asynchronously in your thread, or an interrupt routine); it is not enough for sharing data between threads, where you need atomics or a lock.

What volatile does and does not do

The C++ reference puts the two sides this way: volatile accesses cannot be optimized out or reordered with another visible side effect, which "makes volatile objects suitable for communication with a signal handler, but not with another thread of execution".

Case where volatile is needed: a hardware status register

A memory-mapped register changes on its own and a read or write has an effect. Without volatile the compiler may read the status once and spin forever on the cached value. With volatile every iteration reloads it. The register addresses below are placeholders; this was compiled, not run, because there is no device here:

#include <stdint.h>
#define UART_STATUS (*(volatile uint32_t *)0x40011000u)   /* stub address, compile-only here */
#define UART_DATA   (*(volatile uint32_t *)0x40011004u)
#define TX_READY    (1u << 7)
void uart_put(uint8_t c) {
    while ((UART_STATUS & TX_READY) == 0) { }   /* every iteration performs a real load */
    UART_DATA = c;                              /* a real store with a hardware side effect */
}

gcc -O2 -Wall -c mmio.c -o mmio.o && objdump -d --no-show-raw-insn mmio.o (gcc 14.4.0, 64-bit Arm host build) gave a loop that reloads the status register on every pass:

0000000000000000 <uart_put>:
   0:	mov	x2, #0x1000                	// #4096
   4:	and	w0, w0, #0xff
   8:	movk	x2, #0x4001, lsl #16
   c:	ldr	w1, [x2]
  10:	tbz	w1, #7, c <uart_put+0xc>
  14:	str	w0, [x2, #4]
  18:	ret

Reading it: the first mov and the movk build the 32-bit address 0x40011000 in register x2 in two steps (mov sets the low part 0x1000, movk ... lsl #16 inserts 0x4001 into the upper 16 bits). and w0, w0, #0xff keeps only the low byte of c. ldr inside the loop (address c) is the real read of the register on each pass, tbz w1, #7, c means test bit 7 of the loaded value and branch back to c if it is zero (bit 7 is TX_READY, so this is the spin until the device is ready), and str at 14 is the real write to the data register. On a real microcontroller the processor and bus may also need a hardware barrier between device accesses in some sequences (the Arm barrier instructions: DMB orders memory accesses against each other, DSB is stronger and waits until earlier accesses have completed, and ISB makes the CPU refetch the instructions that follow, which matters after changing system settings; x86's mfence orders all earlier loads and stores before later ones). std::atomic_thread_fence is the portable way to order ordinary memory accesses between threads (GCC 14 on 64-bit Arm emitted dmb ish for a release fence and dmb ishld for an acquire fence), but it is not a way to request DSB or ISB, and it is not meant for ordering device accesses. For device registers use the platform's barrier facility (for example the CMSIS __DSB() and __ISB() intrinsics on Cortex-M, or the Linux kernel's mb() and readl()/writel() helpers) and consult the core's architecture manual for when your sequence needs one, because volatile alone does not insert them.

A second legitimate case is a flag shared between main code and an interrupt service routine (ISR) on one core: the ISR runs on the same core, so from the program's point of view the hardware keeps program order and the compiler is the main problem, which volatile solves for that one variable (for a flag shared with a C signal handler, the type the C standard blesses is volatile sig_atomic_t).

Cases where volatile is not enough

1. Data plus flag between threads. The producer sets data, then sets a flag; the consumer waits for the flag, then reads data. The flag being volatile does not order the ordinary store to data: the compiler may move it after the flag store, and on weakly ordered CPUs (Arm, Power: processors allowed to make one core's writes visible to others in a different order than written) the hardware may make it visible later:

#include <cstdio>
#include <thread>
int data = 0;
volatile bool ready = false;       // volatile: the compiler must re-read it, but nothing orders data
int main() {
    std::thread producer([] { data = 42; ready = true; });
    std::thread consumer([] { while (!ready) {} std::printf("data=%d\n", data); });
    producer.join(); consumer.join();
}

ThreadSanitizer (a data race detector) on g++ -O1 -g -fsanitize=thread vol_flag.cpp -o vf && ./vf printed two WARNING: ThreadSanitizer: data race reports (the flag and the data) and then data=42: it treats a volatile as a plain access, because the language does too. The fix is a release store and an acquire load on an atomic flag.

2. Read-modify-write. volatile int counter; counter++ is a read, an add and a write, not one step: two threads lose updates. It needs std::atomic<int>::fetch_add or a lock.

3. Wide values. A volatile uint64_t on a 32-bit core is two loads; an interrupt between them yields a torn value.

Portable fence expression, and weakly ordered CPUs

On Arm and Power, writes from one core can become visible in a different order from the one written, so "data then flag" needs either release/acquire on the flag or a pair of fences around a relaxed atomic flag. A fence is a barrier that is not tied to one variable: a release fence orders all of this thread's earlier reads and writes before any later store, and an acquire fence orders any earlier load before all later reads and writes; a release fence followed by a relaxed atomic store pairs with a relaxed atomic load followed by an acquire fence. The fence form, compiled and run (g++ 14.4.0, printed data=42):

#include <atomic>
#include <cstdio>
#include <thread>
int data = 0;
std::atomic<bool> ready{false};
int main() {
    std::thread producer([] {
        data = 42;
        std::atomic_thread_fence(std::memory_order_release);      // everything above ...
        ready.store(true, std::memory_order_relaxed);             // ... is ordered before this store
    });
    std::thread consumer([] {
        while (!ready.load(std::memory_order_relaxed)) {}
        std::atomic_thread_fence(std::memory_order_acquire);      // this load is ordered before everything below
        std::printf("data=%d\n", data);
    });
    producer.join(); consumer.join();
}

The release fence orders everything above it before the relaxed flag store; the acquire fence orders the flag load before everything below it. g++ warned 'atomic_thread_fence' is not supported with '-fsanitize=thread' when TSan was enabled, and the resulting binary printed one WARNING: ThreadSanitizer: data race on data followed by data=42. That report is a false positive: TSan does not model standalone fences, so it cannot see the synchronization the two fences provide, and it cannot validate this version either way. Prefer the release/acquire on the flag itself unless you need one fence to cover several relaxed stores.

Pitfalls

Treating volatile as "thread-safe" because it fixed a spin loop at -O2; using it for a counter; assuming ordering between a volatile flag and nearby ordinary data; and forgetting that the same volatile that is mandatory for a register is nothing more than a compiler hint for threads.

Direct answer

Compare-and-swap (CAS) is one atomic hardware operation (atomic means no other thread can ever observe it half done): "if the memory location currently holds expected, replace it with desired and report success; otherwise change nothing, report failure and tell me what is actually there." A CAS retry loop reads the current value, computes the new value from it, and tries to CAS; if another thread got in first the CAS fails, the loop re-reads and recomputes. It lets you build any single-word update without a lock. Its problems: the ABA problem, retry storms under contention (and starvation of an unlucky thread), spurious failures of the weak form, it only covers what fits in one atomic word, and the update must be safe to recompute.

How it works, step by step

C11 / C++ spell it atomic_compare_exchange_* / compare_exchange_*. cppreference says that on failure the actual value is loaded into expected, so the loop does not need a separate re-read. On x86-64, GCC 14 emits lock cmpxchg for the strong form (compiling atomic_compare_exchange_strong for x86-64 shows it); on ARM it is built from a load-exclusive / store-exclusive pair.

Trace with concrete values: in_use is 5 and CAP is 8. Threads A and B both read cur = 5. A runs CAS(expected 5, desired 6): memory holds 5, so it succeeds and in_use becomes 6. B then runs CAS(expected 5, desired 6): memory holds 6, not 5, so it fails, writes the real value 6 into its cur, and changes nothing. B loops: 6 < 8, so it computes 7 and runs CAS(expected 6, desired 7), which succeeds. The failed attempt cost B one retry, and no increment was lost.

Example: allow at most CAP requests in flight, an "increment unless at the cap" that a plain atomic add cannot express (it has no "unless"):

#include <pthread.h>
#include <stdatomic.h>
#include <stdbool.h>
#include <stdio.h>
#define CAP 1000000
#define THREADS 4
#define TRIES 400000
static atomic_int in_use = 0;
static atomic_long retries = 0;
static atomic_int refused = 0;

/* Increment in_use unless it is already CAP. A plain fetch_add cannot express the "unless". */
static bool try_acquire(void) {
    int cur = atomic_load_explicit(&in_use, memory_order_relaxed);
    for (;;) {
        if (cur >= CAP) return false;
        /* On failure, compare_exchange_weak writes the value it actually saw into cur. */
        if (atomic_compare_exchange_weak_explicit(&in_use, &cur, cur + 1,
                memory_order_acq_rel, memory_order_relaxed))
            return true;
        atomic_fetch_add_explicit(&retries, 1, memory_order_relaxed);
    }
}
static void *worker(void *a) {
    (void)a;
    for (int i = 0; i < TRIES; i++) if (!try_acquire()) atomic_fetch_add(&refused, 1);
    return NULL;
}
int main(void) {
    pthread_t t[THREADS];
    for (int i = 0; i < THREADS; i++) pthread_create(&t[i], NULL, worker, NULL);
    for (int i = 0; i < THREADS; i++) pthread_join(t[i], NULL);
    printf("attempts=%d in_use=%d refused=%d retried_at_least_once=%s\n",
           THREADS * TRIES, atomic_load(&in_use), atomic_load(&refused),
           atomic_load(&retries) > 0 ? "yes" : "no");
    return 0;
}

gcc -O2 -Wall -Wextra -fsanitize=thread -pthread cas.c -o cs && ./cs, three runs in a gcc:14 container (aarch64), identical results every time:

attempts=1600000 in_use=1000000 refused=600000 retried_at_least_once=yes
attempts=1600000 in_use=1000000 refused=600000 retried_at_least_once=yes
attempts=1600000 in_use=1000000 refused=600000 retried_at_least_once=yes

The invariant holds (in_use never exceeds CAP even though four threads race), the count of refusals is exact (1,600,000 - 1,000,000 = 600,000), and at least one CAS lost a race and retried. How many retries happen varies from run to run, so the program prints only whether any occurred. A CAS loop is only exercised under real contention: in an earlier run of the same program with 2,000 attempts in total, no CAS ever failed because the threads barely overlapped.

Weak versus strong

compare_exchange_weak "is allowed to fail spuriously": it may report failure even when the values were equal, because on load-exclusive / store-exclusive machines the store can fail if the reservation (the CPU's note that nobody else touched this location since the load-exclusive) was lost, for example after an interrupt or when another core wrote nearby. compare_exchange_strong must retry internally and only fails when the values really differed. In a loop that retries anyway, use weak; use strong when a spurious failure would be costly or you are not in a loop.

What can go wrong

1. ABA. CAS compares values, not history. If another thread changes A to B and back to A, your CAS succeeds although the structure changed underneath you. It matters for pointers in linked structures, not for a plain counter. Concrete case, a stack whose top is node A with A pointing to B: thread 1 reads top = A and next = B, then is paused. Thread 2 pops A, pops B (and frees it), then pushes A back, so the top is A again and A now points to something else. Thread 1 resumes and runs CAS(top, expected A, desired B): the top is A, so it succeeds, and the stack's top is now the freed node B.
   Ways out of ABA. (a) Version-tag the word: pack a counter next to the pointer (or use a double-width CAS) and bump it on every change, so A-with-version-7 no longer equals A-with-version-9; the cost is a wider atomic and the counter can in principle wrap. (b) Defer reclamation so a node cannot be freed and reused while any thread may still hold a pointer to it: hazard pointers (each thread publishes the pointers it is about to use) or epoch-based reclamation (free only after every thread has moved past the epoch in which the node was unlinked). (c) In a garbage-collected language the node cannot be freed under you, which removes the freed-memory form of the bug, but a recycled or reused object (for example from a free list) can still produce ABA. (d) Avoid the pattern: use a lock, or an immutable snapshot swapped by one pointer CAS. Version tags fix the symptom (a stale value matching); deferred reclamation fixes the cause for pointers (the address is not reused while in use).
2. Contention. Under many writers most CAS attempts fail and redo their work. The structure as a whole keeps making progress (that is what lock-free means: some thread always succeeds), but an individual thread can lose repeatedly, so it can starve (never get its turn although the system as a whole progresses). Wait-free is the stronger promise that every thread finishes in a bounded number of steps, which a plain CAS retry loop does not give. Each failed attempt also bounces the cache line (the 64-byte block of memory that cores hand back and forth to own it for writing) between cores.
3. Recompute must be safe. Everything between the load and the CAS runs possibly many times, so it must have no side effects (no allocation you forget to free, no logging, no I/O). Compute desired purely from expected.
4. One word only. Two fields cannot be updated by one CAS unless packed into one word (or a double-width CAS exists, an instruction that compares and swaps two adjacent words at once, not available on every CPU). Multi-field invariants need a lock or a redesign such as swapping a pointer to an immutable snapshot.
5. Memory ordering. The ordering you pass decides what other data the successful CAS publishes to other threads. Relaxed ordering guarantees only that the atomic itself is indivisible, with no promise about other memory; acquire-release makes a successful CAS publish the writes before it and lets the next acquirer see them. The demo counts slots and hands over no other data, so relaxed ordering would be enough; it uses acquire-release on success so the same loop stays correct if the slot guards data (acquiring a slot then sees what the previous releaser wrote).

Pitfalls and judgement

Prefer a built-in atomic add/or/exchange when one fits (on many CPUs the hardware does it as a single instruction with no retry loop, for example lock xadd on x86). Reach for a CAS loop when the update is conditional or computed. Reach for a mutex when the state is more than one word or the section is long.

Direct answer

Priority inheritance fixes priority inversion: a high-priority task H blocks on a mutex held by a low-priority task L, and a medium-priority task M that does not need the mutex keeps pre-empting L, so H effectively waits on M. The fix is that while H is blocked on L's mutex, L runs at H's priority (L inherits it). When L releases the mutex, L drops back to the priority its remaining locks justify, and the mutex goes to the highest-priority waiter. The mutex must therefore remember its owner and its waiters, and each task must remember its base priority, its current effective priority, the mutex it waits on, and the mutexes it holds.

State the design keeps

Convention here: a larger number means a higher priority.

Acquire and release

Acquire (pi_lock). If the mutex is free, take it. Otherwise record blocked_on, add the caller to the waiters, then propagate: set the owner's eff_prio to the caller's if that is higher; if that owner is itself blocked on another mutex, move to that mutex's owner and repeat. Stop when the next owner already has an equal or higher priority, when the owner is not blocked, or when you come back to the caller (a cycle, which is a deadlock: undo the wait and report it).

Release (pi_unlock). Remove the mutex from the owner's held list. Give it to the highest-priority waiter, who becomes the owner and stops being blocked. Then recompute the old owner: max(base_prio, highest waiter on each mutex it still holds). This is the nested-locks rule: a task holding two mutexes must not fall to its base priority when it releases one if a high-priority task still waits on the other.

Bounding the adjustments.

• Each task waits for at most one mutex, so the chain is a simple path and the walk visits each task at most once. Its length is bounded by the number of tasks, and a cycle is detected instead of looped on. The code also has a hard hop limit as a second guard.
• A boost is a copy of an existing priority, never an increase, so no task can exceed the highest priority present.
• Time spent blocked is bounded by the critical sections along the chain, so keep critical sections short and do not call blocking functions while holding a lock.
• Linux's real-time mutex does the same kind of chain walk, and the kernel's rt-mutex design document says that, to prevent denial-of-service attacks, it holds at most two different locks at a time while it walks the chain: it lets go of the earlier locks as it moves along, rather than holding every lock in the chain at once.

Worked example, compiled and run on the host model

This is a model of the kernel-side bookkeeping, with no real scheduler and no real blocking, so every state change can be asserted. It was compiled and run on a Linux container (not on an RTOS or microcontroller): gcc -std=c11 -O1 -Wall -Wextra -Wno-missing-field-initializers -fsanitize=address,undefined pimutex.c -o pi && ./pi. The model has no waiter timeouts and no priority-change calls; a real kernel must re-run the same recompute along the chain on either.

#include <assert.h>
#include <stdio.h>

/* Larger number = higher priority. This models the kernel-side bookkeeping only
   (no real scheduler, no real blocking), so every state change can be checked. */
#define MAX_TASKS 8
#define MAX_HELD 4
#define MAX_WAIT 4

typedef struct mutex mutex_t;
typedef struct task {
    const char *name;
    int base_prio;            /* never changed by inheritance */
    int eff_prio;             /* what the scheduler uses */
    mutex_t *blocked_on;      /* at most one: a task waits on one mutex at a time */
    mutex_t *held[MAX_HELD];
    int nheld;
} task_t;

struct mutex {
    const char *name;
    task_t *owner;
    task_t *waiters[MAX_WAIT];
    int nwait;
};

static int highest_waiter_prio(const mutex_t *m) {
    int p = -1;
    for (int i = 0; i < m->nwait; i++) if (m->waiters[i]->eff_prio > p) p = m->waiters[i]->eff_prio;
    return p;
}

/* eff = max(base, highest-priority waiter on ANY mutex still held) */
static void recompute(task_t *t) {
    int p = t->base_prio;
    for (int i = 0; i < t->nheld; i++) {
        int w = highest_waiter_prio(t->held[i]);
        if (w > p) p = w;
    }
    t->eff_prio = p;
}

/* Walk owner -> the mutex the owner waits on -> its owner ... raising priorities.
   The walk is bounded: it visits each task at most once and stops on a cycle (deadlock). */
static int propagate(task_t *from, int *depth) {
    mutex_t *m = from->blocked_on;
    int hops = 0;
    while (m && m->owner) {
        task_t *o = m->owner;
        if (o == from) return -1;                 /* cycle: report deadlock, do not loop */
        hops++;
        if (hops > MAX_TASKS) return -1;          /* defensive hard bound */
        if (o->eff_prio >= from->eff_prio) break; /* nothing more to raise down the chain */
        o->eff_prio = from->eff_prio;
        m = o->blocked_on;
    }
    *depth = hops;
    return 0;
}

/* returns 1 if acquired, 0 if the caller must block, -1 if blocking would deadlock */
static int pi_lock(task_t *t, mutex_t *m) {
    if (!m->owner) { m->owner = t; t->held[t->nheld++] = m; return 1; }
    t->blocked_on = m;
    m->waiters[m->nwait++] = t;
    int depth = 0;
    if (propagate(t, &depth) < 0) {               /* undo and report */
        m->nwait--; t->blocked_on = NULL;
        /* the failed walk already raised owners along the chain: recompute them, nearest first */
        int guard = 0;
        for (mutex_t *w = m; w && w->owner && guard < MAX_TASKS; w = w->owner->blocked_on, guard++)
            recompute(w->owner);
        return -1;
    }
    return 0;
}

/* returns the new owner (highest-priority waiter) or NULL */
static task_t *pi_unlock(task_t *t, mutex_t *m) {
    assert(m->owner == t);
    int k = 0;                                    /* drop m from t's held list */
    for (int i = 0; i < t->nheld; i++) if (t->held[i] != m) t->held[k++] = t->held[i];
    t->nheld = k;
    task_t *next = NULL; int bi = -1;
    for (int i = 0; i < m->nwait; i++)
        if (!next || m->waiters[i]->eff_prio > next->eff_prio) { next = m->waiters[i]; bi = i; }
    if (next) {
        m->waiters[bi] = m->waiters[--m->nwait];
        next->blocked_on = NULL;
        m->owner = next; next->held[next->nheld++] = m;
    } else m->owner = NULL;
    recompute(t);                                 /* deboost: only to what the OTHER held mutexes still justify */
    if (next) recompute(next);
    return next;
}

#define SHOW(t) printf("  %-4s base=%d eff=%d\n", (t)->name, (t)->base_prio, (t)->eff_prio)

int main(void) {
    task_t H = {"H", 30, 30}, M = {"M", 20, 20}, L = {"L", 10, 10};
    mutex_t A = {"A"}, B = {"B"};

    puts("1) basic inversion: L holds A, H blocks on A");
    assert(pi_lock(&L, &A) == 1);
    assert(pi_lock(&H, &A) == 0);
    SHOW(&L); assert(L.eff_prio == 30);          /* M (20) can no longer preempt L */
    assert(L.eff_prio > M.base_prio);

    puts("2) release restores base priority and hands A to H");
    task_t *n = pi_unlock(&L, &A);
    assert(n == &H); SHOW(&L); SHOW(&H);
    assert(L.eff_prio == 10);
    pi_unlock(&H, &A);

    puts("3) nested chain: L holds B; M holds A and waits on B; H waits on A");
    assert(pi_lock(&L, &B) == 1);
    assert(pi_lock(&M, &A) == 1);
    assert(pi_lock(&M, &B) == 0);                 /* M blocked on B, owner L -> L = 20 */
    assert(L.eff_prio == 20);
    assert(pi_lock(&H, &A) == 0);                 /* H blocked on A, owner M -> M = 30 -> L = 30 */
    SHOW(&M); SHOW(&L);
    assert(M.eff_prio == 30 && L.eff_prio == 30);

    puts("4) L releases B: L drops to base, M gets B and stays at 30 because H still waits on A");
    n = pi_unlock(&L, &B);
    assert(n == &M); SHOW(&L); SHOW(&M);
    assert(L.eff_prio == 10 && M.eff_prio == 30);

    puts("5) multiple held mutexes: deboost only as far as remaining waiters allow");
    task_t P = {"P", 5, 5}, Q = {"Q", 15, 15}, R = {"R", 28, 28};
    mutex_t C = {"C"}, D = {"D"};
    assert(pi_lock(&P, &C) == 1 && pi_lock(&P, &D) == 1);
    assert(pi_lock(&Q, &C) == 0);  assert(P.eff_prio == 15);
    assert(pi_lock(&R, &D) == 0);  assert(P.eff_prio == 28);
    pi_unlock(&P, &D);             SHOW(&P); assert(P.eff_prio == 15);   /* Q still waits on C */
    pi_unlock(&P, &C);             SHOW(&P); assert(P.eff_prio == 5);

    puts("6) a lock cycle is detected, not looped on");
    task_t U = {"U", 12, 12}, V = {"V", 14, 14};
    mutex_t E = {"E"}, F = {"F"};
    assert(pi_lock(&U, &E) == 1 && pi_lock(&V, &F) == 1);
    assert(pi_lock(&U, &F) == 0);
    int r = pi_lock(&V, &E);
    printf("  V tries E -> %d (-1 = would deadlock)\n", r);
    assert(r == -1);
    SHOW(&U); SHOW(&V);                           /* the failed attempt must leave no boost behind */
    assert(U.eff_prio == 12 && V.eff_prio == 14);
    puts("all checks passed");
    return 0;
}

Output:

1) basic inversion: L holds A, H blocks on A
  L    base=10 eff=30
2) release restores base priority and hands A to H
  L    base=10 eff=10
  H    base=30 eff=30
3) nested chain: L holds B; M holds A and waits on B; H waits on A
  M    base=20 eff=30
  L    base=10 eff=30
4) L releases B: L drops to base, M gets B and stays at 30 because H still waits on A
  L    base=10 eff=10
  M    base=20 eff=30
5) multiple held mutexes: deboost only as far as remaining waiters allow
  P    base=5 eff=15
  P    base=5 eff=5
6) a lock cycle is detected, not looped on
  V tries E -> -1 (-1 = would deadlock)
  U    base=12 eff=12
  V    base=14 eff=14
all checks passed

Every assert passed. How propagate works, line by line: it starts at the task that just blocked (from) and looks at the mutex it waits on, m. The loop body takes that mutex's owner o; if o is from the chain has come back to the start, which is the cycle, so it returns -1; if o already has equal or higher priority nothing more needs raising, so it breaks; otherwise it copies from's priority into o and moves on to the mutex o itself waits on. hops counts steps and is capped at MAX_TASKS as a second guard. Case 6 in words: U holds E and V holds F. U asks for F and blocks (V already has priority 14 so nothing is raised). V then asks for E: the walk goes to E's owner U, raises U to 14, then to the mutex U waits on, F, whose owner is V, the caller, so it reports the cycle and -1. The failed attempt had raised U, so pi_lock recomputes the owners along the chain before returning, and the printed U and V lines show that no boost was left behind (U back at 12). Case 3 is the nested chain (H waits for M who waits for L, so L reaches 30). Case 4 shows M keeps 30 after receiving B because H still waits on A. Case 5 shows the deboost stops at 15, not at the base 5, while Q still waits on C.

Trade-offs and pitfalls

• Inheritance does not prevent deadlock. The cycle case simply detects it. Preventing it needs a lock ordering rule. A priority ceiling protocol (every mutex has a ceiling equal to its highest-priority user) is the other classic fix: if a mutex is used by tasks at priorities 10 and 30, its ceiling is 30, and any task that locks it runs at 30 for the whole critical section, so no medium-priority task can preempt it, and no waiting is needed to trigger the boost.
• Never lock it from an interrupt handler. An ISR (interrupt service routine, the code the CPU runs when a hardware event fires) is not a schedulable task with a priority to inherit, and it cannot block.
• Cost. Chain walks happen in the slow path (when blocked), and the fast path is one atomic operation. The price is bookkeeping and a longer slow path.
• Pitfall. Forgetting to recompute from the remaining held mutexes on release leaves a task boosted forever, or drops it too early. Case 5 is the test that catches it.

Direct answer

Give every slot a sequence number that says whose turn it is: at the start slot i holds i, meaning "free for the producer at position i". Producers claim a position by CAS (compare-and-swap: write a new value only if the current value is still what I last read) on a shared enqueue counter, write the data, then store pos + 1 into the slot's sequence ("full, for the consumer at pos"). Consumers claim a position the same way on a dequeue counter, read the data, then store pos + capacity ("free again, next lap"). Full and empty are not tracked by a separate count: they fall out of comparing the slot's sequence to the position you want. No allocation, no locks, only 32-bit atomics.

Terms used below: a weakly ordered core is one whose hardware may make memory operations visible to other cores in a different order from the program order (Arm cores are like this, x86 is stricter); Cortex-M is Arm's family of small 32-bit microcontroller cores; a lap is one pass around the ring, so position 8 in an 8-slot ring is lap 1 of slot 0; acquire, release and relaxed are C11 memory orders, where a release store makes earlier writes visible to a thread whose acquire load reads that stored value, and relaxed gives atomicity only.

Slot protocol

Let cap be a power of two, pos a 32-bit position counter, slot = buf[pos & (cap-1)].

A trace with cap = 4: the sequence numbers start as [0, 1, 2, 3], enq = deq = 0.

1. Push at pos = 0: slot 0 has seq = 0, the difference is 0, so CAS enq 0 to 1, write the data, and set seq = 1 (published).
2. Pop at pos = 0: slot 0 has seq = 1, and pos + 1 = 1, difference 0, so CAS deq 0 to 1, read the data, and set seq = 0 + 4 = 4 (free for the next lap).
3. Pop at pos = 1 on an empty queue: slot 1 has seq = 1, pos + 1 = 2, difference 1 - 2 = -1, which is below zero, so the queue is empty.
4. Next lap: suppose positions 1 to 3 have also been pushed and popped, so enq = deq = 4. A push at pos = 4 finds slot 4 & 3 = 0 with seq = 4 (set in step 2), difference 0, so it is free again.
5. Full: starting again from a fresh queue, four pushes and no pops leave seq = [1, 2, 3, 4] and enq = 4. A push at pos = 4 finds slot 0 with seq = 1, difference 1 - 4 = -3, below zero: full.

Wraparound: positions are unsigned 32-bit numbers that wrap at 2^32, so the code compares with the signed difference (int32_t)(seq - pos). That is correct as long as the capacity is far below 2^31 and positions never get that far apart, which holds because at most cap positions are outstanding. Example with cap = 8 just after the position counter wrapped: a producer at pos = 2 looks at slot 2, which still holds the item published at position 0xFFFFFFFA (that is 8 positions earlier, 2 - 8 modulo 2^32), so its seq is 0xFFFFFFFA + 1 = 0xFFFFFFFB. Then seq - pos is 0xFFFFFFF9 as unsigned, which read as signed 32-bit is -7: correctly negative, so the slot is still full from the previous lap. Plain unsigned comparison would call 0xFFFFFFFB huge and bigger than 2, which is wrong. The power-of-two capacity lets pos & (cap - 1) pick the slot cheaply, because the low bits of pos are then the slot index.

Worked example, compiled and run

Four producer threads push 50,000 values each, four consumer threads pop them, and the program checks that every one of the 200,000 values arrived exactly once and that each consumer saw each producer's values in increasing order. The capacity is 8, so the queue is full or empty constantly and the retry paths get exercised.

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

#define CAP 8u                       /* power of two */
#define MASK (CAP - 1u)

#ifdef BROKEN
#define PUBLISH_ORDER memory_order_relaxed   /* deliberately wrong, to show what TSan reports */
#else
#define PUBLISH_ORDER memory_order_release
#endif

typedef struct { atomic_uint seq; uint32_t data; } cell_t;
typedef struct {
    cell_t buf[CAP];
    atomic_uint enq;                 /* next position a producer will claim */
    atomic_uint deq;                 /* next position a consumer will claim */
} mpmc_t;

static void q_init(mpmc_t *q) {
    for (uint32_t i = 0; i < CAP; i++) atomic_init(&q->buf[i].seq, i);   /* cell i is free for lap 0 */
    atomic_init(&q->enq, 0); atomic_init(&q->deq, 0);
}

static int q_push(mpmc_t *q, uint32_t v) {
    uint32_t pos = atomic_load_explicit(&q->enq, memory_order_relaxed);
    for (;;) {
        cell_t *c = &q->buf[pos & MASK];
        uint32_t seq = atomic_load_explicit(&c->seq, memory_order_acquire);
        int32_t dif = (int32_t)(seq - pos);
        if (dif == 0) {              /* cell is free for exactly this position: try to claim it */
            if (atomic_compare_exchange_weak_explicit(&q->enq, &pos, pos + 1,
                    memory_order_relaxed, memory_order_relaxed)) {
                c->data = v;                                            /* we own the cell */
                atomic_store_explicit(&c->seq, pos + 1, PUBLISH_ORDER);  /* hand it to consumers */
                return 1;
            }                        /* CAS failure reloaded pos; loop */
        } else if (dif < 0) {
            return 0;                /* cell still holds last lap's item: queue full */
        } else {
            pos = atomic_load_explicit(&q->enq, memory_order_relaxed);   /* another producer moved on */
        }
    }
}

static int q_pop(mpmc_t *q, uint32_t *out) {
    uint32_t pos = atomic_load_explicit(&q->deq, memory_order_relaxed);
    for (;;) {
        cell_t *c = &q->buf[pos & MASK];
        uint32_t seq = atomic_load_explicit(&c->seq, memory_order_acquire);
        int32_t dif = (int32_t)(seq - (pos + 1));
        if (dif == 0) {              /* producer has published position pos */
            if (atomic_compare_exchange_weak_explicit(&q->deq, &pos, pos + 1,
                    memory_order_relaxed, memory_order_relaxed)) {
                *out = c->data;
                atomic_store_explicit(&c->seq, pos + CAP, memory_order_release);  /* free for the next lap */
                return 1;
            }
        } else if (dif < 0) {
            return 0;                /* not yet published: queue empty */
        } else {
            pos = atomic_load_explicit(&q->deq, memory_order_relaxed);
        }
    }
}

#define PRODUCERS 4
#define CONSUMERS 4
#define PER_PRODUCER 50000u

static mpmc_t q;
static atomic_uint seen[PRODUCERS * PER_PRODUCER];   /* one slot per item: counts how often it was received */
static atomic_uint consumed;
static atomic_uint order_violations;

static void *producer(void *arg) {
    uint32_t id = (uint32_t)(uintptr_t)arg;
    for (uint32_t i = 0; i < PER_PRODUCER; i++)
        while (!q_push(&q, id * PER_PRODUCER + i)) { }       /* spin while full */
    return NULL;
}

static void *consumer(void *arg) {
    (void)arg;
    uint32_t last[PRODUCERS]; memset(last, 0xff, sizeof last);   /* last index seen per producer, 0xffffffff = none */
    while (atomic_load(&consumed) < PRODUCERS * PER_PRODUCER) {
        uint32_t v;
        if (q_pop(&q, &v)) {
            atomic_fetch_add(&seen[v], 1);
            uint32_t p = v / PER_PRODUCER, i = v % PER_PRODUCER;
            if (last[p] != 0xffffffffu && i <= last[p]) atomic_fetch_add(&order_violations, 1);
            last[p] = i;
            atomic_fetch_add(&consumed, 1);
        }
    }
    return NULL;
}

int main(void) {
    q_init(&q);
    printf("sizeof(cell_t)=%zu sizeof(mpmc_t)=%zu\n", sizeof(cell_t), sizeof(mpmc_t));
    pthread_t t[PRODUCERS + CONSUMERS];
    for (uintptr_t i = 0; i < PRODUCERS; i++) pthread_create(&t[i], NULL, producer, (void *)i);
    for (int i = 0; i < CONSUMERS; i++) pthread_create(&t[PRODUCERS + i], NULL, consumer, NULL);
    for (int i = 0; i < PRODUCERS + CONSUMERS; i++) pthread_join(t[i], NULL);
    unsigned lost = 0, dup = 0;
    for (uint32_t i = 0; i < PRODUCERS * PER_PRODUCER; i++) {
        unsigned n = atomic_load(&seen[i]);
        if (n == 0) lost++; else if (n > 1) dup++;
    }
    printf("items=%u consumed=%u lost=%u duplicated=%u per-producer-order-violations=%u\n",
           PRODUCERS * PER_PRODUCER, atomic_load(&consumed), lost, dup, atomic_load(&order_violations));
    return 0;
}

Run in a gcc:14 container on aarch64 (a weakly ordered architecture) with gcc -std=c11 -O2 -Wall -Wextra -fsanitize=thread mpmc.c -o mpmc -pthread && ./mpmc, then the same with -DBROKEN (the data-publishing store made relaxed instead of release):

sizeof(cell_t)=8 sizeof(mpmc_t)=72
items=200000 consumed=200000 lost=0 duplicated=0 per-producer-order-violations=0
==================
WARNING: ThreadSanitizer: data race (pid=27)
  Read of size 4 at 0x0000004200b4 by thread T5:
    #0 consumer <null> (mpmc_bad+0x400d2c)
    #1 <null> <null> (libtsan.so.2+0x4fb60)

  Previous write of size 4 at 0x0000004200b4 by thread T1:
    #0 producer <null> (mpmc_bad+0x400e80)
    #1 <null> <null> (libtsan.so.2+0x4fb60)

  Location is global 'q' of size 72 at 0x0000004200a0 (mpmc_bad+0x4200b4)

The correct build prints no ThreadSanitizer report and passes the check. The -DBROKEN build reports a data race between the consumer's read of the slot data and the producer's earlier write (the report prints addresses that change from run to run, so only the first lines are shown). How to read it: Read of size 4 ... by thread T5 with consumer as the function is the unordered read; Previous write of size 4 ... by thread T1 in producer is the write it raced with; both are at the same address; Location is global 'q' says it is inside the queue object, and the address minus the start of q is 0x14 (20) in the report shown, which is inside the third cell (buf[2], cells being 8 bytes) at its data field (in a re-run the offset was 0x24, the data field of buf[4]: which cell is hit varies, the field does not). So the data write and the data read had no happens-before edge between them. That is exactly what the release store prevents: without it nothing orders the data write before the consumer's read.

What was run and what was not: the logic and ordering ran on the host container under ThreadSanitizer. The target here is arm64 (AArch64), not a Cortex-M, so no 32-bit Thumb code was generated or run. The struct is 8 bytes (a 4-byte atomic_uint and a 4-byte uint32_t), and those widths do not change on a 32-bit ARM core.

Ordering on a weakly ordered core

• The release store of the sequence number is what makes the data write visible to whoever later reads that sequence with an acquire load. cppreference defines the pair: everything written before the release store becomes visible after the acquire load that reads the stored value.
• The position counters use relaxed operations because they only need atomicity: the CAS decides who owns a slot, and the sequence number carries the ordering.
• On a single-core Cortex-M, tasks and interrupt handlers interleave on one CPU, so compiler reordering is usually the main hazard, and acquire and release also constrain the compiler. On a multi-core part, or with DMA reading the buffer, they must also produce real barriers; the compiler does that for you when you use the C11 orders, which is why you write orders and not barrier instructions by hand.
• Your CAS needs hardware support. Check the core's reference manual for exclusive load/store (a pair where the store succeeds only if nobody touched the location since the load) or compare-and-swap instructions. Without them, a 32-bit CAS is emulated by briefly masking interrupts or taking a hardware lock, and the structure stops being lock-free.

Progress guarantee: not wait-free, and lock-free only for the claim step

• Not wait-free. A thread's CAS can lose to another thread's CAS any number of times, so there is no bound on the steps one call takes.
• The claim step is lock-free: a strong CAS fails only because another thread's CAS succeeded, so the system as a whole progresses. The code uses compare_exchange_weak, which may also fail spuriously (on Arm exclusive load/store cores when the exclusive monitor is lost, which the architecture permits for several reasons); the loop just retries, and that does not change the argument, since no thread is stalled holding anything.
• A caveat to state out loud. Claiming a slot and publishing into it are two steps. If a producer is preempted after its CAS and before storing pos+1, consumers reaching that slot see "not published" and report empty, even if later slots are full. In the strict textbook sense that means the queue is blocking on that producer. It is the standard cost of this design. Do not hide it.
• Consequence in an ISR. Never spin on "full" inside an interrupt handler: if the consumer is a lower-priority task that the handler preempted, it can never run, and the handler spins forever. Use the non-blocking return value and drop or count the item.

ABA and wraparound

Each slot's sequence advances by cap on every lap, so a slot's state is never confused with its state a lap earlier: that is the per-slot ABA protection (ABA: a CAS succeeds because the value looks unchanged although it was changed and changed back). The shared counters can still wrap: a thread that reads enq as p, is suspended while 2^32 further positions are claimed, and then CAS-es p to p+1 would succeed against a slot that is now in a different state. That needs 2^32 claims during one suspension. It is not impossible on a fast producer (at one million pushes a second, about 71 minutes), so state it as a bound, not as zero. 64-bit counters push it out of reach but need 64-bit atomics, which 32-bit Cortex-M cores do not provide.

Pitfalls

• Capacity must be a power of two so the mask works; non-power-of-two needs a modulo.
• "Full" is conservative: it also fires while a consumer has claimed a slot but not yet released it.
• Place the two counters on separate cache lines on cores with caches, or producers and consumers slow each other (false sharing: unrelated variables on one cache line make cores keep taking ownership of that line from each other).
• If a single producer or single consumer is enough, a single-producer single-consumer ring needs no CAS at all and is simpler to prove.