Concurrency

Deadlock

A deadlock is the permanent blocking of a set of processes that either compete for system resources or communicate with each other.

Why does it happen?

Every process in the set is waiting on a resource another member of the set holds. No one can release, so no one can proceed. In ECE459 terms: the program stops making progress without crashing.

I first learned about this when preparing for my AMD interview, as well as CS348. Taught in detail through SE350.

Coffman conditions — all four must hold simultaneously for a deadlock. Break any one and deadlock cannot occur:

1. Mutual exclusion: a resource belongs to at most one process at a time
2. Hold-and-wait: a process holding resources can request more and be forced to wait
3. No preemption: a resource cannot be taken; only the holder releases it
4. Circular wait: a cycle in the resource allocation graph

Figure 6.5d has the same topology as 6.5c but there is no deadlock, because multiple units of each resource are available.

Minimal deadlock

In (c) above, P1 holds Rb and wants Ra; P2 holds Ra and wants Rb. Neither process can continue.

Dealing with Deadlocks

Three approaches:

1. Deadlock Prevention
2. Deadlock Avoidance
3. Deadlock Detection

Practical rules

• Avoid nested locks, the main cause of deadlock, don’t take a second lock while holding the first if you can help it
• Avoid unnecessary locks, lock only what actually needs protection
• Enforce a global lock order so cycles can’t form

Rust’s Mutex auto-releases on drop but does not prevent deadlock: thread 1 acquiring A then B while thread 2 acquires B then A still deadlocks.

Avoiding deadlock with multiple locks

Two options from ECE459 L11:

• Consistent ordering: assign each resource an integer f(R). A process holding R_i may only request R_j if f(R_j) > f(R_i). If it needs one with a smaller value, it releases everything at or above that value first. Makes circular wait impossible
• Trylock: attempt the second lock; on failure release the first and retry. Breaks hold-and-wait

Bank transfer deadlock

Two concurrent transfers can deadlock if one locks sender-then-receiver while the other locks receiver-then-sender. Fix by ordering on the immutable account number (kept outside the mutex), or use trylock.

Related

• Livelock
• Data Race