CSE Roadmap

Common tier · about 3 hours · 8 parts

Part 4 of 8 · 2 min read

Locks and deadlock

Think of a narrow bridge with one lane. Cars from both sides can pass in turn if they wait. If two cars meet in the middle and both refuse to back up, nothing moves. The analogy stops in one place: a bridge has a police officer who can order a car to reverse, and a deadlocked program has none.

In plain words: Model answers:

  1. What is a race condition? A bug in which the result depends on the order in which threads run, because they use shared data without protection. Example: two threads each do counter++, which is a read, an add and a write, and one update is lost (Level 4).
  2. Mutex or semaphore? A mutex is a lock with an owner: one thread locks and the same thread unlocks, and it protects a critical section. A semaphore is a counter with wait and post, with no owner, used to count resources or to signal between threads (Level 4).
  3. What are the four conditions for deadlock? Resources are used by one thread at a time (mutual exclusion). A thread holds one while it waits for another (hold and wait). Nothing can be taken away by force (no preemption). The waiting threads form a closed circle (circular wait). All four must hold together, so removing one prevents deadlock (Level 5).
  4. How do you prevent deadlock in practice? Make all code take locks in one global order. That removes circular wait.
  5. Deadlock or starvation? In a deadlock, a group of threads wait for each other and none can proceed. In starvation, a thread could proceed but is never chosen (Levels 3 and 5).

A worked example. Thread A locks m1 then m2. Thread B locks m2 then m1. If A holds m1 and B holds m2, each waits for the other: all four conditions hold (the locks are exclusive, each holds one and waits for another, none can be taken away, and the wait is circular). The fix: both threads lock m1 first and m2 second. Then B cannot hold m2 without having m1, and the circle cannot form.

The key lines. Say which of the four conditions your fix removes. That shows that you understand why it works, not only that it works.

Deadlock

A deadlock is a state in which a set of threads each wait for a resource that another thread in the set holds, so that none can continue. It needs four conditions at once: exclusive use, hold and wait, no forced removal of a resource, and a circle of waiting threads.

Example: A holds m1 and wants m2 while B holds m2 and wants m1.

Check yourself: 1. Why can counter++ lose an update? 2. What is the difference between a mutex and a semaphore? 3. Which condition does lock ordering remove?