第六章 并发行：死锁和饥饿
6.1死锁
死锁：一组竞争资源或者相互通信的进程的“永远阻塞”
死锁是否发生取决于1.应用程序细节和2.进程推进的过程。
死锁发生的条件：（必要条件）
- 互斥：一次只有一个进程可以一个资源，其他进程不能访问已经分配给其他进程的资源。
- 占有并等待：当一个进程在等待分配其他资源的时候码仅需占有已经分配的资源。
- 非占有：不能强行抢占进程已经占有的资源。
（· 循环等待）（加上这个之后就是充要条件了）
处理死锁的三类方法：
- 死锁预防：从产生死锁的四个条件入手，避免死锁条件的发生。
- 死锁避免：从进程的角度入手，避免死锁发生，有时多个进程中存在发生死锁的条件，但可以通过有效地推进，避免死锁。
- 死锁检测与恢复：从死锁真的发生了，如何处理的角度入手，一般来说，处理死锁可能存在损失。
6.2死锁预防
预防分为两类：1.防止前面列出来的三个必要条件中的任何一个的发生。2.直接的死锁预防方式，即防止循环等待的发生。（我们来一个个考虑哈）
互斥条件：一般来说我们不可能禁止互斥。如果访问资源要求呼哧，那么操作系统必须支持互斥操作。
占有且等待：我们可以要求进程一次行地请求所有需要的资源，并且阻塞这个进程直到所有请求都同时满足。 这种方式实际上很低效的。
非抢占：我们可以将其设置为进行进一步资源请求被拒绝时，则该进程必须释放它最初占用的资源。
避免循环等待：为了避免这种，它的方式也很低效。
6.3死锁避免
两种思路：1.进程启动拒绝，如果一个进程的请求会导致死锁，则不启动此进程。2.资源分配拒绝，如果一个进程增加资源的请求会导致死锁，则不允许此分配。
6.3.1进程启动禁止
首先假设（如下）：
| Resource=R=($R_1,R_2,R_3,···R_m$) | 系统中每种资源的总量 |
|---|---|
| Available=V=($V_1,V_2,V_3,···，V_m$) | 未分配给进程的各种资源的总量 |
| Claim=C=a = $\left[ \matrix{ \C_{11} & C_{12} & ··· & C_{1m}\ \C_{21} & C_{22} &··· &C_{2m}\ ··· & ··· &··· &···\C_{n1} & C_{n2} &··· &C_{nm}\ } \right]$ | $C_{ij}$=进程i对各种资源的需求 |
| Allocation=A=$\left[\matrix {A_{11} &A_{12}&··· &A_{1m}\{A_{11} &A_{12}&··· &A_{1m}\ ···& ··· &··· &··· \{A_{11} &A_{12}&··· &A_{1m}} \right]$ | $A_{ij}$=对资源j的进程i的当前分配 |
由假设我们可以看出来 $R_j = V_j + \sum{A_{ij}}$ 未非分配的，加上已经分配的就是系统中所具有的总的资源总量
$C_{ij} <= R_i$ 任何一个进程对资源的请求不能超过系统中这个资源的总量
$A_{ij} <= C_{ij}$ 分配给任何一个进程的任何一种资源都不会超过过该进程最初声明的此资源的最大请求个数。
这个时候：如果一个新的进程的资源需求会导致死锁，则拒绝启动这个新的进程。也就是：对于任意j有 \(V_j >= C_{(i+1)j}\) 意思就是说，对于任意一项资源的剩余量都比新增的这个进程的需求量要大。否则我们就会拒绝这个新的进程。
6.3.2资源拒绝分配
这里面涉及到银行家算法：银行家算法里面有单资源模型和多资源模型，我们在此直接省略了单资源模型由于过于简单，而且跟多资源模型一个道理。
安全状态是指至少有一个进程执行序列不会导致死锁。不安全序列是指不是一个安全状态。所谓安全序列就是指系统中的所有进程能够按照某一次许分配资源，并且一次地运行完毕的序列。如果找不到这样的序列，我们就称这个进程处于不安全状态。
安全状态、不安全状态和死锁的关系：
- 存在安全序列–》处于安全状态–》一定不会发生死锁
- 不存在安全序列–》进入不安全状态–》不一定会发送死锁
- 产生死锁–》处于不安全状态
没有安全序列可能会出问题，但是也有可能不出问题，因为我们不一定要一次吧资源给分配完，可以在原有资源进行中将部分使用过的资源释放出来。不一定会一直占有。
银行家算法的流程：
- 查找请求矩阵中进程$P_i$对资源$R_j$的请求量是否小于等于$V_j$,否则，则拒绝请求；是，则向下进行；
- 假设将资源分配给$P_i$,它能最终完成运行，则将进程$P_i$标志以完成，并将它占有的资源完全归还给系统
- 重复上述步骤
死锁避免的不足之处：
- 必须事先声明每个进程请求的最大资源
- 考虑的进程必须是无关的，也就是说哦，它们执行的顺序必须没有任何同步要求的限制。
- 分配的资源数目是固定的。
- 在占有资源时，进程不能退出。
6.4死锁检测
死锁检测检测的策略是它不限制资源访问或者约束进程的行为。对于死锁检查行为只要有可能都被授权给了进程。
这种死锁检测的方法的优缺点：优点：1.他使得可以尽早地检测死锁情况，2.并且由于此方法给予系统状态的情况，因此算法相对比较简单。不足：1.若频繁的检查会耗费相当多的处理器时间。
死锁检测算法（银行家算法）：
- 标记Allocation矩阵中一行全部为0的进程。
- 初始化一个临时向量V，令V等于Available向量。
- 查找下标i，是进程i当前未标记且C的第i行小于等于V，即对于所有的1<=k<=m.
- 如果找到这样的行，标记进程i，并把Allocation矩阵中的相应行加到C中。然后V = $C_i$ + V.
死锁恢复：一旦检测到死锁，就需要某种策略以恢复死锁。可能的方法
- 取消所有的死锁进程
- 把每个死锁进程回滚到前面定义过的某个检查点，并且重新启动所有进程。
一个对于死锁处理的总结：
6.5哲学家就餐问题
考虑增加一个服务员，每次只允许4位哲学家同时进入餐厅。因此只要有一个哲学家可以有两个叉子。这样的话该方案就不会发生死锁了。
