第三章：处理机调度与死锁

💡整理不易，先赞后看，养成习惯💡 ![$45]L}1IJT}O~WQRF9GEC0.png

3.1 处理机调度的层次和调度算法的目标

💡调度是指在一个队列中，按照某种方法（算法），选择一个合适的个体的过程。

处理机的调度层次

根据调度对象的不同，可以分为三个层次高级调度，中级调度，低级调度

低级调度

低级调度有叫做进程调度或者短程调度。也就是说调度的对象是进程（或者是内核级线程），由分派程序（Dispatcher）分派处理机。
其主要功能就是根据算法，从**就绪队列**选择某一个进程获得处理机。

进程调度是一种最基本的调度，在多批道处理、分时和实时系统中都必须配置此类调度。

高级调度

高级调度又叫做作业调度、长程调度、接纳调度。调度的对象是作业。其重要功能是从后背队列汇总选取哪几个作业调入内存当中。

这种调度一般用于批处理系统，分/实时系统一般直接入内存，无此环节。

中级调度

中级调度又叫做内存调度，主要是为了提高内存的利用率和系统吞噬量。

三种调度中，**进程调度**运行频率最高，在分时系统中通常是10~100ms便进行一次进程调度，因而进程调度算法不能太复杂。
**作业调度**往往是发生在一个（批）作业运行完毕，退出系统，而需要重新调入一个（批）作业进入时，一般作业调度的周期较长，大约几分钟一次。中级调度的运行频率，介于上述两种调度之间。

处理机调度算法的目标

调度算法的共同目标

1. 资源利用率

为提高系统的资源利用率，应使系统中的处理机和其它所有资源尽可能的保持忙碌状态。其中CPU的利用率可计算如下：

1. 公平性

指所有进程都获得合理的CPU时间，不会发生进程饥饿现象。

公平性是相对的，对于相同类型的进程应该获得相同的服务，不同类型的进程提供不同的服务。

1. 平衡性

由于系统中可能具有多种类型的进程，有的属于计算型作业，有的属于I/O型。为使CPU和各种外设经常处于忙碌状态，调度算法应尽可能保证系统资源使用的平衡性。

1. 策略强制执行

对于所制定的各种策略，如果需要，必须予以正确执行。

不同系统的目标

3.2 💡作业与作业调度

相关概念

作业的相关概念

💡作业调度仅存在于批处理系统中

• 作业：包含通常的程序和数据，配作业说明书，系统根据该说明书对程序的运行进行控制。
• 作业步：作业运行经过的，相对独立又相互关联的加工步骤。

• 作业控制块（JCB）：它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。

  作业运行的三个阶段

• 收容阶段：操作员把用户提交的作业通过某种方式或SPOOLING系统输入到硬盘上，再为该作业建立JCB，并把它放入作业后备队列中。后备状态。

• 运行阶段：当作业被作业调度选中后，便为它分配必要的资源和建立进程，并将它放入就绪队列。一个作业从第一次进入就绪状态开始，知道它运行结束前，在此期间都处于运行状态。
• 完成阶段：当作业运行完成、或发生异常情况而提前结束时，作业便进入完成阶段，相应的作业状态为完成状态。

  💡调度算法

  先来先服务调度算法（FCFS）

  当系统有多个作业请求 CPU 处理时，FCFS 调度算法会按照它们被提交的时间顺序依次得到 CPU 时间片，并执行对应的进程。
  如果当前进程执行完了，但仍有其他作业等待 CPU 时间片，则根据他们的进入时间，按照 FCFS 的方式进行排序，然后依次分配 CPU 时间片给这些进程。
  举个例子：

相关名词解释：

• 服务时间：指进程执行的时间
• 周转时间：完成时间 - 到达时间
• 带权周转时间：（完成时间 - 到达时间）/ 服务时间

这上面这个表格中，四个进程就是按照到达时间以此进入CPU执行。

优点：

1. 实现简单
2. 有利于长作业
3. 有利于CPU繁忙型的作业

缺点：

1. 不利于短作业
2. 低响应时间

   短作业优先调度算法（SJF）

   短作业优先调度算法（Shortest Job First，简称SJF）是一种根据进程预计执行时间来进行调度的算法，即预测 cpu 执行时间最短的进程先执行。
   还是上面那个例子：

按照短作业优先调度进程执行的顺序如下：

1. 0时刻只有A进程在就绪队列中，所以先执行A进程，此时时间来到1，进程B进入就绪队列
2. 1时刻就绪队列只有B，所以再执行B进程，此时时间来到101，进程C和进程D进入就绪队列
3. 101时刻就绪队列有两个，其中D的服务时间最短，所以先执行D，此时时间来到111，无后续进程
4. 111时刻只有C进程，最后执行C进程

综上，在这个例子中采用短作业优先的顺序为：A->B->D->C。
优点：

1. 有效地降低作业的平均等待时间
2. 缩短平均周转时间和平均带权周转时间
3. 提高了系统吞吐量
4. 有利于短作业

缺点：

1. 不利于长作业，会出现饿死现象
2. 未考虑紧迫程度，不能保证紧迫性作业(进程)会被及时处理。
3. 该算法不一定能真正做到短作业优先调度。进程运行时间不易确定，通常采用近似估算方法值。

   所谓“饿死”就是指一个进程长时间没有获取资源从而一直处于等待的情况。

优先级调度算法（PSA）

优先级调度算法是从后备队列中选择若干个优先级最高的作业，调入内存运行。
从就绪队列中选择一个优先级最高的进程，让其获得处理器并执行。
看下面这个简化的例子：

在0时刻四个进程都存在，也就是说四个进程都在就绪队列当中，此时按照优先级大小从小到大依次执行进程，所以进程的执行顺序为：A->C->B->D。

当然如果进程在某一时刻还没到达则不参与优先级次序的比较。

高响应比调度算法（HRRN）

高响应比优先调度算法综合考虑等待时间和服务时间为调度指标。其衡量的指标为响应比，计算方式如下：

Rp=（等待时间＋服务时间）/ 服务时间 = 1+ tw/ts

1. tw（等待时间）相同的进程，短作业RP大
2. ts（服务时间）相同的进程间相当于FCFS

没调度进程都优先选择响应比较高的作业（进程）运行。

这种调度算法可用于作业调度，也可用于进程调度。

举个例子：

1. 首先肯定还是执行A，此时时间来到4。
2. 时间为1的时候，BCD三个进程都已经到了所以：twB = twC = twD = 3
3. 三个进程的响应比为：
   1. RpB = 1 + 3/2 = 2.5
   2. RpC = 1 + 3/3 = 2
   3. RpD = 1 + 3/4 = 1.75
4. 此时响应比最高是B，所以先执行B
5. 后续类推….

优点：

1. 介于FCFS和SJF算法之间的一种拆衷的算法。长短兼顾

缺点：

1. 需计算Rp，增加系统开销

3.3 💡进程调度

进程调度是操作系统中的一项关键任务，用于决定哪个进程可以继续执行下一条指令。操作系统通过对进程的管理和调度来确保系统资源（例如CPU、内存等）得到最优的利用，并提高系统的稳定性和性能。

进程调度的任务，机制和方式

进程调度的任务

• 保存处理机的现场信息
• 按某种算法选取进程

• 把处理机分配给进程

  进程调度机制

  想要实现进程调度，需要配备以下内容：

• 排队器：每当一个进程变为就绪状态，排队器便将它插入到相应的就绪队列。

• 分派器：分派器依据进程调度程序所选出的进程，将其从就绪队列取出，然后进行从分派器到新选出进程间的上下文切换，将处理机分配给新选出的进程。

• 上下文切换器：在处理机进行切换时，会发生两对上下文的切换。

  进程调度方式

  进程调度的方式主要有两种：
  （1）非抢占式 :::info 系统一旦把处理器分配给某进程后，该进程就占有处理器一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。 ::: 也就是说一旦一个进程被调度获得处理器，那么其他的进程就不可以抢占其获得的处理器。
  在这种方式下引起进程调度的原因有：

• 正在执行的进程运行完毕或无法再继续（自然结束进程）

• 正在执行的进程提出I/O请求而暂停
• 在通信或同步中，执行了某种原语操作，如Block.

（2）抢占式 :::info 允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。 ::: 这种方式下，其他进程可以抢占现有进程的处理器。
抢占的原则如下：

• 优先权原则
• 短进程原则
• 时间片原则

  轮转调度算法

  :::info 轮转调度算法是分时系统中的一个基于时间片算法。 :::

  这是一种剥夺式（抢占式）算法。

轮转调度算法的原理

• 所有的就绪进程按进入就绪队列的先后次序排列
• 每次调度时把CPU分配给队首进程，让其执行一个时间片
• 当时间片用完，暂停该进程的执行，使其退出处理器，并将它送到就绪队列的末尾
• 依次轮转对每个进程调度

• 处理完毕的进程退出队列

  进程切换时机

  在上面的过程中，最重要的就是什么时候需要切换进程：

• 若一个时间片尚未用完，正在运行的进程已完成，就立即激活调度程序，将它从就绪队列删除，在重新调度并启动一个新的时间片。

• 在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将之送往就绪队列的末尾。

  时间片大小的确定

  每个进程每次获得的时间片的大小也影响着这个算法的效率：
  如果时间片过长：这个算法就会退化为FCFS算法（因为每一个进程都可以在时间片内执行完毕，也就不需要轮转了），这样会导致平均响应时间较长。
  如果时间片过短：那么多个进程就会频繁的进行切换，早上系统的上下文切换开销过大。

  算法实例

  设有A、B、C、D、E五个进程，其到达时间分别为0、1、2、3、4，要求运行时间依次为4、3、4、2、4，采用时间片轮转调度算法，当时间片大小为1和4时，试计算其平均周转时间和平均带权周转时间。

首先根据到达时间对五个进程排序可得：ABCDE，这就是后面需要轮转的队列。
在没有进程执行完毕的情况下，队列的变换应该是ABCDE->BCDEA->.CDEBA->…
一旦有进程完成就退出这个队列即可。
当时间片大小为1的时候，运行过程如下：

很好理解就不解释了

最后可以获得一张下面的表：

时间片为4也是同理，不多讲解了。

优先级调度算法

优先级调度算法广泛用于多道程序系统中作业或进程调度。
将CPU分配给就绪队列中最高优先级的进程。优先级调度算法是终合考虑各方面的因素。核心在于进程优先级的确定：

• 系统确定：运行时间、系统资源使用情况

• 用户确定：紧迫程度，计费有关，等待时间

  优先级调度算法的类型

• 非抢占式优先权算法

• 抢占式优先权算法，实时性更好

  优先级的类型

  （1）静态优先权
  优先数在进程创建时确定，整个运行期不变不再变化。
  确定进程优先级的依据：

• 进程类型

• 进程对资源的需求
• 用户要求

（2）动态优先权
系统在运行的过程中，不断地调整进程的优先数。

多队列调度算法（了解）

这种算法的要点如下：

• 进程就绪队列从一个拆分为若干个
• 不同类型或性质的进程固定分配在不同的就绪队列
• 不同的就绪队列采用不同的调度算法
• 一个就绪队列中的进程可以设置不同的优先级
• 不同的就绪队列本身也可以设置不同的优先级

  了解即可，极大概率不考所以不细讲。

多级反馈队列调度算法

:::info 💡多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展。 :::

调度机制

系统中设置多个就绪队列，分别赋予不同的优先级，并逐级降低。为不同队列所规定的时间片长度不同，优先权越高的队列分配的时间片越小。依次逐级加倍。
新进程进入内存后，先投入队列1的末尾，按FCFS算法排队调度；若按队列1的一个时间片未能执行完，则降低投入到队列2的末尾。如果在队列2的时间片内未能完成，则降低投入到队列3……；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成。
仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。

如图所示，图中就绪队列从上到下优先级逐级降低。

调度算法性能

1. 响应时间高
2. 短批处理作业快
3. 长批处理作业不会饿死

   基于公平原则的调度算法

   这两个算法都不重要，了解即可

保证调度算法

保证调度算法是另一种类型的调度算法，它向用户所作出的保证并不是优先运行，而是明确的性能保证，该算法可以做到调度的公平性。
在实施公平调度算法时系统必须具备这样一些功能：
（1）跟踪计算每个进程自创建以来已经执行的处理时间。
（2）计算每个进程应获得的处理机时间，即自创建以来的时间除以n.
（3）计算进程获得处理机时间的比率，即进程实际执行的处理时间和应获得的处理机时间之比
（4）比较各进程获得处理机时间的比率。
（5）调度程序应选择比率最小的进程将处理机分配给它，并让该进程一直运行，直到超过最接近它的进程比率为止。

公平分享调度算法

分配给每个进程相同的处理机时间，显然，对诸进程而言，是体现了一定程度的公平，但如果各个用户所拥有的进程数不同，就会发生对用户的不公平问题。调度的公平性主要是针对用户而言，然而调度又是以进程为单位的，所以，必须考虑每个用户所拥有的进程数目。
例如用户1包含4个进程A，B，C，D，用户2包含一个进程E。为保证两个用户获得相同处理机时间，则必须强制调度序列为：
A E B E C E D E A E B E C E D E …
如果希望用户1获得的处理机时间是用户2的两倍，则必须强制调度序列为：
A B E C D E A B E C D E…

3.4 实时调度

实时调度是指针对实时系统中进程的调度方法。

实时系统是指对实时性要求比较高的系统，例如飞机控制系统、医疗设备控制系统、自动化生产线控制系统等。

实现调度的基本条件

想要达成实时调度，就需要满足以下的条件：

• 提供必要的基本信息
• 系统处理能力强
• 采用抢占式调度机制

• 具有快速切换能力

  提供必要的基本信息

  为了完成进程实时调度，必须提供进程以下的信息：

• 就绪时间

• 开始截止时间和完成截止时间
• 处理时间
• 资源要求
• 优先级

  如果某任务的开始截止时间错过，势必引起故障，则应为该任务赋予“绝对优先级”；如果其开始截止时间的错过，并对任务的继续运行无重大影响，则可为其赋予“相对优先级”，供调度程序参考。

处理能力强

在实时系统中，通常都有着多个实时任务。若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。
假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件：系统才是可调度的

当采用多处理机系统时，假如系统中的处理机数目为N，则应将上述条件修改为：

采用抢占式调度机制

一般来说为了能及时对任务进行相应，实时调度一般都蔡旭抢占式调度，当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行。

具有快速切换能力

• 外部中断的快速响应能力

• 快速的任务分派能力

  实时调度算法的分类

  抢占式调度算法

  (1)基于时钟中断抢占的优先权调度算法（毫秒级）：基于时钟中断抢占
  (2)立即抢占的优先权调度算法（毫秒-微秒级）：只要不在临界区即抢占（中断引发）

  非抢占式调度算法

  (1) 非抢占式轮转调度算法。（秒级）：用于工业生产的群控系统中。
  (2) 非抢占式优先调度算法。（秒-毫秒级）：用于有一定时间要求的实时控制系统之中。

  💡最早截止时间优先EDF算法

  :::info EDF根据任务的截止时间来确定任务的优先级。 :::

• 截止时间越早，优先级越高

• 就绪队列中任务按其截止时间排列，队首任务先分配处理机
• 可以是抢占式或非抢占式

  固定优先级调度

  有两个周期性任务，任务A的周期时间为**20ms**，每个周期处理时间为**10ms**；任务B的周期时间为**50ms**，每个周期处理时间为**25ms**。两个任务的到达时间，最后期限和执行时间如下图：

不重要，看图就行，看得懂最好，不懂也没有关系

AB进程的时间到达和期限时间线。

A优先级高：

每当有A进程进入的时候，会抢占B进程的时间片。

B优先级高：

每当有B进程进入的时候，会抢占A进程的时间片。

EDF

使用最早截止时间优先抢占调度算法如下，核心就在于：每当有一个进程到达的时候，判断现有进程开始截止时间和就绪队列中进程的截止时间比较，哪个截止时间早哪个占用处理机。

固定优先级调度（A有较高优先级）时，B任务易错过截止最后期限；
固定优先级调度（B有较高优先级）时，A任务易错过截止最后期限，同时可能出现CPU空闲，降低系统效率。

最低松弛度LLF算法

:::info 松弛度：由任务的完成截止时间决定。
松弛度＝完成截止时间－运行还需要时间－当前时刻 ::: 例如：若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：200－100－10＝90
该算法根据松弛度（任务紧急程度）来确定任务的优先级。松弛度愈高，优先级愈低。主要用于可抢占的调度方式中。

了解即可

💡优先级倒置

:::info 💡优先级倒置：即高优先级进程（线程）被低优先级进程（线程）延迟或阻塞。 :::

优先级倒置的形成

1. 优先级反转：当一个低优先级的任务在执行时需要占用一个高优先级任务所需的共享资源，高优先级任务就会被阻塞，从而导致优先级倒置。
2. 非抢占式调度：非抢占式调度是指一个任务在执行时，其他任务无法中断它。如果在这种调度策略下优先级低的任务需要占用优先级高的任务所需的资源，就会导致优先级倒置。
3. 中断处理：当一个中断处理程序需要访问一个共享资源时，就会导致优先级倒置。因为中断处理程序的优先级通常很高，比如操作系统内核的中断处理程序。

举个例子：

P1:…P(mutex); CS-1; V(muxtex)…
P2: program2
P3:…P(mutex); CS-3; V(muxtex) 优先级：P1>P2>P3

虽然优先级是1、2、3，但是如果P3先执行了第一步P(mutex)，也就是进入了临界区，P1此时进入，由于优先级高于3，此时会打断进程3，但是由于P3已经进了临界区，P1就被堵在外面了。

优先级倒置的解决方案

1. P3在进入临界区后所占用的处理机就不允许被抢占（处理机不可被抢占）
2. 当高优先级进入P1要进入临界区时，如果已有一个低优先级进程P3正在使用该临界区资源，此时一方面P1被阻塞，另一方面由P3继承P1的优先级并一直保持到P3退出临界区，以此来保证中间优先级进程插入申请处理机，延缓P3退出临界区。

3.5 死锁概述

:::info 💡死锁是指在多个进程或线程中，每个进程都占用了一些资源并正在等待其它进程释放它们所需要的资源，而导致所有进程都无法继续执行的情况。 ::: 如果没有外力干预，这个几个进程就会一直耗着，严重影响CPU的工作。

💡资源问题

可重用性资源和消耗性资源

（1）可重用性资源
是一种可供用户重复使用的资源。
有以下性质：

• 一个可重用性资源只能分配一个进程使用，不允许多个进程共享
• 按申请资源->使用资源->释放资源的顺序使用可重用性资源
• 可重用性资源单元数目固，在运行期间，不可创建不可删除

（2）消耗资源
在进程运行期间，由进程动态创建和消耗的资源。
有以下性质：

• 单元数目在进程运行期间是可以变化的
• 在运行期间，可以创造可消耗资源，且不用归还

  实际上我认为更直白的理解，可重用性资源类似公用资源，每个进程都可以使用但是不能同时使用，只能一个一个排队进行使用。消耗资源顾名思义是一种消耗了就无法再使用的资源，类似打印机的油墨，这种一次性消耗的资源肯定不用归还，更像一种私有资源。

可抢占性资源和不可抢占性资源

• 可抢占资源：分配给某进程后又可以被其他进程或系统抢占的资源。（这类资源通常都不会引起死锁）

• 不可抢占资源：一旦分配给某进程后不能强行收回，只能由进程自行释放的资源

  💡计算机中的死锁

  竞争不可抢占性资源引起死锁

  如图所示：
  
  其中：

• P：表示进程

• R：表示不可抢占资源。
• R->P：表示资源R分配给了P进程
• P->R：表示进程P请求获得资源R

在这张图中，两个进程P1和P2实际都需要两个资源R1和R2，如上图所示：一旦**R****1**已经分配给了**P****1**，**R****2**已经分配给了**P****2**，由于R是不可抢占性资源，P1和P2都不能抢占对方的资源，于是只能互相等待，形成了死锁。

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

还是这张图：

这个时候R变成了可消耗性资源。
虽然此时P进程之间可以根据优先级之类的抢占对方的资源了，但是一旦资源已经被消耗了，那么还是会造成死锁。

💡死锁的必要条件和处理方式

产生死锁的必要条件

• 互斥条件：竞争的资源必须被互斥的使用
• 请求和保持条件：进程需要不断请求需要的资源并且保持已有的资源不释放
• 不剥夺条件：进程已获得的资源，只能在使用完时自行释放资源

• 循环等待条件：存在一个至少包括两个进程的循环等待链，链中的每个进程都正在等待下一个进程所占有的资源 :::info 💡四个条件必须同时存在才有可能发生死锁，有一个不成立也不能发生死锁。 :::

  处理死锁的方法

• 预防死锁：设置限制条件，破坏产生死锁的四个必要条件中的一个或几个条件 。

• 避免死锁：在每次的资源动态分配过程中，对系统能够满足的资源申请进行安全性检查 ，根据结果决定是否进行此次分配。
• 检测死锁：允许系统发生死锁，但设置检测机构，及时检测出死锁的发生。
• 解除死锁：外力推动解除死锁。具体方法有：撤消或挂起死锁进程、剥夺资源等。

3.6 💡预防死锁

破坏“请求和保持”条件

第一种协议

进程必须在运行前一次性地申请运行期间所需的全部资源，这样进程在整个运行期间不会再提出资源请求，从而摒弃了请求和保持条件。
缺点：

• 资源浪费严重。降低进程并发度。
• 进程延迟运行

• 不适用资源需要未知的进程

  第二种协议

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

  破坏“不可抢占”条件

  允许进程逐个申请资源，当进程新的资源请求未满足时，必须释放已占有的资源，待以后需要时再重新申请。此策略表明进程已占有的资源可被暂时释放，即被抢占了，从而摒弃“不抢占”条件。
  缺点：

• 复杂，实现困难且代价大

• 延长了进程的周转时间，增加系统开销。

  破坏“循环等待”条件

  原理

  系统给每类资源赋予一个序号，每一个进程严格按照序号递增的顺序请求资源，释放则相反。此方法不可能形成资源占有与请求的环路，从而破坏循环等待条件。
  优点：相对而言，系统利用率高，系统吞吐量大。
  缺点：

• 限制设备扩充。系统事先确定资源序号，限制了新类型设备的增加。

• 限制了进程对资源的请求，编程困难。
• 资源浪费。当进程使用顺序与资源序号不相符时，也会造成资源浪费。

  实例

  例如： 进程P1，使用资源的顺序是R1，R2； 进程P2，使用资源的顺序是R2，R1； 若采用动态分配有可能形成环路条件，造成死锁。

采用有序资源分配法：

• R1的编号为1，R2的编号为2；
• P1：申请次序应是：R1，R2
• P2：申请次序应是：R1，R2

  这样就破坏了环路条件，预防了死锁的发生。

3.7 避免死锁

:::info 避免死锁同样是属于事先预防的策略，但并不是事先采取某种限制措施，破坏产生死锁的必要条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。这种方法所施加的限制条件较弱，可能获得较好的系统性能，目前常用此方法来避免发生死锁。 :::

系统安全状态

安全状态

:::info 安全状态是指系统能按某种顺序如 (P1、P2… 、Pn) 来为每个进程 Pi 分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成，则称此时的系统状态为安全状态，称序列 ( P1、P2、…、Pn ) 为安全序列。 ::: 若某一时刻系统中无法找到这样一个安全序列，则称此时的系统状态为不安全状态。

不是说所有的不安全状态都会造成死锁，但是安全状态一定不会造成死锁。

安全状态的例子

假定系统中有三个进程P1，P2和P3，共有12台磁带机。进程P1共需要10台，P2和P3各需要4台和9台。假设在T0时刻，进程的资源分配情况如下：

从上面的表中我们可以知道三个进程分别需要的资源数量是5、2、7，那么此时可以先给P2分配资源，P2获取资源完成任务之后，就可以回收其所有的资源，此时：

以此类推，可以找到一个安全序列：（P2,P1,P3）。

注意：安全序列不是唯一的，比如这里其实（P2,P3,P1）也是一个安全序列。

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

在上面的例子中如果改一点数据：

首先资源只能分配给P2，此时即使P2完成任务之后回收了所有资源，资源也只有4个，不满足P1和P3的其中任意一个的需求，因此此时就是不安全状态，有可能会造成死锁。 :::info 一个系统开始处于安全状态，当有进程请求一个可用资源时，系统需对该进程的请求进行检测，若将资源分配给进程后系统仍然处于安全状态，才将该资源分配给进程。 :::

利用银行家算法避免死锁

:::info 银行家算法是一种用于避免死锁的算法，它通过判断系统资源分配是否安全来决定是否分配资源 :::

银行家算法的数据结构

1. Available（可用资源向量）：表示系统还剩下多少资源可以分配给进程。

可利用资源向量Available是一个含有m个元素的数组，其中每一个元素代表一类资源的空闲资源数目。

如果Available[j]＝K，表示系统中现有空闲的Rj类资源K个。

1. Allocation（分配矩阵）：表示当前已经分配给每个进程多少资源。

分配矩阵Allocation是一个n×m的矩阵，定义了系统中每一类资源当前已分配给每一个进程的资源数目。

如果Allocation[i，j]＝K ，表示进程i当前已分到Rj类资源的数目为K。

1. Need（需求矩阵）：表示每个进程还需要多少资源才能完成其任务。

需求矩阵Need是一个n×m的矩阵，它定义了系统中每一个进程还需要的各类资源数目。

如果Need[i，j]＝K，表示进程i还需要Rj类资源K个。

1. Max（最大需求矩阵）：表示每个进程所需要的所有资源数量的上限。

最大需求矩阵Max是一个n×m的矩阵，定义了系统中每个进程对m类资源的最大需求数目。

如果Max[i，j]＝K ，表示进程i需要Rj类资源的最大数目为K。

银行家算法

首先，对于每一个进程都设定一个请求向量**Request**，设Requesti是进程Pi的请求向量，那么Requesti[j]＝K表示进程Pi请求分配Rj类资源K个。
当Pi发出资源请求后，系统按下述步骤进行检查：
（1）若Requesti [j]≤Need[i,j], 转（2）； 否则错误返回

检查请求量和需求量，如果请求大都大于需求量，说明本次请求不合理，错误返回

（2）若Requesti [j]≤Available[j], 转（3）； 否则进程等待

检查请求量和现有资源数量，如果资源数目不够，等待。

（3）假设系统分配了资源，则有：

Available[j]=Available[j]-Requesti[j]; // 更新现有资源数量
Allocation[i,j]=Allocation[i,j]+Requesti[j]; // 更新分配资源矩阵
Need[i,j]=Need[i,j]-Requesti[j] // 更新需求矩阵

（4）执行安全性算法，若系统新状态是安全的，则分配完成，若系统新状态是不安全的，则恢复原状 态，进程等待

安全性算法

1. 设置两个向量

工作向量Work：表示系统可提供给进程继续运行的各类空闲资源数目，含有m个元素，执行安全性算法开始时，Work＝Available 。
Finish：表示系统是否有足够的资源分配给进程，使之运行完成，开始时，Finish[i]＝false；当有足够资源分配给进程Pi时，令Finish[i]＝true 。

1. 从进程集合中找到一个能满足下述条件的进程：

   Finish[i]= false ;
   Need[i,j]≤Work[j] ;

   也就是找一个暂时不能完成任务，但是分配了资源之后可以完成任务的进程。 如找到则执行步骤3；否则执行步骤4。

2. 当进程Pi获得资源后，可顺利执行直到完成，并释放出分配给它的资源，故应执行：

   Work[j]＝Work[j] ＋ Allocation[i,j] ; // 回收了之前已经被分配的资源
   Finish[i]＝true ; // 说明这个线程当前可以安全执行
   goto step 2 ; // 返回步骤二继续找

3. 若所有进程的Finish[i]都为true ，则表示系统处于安全状态；否则，系统处于不安全状态。

3.8 死锁的检测与解除

• 死锁检测算法：该算法用于检测系统状态，以确定系统中是否发生了死锁。

• 死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

  死锁的检测

  资源分配图

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

• N：结点集，分为P，R两部分，

• P={P1,P2,…,Pn}：进程结点
• R={R1,R2,…,Rm}：资源结点

如图所示：

• 其中r中的圆圈的个数表示资源的个数（比如这里的r1资源总共有3个）
• 进程需要的总的资源量是其所有入度和出度（比如P1实际需要2个r1和一个r2）
• P->r：表示P需要申请一个资源R，但是这个资源还没有被分配出去

• r->R：表示r分配给了P一个资源，并且这个资源已经分配出去了

  死锁定理

  首先我们需要化简资源图，以此图为例：
  
  第一步：找一个既不阻塞又非孤立点进程结点
  不孤立很好理解，就是这个结点必须和其他结点有关联即可。不阻塞需要进一部分析整个资源图，假设我们找到的是P，分析：

• P是否可以获得请求的资源

• P是否可以获得被分配的资源

那么首先一律把图中的资源先分配，再请求。如果先分配的话，那么：

• P1获得了两个r1
• P2获得了一个r1，一个r2
• 此时r1剩下0个
• 此时r2剩下1个

P1和P2明显都可以获得被分配的资源，但是：

• P1请求一个r2资源，此时r2资源剩余1个，所以请求成功
• P2请求一个r1资源，此时r2资源剩余0个，所以请求失败

那么综上可以知道：

• P1可以顺利运行
• **P2**被阻塞

所以第一步要找的结点是P1。

第二步：再把被请求的资源分配给这个进程吗，让他执行完毕。此时返回用完的资源，并且消除相应的边。
第三步：重复上述两边，直到所有的结点都孤立或者所有的结点都阻塞。

这就是完整的化简流程。

死锁的解除

终止进程的方法

（1）终止所有死锁进程
最简单的方法是撤消全部死锁进程，使系统恢复到正常状态。但这种做法付出的代价太大。
（2）逐个终止进程
按照某种顺序逐个撤消死锁进程，直到有足够的资源供其他未被撤消的进程使用，消除死锁状态为止。这种方法的代价也很大。

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

也就是最小生成树算法。

直到这个算法即可。

实验

实验内容：使用线程实现四种调度算法：