操作系统

处理机调度与死锁（二）

接处理机调度与死锁（一），本篇主要讲述死锁部分内容。

四.死锁概述

本节排版有些问题，可以先看本章第三部分对死锁概念的解释及定义，之后再来看第二部分计算机系统中的死锁可能会更好理解。

1.资源问题

  • 引起死锁的资源类型：临界资源（需要互斥访问，不可被抢占的资源）。

（1）可重用性资源和消耗性资源

  • 可重用性资源

1）独占使用，不允许共享。

2）使用方法：请求资源 ——> 使用资源 ——> 释放资源

3）在系统中数量相对固定，进程在运行期间不能创建和删除。

  • 可消耗性资源（临时性资源）

1）在系统中数量可以不断变化

2）进程在运行过程中可以（生产者）创造和（消费者）消耗。

（2）可抢占性资源和不可抢占性资源

  • 可抢占性资源：< 处理机 > < 内存 >
  • 不可抢占性资源：< 磁带机 > < 刻录机 > < 打印机 >

2.计算机系统中的死锁

  • 死锁的起因：源于多个进程对资源的竞争，包括不可抢占性资源和可消耗性资源。

（1）竞争不可抢断性资源引起死锁

共享文件时的死锁情况：

（2）竞争可消耗性资源引起死锁

进程之间通信时的死锁：

（3）进程推进顺序不当引起死锁

进程推进顺序对死锁的影响：

3.死锁的定义、必要条件和处理方法

（1）死锁的定义

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

饥饿与死锁：

  • 饥饿：线程无限等待

例如：低优先级的线程等待着不断被高优先级线程所使用的资源。

  • 死锁：等待资源形成环路

线程A拥有资源1并且等待资源2

线程B拥有资源2并且等待资源1

  • 死锁 ——> 饥饿（反之不成立）

饥饿可以结束（但不是必须的）

死锁如果没有外力介入无法结束

（2）产生死锁的必要条件

产生死锁必须同时具备以下四个必要条件：

  • 互斥条件：要求在一段时间内某资源仅被一进程占用。
  • 请求和保持条件：当前已拥有资源的进程，仍能申请新的资源；而且，当该进程因新的资源被其他进程占用而阻塞时，对已获得的资源保持不放。
  • 不可抢占条件：进程已获得的资源，只能在使用完时自行释放。
  • 循环等待条件：在发生死锁时，必然存在一个进程 —— 资源的环形链。即进程集合{ $P_0 , P_1 , …. , P_n$ } 对资源的请求成环状：$ P_0 -> P_1 -> P_2 -> … P_n -> P_0$

（3）处理死锁的方法

  • 预防死锁

1）通过设置某些条件，以破坏产生死锁的四个必要条件之一的一个或几个条件，来防止发生死锁。

2）易实现，但可能导致资源利用率和系统吞吐量低。

  • 避免死锁

1）在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。

2）可获得较高的资源利用率和系统吞吐量，但难度较大。

  • 检测死锁

1）通过系统设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；然后采取适当措施。

2）从系统中将已发生的死锁清除掉，需要采用一些用于强制性抢夺资源或者终止任务的技术。

  • 解除死锁

常用方法：撤销或挂起一些进程，回收资源分配给其他处于阻塞的进程。

特点：资源利用率好，系统吞吐量大。实现难度最大。

六.预防死锁

  • 预防死锁的方法

使四个必要条件中的第2、3、4条件中的一个或者几个不能成立，以防止发生死锁。

1）方法一：破坏“请求和保持”条件

2）方法二：破坏“不可抢占”条件

3）方法三：破坏“循环等待”条件

1.破坏“请求和保持”条件

  • 破坏“请求和保持”条件：系统确保当一个进程在请求资源时，它不能持有不可抢占的资源。

（1）第一种协议（预先静态分配法）

  • 系统要求所有进程在开始运行之前，必须一次性地申请在整个运行过程中所需要的全部资源。

破坏“请求”条件：进程在整个运行期间，不会再提出资源要求

破坏“保持”条件：等待期间进程未占有任何资源

  • 优点：简单、易于实现、安全
  • 缺点：资源浪费严重，进程经常发生饥饿现象

（2）第二种协议（阶段性资源分配法）

  • 允许一个进程只获得运行初期所需的资源后便开始运行，进程运行过程中再逐步释放已经分配给自己、且已用毕的全部资源，然后再请求新的所需资源。

2.破坏“不可抢占资源”条件

  • 当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。
  • 实现难度较大，且要付出很大代价。
  • 反复申请和释放资源，使进程的执行无限地推迟。延长进程的周转时间，增加系统开销，降低系统吞吐量。

3.破坏“循环等待”条件

  • 系统将所有资源类型按线性排序，并赋予不同的序号，所有进程对资源的请求必须严格按资源序号递增的次序提出。这样，在资源分配图中，不会出现环路，因此摒弃了“环路等待”条件。
  • 优点：与前两种策略相比，资源利用率和系统吞吐量都有明显提高。
  • 缺点

1）限制新设备类型的增加

2）作业（进程）使用各类资源的顺序，与系统规定顺序不同而造成资源浪费

3）限制用户的自主编程

七.避免死锁

1.系统安全状态

  • 避免死锁的方法：将系统的状态分为安全状态和不安全状态，只要系统的状态处于安全状态，便可避免发生死锁。
  • 资源分配方法：允许进程动态地申请资源，系统在进行分配之前，先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，便将资源分配给进程；否则，进程等待。

（1）安全状态

  • 安全状态：指系统能按照某种进程推进顺序如 < $P_1 , P_2 , P_3 , … , P_n$ > （称 < $P_1 , P_2 , P_3 , … , P_n$ > 为安全序列），来为每个进程分配其所需资源，直至最大需求，使每个进程都顺利完成。
  • 不安全状态：不存在安全序列的状态。
  • 避免死锁的实质：如何使系统不进入不安全状态。
  • 结论：并非所有不安全状态都是死锁状态，但只要系统处于安全状态便可避免死锁状态。

（2）安全状态举例

不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。

2.利用银行家算法避免死锁

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

  • 可利用资源向量 Available ：是一个含有 m 个元素的数组，其中每一个元素代表一类可利用的资源数目，其初始值使系统中所配置的该类全部可用资源数目。其值随资源的分配和回收而动态地改变。
  • 最大需求矩阵 Max ：是一个 n×m 的矩阵，定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求。
  • 分配矩阵 Allocation ：是一个 n×m 的矩阵，定义了系统中每一类资源当前__已分配__给每一进程的资源数。
  • 需求矩阵 Need ：是一个 n×m 的矩阵，表示每一个进程尚需的该类资源数。

银行家算法中的数据结构

int n; //系统中进程的总数 
int m;  //资源类总数
int Available[m];
int Max[n,m];
int Allocation[n,m];
int Need[n,m];
int Request[n,m];
  • 上述三个矩阵的关系

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

其中：

Need[ i , j ] = k表示进程 i 还需要 $R_j$ 类资源 k 个。

Max[ i , j ] = k表示进程 i 还需要 $R_j$ 类资源的最大数目为 k。

Allocation[ i , j ] = k表示进程 i 当前已分得 $R_j$ 类资源的数目为。

Available[ j ] = k表示系统中现有 $R_j$ 类资源 k 个。

（2）银行家算法

设$Request_i$是进程$P_i$的请求向量。

例：$Request_i$[ j ] = k

（3）安全性算法

  • 为进行安全性检查，定义数据结构：
int Work[m];
int Finish[n];
  • 安全性检查步骤

1）Work = Available Finish[ i ] = false

2）寻找满足条件的 i ：

Finish[ i ] = false && Need[ i , j ] <= Work

if not find

转4）

3）Work[ i ] = Work[ i ] + Allocation[ i , j ] && Finish[ i ] = true 转2）

4）若对所有 i ，Finish[ i ] = true都满足，则系统处于安全状态，否则处于不安全状态

（4）银行家算法举例

假定系统中有五个进程｛$ P_0 , P_1 , P_2 , P_3 , P_4$｝和三类资源｛A, B, C｝，各种资源的数量分别为10、5、7。

$T_0$时刻资源分配表：

工作向量Work，它表示系统可提供给进程所需运行时间的各类资源的数目

$T_0$时刻的安全序列：

当$P_1$发出请求向量Request（1，0，2）

系统作如如下动作：

1）合理性检查：$Request_i(1,0,2) <= Need_i(1,2,2)$

2）查库存：$Request_i(1,0,2) <= Available(1,2,2)$

3）试分配

4）安全性检查

5）得出结论：因为可以找到一个安全序列{$P_1,P_2, P_4,P_0, P_2$}，系统是安全的，所以可以满足P1的资源申请

若P4发出请求向量Request（3，3，0）

这种情况，就不能满足要求。$P_4$就需要继续等待。

若P0发出请求向量Request（0，2，0）

系统进行如下操作：

1）合理性检查：$Request_0$（0，2，0） <= $Need_0$（7，4，3）

2）查库存：$Request_0$（0，2，0） <= $Available$（2，3，0）

3）试分配

4）安全性检查

5）结论：可用资源Available(2,1,0)已不能满足任何进程的需要，系统进入不安全状态，拒绝$P_0$的资源申请。

八.死锁的检测与解除

1.死锁的检测

  • 当系统为进程分配资源时，若未采取任何限制措施，则系统必须提供检测和解除死锁的手段。为此系统必须有：

    1）保存有关资源的请求和分配信息

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

  • 检测时机：

    1）进程等待时检测死锁（其缺点是系统的开销大）

    2）定时检测

    3）系统资源利用率下降时检测死锁

（1）资源分配图

（2）死锁定理

  • 充分条件：当且仅当系统某状态S所对应的资源分配图是不可完全简化的，则S是死锁状态，而不可化简的进程是被死锁的进程。

  • 完全简化：通过一系列简化后，所有的进程都成为孤立节点。

  • 不可能完全简化：通过任何过程都不能使图完全简化。。

  • 资源分配图的简化

（3）死锁检测中的数据结构

  1. 可利用资源向量Available，它表示了m 类资源中每一类资源的可用数目。

  2. 把不占用资源的进程（向量Allocation = 0）记入L表中， 即$L_i$∪L。

  3. 从进程集合中找到一个$Request_i$ ≤ Work的进程，做如下处理：

将其资源分配图简化，释放出资源，增加工作向量Work = Work + $Allocation_i$。 将它记入L表中。

  1. 若不能把所有进程都记入L表中，便表明系统状态S的资源分配图是不可完全简化的。因此，该系统状态将发生死锁。
Work  =  Available;
L  = {Li | Allocationi=0 ∩ Requesti=0} //孤立进程点
for (all  Li 不属于 L) 
{
   For (all Requesti <= Work) 
   {  
   	Work  = Work + Allocationi;
   	Li∪L
    }
}
deadlock  =  not (L={P1, P2, …, Pn})

2.死锁的解除

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

    1）剥夺资源：从其它进程剥夺足够数量的资源给死锁进程。

    2）撤消进程：

    最简单的方法是撤消全部死锁的进程，使全部死锁进程都夭折掉。

    稍微温和一点的方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用，死锁状态消除为止。

  • 对撤消进程方法，选择原则可采用下面的一种：

    1）目前为止消耗的处理机时间最少；

    2）目前为止产生的输出最少；

    3）预计剩下的时间最长；

    4）目前为止分配的资源总量最少；

    5）优先级最低。

  • 为把系统从死锁状态中解脱出来，所花费的代价可表示为：

    $ R(S){min} = min{C{ui}}+min{C_{uj}}+min{C_{uk}}+…$

    付出代价最小的死锁解除方法：

    更新于 2019/01/26 — 16:39

© 2018 - 2023 fmt.Println("Li Duo")
自认为是幻象波普星的来客
Built with Hugo
主题 Stack 由 Jimmy 设计