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如何解除
- 资源剥夺法
- 撤销进程法（终止进程法）
- 进程回退法