操作系统入门 -- 死锁

操作系统入门 – 死锁

1.什么是死锁、死锁产生的条件

1.1 死锁

在两个或多个并发进程中，如果每个进程都持有某种资源，并且正在等待其他进程释放它或进程都保持资源，在当前状态下无法推进。通俗来说就是两个或多个进程进入无限期阻塞、互相等待状态。

1.2 产生死锁的必要条件

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

1.3 死锁的处理和预防

• 预防死锁：通过破坏死锁必要条件之一即可预防。
• 避免死锁：在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免发生死锁。
• 检测死锁：允许进程在运行过程中发生死锁，但需要及时检测到，并通过合理的方式解除死锁。
• 解除死锁：当系统发生死锁时，采取相应措施，解除死锁。
• 忽略死锁：如鸵鸟算法，当发生死锁时忽略问题，适用于发生的死锁不会对用户造成太大影响。

2. 死锁的预防方式

2.1 破坏“不抢占”条件

2.1.1 运行方式

当某个进程请求新的资源得不到满足时，立即释放保持的所有资源,并等待重新申请。

2.1.2 缺点

实现过程复杂，抢占资源可能导致部分工作失效，反复申请和释放对系统开销大,也可能导致饥饿。

2.2 破坏“请求和保持”条件

当一个进程请求资源时，不能持有不可抢占的系统资源。一下有两种协议

2.2.1 协议1

• 第一种协议：所有进程在运行前，必须一次性申请其在运行过程中所需的全部资源。此时若系统有足够的资源分配给某进程，就可以把进程所需资源分配给给它，在运行过程中，进程就不会再申请资源，破坏了“请求”条件。系统在分配资源时只要有一种资源不能满足进程要求，即使其他所需的各个资源都空闲也不会分分给当前线程。
  -第一种协议缺点：该协议看似简单易行且安全，但是资源会被严重浪费，降低资源利用率，同时也经常会发生饥饿现象。

2.2.2 协议2

• 第二种协议：这是对上述协议的改进，该协议能够允许一个进程只获得运行初期所需资源后就开始运行。在运行过程中逐步释放系统已经分配并用完的资源，再请求新的资源。

2.3 破坏“循环等待”条件

2.3.1 实现过程

系统将会给资源先进行编号，规定每个进程必须按照序号递增顺序请求资源，编号相同的同类资源一次性申请完毕。该过程保证了当一个进程占有小号的资源后才能申请大号的资源，而持有大号资源的进程无法申请小号资源，杜绝了循环等待的现象。

2.3.2 缺点

• 不方便增加新设备，增加新设备后所有资源需要重新编号。
• 进程实际使用的资源顺序可能和编号不一致，浪费资源。
• 按规定申请资源在编程过程中较为麻烦。

3.银行家算法

3.1 概念

银行家算法是用来避免操作系统出现死锁的有效算法。为实现银行家算法，系统必须设置若干数据结构，同时要解释银行家算法，必须先解释操作系统安全状态和不安全状态。

• 安全序列：指一个进程序列<P₁，…，P_n>是安全的。即对于每个进程 P_i (1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程P_j(j < i)当前占用资源总和。
• 安全状态：如果存在一个又系统中所有进程构成的安全序列<P₁，…，P_n>，则系统处于安全状态，该状态下一定不会发生死锁。
• 不安全状态：不存在一个安全序列。该情况下可能会导致死锁。

3.2 银行家算法数据结构

• 可利用资源向量Available：是一个含有m个元素的数组，其中每个元素代表一类可利用的资源数目。若Available[j] = K，则表示系统中现有Rj类资源K个。
• 最大需求矩阵Max：一个n*m的矩阵，其中定义了系统中n个进程中每个进程所需最大为m的资源值。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。
• 分配矩阵Allocation：同上，也是一个n*m的矩阵，其中定义了系统中每一类资源当前已经分配每一个进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的 数目为K。
• 需求矩阵Need：这也是一个n*m的矩阵，表示每个进程尚需各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。

3.3 算法流程

设Req(i)是进程P_i请求的向量，若Req(i)[j] = K。表示进程P_i需要K个R(j)类型资源。当P_i发现资源请求后系统将执行以下步骤。

• (1).若Req(i)[j] <= Need[i , j]转至步骤(2)，否则出错，因为所请求的资源数超过其规定的最大值。
• (2).若Req(i)[j] <= Available[i , j]转至步骤(3)，否则表示尚无足够资源，P_i等待。
• (3).系统尝试将资源分配给P_i并修改以下参数：
  Available[j] = Available[j] - Req(i)[j]；
  Allocation[i , j] = Allocation[i j] + Req(i)[j];
  Need[i , j] = Need[i , j] - Req(i)[j];

4.死锁的检测与解除

为了能够对系统中的死锁进行检测必须要有

• 保存有关资源的请求和分配信息；
• 提供一种算法，利用信息监测系统是否死锁

4.1 算法

• 找出既不阻塞又非独立的进程节点P_i，顺利情况下，P_i可以得到所需的资源并能继续运行，直至完成，最后释放持有的所有资源。这相当于消去它所有的请求边和分配边，使之称为孤立的结点。
• 进程P_i释放的资源可以唤醒某些因等待这些资源而被阻塞的进程，这些被阻塞的进程变为非阻塞状态。然后重复上面的过程，消去请求边和分配边。
• 当节点为孤立状态是，则可以完全简化。

4.2 解除死锁

• 抢占资源：从一个或多个进程中抢占足够多的资源，分配给死锁进程，以解除死锁。
• 终止进程（包括终止所有死锁进程和逐个终止进程）：终止系统中的一个或多个死锁进程，直到打破循环环路，使系统从死锁状态中解脱出来。
• 进程退回