操作系统-死锁
3 死锁
在多道程序中，由于多个并发进程共享系统的资源，如果使用不当，可能会造成一种僵局，即当某个进程提出资源使用请求后，使得系统中一些进程处于无休止的阻塞状态，在无外力作用下，这些进程将无法继续进行下去，称为死锁。
3.1 死锁产生的环境和条件
死锁产生的环境
1) 多道程序设计
2) 多个进程并发
3) 资源共享和独占
4) 没有外力可以借助
死锁产生的必要条件
1) 资源互斥使用（资源独占）
2) 非剥夺控制（不可强占）
3) 请求与保持
4) 循环等待
如果死锁发生，则四个条件必然同时满足
死锁的危害
轻则系统资源利用率下降，重则系统瘫痪
3.2 死锁的解决策略
置之不理--鸵鸟政策
优点：简单、简化系统设计，节约成本
缺点：安全性欠佳，适合于低可靠性和低安全性系统
事后处理法--让死锁发生，事后处理
思路：可以容忍死锁的发生，事后处理
优点：灵活，但不是所有情况都可以容忍死锁的发生
积极预防法--不让死锁发生
思路：以积极的抑制为出发点
手段：
1) 死锁的预防：破坏死锁产生的条件，使其不具备发生的可能
2) 死锁的避免：允许存在发生死锁的可能性，但是在每一步进行资源分配时灵活处理，使得永远不到达死锁的状态。
3.2 死锁的预防
破坏互斥条件
局限性：“互斥”条件破坏往往困难，而且对很多资源行不通，因此不是一种好的方案。
破坏不可剥夺条件
思路：允许一个进程还未执行完成时释放已经占有的资源（被剥夺使用权）
局限：实现困难，为了恢复现场需要耗费很多时间和空间。因此只适合类似CPU、存储器这样的资源。
破坏请求与保持条件（零散请求）
思路：进程创建时就由系统分配了所有需要的资源，然后执行，并且以后没有资源申请要求，进程执行完后，释放资源。
局限：系统效率低，资源浪费严重，并发性下降。
破坏循环等待条件
思路：给资源进行编号，进程必须按序进行申请。
局限：资源编号困难，资源编号很难和进程申请资源的顺序一致。
结论：死锁预防是一破坏死锁产生的必要条件为基本方法，从而防止死锁的发生，对资源加上了诸多的限制，因此这种策略虽然具有一定的效果，但其资源的利用率和效率较低，很难令人满意。
3.3 死锁的避免
思路：允许死锁产生的条件存在，但是通过动态的明智的选择--在分配资源之前，系统判断，假若满足进程的要求是否会产生死锁，如果会，资源不予分配，从而确保永远不会到达死锁，避免死锁的发生。
优点：比预防更为灵活实用，允许更多的并发，其资源利用率和效率也更高。
系统的状态
安全状态：指在某个时刻，当多个进程动态的申请资源时，如果存在一种顺序，使得系统按照这种顺序逐次地为每个进程分配所需要的资源后，每个进程都可以在最终得到最大需求量后，依次顺序的完成。
不安全状态：死锁状态
避免死锁的关键就是：让系统在动态分配资源的过程中，不要进入到不安全状态。
银行家算法
单银行家算法
例：假设一个银行拥有资金数量为 10 现有 4 个客户 a,b,c,d 。要求贷款所需最大资金需求量为 8,5,6,7
多项资源银行家避免算法
适用于一个进程申请多个资源的情况
例：系统中有5台打印机，7个写字板，8台扫描仪，9个读卡器，共有5个进程T1、T2、T3、T4、T5共享这些资源，各进程Max和Allocation矩阵如下：
问：如果T2此时希望得到1台打印机，1个手写板，2个读卡器是否可以满足？
3.4 死锁的检测与解除
检测工具 -- 资源分配图
资源分配图：是描述进程申请资源和资源分配的关系模型图，表示系统中某个时刻进程对资源的申请和占有情况。
规则：
1） 圆表示一个进程
2）方块表示资源类，其中的圆点表示该类型资源中的某个单个资源。
3）从资源指向进程的箭头表示资源分配给了这个进程
4）从进程指向资源的箭头表示进程请求这个资源
检测方法 -- 化简
方法：
1） 从那些没有阻塞的进程入手，删除那些没有阻塞进程的请求边，并使得资源数减1
2）重复
a) 途中所有请求边都删除了，则不会死锁。
b) 图中仍然有请求边但无法化简，系统死锁。
死锁的解除
a) 重新启动（简单、浪费）
b) 撤销进程
1） 撤销造成死锁的进程
2） 一次性撤销所有死锁进程（损失较大）
3）逐个撤销，分别回收资源（可Ian撤销那些优先级低的、已占有资源少或已运行时间短、还需运行时间较长的进程，尽量减少系统的损失）。
c) 剥夺资源
d) 进程回退