操作系统-死锁

1. 死锁的概念：

在两个或多个并发进程中，如果每个进程持有某种资源而又等待其它进程释放它或它们现在持有的资源，在未改变这种状态之前，都不能向前推进，称这一组进程产生了死锁。通俗的讲就是两个或多个进程无限期的阻塞、相互等待状态。

2. 死锁产生的条件：

互斥条件：在一段时间内，某个资源只能被一个进程使用。
请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
不剥夺条件：进程获得资源，在未完全使用完之前，不能强行剥夺。
循环等待条件：若干进程之间形成一种头尾相接的环形等待资源关系

3. 解决死锁的常用策略：

鸵鸟策略：
因为解决死锁的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能，当发生死锁时不会对用户造成多大的影响，或者发生死锁的概率很低，可以采用鸵鸟策略，大多数操作系统，包括linux unix windows，处理死锁的办法仅仅是忽略它。

预防死锁：
由于互斥条件是非共享设备所必需的，不仅不能改变，还应该加以保证，因此主要是破坏产生死锁的三个个条件。
- 破坏请求与保持条件：
  1. 第一种协议：所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需要的全部资源
  2. 第二种协议：是对第一种协议的改进，它允许一个进程只获得初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的，且已经使用完毕的全部资源，然后再请求新的所需资源。
- 破坏不剥夺条件：
  在一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时在重新申请。
- 破坏循环等待条件：
  对系统中所有资源类型进行线性排序，并赋予不同的序号。规定每个进程必须按照序号递增的顺序请求资源

避免死锁：
避免死锁同样是属于事先预防的策略，但并不是事先采取某种限制措施，破坏产生死锁的必要条件，而是在资源的动态分配过程中，防止系统进入不安全的状态，以避免发生死锁。这种方法所施加的限制条件较弱，可能获得较好的系统性能，目前常用此方法来避免发生死锁。
- 银行家算法：
  每一个新进程在进入系统时，它必须申明在运行过程中，可能需要的每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。若满足，再进一步计算在将这些资源分配给进程后，是否会使系统出于不安全状态。如果不会，才将资源分配给进程，否则让进程等待。
  - 数据结构：
    available：可利用资源向量，含m个元素的数组，其中的每个元素代表一类可利用的资源数目，其初值是系统中所配置的该类全部可用资源的数目。
    max：最大需求矩阵，这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。
    allocation：分配矩阵，这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。
    need：需求矩阵，这也是一个n*m的矩阵，用以表示每一个进程尚需要的各类资源数
  - 算法：
    设request是进程Pi的请求向量，如果requesti[ j ] = K，表示进程Pi需要K个Rj类型的资源，当Pi发出资源请求时，系统便按下述步骤进行检查：
    1. 如果Requesti[ j ] <= Need[ i, j ]，便转向步骤2，否则认为出错，因为它所需要的资源超过它所宣布的最大值
    2. 如果Requesti[ j ] <= Available[ j ]，便转向步骤3，否则表示尚无足够资源，Pi需要等待
    3. 系统尝试着把资源分配给进程Pi，并修改下面数据结构中的数值：
      Available[ j ] = Available[ j ] - Requesti[ j ];
      Allocation[ i, j ] = Allocation[ i, j ] + Requesti[ j ];
      Need[ i, j ] = Need[ i, j ] - Requesti[ j ];
    4. 系统执行安全性检查，检查此次资源分配后系统是否处于安全状态，若安全，才正式将资源分配给进程，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待
  - 安全性算法：
    系统所执行的安全性算法可描述如下：
    1. 设置两个向量，工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work = Available，Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时Finish[ i ] = false，当有足够资源分配给进程时，再令Finish = true
    2. 从进程集合中找到一个能满足下述条件的进程：
      Finish[ i ] = false;
      Need[ i, j ] <= Work[ j ];
      若找到，执行步骤3，否则，执行步骤4
    3. 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
      Work[ j ] = Work[ j ] + allocation[ i, j ];
      Finish[ j ] = true;
      go to step 2;
    4. 如果所有进程的Finishi[ i ] = true都满足，则表示系统处于安全状态，否则，系统处于不安全状态

死锁的检测与解除
死锁检测中的数据结构类似于银行家算法中的数据结构：
1 . Available：可利用资源向量表，它表示了m类资源中每一类资源的可用数目。
1. 把不占用资源的进程（向量Allocation = 0）记入L表中，即Li ∪ L
2. 从进程集合中找到一个Requesti <= Work的进程，做如下处理：
  1. 将其资源分配图简化，释放出资源，增加工作向量Work = Work + Allocation i
  2. 将其记入L表中
3. 若不能把所有进程都计入到L表中，便表明系统状态S的资源分配图是不可完全简化的。因此，该系统状态将发生死锁。
  - 代码表示：
    Work = Available;
    L = { Li | Allocation i = 0 ∩ Request i = 0 }
    for ( all Li ∉ L )
    {
    for( all Request i <= Work ) {
    Work = Work + Allocation i;
    Li ∪ L;
    }
    }
- 资源分配图的化简过程：
  
  image
- 死锁的解除：
  最简单的处理措施是立即通知操作员，请操作员以人工方法处理死锁，另一种措施则是利用死锁接触算法，常用的方法有：
  1. 抢占资源，从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以解除死锁状态
  2. 终止（或撤销）进程，终止（或撤销）系统中的一个或多个进程，直至打破循环环路，是系统从死锁状态解脱出来
- 数据库死锁及解决方法参考