死锁

死锁的概念

两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。

产生死锁的原因

（1） '互斥条件'： 一个资源每次只能被一个进程使用。
（2） '请求与保持条件'： 一个进程因请求资源而阻塞时， 对已获得的资源保持不放。
（3） '不可剥夺条件':进程已获得的资源， 在末使用完之前， 不能强行剥夺。
（4） '环路等待条件':若干进程之间形成一种头尾相接的循环等待资源关系。
    只要系统发生了死锁， 这些条件必然成立， 而只要上述条件之一不满足， 就不会发生死锁。

预防死锁

1) '破坏互斥条件'
     如果'允许系统资源都能共享使用'， 则系统不会进入死锁状态。 但有些资源根本不能同时访问， 如打印机等临界资源只能互斥使用。 所以， 
    破坏互斥条件而预防死锁的方法不太可行， 而且在有的场合应该保护这种互斥性。

2) '破坏不剥夺条件'

    当一个已保持了某些不可剥夺资源的进程， '请求新的资源而得不到满足时，它必须释放已经保持的所有资源， 待以后需要时再重新申请。' 这
    意味着， 一个进程已占有的资源会被暂时释放， 或者说是被剥夺了，或从而破坏了不可剥夺条件。该策略实现起来比较复杂， 释放已获得
    的资源可能造成前一阶段工作的失效， '反复地申请和释放资源会增加系统开销， 降低系统吞吐量'。 这种方法常用于状态易于保存和恢复的资
    源，如 CPU 的寄存器及内存资源， 一般不能用于打印机之类的资源。

3) '破坏请求和保持条件'

    釆用'预先静态分配方法'， 即'进程在运行前一次申请完它所需要的全部资源'， 在它的资源未满足前，不把它投入运行。 一旦投入运行后， 这
    些资源就一直归它所有， 也不再提出其他资源请求， 这样就可以保证系统不会发生死锁。
    这种方式实现简单， 但缺点也显而易见， 系统资源被严重浪费， 其中有些资源可能仅在运行初期或运行快结束时才使用， 甚至根本不使用。 
    而且还会导致“饥饿” 现象， 当由于个别资源长期被其他进程占用时， 将致使等待该资源的进程迟迟不能开始运行。

4) '破坏环路等待条件'

    为了破坏循环等待条件， 可釆用'顺序资源分配法'。 首先给系统中的资源编号，规定每个进程， 必须按编号递增的顺序请求资源， 同类资源
    一次申请完。 也就是说， 只要进程提出申请分配资源 Ri， 则该进程在以后的资源申请中， 只能申请编号大于 Ri 的资源。

    这种方法存在的问题是， 编号必须相对稳定， 这就'限制了新类型设备的增加'；尽管在为资源编号时已考虑到大多数作业实际使用这些资源的
    顺序， 但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费； 此外， 这种按规定次序申请资源的方法， 也必
    然会给用户的编程带来麻烦。

避免死锁（银行家算法）

我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。

为保证资金的安全，银行家规定：

(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；

(2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量；

(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；

(4) 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金.

> 操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，
> (1)如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。
> (2)当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。
> (3)若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。
>

检测死锁(死锁定理)

通常分析描述死锁，可以用资源分配图。关于资源分配图，要仅仅抓住两点：

• 请求边
• 分配边

关键在找：空闲资源。如果空闲资源可以满足某个进程，这个进程就可以解脱了，把它摘除资源分配图，再看剩下的资源分配图，策略相同。

在资源分配图中，把分配的资源与进程连好，再看进程请求边。按照分配边分配好以后，剩余的资源就是空闲资源。此时再来分析进程Pi的请求边，如果空闲资源都能满足Pi的请求，也就意味着Pi可以从这个纠缠的图中得到解脱。删除Pi的所有相关的资源：已分配的+请求的。再递归处理剩下的资源分配图。

参看：https://blog.csdn.net/jgm20475/article/details/81297819

解除死锁

1、资源剥夺法

挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源，而处于资源匮乏的状态。

2、撤销进程法

强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。

3、进程回退法

让一（多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。