Skip to content

Locking & Synchronization

Deadlock

Four conditions (ALL must hold for deadlock): 1. Mutual exclusion: resource held exclusively 2. Hold and wait: thread holds one resource while waiting for another 3. No preemption: resources can't be forcibly taken 4. Circular wait: cycle in the wait-for graph

Deadlock Prevention

Break any one condition. Most common: break circular wait by imposing a total order on lock acquisition. Always acquire locks in the same global order.

Classic Deadlock Scenario

  • Products share parts. Two threads order different products with overlapping parts.
  • Thread 1 locks part A, then tries to lock part B
  • Thread 2 locks part B, then tries to lock part A
  • Deadlock! Circular wait.
  • Fix: Order locks by part ID. Both threads lock A first, then B.

Single Lock vs Fine-Grained Locking

  • Single lock: Simple, correct, but kills parallelism (all threads serialize)
  • Per-resource lock: More parallelism, but risk of deadlock if multiple locks needed
  • STM: Best of both worlds (composable, deadlock-free) but has retry overhead

MVar as Lock

-- Lock = MVar ()
-- Acquire: takeMVar lock  (blocks if already taken)
-- Release: putMVar lock ()
-- The empty state = locked, full state = unlocked
-- Stock count as MVar Int: takeMVar gets value AND locks, putMVar updates AND unlocks

Livelock

Threads are active (not blocked) but make no useful progress — they keep reacting to each other and changing state without ever completing their work.

  • Different from deadlock: threads are NOT stuck waiting; they are executing
  • Example: two threads each repeatedly back off and retry when they see the other, but always collide again
  • Can occur with poorly implemented backoff in lock-free algorithms

Deadlock vs Livelock vs Starvation:

Threads blocked? Progress made?
Deadlock Yes (waiting) None
Livelock No (running) None — activity without progress
Starvation Some blocked, others running Some threads make no progress indefinitely

Properties Quick Reference

  • Wait-free: operation always completes in bounded steps (no blocking ever)
  • Lock-free: at least one thread makes progress (no deadlock, but individual threads may starve)
  • Deadlock-free: no circular waiting (weaker than lock-free)
  • Starvation-free: every thread eventually makes progress

GPU Lock Warning

  • A classic CPU-style spin lock can deadlock on a GPU because threads in a warp execute in lockstep.
  • If one lane holds the lock and another lane in the same warp spins waiting for it, the whole warp can get stuck.