第七章 死锁
第 7章 死锁
? 7.1 死锁问题的提出
? 7.2 死锁的必要条件
? 7.3 死锁的预防
? 7.4 死锁的避免和银行家算法
? 7.5死锁检测与恢复
第七章 死锁
7.1 死锁问题的提出
? 定义
? 死锁是计算机系统和进程所处的一种状态。
在系统中的一组进程由于竞争系统资源或由
于彼此通信而永远阻塞，称这些进程处于死
锁状态
? 死锁是多道程序系统中普遍存在的一种
现象
第七章 死锁
7.1 死锁问题的提出
? 死锁问题描述
? 例如：系统中存在的两个进程 P1和 P2，它们在执行
中都需要某种资源 R1和 R2（如磁盘和打印机）；由
于对资源申请的顺序等其它原因，某时刻进程 P1得
到了资源 R1，进程 P2得到了资源 R2；而进程 P1必
须得到 R2才能继续执行，进程 P2必须得到 R1才能继
续执行，两个进程都占用了对方需要的资源，不能
释放，又都在等待对方占用的资源；这样的两个进
程只能永远的处于阻塞状态，成为死锁进程。
? 这种情况也会发生在多个进程、多种资源上。
第七章 死锁
乙进程的进展
甲进程的进展
X
Y
占用打印机
占用输入机
释放输入机
释放打印机
占用输入机
占用打印机
释放输入机
释放打印机
死锁点
危险区
禁区
第七章 死锁
7.2 死锁的必要条件
? 死锁的根本原因是竞争资源
? 资源：一个逻辑资源，简称资源，使之
可以引起一个进程进入等待状态的事物。
第七章 死锁
7.2 死锁的必要条件
? 资源的类型
? 从资源的使用策略上分
? 可抢占资源
? 不可抢占资源
? 从资源的使用方式上分
? 共享资源
? 独占资源
? 从资源的使用期限上分
? 永久资源
? 临时资源
死锁的原因
第七章 死锁
7.2 死锁的必要条件
? 死锁的必要条件
? 互斥条件：一个资源一次只能被一个进程使用；
? 不可抢占条件：一个资源只能被占用它的资源释放，
不能被其它进程强行抢占；
? 部分分配条件：一个进程已经占有了分给它的资源，
但仍要求其它资源；
? 循环等待条件：系统中存在一个由若干进程形成的
环形请求链，其中每个进程均占有若干种资源的某
一种，同时还要求下一个进程拥有的资源
第七章 死锁
7.3 死锁的预防
? 死锁的预防就是破坏死锁的必要条件，
是它永远不能成立,
? 破坏互斥条件
? 破坏不可抢占条件
? 破坏部分分配条件
? 破坏循环等待条件
由资源本身的性
质决定
—— 预先静态分配法
—— 有序资源使用法
第七章 死锁
7.3 死锁的预防
? 预先静态分配法
? 针对部分分配条件，在进程开始运行之前，
一次分配给所需要的全部资源；
? 如果系统资源不能满足进程需要，则进程阻
塞直到得到所有的资源
? 缺点
? 降低了资源利用率
? 进程等待时间长
第七章 死锁
7.3 死锁的预防
? 有序资源使用法
? 针对循环等待条件，系统中所有的资源按类
编号，进程只能按资源的编号顺序申请资源；
? 如：进程 P1已经申请到了资源 R2，就不能
再申请 R1，只能申请 R3,R4……
? 缺点
? 也存在资源浪费的情况
? 设备编号编排困难：要考虑大多数进程使用资源
的顺序；添加新的资源时要重新编号
第七章 死锁
7.4 死锁的避免和银行家算法
? 死锁的避免和预防的区别
? 预防：严格控制死锁必要条件的出现
? 避免：在有可能出现死锁的时候，采取措施
避免发生死锁
? 著名的死锁避免算法：银行家算法。由
Dijkstra在 1965年提出并解决，借鉴银行
家的经营策略，保证操作系统能够安全
的回收资源
第七章 死锁
7.4 死锁的避免和银行家算法
操作系统 银行家
资源 资金
进程 顾客
商业系统计算机系统
第七章 死锁
7.4 死锁的避免和银行家算法
? 银行家算法描述
? 从系统当前状态出发，检查各进程对各类资源的最大
需求量，如果系统现存的资源可以满足某进程对资源
的最大需求量，就满足该进程当前的请求；即只有进
程能够在一定时间内无条件的归还所有资源，系统才
把资源分配给它。
? 条件
? 进程应当提前说明对资源的最大需求量
? 如果所有进程都能安全的执行完成并归还所有资源，
称当前系统状态是安全的，否则就是不安全的
第七章 死锁
7.4 死锁的避免和银行家算法
? 单资源银行家算法举例,
? 系统中有 3个进程 P1,P2,P3，它们申请
使用的最大资源数分别是,7,8,3；已
经分配的资源数分别是,4,3,1；系统
中可用资源总数为 10；按照银行家算法，
判断当前系统状态是否安全。
第七章 死锁
系统可用资源 2
3 5 2仍需求数
7 8 3最大需求
4 3 1已经分配
10系统资源总数
3 5 0第1 次分配 3
0 5 0第2 次分配 7
0 0 0第3 次分配 10安全
第七章 死锁
7.4 死锁的避免和银行家算法
? 多资源银行家算法：考虑系统中有 n个进程 P1,
P2… Pn, m类资源 R1,R2 … Rm的情况
? 引入几个量
? 系统资源向量 R=(R1,R2… Rm),Ri表示系统拥有第 I
类资源的总量；
? 系统当前可用资源向量 V=(V1,V2… Vm),Vi表示系
统当前剩余第 I类资源的数量；
? 各进程当前需求矩阵 C=(Cij),Cij表示进程 i当前要
求第 I类资源的数量；
? 当前资源分配矩阵 A=(Aij),Aij表示进程 i当前已得
到第 I类资源的数量；
第七章 死锁
7.4 死锁的避免和银行家算法
? 多资源银行家算法描述
? 查找请求矩阵中进程 Pi对资源 Rj的请求数量数否小
于 Vj，如不能满足，则拒绝此进程的资源请求，否
则向下进行；
? 假定将资源分给进程 Pi，该进程最终完成运行，对
进程 Pi加以完成标记，并将它占有的所有资源归还
系统；
? 对未标记进程，重复以上两步操作，直到所有进程
均被标志完成，则系统的分配和分配时的状态都是
安全的，于是实际的将资源分给 Pi。
第七章 死锁
7.4 死锁的避免和银行家算法
? 注：以上系统的资源分配可能会产生不
同的分配顺序，但结构应该是相同的。
? 例,
R = ( 5,3,5 ),V = ( 1,0,2 ),
A=
2 0 2
0 1 0
1 1 1
1 1 0
C=
1 1 1
0 1 1
3 1 0
0 0 1
第七章 死锁
R = ( 5,3,5 ),V = ( 1,0,2 ),
A=
2 0 2
0 1 0
1 1 1
1 1 0
C=
1 1 1
0 1 1
3 1 0
0 0 1
V=(2,1,2)P4 C=
1 1 1
0 1 1
3 1 0
0 0 0
V=(4,1,4)P1 C=
0 0 0
0 1 1
3 1 0
0 0 0
V=(4,2,4)P2 C=
0 0 0
0 0 0
3 1 0
0 0 0
V=(5,3,5)P3 C=
0 0 0
0 0 0
3 1 0
0 0 0
请同学们尝试其它的
分配顺序，看是否能
得到同样的结果。
第七章 死锁
7.4 死锁的避免和银行家算法
? 银行家算法在实际应用中效果不好，请
大家讨论一下原因
? 进程难以预见它的最大资源需求
? 系统中进程的数量是随时改变的
第七章 死锁
7.5 死锁的检测与恢复
? 死锁的检测
? 需要使用银行家算法中类似的向量 R,V和矩阵 A,C；
? (1)对于系统内所有没有, 可完成, 标志的进程 Pi
(i=1,2,… )检查它的 Cij是否小于 V；
? (2)若有这样的进程 Pi，则将分配矩阵 A的第 i行各项
加入可用资源向量 V中，并将进程 Pi标志为, 可完
成, ；
? (3)重复上两步操作，直到已无满足 (1)中条件的进
程为止，此时所有未标记进程都是死锁进程。
第七章 死锁
7.5 死锁的检测与恢复
? 死锁的恢复：即采取措施把系统从死锁
状态中恢复
? 终止 (abort)所有死锁进程
? 将死锁进程退回到钱一个检查点，从这个检
查点重新启动
? 相继的逐个终止死锁进程，直到死锁不再存
在
? 相继的逐个抢占死锁进程的资源，直到死锁
不再存在
第七章 死锁
7.5 死锁的检测与恢复
? 死锁的恢复,
? 选择被终止的死锁进程的原则
? 使用最少处理器时间的进程
? 使用最少输出工作量的进程
? 具有最多剩余时间的进程
? 得到资源最少的进程
? 具有最小优先级的进程
第七章 死锁
课后作业
? Page 147
? 7.6
? 7.7
? 上交时间：下周
第 7章 死锁
? 7.1 死锁问题的提出
? 7.2 死锁的必要条件
? 7.3 死锁的预防
? 7.4 死锁的避免和银行家算法
? 7.5死锁检测与恢复
第七章 死锁
7.1 死锁问题的提出
? 定义
? 死锁是计算机系统和进程所处的一种状态。
在系统中的一组进程由于竞争系统资源或由
于彼此通信而永远阻塞，称这些进程处于死
锁状态
? 死锁是多道程序系统中普遍存在的一种
现象
第七章 死锁
7.1 死锁问题的提出
? 死锁问题描述
? 例如：系统中存在的两个进程 P1和 P2，它们在执行
中都需要某种资源 R1和 R2（如磁盘和打印机）；由
于对资源申请的顺序等其它原因，某时刻进程 P1得
到了资源 R1，进程 P2得到了资源 R2；而进程 P1必
须得到 R2才能继续执行，进程 P2必须得到 R1才能继
续执行，两个进程都占用了对方需要的资源，不能
释放，又都在等待对方占用的资源；这样的两个进
程只能永远的处于阻塞状态，成为死锁进程。
? 这种情况也会发生在多个进程、多种资源上。
第七章 死锁
乙进程的进展
甲进程的进展
X
Y
占用打印机
占用输入机
释放输入机
释放打印机
占用输入机
占用打印机
释放输入机
释放打印机
死锁点
危险区
禁区
第七章 死锁
7.2 死锁的必要条件
? 死锁的根本原因是竞争资源
? 资源：一个逻辑资源，简称资源，使之
可以引起一个进程进入等待状态的事物。
第七章 死锁
7.2 死锁的必要条件
? 资源的类型
? 从资源的使用策略上分
? 可抢占资源
? 不可抢占资源
? 从资源的使用方式上分
? 共享资源
? 独占资源
? 从资源的使用期限上分
? 永久资源
? 临时资源
死锁的原因
第七章 死锁
7.2 死锁的必要条件
? 死锁的必要条件
? 互斥条件：一个资源一次只能被一个进程使用；
? 不可抢占条件：一个资源只能被占用它的资源释放，
不能被其它进程强行抢占；
? 部分分配条件：一个进程已经占有了分给它的资源，
但仍要求其它资源；
? 循环等待条件：系统中存在一个由若干进程形成的
环形请求链，其中每个进程均占有若干种资源的某
一种，同时还要求下一个进程拥有的资源
第七章 死锁
7.3 死锁的预防
? 死锁的预防就是破坏死锁的必要条件，
是它永远不能成立,
? 破坏互斥条件
? 破坏不可抢占条件
? 破坏部分分配条件
? 破坏循环等待条件
由资源本身的性
质决定
—— 预先静态分配法
—— 有序资源使用法
第七章 死锁
7.3 死锁的预防
? 预先静态分配法
? 针对部分分配条件，在进程开始运行之前，
一次分配给所需要的全部资源；
? 如果系统资源不能满足进程需要，则进程阻
塞直到得到所有的资源
? 缺点
? 降低了资源利用率
? 进程等待时间长
第七章 死锁
7.3 死锁的预防
? 有序资源使用法
? 针对循环等待条件，系统中所有的资源按类
编号，进程只能按资源的编号顺序申请资源；
? 如：进程 P1已经申请到了资源 R2，就不能
再申请 R1，只能申请 R3,R4……
? 缺点
? 也存在资源浪费的情况
? 设备编号编排困难：要考虑大多数进程使用资源
的顺序；添加新的资源时要重新编号
第七章 死锁
7.4 死锁的避免和银行家算法
? 死锁的避免和预防的区别
? 预防：严格控制死锁必要条件的出现
? 避免：在有可能出现死锁的时候，采取措施
避免发生死锁
? 著名的死锁避免算法：银行家算法。由
Dijkstra在 1965年提出并解决，借鉴银行
家的经营策略，保证操作系统能够安全
的回收资源
第七章 死锁
7.4 死锁的避免和银行家算法
操作系统 银行家
资源 资金
进程 顾客
商业系统计算机系统
第七章 死锁
7.4 死锁的避免和银行家算法
? 银行家算法描述
? 从系统当前状态出发，检查各进程对各类资源的最大
需求量，如果系统现存的资源可以满足某进程对资源
的最大需求量，就满足该进程当前的请求；即只有进
程能够在一定时间内无条件的归还所有资源，系统才
把资源分配给它。
? 条件
? 进程应当提前说明对资源的最大需求量
? 如果所有进程都能安全的执行完成并归还所有资源，
称当前系统状态是安全的，否则就是不安全的
第七章 死锁
7.4 死锁的避免和银行家算法
? 单资源银行家算法举例,
? 系统中有 3个进程 P1,P2,P3，它们申请
使用的最大资源数分别是,7,8,3；已
经分配的资源数分别是,4,3,1；系统
中可用资源总数为 10；按照银行家算法，
判断当前系统状态是否安全。
第七章 死锁
系统可用资源 2
3 5 2仍需求数
7 8 3最大需求
4 3 1已经分配
10系统资源总数
3 5 0第1 次分配 3
0 5 0第2 次分配 7
0 0 0第3 次分配 10安全
第七章 死锁
7.4 死锁的避免和银行家算法
? 多资源银行家算法：考虑系统中有 n个进程 P1,
P2… Pn, m类资源 R1,R2 … Rm的情况
? 引入几个量
? 系统资源向量 R=(R1,R2… Rm),Ri表示系统拥有第 I
类资源的总量；
? 系统当前可用资源向量 V=(V1,V2… Vm),Vi表示系
统当前剩余第 I类资源的数量；
? 各进程当前需求矩阵 C=(Cij),Cij表示进程 i当前要
求第 I类资源的数量；
? 当前资源分配矩阵 A=(Aij),Aij表示进程 i当前已得
到第 I类资源的数量；
第七章 死锁
7.4 死锁的避免和银行家算法
? 多资源银行家算法描述
? 查找请求矩阵中进程 Pi对资源 Rj的请求数量数否小
于 Vj，如不能满足，则拒绝此进程的资源请求，否
则向下进行；
? 假定将资源分给进程 Pi，该进程最终完成运行，对
进程 Pi加以完成标记，并将它占有的所有资源归还
系统；
? 对未标记进程，重复以上两步操作，直到所有进程
均被标志完成，则系统的分配和分配时的状态都是
安全的，于是实际的将资源分给 Pi。
第七章 死锁
7.4 死锁的避免和银行家算法
? 注：以上系统的资源分配可能会产生不
同的分配顺序，但结构应该是相同的。
? 例,
R = ( 5,3,5 ),V = ( 1,0,2 ),
A=
2 0 2
0 1 0
1 1 1
1 1 0
C=
1 1 1
0 1 1
3 1 0
0 0 1
第七章 死锁
R = ( 5,3,5 ),V = ( 1,0,2 ),
A=
2 0 2
0 1 0
1 1 1
1 1 0
C=
1 1 1
0 1 1
3 1 0
0 0 1
V=(2,1,2)P4 C=
1 1 1
0 1 1
3 1 0
0 0 0
V=(4,1,4)P1 C=
0 0 0
0 1 1
3 1 0
0 0 0
V=(4,2,4)P2 C=
0 0 0
0 0 0
3 1 0
0 0 0
V=(5,3,5)P3 C=
0 0 0
0 0 0
3 1 0
0 0 0
请同学们尝试其它的
分配顺序，看是否能
得到同样的结果。
第七章 死锁
7.4 死锁的避免和银行家算法
? 银行家算法在实际应用中效果不好，请
大家讨论一下原因
? 进程难以预见它的最大资源需求
? 系统中进程的数量是随时改变的
第七章 死锁
7.5 死锁的检测与恢复
? 死锁的检测
? 需要使用银行家算法中类似的向量 R,V和矩阵 A,C；
? (1)对于系统内所有没有, 可完成, 标志的进程 Pi
(i=1,2,… )检查它的 Cij是否小于 V；
? (2)若有这样的进程 Pi，则将分配矩阵 A的第 i行各项
加入可用资源向量 V中，并将进程 Pi标志为, 可完
成, ；
? (3)重复上两步操作，直到已无满足 (1)中条件的进
程为止，此时所有未标记进程都是死锁进程。
第七章 死锁
7.5 死锁的检测与恢复
? 死锁的恢复：即采取措施把系统从死锁
状态中恢复
? 终止 (abort)所有死锁进程
? 将死锁进程退回到钱一个检查点，从这个检
查点重新启动
? 相继的逐个终止死锁进程，直到死锁不再存
在
? 相继的逐个抢占死锁进程的资源，直到死锁
不再存在
第七章 死锁
7.5 死锁的检测与恢复
? 死锁的恢复,
? 选择被终止的死锁进程的原则
? 使用最少处理器时间的进程
? 使用最少输出工作量的进程
? 具有最多剩余时间的进程
? 得到资源最少的进程
? 具有最小优先级的进程
第七章 死锁
课后作业
? Page 147
? 7.6
? 7.7
? 上交时间：下周
