OS Walkthrough 05 — Deadlock

PKU’s OS on Coursera: Week 12

Deadlock is an intriguing concept to me. Hope you are also fascinated by it.

This article is about conditions for deadlock (mutual exclusion, hold and wait, no preemption, circular wait), RAG (resource allocation graph), deadlock VS. livelock, deadlock VS. spinlock, methods for handling deadlock, & deadlock prevention.

A deadlock in real life[1]

Last article:

OS Walkthrough 04— File Management & I/O

(1) Week 12: Deadlock

(2) References

(1) Week 12: Deadlock

1. Preemptibility

• Preemptible resources: CPU
• Non-preemptible resources: Printer

2. Individually necessary and jointly sufficient conditions for deadlock

A deadlock situation on a resource can arise only if all of the following conditions occur simultaneously in a system:

• Mutual exclusion
• Hold and wait
• No preemption
• Circular wait

3. Resource allocation graph (RAG): can be used to determine a deadlock.

(Left) There are two deadlock cycles in this case. (Right) There is no deadlock in this case even though there is a cycle.[2]

4. Deadlock VS. livelock

• Deadlock: All processes are blocked.
• Livelock: Processes can run on the CPU but can’t make any progress.

5. Deadlock VS. spinlock

• Deadlock: All processes are blocked.
• Spinlock: For multiple CPUs. A process is waiting (busy waiting) to enter the critical section, but the process is not blocked.

6. Methods for handling deadlock

• Prevention: Fail at least one of the necessary conditions.
• Avoidance: Banker’s Algorithm. Provide information regarding their resource usage. Make sure that the system always stays in a “safe” state.
• Detection: Do recovery if the system is deadlocked. Step 1 is deadlock detection; step 2 is recovery.
• Ignoring: Restart the system “manually” if the system “seems” to be deadlocked or stops functioning. Note that the system may be “frozen” temporarily!

7. Deadlock prevention

• Destroy “mutual exclusion”: Hard to destroy.
• Destroy “hold and wait”: Require processes to request all the necessary resources before starting up. This is an inefficient use of resources.
• Destroy “no preemption”: When a process can’t receive the resources it applies for, then release all the resources it holds.
• Destroy “circular wait”: Resource ordering. Probably the best way to prevent deadlock.

8. A cyclic RAG doesn’t necessarily imply a deadlock, but a deadlock implies a cyclic RAG.

9. Preemptive multitasking: for resources can be easily saved and restored

• CPU: preemptive scheduling / preemptive scheduling algorithm
• Memory: page replacement / page replacement algorithm

(2) References

[1] https://arctype.com/blog/database-deadlock/

[2] http://web.cs.ucla.edu/classes/spring14/cs111/scribe/10a/

(Chinese)

操作系统 — — 死锁的概念以及死锁处理策略

https://www.cnblogs.com/wkfvawl/p/11598647.html

操作系统 — — 银行家算法（Banker’s Algorithm）

https://www.cnblogs.com/wkfvawl/p/11929508.html

详解操作系统之银行家算法（附流程图）

https://zhuanlan.zhihu.com/p/384678500

并发问题中活锁（live lock）到底指的是什么？

https://www.zhihu.com/question/20566246