Deadlock

1. What Is Deadlock?

A holds lock 1 and needs lock 2; B holds lock 2 and needs lock 1.

2. Necessary Conditions for Deadlock

• Mutual exclusion: resources cannot be shared. If I hold this resource at a given time, you cannot hold it.
• Hold and wait: after I hold resource A, I also want to acquire resource B.
• No preemption: while I hold this resource, you cannot preempt it.
• Circular wait: I hold resource A and wait for resource B; you hold resource B and wait for resource A. We are both waiting for each other’s resource.

3. Methods for Handling Deadlock

There are mainly four methods:

3.1. Ostrich Algorithm

Take no measures and simply ignore it. Use case: when deadlock does not have much impact on users, or the probability of deadlock is very low.

• This strategy is also the implementation used by most systems.

3.2. Deadlock Detection and Recovery

Do not try to prevent deadlock; instead, take recovery measures when deadlock is detected.

Detect deadlock through a resource-allocation graph, and recover through methods such as preemption, rollback, or killing processes.

PG: Database Deadlock

3.3. Deadlock Prevention

Prevent deadlock by breaking any of the four deadlock conditions.

1. Break mutual exclusion: allow resources to be shared.
2. Break hold and wait: request all required resources at once instead of applying for them one by one.
3. Break no preemption: make resources preemptible.
4. Break circular wait: assign a uniform numbering to resources, and processes can only request resources in numerical order.

3.4. Deadlock Avoidance

Banker’s algorithm.

4. References

• Master Operating System Interviews with This Article (2) - Juejin