死锁

死锁：如果一组进程中的每一个进程都在等待该组进程中的其他进程才能引发的事件，那么该组进程是死锁的。

一、死锁的产生

死锁产生的四个必要条件：互斥条件、请求和保持、不可抢占、环路等待。

1.互斥

一段时间内，每个资源只能被一个进程占用，如果有其他进程请求该资源，那么就只能等待，直到占有该资源的进程释放资源。

2.请求和保持

进程已经保持了至少一个资源，又提出请求其他资源，该资源已经被其他进程所占用，此时请求资源的进程等待，且继续占用已获得的资源。

3.不可抢占

进程已经获得的资源不能被其他进程抢占，只能当进程使用完后自己释放。

4.循环等待

有两个及以上的进程组成一个环路，环路中的每个进程都在等待下一个进程所占用的资源。

二、死锁的预防

1.鸵鸟策略：

假装没发生死锁，由于解决死锁的代价非常高，发生死锁的时候如果对用户不会造成多大影响，或者发生死锁的概率很低，就采用鸵鸟策略来获取更高的性能。

2.在程序运行之前防止发生死锁，破坏死锁产生的四个必要条件中的一个或多个：

破环互斥条件，由于互斥是非共享设备所必须的，所以此条件一般不改变。
破坏请求和保持，分成两种策略：
- 给进程一次性分配运行所需的所有资源，这样进程运行过程中就不会提出资源要求，破坏了请求条件。
对于其他进程，如果不能一次获取所有资源就等待，这样进程不占用资源就破坏了保持条件。

该策略的缺点就是资源严重被浪费，降低了资源的利用率。进程可能发生饥饿，因为只有当存在满足进程需求的所有资源进程才能运行，这样有的进程就必须一直处于等待状态。
- 运行一个进程只获取部分资源后就可以开始运行，在运行过程中逐步释放已经分配且被使用完的资源，再进行新的资源请求。
破坏不可抢占，当已经占用部分资源的进程再次请求资源的时候，如果请求不能满足，它必须释放当前占用的资源，等到需要这些资源的时候再次申请，从而破坏了不可抢占条件。

缺点就是需要付出的代价较大，因为很多不可抢占资源一旦释放会导致一段时间内的成果无用，比如打印机。
破坏循环等待，将所有资源进行排序，进程只能按照资源的排序来获取资源。如果进程想要获取编号低的资源，就必须先释放具有相同或者更高编号的资源，才可以申请低编号资源，这样就保证了总是有一个进程占用了编号高的资源，该进程后续申请的资源必然是空闲的，就保证了进程能够继续递推下去，不会产生环路。

三、死锁的避免

在程序运行时避免发生死锁。就是在资源分配的过程中避免程序进入不安全状态，可以使用银行家算法来避免死锁。

安全状态：是指系统按照某种进程的递推顺序为每个进程分配资源，直到满足每个进程对资源的最大需求，使每个进程都能够顺利完成。

银行家算法：主要是确保银行发放贷款的时候，不会发生不能满足所有客户需求的情况。

每当有新进程进入系统的时候，需要声明它所需的最大资源数，该数不得超过系统总共拥有的资源数。当进程请求资源的时候，要确保请求的资源数小于系统现有的资源，然后分析系统将资源分配给该进程后是否会进入不安全状态，如果会就让其等待，不会就分配。

银行家算法有四种主要的数据结构：

可利用资源向量Available，向量中每个数代表了每种资源可分配的数量。
最大需求矩阵n*m，代表了n种进程对m种资源的最大需求数量。
已分配资源矩阵，代表了n种进程已经占用了m种资源的数量。
需求矩阵，代表了n种进程对m种资源还有多少需求的数量。

算法的流程：在需求矩阵中找到某个进程需求小于可利用资源向量的，如果找不到就说明系统会发生死锁。

如果找到了，就将进程标记为终止状态，将其占用的资源释放，然后继续之前的步骤，直到系统中的所有进程都被释放，此时状态是安全的。

四、死锁的检测和解除

不预先限制死锁的发生，而是当检测到死锁发生的时候采取措施解除死锁。

1.死锁的检测：需要采用资源分配图来检测当前是否发生死锁。

资源分配图是由一组进程和一组资源以及相互指向的边所构成的，进程请求的资源指向资源，资源分配给进程则指向进程，我们通过查找有向图中是否存在环来检测是否产生死锁，通过对访问过的节点进行标记，如果访问到已访问过的节点就说明存在环。

2.死锁的接触：

抢占资源：系统抢占死锁进程所需的资源，将其分配给死锁进程来解除死锁状态。
终止或者撤销进程：终止系统中的一个或多个死锁进程，直到打破循环。
- 终止所有死锁进程，开销极大。
- 逐个进程终止，按照某种顺序终止进程，直到释放的资源足够打破循环环路，系统就能解除死锁。
  
  对此需要思考按什么顺序代价最小：优先级、进程执行的时间、进程已获资源还需多少资源等。