Chapter 7: Deadlocks

:material-circle-edit-outline: 约 1005 个字 :material-clock-time-two-outline: 预计阅读时间 3 分钟

[!ABSTRACT]

突然意识到 DBMS 是一个管理数据资源的操作系统

ch7 Deadlocks.pdf

操作系统（本）2024-11-12 第 7-8 节 操作系统（本）2024-11-14 第 7-8 节

Deadlock：A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set

Deadlock Characterization

产生死锁的四个必要条件：

1. Mutual exclusion（互斥）
   • 每个资源只能有一个进程使用
2. Hold and wait（占有并等待、请求和保持）
   • 拿了资源，但还需要更多资源，等待时不会释放已经拿了的资源
3. No preemption（不可抢占、不剥夺）
4. Circular wait（循环等待）
   • 

Resource-Allocation Graph 资源分配图

A set of vertices V and a set of edges E.

V is partitioned into two types

• P = {P1, P2, …, Pn}, all the processes，用圆圈表示
• R = {R1, R2, …, Rm}, all resource types，用方框表示
  • 一个资源可能会有多个 instance，所以方框里面会有小方框

E is partitioned into two types

• request edge – Pi → R
• assignment edge – Rj → Pi

[!EXAMPLE] Resource Allocation Graph With A Deadlock

Resource Allocation Graph With A Cycle But No Deadlock

• 如果图里没有环路，则一定不会有死锁
• 如果图里有环路
  • 如果环路里的 resource type 均只有一个 instance，则必死锁
  • 否则不确定，只能说有可能死锁

S 为死锁状态的充分条件是：尚且仅当 S 状态的资源分配图是不可完全简化的

资源分配图的简化

1. 先看系统还剩下多少资源没分配，再看有哪些进程是不阻塞的

   • 不阻塞是指系统有足够的空闲资源分配给它

2. 把不阻塞的进程的所有边都去掉，形成一个孤立的点，再把系统分配给这个进程的资源回收回来

3. 看剩下的进程有哪些是不阻塞的，然后把它们逐个变成孤立的点。
4. 最后，所有的资源和进程都变成孤立的点
   • 这样的图就叫做可完全简化，如果一个图可完全简化，则不会产生死锁
   • 如果图中还有边存在，则不可完全简化，会产生死锁

[!EXAMPLE] 没有死锁的化简例子

[!QUESTION] Review Questions

1. What are the four necessary conditions for characterizing deadlock?
2. 是否可能存在一种死锁现象，只涉及单个进程？
3. 处理死锁有哪些策略？

answer

1. Mutual exclusion, Hold and wait, No preemption, Circular wait
2. 不可能
3. 下面

Methods for Handling Deadlocks

死锁处理的策略：

1. Prevention 死锁预防
2. Avoidance 死锁避免
3. Detection 死锁检测 + Recovery 死锁解除

Deadlock Prevention

就从四个必要条件分别下手咯

1. 互斥是不能破坏的，共享资源必须互斥
2. Hold and wait，这个的破坏之前讲过，线程随机超时后释放资源
   • Low resource utilization; starvation possible
3. No Preemption，需要 waite 话就先释放已经拿到的资源，空手 wait
4. Circular Wait ，这个就得对进程执行、申请顺序进行排序了

Deadlock Avoidance

一个进程在申请资源时，检查这个申请是否会造成 circular-wait，会就不给申请

这个检查需要用到一个概念叫 Safe State 安全状态

Safe State 安全状态

每次分配资源时就先检查分配后系统是否处于 Safe State

安全状态是指，此状态系统能按某种顺序（如 P1、 P2……Pn）来为各个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成

这个序列（P1、P2…….Pn）称为安全序列

[!NOTE] 安全序列

确切而言， 是安全的，如果：

• 对于任意 Pi，假设它全面的进程全部执行，Pi 所需要的资源仍然可以获取，或者不能获取，但是它前面的进程有使用
• 即，任意 Pi 都可以等它前面的进程执行完后得到所需资源

若系统某个状态下不存在安全序列，则称系统处于不安全状态

• 如果系统处于安全状态，不会发生死锁
• 如果处于非安全状态，则可能死锁

[!EXAMPLE]

[!EXAMPLE]