Skip to content

Concurrency Primitives — Detailed#

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