======第三章处理机调度与死锁======（4）

======第三章处理机调度与死锁======（3）https://developer.aliyun.com/article/1415810

3.5.2 产生死锁的必要条件

  (1) 互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求该资源，则请求者只能等待，直至占有该资源 的进程用毕释放。

(2) 请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。

 (3) 不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

 (4) 环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0 ，P1 ，P2 ，…，Pn }中的 P 0 正在等待一个 P1 占用的资源；P1 正在等待 P 2 占用的资源，……， Pn 正在等待已被 P 0 占用的资源。

3.6 预防死锁的方法

3.6.1 预防死锁

1. 摒弃“请求和保持”条件

在采用这种方法时，系统规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。此时，若系统有足够的资源分配给某进程，便可把其需要的 所有资源分配给该进程，这样，该进程在整个运行期间便不会再提出资源要求，从而摒弃 了请求条件。但在分配资源时，只要有一种资源不能满足某进程的要求，即使其它所需的各资源都空闲，也不分配给该进程，而让该进程等待。由于在该进程的等待期间，它并未占有任何资源，因而也摒弃了保持条件，从而可以避免发生死锁。

 这种预防死锁的方法其优点是简单、易于实现且很安全。但其缺点却也极其明显：首先表现为资源被严重浪费，因为一个进程是一次性地获得其整个运行过程所需的全部资源 的，且独占资源，其中可能有些资源很少使用，甚至在整个运行期间都未使用，这就严重地恶化了系统资源的利用率；其次是使进程延迟运行，仅当进程在获得了其所需的全部资源后，才能开始运行，但可能因有些资源已长期被其它进程占用而致使等待该资源的进程 迟迟不能运行。

摒弃 “不剥夺” 条件

 在采用这种方法时系统规定，进程是逐个地提出对资源的要求的。当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。这意味着某一进程已经占有的资源，在运行过程中会被暂时地释放掉，也可认为是被剥夺了，从而摒弃了“不剥夺”条件。

 这种预防死锁的方法实现起来比较复杂且要付出很大的代价。因为一个资源在使用一 段时间后，它的被迫释放可能会造成前段工作的失效，即使是采取了某些防范措施，也还会使进程前后两次运行的信息不连续，此外，这种策略还可能因为反复地申请和释放资源，致使进程的执行被无限地推迟，这不仅延长了进程的周转时间， 而且也增加了系统开销，降低了系统吞吐量。

摒弃 “环路等待” 条件

 这种方法中规定，系统将所有资源按类型进行线性排队，并赋予不同的序号。例如， 令输入机的序号为 1，打印机的序号为 2，磁带机为 3，磁盘为 4。所有进程对资源的请求 必须严格按照资源序号递增的次序提出，这样，在所形成的资源分配图中，不可能再出现 环路，因而摒弃了“环路等待”条件。事实上，在采用这种策略时，总有一个进程占据了较高序号的资源，此后它继续申请的资源必然是空闲的，因而进程可以一直向前推进。

 这种预防死锁的策略与前两种策略比较，其资源利用率和系统吞吐量都有较明显的改善。但也存在下述严重问题：

 首先是为系统中各类资源所分配(确定)的序号必须相对稳定，这就限制了新类型设备的增加。

 其次，尽管在为资源的类型分配序号时，已经考虑到大多数作业在实际使用这些资源时的顺序，但也经常会发生这种情况：即作业(进程)使用各类资源的顺序与系统规定的顺序 不同，造成对资源的浪费。

 第三，为方便用户，系统对用户在编程时所施加的限制条件应尽量少。然而这种按规定次序申请的方法，必然会限制用户简单、自主地编程。

3.6.2 系统安全状态

在该方法中把系统的状态分为安全状 态和不安全状态，只要能使系统始终都处于安全状态，便可避免发生死锁。

安全状态

 在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给 进程；否则，令进程等待。

 所谓安全状态，是指系统能按某种进程顺序(P1 ，P2 ，…，Pn )(称〈P1 ，P2 ，…，Pn 〉序列为安全序列)，来为每个进程 P i 分配其所需资源，直至满足每个进程对资源的最大需求， 使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全 状态。

 虽然并非所有的不安全状态都必然会转为死锁状态，但当系统进入不安全状态后，便有可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。 因此，避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态。

安全状态之例

 我们通过一个例子来说明安全性。假定系统中有三个进程 P1 、P 2 和 P3 ，共有 12 台磁带 机。进程 P 1 总共要求 10 台磁带机，P 2 和 P 3 分别要求 4 台和 9 台。假设在 T 0 时刻，进程 P1 、 P 2 和 P 3 已分别获得 5 台、2 台和 2 台磁带机，尚有 3 台空闲未分配，如下表所示：

 经分析发现，在 T 0 时刻系统是安全的，因为这时存在一个安全序列〈P2 ，P1 ，P3 〉，即 只要系统按此进程序列分配资源，就能使每个进程都顺利完成。例如，将剩余的磁带机取 2 台分配给 P2 ，使之继续运行，待 P 2 完成，便可释放出 4 台磁带机，于是可用资源增至 5 台； 以后再将这些全部分配给进程 P1 ，使之运行，待 P 1 完成后，将释放出 10 台磁带机，P 3 便 能获得足够的资源，从而使 P1 、P2 、P 3 每个进程都能顺利完成。

由安全状态向不安全状态的转换

 如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在 T 0 时刻以后，P 3 又请求 1 台磁带机，若此时系统把剩余 3 台中的 1 台分配给 P3 ，则系统便 进入不安全状态。因为此时也无法再找到一个安全序列，例如，把其余的 2 台分配给 P2 ， 这样，在 P 2 完成后只能释放出 4 台，既不能满足 P 1 尚需 5 台的要求，也不能满足 P 3 尚需 6 台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果 导致死锁。类似地，如果我们将剩余的 2 台磁带机先分配给 P 1 或 P3 ，也同样都无法使它们 推进到完成，因此，从给 P 3 分配了第 3 台磁带机开始，系统便又进入了不安全状态。由此 可见，在 P 3 请求资源时，尽管系统中尚有可用的磁带机，但却不能分配给它，必须让 P 3 一 直等待到 P 1 和 P 2 完成，释放出资源后再将足够的资源分配给 P3 ，它才能顺利完成。

3.6.3 利用银行家算法避免死锁

1. 银行家算法中的数据结构

=Max[i, j]-Allocation[i, j]

银行家算法

 设 Request i 是进程 P i 的请求向量，如果 Requesti [j]=K，表示进程 P i 需要 K 个 R j 类型 的资源。当 P i 发出资源请求后，系统按下述步骤进行检查：

 (1) 如果 Request i [j]≤Need[i,j]，便转向步骤(2)；否则认为出错，因为它所需要的资源 数已超过它所宣布的最大值。

 (2) 如果 Requesti [j]≤Available[j]，便转向步骤(3)；否则，表示尚无足够资源，P i 须 等待。

 (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 ，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资 源分配状态，让进程 P i 等待。

安全性算法

系统所执行的安全性算法可描述如下：

(1) 设置两个向量：

   ① 工作向量 Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有 m 个元素，在执行安全算法开始时，Work:=Available。

   ② Finish， 它表示系统是否有足够的资源分配给进程，使之运行完成。 开始时先做 Finish[i]:=false；当有足够资源分配给进程时，再令 Finish[i]:=true。

 (2) 从进程集合中找到一个能满足下述条件的进程：

   ① Finish[i]=false；

   ② Need[i,j]≤Work[j]；若找到，执行步骤(3)，否则，执行步骤(4)。

 (3) 当进程 P i 获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应 执行： Work[j]:= Work[j]+Allocation[i,j]； Finish[i]:=true； go to step 2；

 (4) 如果所有进程的 Finish[i]=true 都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

银行家算法之例

 假定系统中有五个进程{P0 ，P1 ，P2 ，P3 ，P4 }和三类资源{A，B，C}，各种资源的数量 分别为 10、5、7，在 T 0 时刻的资源分配情况如图 3-16 所示。

(1) T 0 时刻的安全性：利用安全性算法对 T 0 时刻的资源分配情况进行分析(见图 3-17 所 示)可知，在 T 0 时刻存在着一个安全序列{P1 ，P3 ，P4 ，P2 ，P0 }，故系统是安全的。

(2) P 1 请求资源：P 1 发出请求向量 Request1 (1，0，2)，系统按银行家算法进行检查：

  ① Request1 (1，0，2)≤Need1 (1，2，2)

 ② Request1 (1，0，2)≤Available1 (3，3，2)

 ③ 系统先假定可为 P 1 分配资源，并修改 Available，Allocation 1 和 Need 1 向量，由此形 成的资源变化情况如图 3-16 中的圆括号所示。

由所进行的安全性检查得知，可以找到一个安全序列{P1 ，P3 ，P4 ，P2 ，P0 }。因此，系 统是安全的，可以立即将 P 1 所申请的资源分配给它。

 (3) P 4 请求资源：P 4 发出请求向量 Request4 (3，3，0)，系统按银行家算法进行检查：

   ① Request4 (3，3，0)≤Need4 (4，3，1)；

   ② Request4 (3，3，0)≤Available(2，3，0)，让 P 4 等待。

 (4) P 0 请求资源：P 0 发出请求向量 Requst0 (0，2，0)，系统按银行家算法进行检查：

   ① Request0 (0，2，0)≤Need0 (7，4，3)；

   ② Request0 (0，2，0)≤Available(2，3，0)； ③ 系统暂时先假定可为 P 0 分配资源，并修改有关数据，如图 3-19 所示。

(5) 进行安全性检查：可用资源 Available(2，1，0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。

  如果在银行家算法中，把 P 0 发出的请求向量改为 Request0 (0，1，0)，系统是否能将资源分配给它，请读者考虑。

3.7 死锁的检测与解除

3.7.1 死锁的检测

(1) 保存有关资源的请求和分配信息；

(2) 提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。

资源分配图

 系统死锁可利用资源分配图来描述。该图是由一组结点 N 和一组边 E 所组成的一个对 偶 G=(N1 E)，它具有下述形式的定义和限制：

 (1) 把 N 分为两个互斥的子集，即一组进程结点 P={p1 ， p2 ，…，pn }和一组资源结 点 R={r1 ，r2 ，…，rn }，N=P∪R。在图 3-20 所示的例子中，P={p1 ，p2 }，R={r1 ，r2 }， N={r1 ，r2 }∪{p1 ，p2 }。

 (2) 凡属于 E 中的一个边 e∈E，都连接着 P 中的一个结点和 R 中的一个结点，e={pi ，rj } 是资源请求边，由进程 p i 指向资源 rj ，它表示进程 p i 请求一个单位的 r j 资源。e={rj ，pi }是 资源分配边，由资源 r j 指向进程 pi ，它表示把一个单位的资源 r j 分配给进程 pi 。图 3-13 中 示出了两个请求边和两个分配边，即 E={(p1 ，r2 )，(r2 ，p2 )，(p2 ，r1 )，(r1 ，p1 )}。

 我们用圆圈代表一个进程，用方框代表一类资源。由于一种类型的资源可能有多个，我们用方框中的一个点代表一类资源中的一个资源。此时，请求边是由进程指向方框中的 rj ，而分配边则应始于方框中的一个点。图 3-20 示出了一个资源 分配图。图中，p 1 进程已经分得了两个 r 1 资源， 并又请求一个 r 2 资源；p 2 进程分得了一个 r 1 和一 个 r 2资源，并又请求 r 1资

死锁定理

 (1) 在资源分配图中，找出一个既不阻塞又非独立的进程结点 Pi 。在顺利的情况下，Pi 可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去 p i 所求的请求边和分配边，使之成为孤立的结点。在图 3-21(a)中，将 p 1 的两个分配边和一 个请求边消去，便形成图(b)所示的情况。

 (2) p 1 释放资源后，便可使 p 2 获得资源而继续运行，直至 p 2 完成后又释放出它所占有 的全部资源，形成图©所示的情况。

 (3) 在进行一系列的简化后，若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完 全简化的。

 对于较复杂的资源分配图，可能有多个既未阻塞，又非孤立的进程结点，不同的简化顺序是否会得到不同的简化图？有关文献已经证明，所有的简化顺序，都将得到相同的不 可简化图。同样可以证明：S 为死锁状态的充分条件是：当且仅当 S 状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。

2.7.2 死锁的解除

当发现有进程死锁时，便应立即把它们从死锁状态中解脱出来。常采用解除死锁的两种方法是：

(1) 剥夺资源。从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。

(2) 撤消进程。最简单的撤消进程的方法是使全部死锁进程都夭折掉；稍微温和一点的方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。 在出现死锁时，可采用各种策略来撤消进程。 例如， 为解除死锁状态所需撤消的进 程数目最小；或者，撤消进程所付出的代价最小等。一种付出最小代价的方法如图 3-22 所示。

假定在死锁状态时，有死锁进程 P1 ，P2 ，…，Pk 。首先，撤消进程 P1 ，使系统状态由 S→U1 ，付出的代价为 CU1 ，然后，仍然从 S 状态中撤消进程 P2 ，使状态由 S→U2 ，其代价 为 CU2 ，…，如此下去可得到状态 U1 ，U2 ，…，Un 。若此时系统仍处于死锁状态，需再进 一步撤消进程，如此下去，直至解除死锁状态为止。这种方法为解除死锁状态可能付出的 代价将是 k(k-1)(k-2)…/2C。显然，所花费的代价很大，因此，这是一种很不实际的方法。

一个比较有效的方法是对死锁状态 S 做如下处理：从死锁状态 S 中先撤消一个死锁进 程 P1 ，使系统状态由 S 演变成 U1 ，将 P 1 记入被撤消进程的集合 d(T)中，并把所付出的代价 C 1 加入到 rc(T)中；对死锁进程 P2 、P 3 等重复上述过程，得到状态 U1 ，U2 ，…，Ui ，Un ， 然后，再按撤消进程时所花费代价的大小，把它插入到由 S 状态所演变的新状态的队列 L 中。显然，队列 L 中的第一个状态 U 1 是由 S 状态花最小代价撤消一个进程所演变成的状态。 在撤消一个进程后，若系统仍处于死锁状态，则再从 U 1 状态按照上述处理方式再依次地撤 消一个进程，得到 U 1 ′ ， U ′ 2 ， U ′ 3 ，…， U ′ k 状态，再从 U ′ 状态中选取一个代价最小的 U ′ j ， 如此下去，直到死锁状态解除为止。为把系统从死锁状态中解脱出来，所花费的代价可表示为：

R(S) min = min{CUi } + min{CUj } + min{CUk } + …