Table of Contents generated with DocToc
可抢占资源
不可抢占资源，死锁何如不可抢占资源有关。
死锁的四个必要条件：
1) 互斥条件
2) 占有和等待条件
3) 不可抢占条件
4) 环路等待条件
死锁的建模：资源分配图。
死锁的四种处理策略：
- 忽略该问题，鸵鸟算法。
- 检测死锁并恢复。
- 仔细对资源进行分配，动态地避免死锁。
- 通过破坏死锁的四个必要条件之一，防止死锁的发生。
如果资源分配图中包含了一个或一个以上的环，那么死锁就存在。
- 对图中的每一个节点N，将N作为起始节点执行以下5个步骤
- 将L初始化为空表，清楚所有的有向边标记
- 将当前节点添加到L的尾部，并检测该节点L是否出现过两次，如果是，则包含环，算法结束
- 从给定的节点开始，检测是否存在没有被标记的从该节点出发的弧，如果存在，则做5)，不存在就做6)
- 随机选取一条没有被标记的从该节点出发的弧，标记它，然后顺着这条弧找到新的当前节点，返回到第3)
- 现在走入了死胡同，所以需要移走该节点，返回前一个节点，并将它作为新的当前节点，同时转到第3)，如果这一节点是厨师节点，则不存在环
基于矩阵的算法，假设资源的类型数为m，C代表当前分配矩阵，R代表请求矩阵。死锁检测算法是基于向量的比较：
- 寻找一个没有被标记的进程P，对于他而言，R向量的第i行小于或者等于A
- 如果找到了这样一个进程，那么将C向量的第i行加入到A中，标记该进程，并转到步骤1)
- 如果没有这样的进程存在，那么算法终止
1. 利用抢占恢复
2. 利用回退恢复
3. 通过杀死进程恢复
避免死锁的主要算法是基于一个安全状态的概念。
银行家算法
1. 破坏互斥条件：Spooling技术，假脱机
2. 破坏占有和等待条件：禁止已持有资源的进程再等待其他资源，在开始时就请求全部资源
3. 破坏不可抢占条件：抢占资源
4. 破坏循环等待条件：资源统一编号、保证每个进程任意时刻只能占用一个资源
上一章：2. 进程与线程
下一章：4. 存储管理