Deadlock

Occurs when no Thread can proceed because each is waiting for a resource held by another. A cyclical dependency on resource acquisition so that none of the threads can proceed.

Thread 1 acquires lock 1
Thread 2 acquires lock 2
Thread 1 attempts to acquire lock 2 and blocks
Thread 2 attempts to acquire lock 1 and blocks

This example can be extended to any number of threads. A deadlock is an example of liveness failure.

Preconditions and prevention

Conditions that need to be met simultaneously for a deadlock to occur, and how to potentially prevent them from occurring.

Mutual exclusion: at least one resource must be held exclusively be a thread
- The issue is that you often can’t avoid using mutexes; you either need them or you don’t.
Hold and wait: a thread must be holding a resource and simultaneously be waiting for a resource that is held by another thread
- Have each thread acquire all resources it needs at the beginning, all at once. Not practical if we don’t know what we’ll need
No preemption: the resource can only be released by the thread itself, not e.g. not able to be freed by the OS
- We can’t do anything here either. Forcing a thread to release a lock may place it in an invalid state
Circular wait: each thread must be waiting for a resource that is held by another thread
- Attempt to enforce an ordering to resource acquisition. However, this is also pretty difficult to predict.

When trying to solve a problem that asks whether a scenario can deadlock, it is useful to view it through these four conditions. Only if all four can/will occur then a deadlock occurs. On the other hand, if we can eliminate one of these issues then we can avoid a deadlock from occurring.

Dining philosophers

$n$ students are sitting around a round table, with one fork between each pair of students. Each student may only eat if they can pick up both forks adjacent to them. Each fork can only be used by 1 person at a time.

This is a useful abstraction that lets us try to tackle two problems: can we avoid the state where no one gets to eat (deadlock free), and can we guarantee that everyone occasionally gets to eat (starvation free, literally)

Naive solution

Each student grabs the fork on their left, then on their right. They proceed to eat. Then they let go of both. Repeat the cycle.

void eat() {
    lock(right_fork);
    lock(left_fork);
    eat();
    unlock(right_fork);
    unlock(left_fork);
}

Why this sucks: if every students attempts to grab the fork on their left, they will all block on the fork on their right being released. This results in a deadlock, and no student will ever get to eat.

Other discussed attempts

Round robin: hand the left and right fork to each person in succession. This works, but eating is limited to a single person at a time. Pretty slow.
Test and fail: attempt to retrieve a chopstick, if we fail then we either return immediately or timeout after e.g. 10 seconds, then return. This also avoids deadlock because no circular dependency can ever happen.

Ostrich algorithm

The idea that deadlocks occur so rarely and infrequently that it is actually better for us to ignore the deadlock if one occurs.

There is a real cost to fixing deadlocks and tracking down where it can occur. See below.

Cost on the developer side: more time to develop
Cost on the software side: more computations to perform, state to track, and may slow things down.

The takeaway is that it’s not free to detect deadlocks, and sometimes it would be a net negative to implement functionality to do so. If a toaster deadlocks it’s not exactly the end of the world, and it’s probably not worth it to invest in it.

Deadlock detection algorithms

Timer

Start a timer. After e.g. 10 seconds have passed and no work has been detected, we consider this a deadlock.

Resource allocation graph

A common way is to represent threads and resources as a graph where dependencies represent edges. If there’s a cycle in the graph, then a deadlock exists.

Each resource and thread is a node
If a thread has a resource, draw an arrow from the resource to the thread
If a thread wants a resource, draw an arrow from the thread to the resource

Wait-for graph

A wait-for graph is the same thing but we remove the resource nodes. It’s a bit cleaner and better demonstrates the relationships between threads. If $T_{1}$ is waiting on a resource acquired by $T_{2}$ , then draw an arrow from $T_{1} \to T_{2}$ .

Same graph as before with resource nodes removed:

All Notes

otherworld