1. 什么是死锁
各进程相互等待对方手里的资源,导致各进程都阻塞,无法向前推进
2. 死锁、饥饿、死循环区别
- 死锁:至少是两个进程一起死锁,死锁进程处于阻塞态
- 饥饿:可以只有一个进程饥饿,饥饿进程可能阻塞也可能就绪
- 死循环:可能只有一个进程发生死循环,死循环的进程可上处理及运行
- 死锁和饥饿是操作系统要解决的问题,死循环是应用程序员要解决的问题
3. 死锁产生的必要条件
- 互斥条件:对必须互斥使用的资源的争抢才会导致死锁
- 不剥夺条件:进程保持的资源只能主动释放,不可强行剥夺
- 请求和保持条件:保持着某些资源不放的同时,请求别的资源
- 破坏等待条件:存在一种进程资源的循环等待链;循环等待未必死锁,死锁一定有循环等待
4. 死锁产生的原因
- 系统资源的竞争:对不可剥夺资源的竞争
- 进程推进顺序非法
5. 死锁的处理策略
5.1预防死锁
不允许死锁发生,静态策略,预防死锁,破坏死锁的四个必要条件
5.1.1破坏互斥条件
- 将临界资源改造为可共享使用的资源(如SPOOLing技术)
- 缺点:可行性不高,很多时候无法破坏互斥条件
5.1.2破坏不剥夺条件
- 方案一,申请的资源得不到满足时,立即释放拥有的所有资源
- 方案二:申请的资源被其他进程占用时,由操作系统协助剥夺(考虑优先级)
- 缺点:实现复杂;剥夺资源可能导致部分工作失效;反复申请和释放导致系统开销大;可能导致饥饿
5.1.3破坏请求和保持条件
- 运行前分配好所有需要的资源,之后一直保持
- 缺点:资源利用率低;可能导致饥饿
5.1.4破坏循环等待条件
- 给资源编号,必须按编号从小到大的顺序申请资源
- 缺点:不方便增加新设备;会导致资源浪费;用户编程麻烦
5.2避免死锁
不允许死锁发生,动态策略,避免系统进入不安全状态(银行家算法)
5.2.1安全序列
如果系统按照这种序列分配资源,则每个进程都能顺利完成。
5.2.2安全状态
只要能找出一个安全序列,系统就是安全状态。安全序列可能有多个
5.2.3系统的不安全状态
分配资源之后,系统中找不到任何一个安全序列,系统就进入不安全状态
5.2.4避免进入系统的不安全状态(银行家算法)
- 系统处于安全状态,就一定不会发生死锁。
- 系统进入不安全状态,就可能发生死锁
- 在资源分配之前预先判断这次分配是否会导致系统进入不安全状态,以此决定是否答应资源分配请求。这是“银行家算法”的核心思想。
5.2.5银行家算法
用于避免死锁。
核心思想
在进程提出资源申请时,先预判此次资源分配是否会导致系统进入不安全状态。如果会进入不安全状态,就暂时不答应这次请求,让该进程先阻塞等待。
数据结构
- 长度为m的一维数组Available表示还有多少可用资源
- n*m矩阵Max表示各进程对资源的最大需求数
- n*m矩阵Allocation表示已经给各进程分配了多少资源
- Max - Allocation = Need 矩阵表示各进程最多还需多少资源
- 用长度为 m 的一维数组 Request 表示进程此次申请的各种资源数
银行家算法步骤
- 检查此次申请是否超过了之前声明的最大需求数
- 检查此时系统剩余的可用资源是否还能满足这次需求
- 试探着分配,更改各数据结构
- 用安全性算法检查此次分配是否会导致系统进入不安全状态
安全性算法步骤
- 检查当前的剩余可用资源是否能满足某个进程的最大需求,如果可以,就把该进程加入安全序列,并把该进程持有的资源全部回收。
- 不断重复上述过程,看最终是否能让所有进程都加入不安全序列。

5.3死锁的检测和解除
允许死锁发生,系统负责检测出死锁并解除
5.3.1如何检测
数据结构:资源分配图
- 两种结点
- 进程结点:对应一个进程
- 资源结点:对应一类资源,一类资源可能有多个
- 两种边
- 进程结点 ---> 资源结点(请求边)
- 资源结点 ---> 进程结点(分配边)
死锁检测算法
- 依次消除与不阻塞进程边相连的边,直到无边可消
- 注:所谓不阻塞进程是指其申请的资源数还足够的进程
- 死锁定理:若资源分配图是不可完全简化的,说明发生了死锁
算法步骤
- 在资源分配图中,找出既不阻塞又不是孤点的进程 Pi(即找出一条有向边与它相连,且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。如下图中,R1没有空闲资源,R2有一个空闲资源。若所有的连接该进程的边均满足上述条件,则这个进程能继续运行直至完成,然后释放它所占有的所有资源)。消去它所有的请求边和分配变,使之称为孤立的结点。在下图中, P1 是满足这一条件的进程结点,于是将P1的所有边消去。
- 进程Pi 所释放的资源,可以唤醒某些因等待这些资源而阻塞的进程,原来的阻塞进程可能变为非阻塞进程。在下图中,P2 就满足这样的条件。根据 1)中的方法进行一系列简化后,若能消去途中所有的边,则称该图是可完全简化的。



5.3.2如何解除
- 资源剥夺法
- 撤销进程法(终止进程法)
- 进程回退法