Home › Concurrency

Concurrency

Memory ordering, lock-free structures, memory reclamation and scheduling.

Memory model

What atomics really guarantee.

Memory ordering

low

What Relaxed, Acquire, Release and SeqCst atomics actually guarantee, what they cost on x86 and ARM, and which one each pattern needs.

False sharing

low

Independent variables written by different cores on one cache line force the line to bounce between cores; pad or regroup hot data to fix it.

Locks

Blocking synchronization done right.

Futex-based mutex

low

A mutex that is one atomic word in user space and enters the kernel (futex wait/wake) only under contention; how std and glibc locks work.

uncontended lock+unlock 2 atomic RMWs, no syscall; contended adds 1 wait and 1 wake syscall

Seqlock

low

Readers copy shared data optimistically and retry if a sequence counter changed; zero reader writes, so reads scale perfectly with a single fast writer.

read O(size) plus retries, no shared writes; write O(size) plus 2 counter stores

spinlocks ticket mcs

Planned.

counting semaphore

Planned.

priority inheritance

Planned.

Lock-free structures

Progress without locks.

MPMC bounded queue

low

Vyukov's array queue for many producers and consumers: each slot carries a sequence number, so one CAS per operation claims a slot without locks.

push/pop O(1) expected, one CAS each; contention scales with the number of threads hitting one counter

Sharded counters

low

Split one hot counter into per-core or per-thread cells on separate cache lines; increments stay local and reads sum the cells.

increment O(1) with no shared-line contention; read O(shards)

shared memory ipc

Planned.

Memory reclamation

Freeing memory other threads may still read.

Epoch-based reclamation

low

Threads announce a global epoch while touching shared lock-free data; garbage retired in epoch e is freed once the epoch reaches e + 2.

pin/unpin O(1) (one store + one fence); epoch advance O(threads); reclamation amortized O(1) per retired object

Hazard pointers

low

Readers publish the exact pointers they are about to dereference; a reclaimer frees retired objects that no published hazard names, giving bounded garbage.

protect O(1) with a store-load fence; retire amortized O(1) with scan threshold R = 2H; unreclaimed objects ≤ O(threads × R)

RCU (read-copy-update)

low

Readers access shared data with no locks or atomic writes; writers publish a new copy and free the old one after a grace period.

read side O(1) with zero shared writes; update O(copy) plus one grace period (order of ms in the kernel)

Task scheduling

Spreading work over cores.

Work-stealing deque

medium

Per-worker deque: the owner pushes and pops at the bottom without contention, idle workers steal from the top; the core of Rayon, Tokio and Go.

push O(1) no RMW; pop O(1) with one fence (CAS only on the last item); steal O(1) with one CAS

cooperative scheduling

Planned.

fibers stackful coroutines

Planned.

async io runtime

Planned.

thread per core

Planned.

Actor model

medium

Isolated units of state that interact only by queued messages and handle one at a time: no locks on state, and the same code runs local or remote.

send O(1); receive O(1) FIFO, O(queue) for selective receive; memory O(actors + queued messages)

Supervision trees

medium

Workers crash on surprises; supervisors only start, watch and restart them, with a restart-rate limit that escalates to their parent.

restart O(affected children); intensity check O(1) amortized; stop is sequential, bounded by each child's shutdown timeout