DSA & System Design
Operating systems and concurrency · Lesson 3 of 12 · 25 min

Locks, Semaphores and Deadlock

Race conditions, the three tools that tame them, and deadlock: its four conditions and the cheap ways to prevent it.

✓ Pick a mutex, semaphore or condition variable for a job✓ Name the four conditions for deadlock✓ Prevent deadlock with a global lock order
Say it in 30 seconds
  • 4 conditionsAll must hold for a deadlock
  • 1 global orderLock order that prevents circular wait
  • N permitsA semaphore sized to the real resource
Show what to say

“A race is a result that depends on timing, and I fix it by making the shared read-modify-write one critical section behind a mutex. A semaphore limits N holders and a condition variable waits for a state. Deadlock needs mutual exclusion, hold and wait, no preemption and circular wait, so I break circular wait with one global lock order.”

Trade-offs

  • Prevention vs detection: a fixed lock order never deadlocks but must be known; detecting a cycle and aborting is flexible but wastes work.
  • One big lock vs fine-grained locks: one lock is simple and safe but serial; many locks scale but invite deadlock.
  • Mutex vs spinlock: a mutex sleeps and costs a context switch; a spinlock burns CPU but wins for waits shorter than a switch.

Bring it up before they ask

Never hold a lock while doing I/O or calling unknown code, because that is how small locks become bottlenecks and deadlocks.

0 of 0 sections ticked
30-second answer

A is a result that depends on timing; a removes it by letting one thread into a critical section at a time. Locks bring their own failure, , which needs four conditions and is prevented by breaking any one of them, usually with a fixed lock order.

Race conditions and critical sections

A race is two threads touching the same data with no rule for who goes first.

Read more · 162 words

The part of the code that touches that shared data is the critical section, and the cure is mutual exclusion: only one thread inside at a time.

JavaScript has a single thread, yet it can still race. Any time you read a value, await, then write it back, another task runs in between.

Without the , two awaiting increments give 1. With it, ten give 10. Keep the critical section small: lock, touch the shared data, unlock. Never call slow I/O while holding a lock.

// A mutex for async code. JavaScript has one thread, but a race is still possible
// whenever you read a value, `await`, then write it back.
export class Mutex {
  #tail = Promise.resolve();

  // Resolves with a release function once every earlier holder has released.
  lock() {
    let release;
    const released = new Promise((resolve) => { release = resolve; });
    const ready = this.#tail.then(() => release);
    this.#tail = this.#tail.then(() => released);
    return ready;
  }

  async withLock(fn) {
    const release = await this.lock();
    try {
      return await fn();
    } finally {
      release(); // always unlock, even if fn throws
    }
  }
}

Mutex, semaphore and condition variable

Three tools, three jobs.

Read more · 161 words
ToolJobDetail
MutexOne at a timeHas an owner; the thread that locks it unlocks it
SemaphoreAt most N at a timeA counter of permits; any thread may release
Condition variableWait until something is trueAlways used together with a mutex

A is how you limit concurrency: a pool of 10 database connections is a semaphore of 10. A is how a thread sleeps until a condition holds, such as "the queue is not empty".

Always wait in a loop: while (queue is empty) wait(cond). Another thread may take the item first, and some systems wake waiters spuriously, so the condition must be rechecked after waking.

// A counting semaphore: at most `n` holders at once. A mutex is the n = 1 case,
// except that any task may release a semaphore permit, not only the one that took it.
export class Semaphore {
  #permits;
  #waiters = [];

  constructor(n) {
    this.#permits = n;
  }

  async acquire() {
    if (this.#permits > 0) {
      this.#permits -= 1;
      return;
    }
    await new Promise((resolve) => this.#waiters.push(resolve)); // sleep until a release hands us a permit
  }

  release() {
    const next = this.#waiters.shift();
    if (next) next(); // hand the permit straight to the longest waiter
    else this.#permits += 1;
  }
}

Press Play to watch it run · 8 steps

The consumer finds the queue empty and waits, which unlocks the mutex and sleeps. The producer locks, adds an item, signals and unlocks. The consumer wakes, re-locks the mutex and checks the queue again.

A condition variable: wait releases the lock, signal wakes the waiterThe consumer finds the queue empty and waits, which unlocks the mutex and sleeps. The producer locks, adds an item, signals and unlocks. The consumer wakes, re-locks the mutex and checks the queue again.lock()Queue is empty, so check failswait(cond): unlock and sleeplock()push(item)signal(cond)unlock()wake: re-lock, check againqueue not empty: pop item
  • Worker
  • Database
  • Service
Text description
  1. Consumer → Mutex + queue: lock()
  2. Consumer → Mutex + queue: wait(cond): unlock and sleep
  3. Producer → Mutex + queue: lock()
  4. Producer → Mutex + queue: push(item)
  5. Producer sends (async) to Consumer: signal(cond)
  6. Producer → Mutex + queue: unlock()
  7. Consumer → Mutex + queue: wake: re-lock, check again
  8. Mutex + queue replies to Consumer: queue not empty: pop item

Deadlock and its four conditions

Thread 1 holds lock A and wants B.

Read more · 105 words

Thread 2 holds B and wants A. Neither can move, and neither will. Try it: with opposite lock orders and alternating steps the lab ; with the same order it cannot.

A deadlock needs all four Coffman conditions at once:

  1. Mutual exclusion: a resource is held by one thread at a time.
  2. Hold and wait: a thread keeps what it has while waiting for more.
  3. No preemption: a held resource cannot be taken away.
  4. Circular wait: a ring of threads each waits for the next.
Interactive

Deadlock lab

Each thread takes two locks, then works, then releases both. Interleave them with opposite lock orders, then with the same order.

Lock order

Thread 1 running

  1. lock A
  2. lock B
  3. work, release both

Thread 2 running

  1. lock B
  2. lock A
  3. work, release both

Locks

Lock Afree
Lock Bfree

Press Step on a thread, or Alternate, to interleave them.

Prevent, avoid or detect

Break any one condition and is impossible.

Read more · 129 words

The cheapest is circular wait: every thread takes locks in the same global order, for example by account id.

Break thisHowCost
Circular waitOne global lock orderMust know all locks up front
Hold and waitTake everything at once, or try-lock and back offLower concurrency, can livelock
No preemptionLock with a timeout, release and retryWork may be redone

Databases instead detect: they find a cycle in the wait-for graph, abort one and let the application retry. Avoidance (the banker's algorithm) needs each thread's maximum demand in advance, so it is a textbook idea more than a production one.

// waitFor maps each blocked thread to the thread holding the lock it wants.
// A cycle in that graph is a deadlock. Databases run this check and abort one victim.
export function findCycle(waitFor) {
  for (const start of Object.keys(waitFor)) {
    const path = [];
    let at = start;
    while (at !== undefined && !path.includes(at)) {
      path.push(at);
      at = waitFor[at];
    }
    if (at !== undefined) return path.slice(path.indexOf(at));
  }
  return null;
}

// Prevention: break "circular wait" by taking locks in one global order, here by account id.
// transfer(3, 7) and transfer(7, 3) now both lock account 3 first, so they cannot wait in a circle.
export const inLockOrder = (a, b) => (a < b ? [a, b] : [b, a]);

Livelock, starvation and priority inversion

is not the only way to stop making progress.

Read more · 128 words
  • Livelock. Threads keep running but undo each other's work. Two polite people in a corridor both step aside, forever. Random breaks the symmetry.
  • Starvation. A thread never gets the lock because others keep winning. Fair locks queue waiters.
  • Priority inversion. A low-priority thread holds a lock a high-priority one needs. Priority inheritance fixes it.

Safer than locking

Locks are the tool of last resort. Prefer to avoid sharing.

Read more · 97 words
  • Immutable data needs no lock: nobody can change it.
  • Message passing gives each piece of data one owner thread, and others send it requests (actors, Go channels, queues).
  • Atomics make a single variable update indivisible without a lock (next lesson).
  • Read-write locks let many readers in together but one writer alone, which helps read-heavy data.
  • A spinlock busy-waits instead of sleeping. It is right only for waits shorter than a .

Follow-up questions

What is the difference between a mutex and a semaphore?

A guards a critical section and has an owner who must unlock it. A counts permits, lets up to N holders in, and any thread can release it.

What are the four conditions for deadlock, and how do you prevent it?

Mutual exclusion, hold and wait, no preemption, circular wait. Break any one: usually take locks in a global order, or use timeouts and retry.

How do databases deal with deadlocks?

They look for a cycle in the wait-for graph, abort the cheapest , and the client retries it.

Why wait on a condition variable in a loop?

Another thread may take the item before you wake, and spurious wake-ups exist, so the predicate must be rechecked.

Check yourself

Question 1 of 7

Score 2 out of 3 or better to mark this page complete.

1. Which of these is NOT one of the four conditions for deadlock?

Next: Locks are the blunt tool. Next: thread pools, producer-consumer, atomics, and when an event loop beats threads.