Concurrency Primitives#

flowchart LR
  M([Mutex / Lock])
  S([Semaphore])
  RW([RW Lock])
  CV([Condition Var])
  A([Atomic])
  TL([Thread-local])

  Threads --> M
  Threads --> S
  Threads --> RW
  Threads --> CV
  Threads --> A
  Threads --> TL

  classDef p fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
  classDef s fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
  class Threads p;
  class M,S,RW,CV,A,TL s;

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class M,S,RW,CV,A,TL service;

The low-level toolbox for sharing state safely across threads: mutexes, semaphores, RW locks, condition variables, atomics, and thread-local storage.

flowchart TB
  subgraph Mutual_Exclusion[Mutual exclusion]
    MTX([Mutex / Lock<br/>one holder])
    SPIN([Spinlock<br/>busy-wait])
    REC([Reentrant lock])
  end

  subgraph Capacity[Capacity]
    SEM([Semaphore<br/>N permits])
    BIN([Binary semaphore])
  end

  subgraph ReadWrite[Read-heavy access]
    RW([RW lock<br/>many readers, one writer])
    STAMP([Stamped lock])
  end

  subgraph Coordination[Coordination]
    CV([Condition variable])
    LATCH([Countdown latch])
    BAR([Cyclic barrier])
    PHA([Phaser])
  end

  subgraph LockFree[Lock-free / atomic]
    ATM([Atomic int / ref])
    CAS([Compare-and-swap])
    MV([Memory ordering<br/>acquire / release])
  end

  subgraph Isolation[Isolation]
    TL([Thread-local])
    IMM([Immutable shared])
  end

  classDef s fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
  class MTX,SPIN,REC,SEM,BIN,RW,STAMP,CV,LATCH,BAR,PHA,ATM,CAS,MV,TL,IMM s;

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class RW client;
    class MTX,SPIN,REC,SEM,BIN,STAMP,CV,LATCH,BAR,PHA,ATM,CAS,MV,TL service;
    class IMM datastore;

Cheat sheet#

Primitive	What it does	When to use
Mutex / Lock	one holder at a time	exclusive access to mutable state
Spinlock	busy-waits; no kernel call	very short critical sections, no scheduler help
Reentrant lock	same thread can re-acquire	recursive code paths under one lock
Semaphore (counting)	N concurrent permits	rate-limit / connection pool / bounded resource
Binary semaphore	0 or 1	signal between threads
Read-Write lock	many readers OR one writer	read-heavy maps / caches
Condition variable	wait until predicate	producer/consumer queue, blocking get
Countdown latch	block until N events	"wait for 5 workers to start"
Cyclic barrier	N threads must reach point	iterative algorithms
Atomic	lock-free ops on a single word	counters, refs
Compare-and-swap (CAS)	atomic "if val==X set to Y"	lock-free queues, optimistic concurrency
Thread-local	per-thread storage	request id, current user, ThreadLocalRandom
Immutability	no shared mutation	safest concurrency

Producer/consumer with a condition variable#

sequenceDiagram
  participant P as Producer
  participant Q as Queue
  participant C as Consumer
  P->>Q: lock, put item, notify, unlock
  Note over C: wait on cv if empty
  Q-->>C: notify
  C->>Q: lock, take item, unlock

class BlockingQueue<T> {
  private final Deque<T> q = new ArrayDeque<>();
  private final int cap;
  private final ReentrantLock lock = new ReentrantLock();
  private final Condition notFull  = lock.newCondition();
  private final Condition notEmpty = lock.newCondition();

  void put(T x) throws InterruptedException {
    lock.lock();
    try {
      while (q.size() == cap) notFull.await();
      q.addLast(x);
      notEmpty.signal();
    } finally { lock.unlock(); }
  }

  T take() throws InterruptedException {
    lock.lock();
    try {
      while (q.isEmpty()) notEmpty.await();
      T x = q.removeFirst();
      notFull.signal();
      return x;
    } finally { lock.unlock(); }
  }
}

CAS-based counter#

final AtomicLong counter = new AtomicLong(0);
counter.incrementAndGet();   // lock-free
counter.compareAndSet(5, 6); // boolean

Pitfalls#

Race condition: result depends on thread interleaving (read-modify-write without locking).
Visibility: a value written by one thread isn't seen by another without proper memory ordering (volatile, atomics, locks).
Re-entrancy traps: calling back into your own lock from a callback - use reentrant locks or refactor.
Spurious wakeups: condition.await() can return without a notification - always re-check in a while loop.
Lost wakeups: notify before await is called - keep state guarded by the same lock as the notify/await.

Where this shows up in this site#

Distributed lock service - same semantics at network scale.
Rate limiter - counting semaphore in spirit.
Stock exchange matching engine - single-threaded per symbol to avoid these primitives entirely.
Logger framework / Background jobs / Distributed counter - extensive use of atomics + condition variables.

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag	Concept	What it is	Page
`HLD`	CAP / PACELC	C vs A under partition; L vs C otherwise	cap-pacelc
`LLD`	Concurrency primitives	mutex, semaphore, RW lock, atomic, CAS	concurrency-primitives
`LLD`	Threading & deadlocks	thread states, Coffman, lock ordering	threading-and-deadlocks
`LLD`	Immutability	immutable types, persistent collections	immutability
`LLD`	Error handling	exceptions vs Result, error boundaries	error-handling

Quick reference#

Hierarchy of preferences (easiest → hardest to get right)#

Make it immutable - share without locks.
Make it thread-confined - only one thread touches it.
Use a higher-level construct (BlockingQueue, ConcurrentMap, Actor, Channel).
Use atomics or CAS for single-word state.
Use a mutex / RW lock for compound state.
Hand-roll lock-free algorithms - only if profiling shows you must.

Common bugs#

Race condition - observable result depends on interleaving.
Deadlock - circular wait on locks.
Livelock - threads remain active but make no progress.
Starvation - a thread is perpetually denied access.
ABA problem - CAS-related: pointer changes A→B→A; CAS thinks nothing happened.
False sharing - two threads write to adjacent cache lines, causing coherence traffic.

Memory model#

Java: volatile, synchronized, j.u.c.atomic.* give specific happens-before guarantees.
C++: explicit memory_order on std::atomic.
Go: channels + sync package.
Python: GIL serialises Python bytecode, but you still need locks for compound state.

Refs#

Java Concurrency in Practice - Brian Goetz.
The Art of Multiprocessor Programming - Herlihy & Shavit.
Doug Lea's j.u.c rationale documents.
Tony Van Eerd's "Lock-Free by Example" talks.

FAQ#

What is the difference between a mutex and a semaphore?#

A mutex protects a critical section with one holder at a time and is tied to the locking thread. A semaphore is a counter that allows up to N concurrent holders and is not owned by any thread.

When should I use a read-write lock?#

When reads vastly outnumber writes and the protected section is non-trivial. For very short critical sections, a plain mutex is faster because RW locks have higher overhead per operation.

What is a condition variable?#

A primitive that lets a thread wait for a predicate to become true while releasing its mutex, and be woken when another thread signals the change. It is the basis of producer-consumer queues.

Are atomics faster than locks?#

Atomics avoid OS-level blocking and excel for simple counters or flags. For multi-step state changes, a mutex with one acquisition is usually clearer and not necessarily slower.

What is thread-local storage?#

Per-thread variables that avoid sharing entirely, useful for caches, request context, or per-thread random generators. It is the simplest concurrency strategy when sharing is unnecessary.

Async Models: higher-level async abstractions built on top of concurrency primitives
Error Handling: safe error propagation across threads and async boundaries
State Machines: modeling concurrent lifecycle with explicit state transitions