第三章 处理机调度与死锁

  • 【目的要求】

    1. [掌握]进程调度和常见的调度算法；
    2. [熟悉]死锁的概念和产生的必要条件；
    3. [掌握]死锁的预防和避免方法；
    4. [了解]死锁的检测及恢复。

  • 【重点与难点】

    • 常见的进程调度算法
    • 死锁的原因和必要条件
    • 银行家算法

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

3.1.1 处理机调度的层次

  1. 高级调度
  2. 低级调度
  3. 中级调度(Intermediate-Level Scheduling)

3.1.2 处理机调度算法的目标

  1. 处理机调度算法的共同目标
    • 资源利用率: CPU的利用率 = $ \frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间} $
    • 公平性：应使诸进程都获得合理的CPU时间。
    • 平衡性：兼顾计算型作业和I/O型作业。
    • 策略强制执行
  2. 批处理系统的目标
    • 平均周转时间短
      • 可把平均周转时间描述为： $ T = \frac{1}{n} [\displaystyle \sum^i_{i=1}T_i] $
      • 作业的周转时间T与系统为它提供服务的时间TS之比，即$ W = \frac{T}{TS} $，称为带权周转时间
      • 平均带权周转时间则可表示为: $ T = \frac{1}{n} [\displaystyle \sum^n_{i=1}\frac{T_i}{T_{si}}] $
    • 系统吞吐量高
      • 吞吐量是指在单位时间内系统所完成的作业数。为了获得高的系统吞吐量，就应该尽量多地选择短作业运行。
    • 处理机利用率高
      • 如果单纯是为了使处理机利用率高，应尽量多地选择计算量大的作业运行。
  3. 分时系统的目标
    • 响应时间快
      • 从键盘输入的请求信息传送到处理机的时间；
      • 处理机对请求信息进行处理的时间；
      • 将所形成的响应信息回送到终端显示器的时间。
    • 均衡性
  4. 实时系统的目标
    • 截止时间的保证
    • 可预测性

3.2 作业与作业调度

3.2.1 批处理系统中的作业

  1. 作业和作业步
    • 作业：包含程序、数据和作业说明书
    • 作业步：作业中每一个相对独立，又相互关联的顺序加工步骤。例如：编译→链接→运行
  2. 作业控制块JCB(Job Control Block）
  3. 作业运行的三个阶段和三种状态
    • 三个阶段：收容、运行和完成
    • 三种状态：后备、运行和完成

3.2.2 作业调度的主要任务

3.2.3 先来先服务(FCFS)和短作业优先(SJF）调度算法

  1. 先来先服务调度算法 FCFS
    • 周转时间

    周转时间=完成时间-到达时间

    • 说明：采用该算法时，系统按照作业到达的先后次序来进行调度。该算法既可以用于作业调度，也可以用于进程调度。一般与其它算法结合使用。
    • 优缺点：对长作业有利，对短作业不利。
    • FCFS
  2. 短作业优先调度算法 SJF
    • FCFS vs SJF
    • 必须预知作业的运行时间,不一定能真正做到短作业优先调度
    • 该算法对长作业不利
    • 在采用SJF算法时，人机无法实现交互
    • 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理

3.2.4 优先级调度算法和高响应比优先调度算法

  1. 优先级调度算法
  2. 高响应比优先调度算法 HRRN
    • 优先权 = $ \frac{等待时间+服务时间}{服务时间} $ = $ \frac{响应时间}{服务时间} $
    • 优点: 实现了FCFS算法和SJF算法的折中
    • 缺点: 由于采用了动态优先级，每次调度前都要先计算相应比，增加了系统开销

3.3 进程调度

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

  1. 进程调度的任务
    • 保存处理机的现场信息
    • 按某种算法选取进程
    • 把处理机分配给进程
  2. 进程调度机制
    • 排队器：将变为就绪状态的进程插入相应的就绪队列。
    • 分派器（分派程序）：将进程调度程序选定的进程从就绪队列中移出，然后进行从分派器到新选进程的上下文切换，将处理机分给新选进程。
    • 上下文切换器：每次调度发生两对上下文切换。
  3. 进程调度方式
    • 非抢占方式(Non-preemptive Mode)
    • 抢占方式(Preemptive Mode)
      • 优先权原则。
      • 短进程优先原则。
      • 时间片原则。

3.3.2 轮转（RR）调度算法

  1. 时间片轮转法的基本原理
  2. 进程切换时机
    • 若一个时间片尚未用完，正在运行的进程便已完成，就立即激活调度程序，再调度就绪队列中队首的进程运行，并启动一个新的时间片。
    • 在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。
  3. 时间片大小的确定

3.3.3 优先级调度算法

  1. 优先级调度算法的类型

    • 非抢占式优先权算法
      • 这种调度算法主要用于批处理系统中
      • 也可用于某些对实时性要求不严的实时系统中
    • 抢占式优先权调度算法

  2. 优先级的类型

    • 静态优先级: 静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。
      • 确定进程优先权的依据有如下三个方面：
        • 进程类型。
        • 进程对资源的需求。
        • 用户要求。
    • 动态优先级: 动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能

3.3.4 多队列调度算法

3.3.5 多级反馈队列调度算法

  1. 调度机制
    • 多级反馈队列调度算法
  2. 多级反馈队列调度算法的性能
    • 终端型作业用户。
    • 短批处理作业用户。
    • 长批处理作业用户。

3.3.6 基于公平原则的调度算法

  1. 保证调度算法
  2. 公平分享调度算法

思考与练习：假设一个系统中有5个进程，它们的到达时间和服务时间如下表所示

进程 到达时间 服务时间
A 0 3
B 2 6
C 4 4
D 6 5
E 8 2

忽略I/O以及其它开销时间，若分别按

  • 先来先服务（FCFS）
  • 非抢占及抢占的短进程优先（SPF）
  • 高响应比优先（HRRN）
  • 时间片轮转（RR，时间片=1）
  • 多级反馈队列（FB，第i级队列的时间片=2i-1）调度算法进行CPU调度。
    请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。

3.4 实时调度

3.4.1 实现实时调度的基本条件

  1. 提供必要的信息
    • 就绪时间
    • 开始截止时间和完成截止时间
    • 处理时间
    • 资源要求
    • 优先级
  2. 系统处理能力强
  3. 采用抢占式调度机制
  4. 具有快速切换机制
    • 对外部中断的快速响应能力
    • 快速的任务分派能力

3.4.2 实时调度算法的分类

  1. 非抢占式调度算法
    • 非抢占式轮转调度算法
    • 非抢占式优先调度算法
  2. 抢占式调度算法
    • 基于时钟中断的抢占式优先权调度算法
    • 立即抢占(Immediate Preemption)的优先权调度算法

实时进程调度

3.4.3 最早截止时间优先即EDF(Earliest Deadline First)算法

  1. 非抢占式调度方式用于非周期性实时任务
    • EDF算法用于非抢占调度方式
  2. 抢占式调度方式用于周期性实时任务

例1: 在一个实时系统中，有两个周期性实时任务A和B，
任务A要求每20ms执行一次，执行时间为10ms；
任务B只要求每50ms执行一次，执行时间为 25 ms。

3.4.4 最低松弛度优先LLF(Least Laxity First)算法

利用LLF算法进行调度的情况

3.4.5 优先级倒置(priority inversion problem)

  1. 优先级倒置的形成
  2. 优先级倒置的解决方法

有3个周期性任务：

  • 任务A要求每20ms执行一次，执行时间为10ms
  • 任务B要求每50ms执行一次，执行时间为10ms
  • 任务C要求每50ms执行一次，执行时间为15ms
    应如何按最低松弛度优先算法对它们进行CPU调度？

3.5 死锁概述

3.5.1 资源问题

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

    • 可重用性资源: 是一种可供用户重复使用多次的资源
      • 每一个可重用性资源中的单元只能分配给一个进程使用，不允许多个进程共享。
      • 进程在使用可重用性资源时，须按照这样的顺序： ①请求资源。如果请求资源失败，请求进程将会被阻塞或循环等待。②使用资源。进程对资源进行操作，如用打印机进行打印； ③释放资源。当进程使用完后自己释放资源。
      • 系统中每一类可重用性资源中的单元数目是相对固定的，进程在运行期间既不能创建也不能删除它。
    • 临时性资源（可消耗性资源）:是指由一个进程产生，被另一个进程使用一短暂时间后便无用的资源，故也称之为消耗性资源（如进程通信中的消息），它也可能引起死锁
      • 每一类可消耗性资源的单元数目在进程运行期间是可以不断变化的，有时它可以有许多，有时可能为0；
      • 进程在运行过程中，可以不断地创造可消耗性资源的单元，将它们放入该资源类的缓冲区中，以增加该资源类的单元数目。
      • 进程在运行过程中，可以请求若干个可消耗性资源单元，用于进程自己的消耗，不再将它们返回给该资源类中。

  2. 可抢占性资源和不可抢占性资源（可剥夺和非剥夺性资源）

    • 可抢占性资源：是指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺，如CPU、内存。对这类资源的使用不会引起死锁。
    • 不可抢占性资源：当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如刻录机、磁带机、打印机等。

3.5.2 计算机系统中的死锁

  1. 竞争不可抢占性资源引起死锁
  2. 竞争可消耗性资源引起死锁
    • 进程之间通信时的死锁
  3. 进程推进顺序不当引起死锁
    • 进程推进顺序合法
    • 进程推进顺序非法

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

  1. 死锁的定义
    • 死锁的定义1：是指多个进程在运行过程中因竞争资源而造成的一种僵局。当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。
    • 死锁的定义2：如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的（Deadlock）。
  2. 产生死锁的必要条件
    • 互斥条件: 进程访问的是临界资源，即在一段时间内某资源仅为一个进程占有。
    • 请求和保持条件: 当一个进程因请求资源而被阻塞时，对已经获得的资源保持不放。
    • 不可抢占条件:进程已经获得的资源，在未使用完之前，不能被其它进程剥夺，只能自己在使用完时由自己释放。
    • 循环等待条件:在发生死锁时，必然存在一个进程-资源的环形链，即若干进程之间形成一种头尾相连的循环等待资源的关系。
  3. 处理死锁的方法
    • 预防死锁:通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。
    • 避免死锁:不事先采取各种限制措施去破坏产生死锁的四个必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。
    • 检测死锁: 不事先采取任何限制性措施，也不必检查系统是否已经进入不安全区，而是允许系统在运行过程中发生死锁。但可通过系统设置的检查机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源。然后，采取适当措施，从系统中将已发生的死锁清除掉。
    • 解除死锁: 这是与检测死锁相配套的一种措施。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。

例1: 考虑n个进程共享的、具有m个同类资源的系统。
证明：如果对于I=1，2，…，n有Need>0而且所有的最大需求量之和小于m+n，那么该系统是死锁无关的。

例2: 设系统中仅有一类独占资源，进程一次只能申请一个资源，系统中多个进程竞争该类资源。试判断下述哪些情况会发生死锁，为什么？

  • 资源数为4，进程数为3，每个进程最多需要2个资源。
  • 资源数为6，进程数为2，每个进程最多需要4个资源。
  • 资源数为8，进程数为3，每个进程最多需要3个资源。
  • 资源数为20，进程数为8，每个进程最多需要2个资源。

3.6 预防死锁

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

  1. 第一种协议：一次性申请
    • 缺点：
      • 资源被严重浪费
      • 使进程延迟运行
  2. 第二种协议：
    • 方法：它允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的、且已用毕的全部资源，然后再请求新的所需资源。
    • 优点：能使进程更快地完成任务，提高设备的利用率，还可减少进程发生饥饿的机率。

3.6.2 破坏“不可抢占”条件

  • 方法：逐个申请；提出新的资源请求得不到满足时必须释放已保持的所有资源，以后需要时再重新申请。
  • 缺点：实现起来比较复杂且要付出很大的代价，还可能因为反复地申请和释放资源致使进程的执行被无限地推迟。

3.6.3 破坏“循环等待”条件

  • 方法：系统将所有资源按类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须严格按照资源序号递增的次序提出。
  • 缺点：
    • 因为系统中各类资源的序号必须相对稳定，所以限制了新类型设备的增加；
    • 作业使用各类资源的顺序可能与系统规定的顺序不同，因而造成对资源的浪费；
    • 按规定次序申请的方法，限制了用户简单、自主地编程。

3.7 避免死锁

3.7.1 系统安全状态

  1. 安全状态
  2. 安全状态之例

    假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配。

    进程 最大需求 已分配 可用
    P1 10 5
    P2 4 2
    P3 9 2
  3. 由安全状态向不安全状态的转换

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

  1. 银行家算法中的数据结构
    • 可利用资源向量Available
    • 最大需求矩阵Max
    • 分配矩阵Allocation
    • 需求矩阵Need
  2. 银行家算法
    • 设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：
    1. 如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
    2. 如果Requesti［j］≤Available［j］，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。
    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，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
  3. 安全性算法
    1. 设置两个向量：
      • 工作向量Work：它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全性算法开始时，Work=Available;
      • Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false; 当有足够资源分配给进程时，再令Finish[i]=true。
    2. 从进程集合中找到一个能满足下述条件的进程：
      • Finish［i］=false;
      • Need［i,j］≤Work［j］；
      • 若找到， 执行步骤(3)， 否则，执行步骤(4)。
    3. 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
      Work［j］=Work［i］+Allocation［i,j］;
      Finish［i］=true;
      go to step 2;
    4. 如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。
  4. 银行家算法之例

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

3.8 死锁的检测与解除

3.8.1 死锁的检测

  • 当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段，为此，系统必须做到：
    • 保存有关资源的请求和分配信息；
    • 提供一种算法，利用这些信息来检测系统是否已进入死锁状态。
  1. 资源分配图(Resource Allocation Graph)
  2. 死锁定理
    • 资源分配图的简化
  3. 死锁检测中的数据结构
    • 工作向量Work：它表示系统可提供给进程继续运行所需的各类资源数目，初始时Work=Available。
    • 把不占用资源的进程Li (向量Allocation=0并且Requesti=0)记入L表中， 即L=Li∪L。
    • 从进程集合中找到一个Requesti≤Work的进程，做如下处理：① 将其资源分配图简化，释放出资源，增加工作向量Work=Work+Allocationi。 ② 将它记入L表中。
    • 若不能把所有进程都记入L表中，便表明系统状态S的资源分配图是不可完全简化的。因此，该系统状态将发生死锁。

3.8.2 死锁的解除

  • 当发现有死锁时，便立即把它们从死锁状态中解脱出来。常采用解除死锁的方法是：
    • 抢占资源。从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以解除死锁状态。
    • 终止（或撤消）进程：全部终止（或撤销）或按某种顺序终止（或撤销）死锁进程，打破循环环路，使系统从死锁状态解脱出来。
  1. 终止进程的方法
    • 逐个终止进程时，选择被终止进程时应考虑的因素有：
      • 进程的优先级大小；
      • 进程已执行了多少时间，还需要多少时间方能完成；
      • 进程在运行中已经使用资源的多少，以后还需要多少资源？
      • 进程的性质是交互式的还是批处理式的？
  2. 付出代价最小的死锁解除算法
    • 解除死锁时，可使撤销的进程数目最少，也可以选择撤销进程所付出的代价最小。为把系统从死锁状态中解脱出来，所花费的代价可表示为：
    • R(S)min=min{Cui}+min{Cuj}+min{Cuk}+…

练习: 某系统T0时刻的资源分配情况如下所示

Allocation Need Avaliable
A 3 1 1 1 0 0 1 2 0
B 0 0 0 0 1 2
C 1 1 0 3 0 0
D 1 0 1 0 1 0
E 0 0 0 2 1 0

试问：

  • 该状态是否安全？
  • 若进程B提出请求RequestB(0,1,0)，系统能否将资源分配给它？

强化一: 作业调度算法

例1: 先来先服务调度算法
先来先服务调度算法

  • 说明：采用该算法时，系统按照作业到达的先后次序来进行调度。该算法既可以用于作业调度，也可以用于进程调度。一般与其它算法结合使用。
  • 优缺点：对长作业有利，对短作业不利。

例2: 短作业(进程)优先调度算法
短作业(进程)优先调度算法
周转时间=完成时间-到达时间
带权周转时间=周转时间/服务时间

例3: 单道批处理系统中有4个进程，其有关情况如下表所示，采用响应比高者优先调度算法时，计算其平均周转时间和平均带权周转时间。（请写出计算过程）

进程名 提交时间 运行时间
P1 8.0 2.0
P2 8.6 0.6
P3 8.8 0.2
P4 9.0 0.5

例4: 有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。在下表所示的作业序列，作业优先数即为进程优先数，优先数越小优先级越高。

作业号 到达时间 估计运行时间（分钟） 优先数
A 10 40 5
B 10:20 30 3
C 10:30 50 4
D 10:50 20 6

要求：

  • 列出所有作业进入内存时间及结束时间
  • 计算平均周转时间(以分钟计算)

例5: 在一个单道批处理系统中，一组作业的提交时刻和运行时间如下表所示：

作业名 提交时间/h 运行时间/h
J1 8.0 1.0
J2 8.5 0.5
J3 9.0 0.2
J4 9.1 0.1

试计算下列三种作业调度算法的平均周转时间T和带权周转时间W。

  • 先来先服务
  • 短作业优先
  • 响应比高者优先

例6: 我们如果为一个作业只建立一个进程，则为了照顾短作业用户，应采用（A）；为照顾紧急作业用户应采用（B）；为能实现人机交互作用应采用（C）；为了兼顾短作业和长时间等待的作业应采用（D）； 为了使短作业、长作业及交互作业用户都比较满意应采用（E）；为了使作业的平均周转时间短应采用（F）算法。
A，B，C, D, E, F：
（1）FCFS调度算法；
（2）短作业优先；
（3）时间片轮转法；
（4）多级反馈队列调度算法；
（5）基于优先权的剥夺调度算法；
（6）高响应比优先
答：
A:（2）短作业优先；
B:（5）基于优先权的剥夺调度算法；
C:（3）时间片轮转法；
D:（6）高响应比优先；
E:（4）多级反馈队列调度算法；
F:（2）短作业优先

强化二: 银行家算法

例1: 考虑n个进程共享的、具有m个同类资源的系统。证明：如果对于I=1,2,…,n有Need>0而且所有的最大需求量之和小于m+n，那么该系统是死锁无关的。

例2: 设系统中仅有一类独占资源，进程一次只能申请一个资源，系统中多个进程竞争该类资源。试判断下述哪些情况会发生死锁，为什么？

  1. 资源数为4，进程数为3，每个进程最多需要2个资源。
  2. 资源数为6，进程数为2，每个进程最多需要4个资源。
  3. 资源数为8，进程数为3，每个进程最多需要3个资源。
  4. 资源数为20，进程数为8，每个进程最多需要2个资源。

例3: 某系统有R1、R2、R3共三种资源，在T0时刻，P1、P2、P3和P4这4个进程对资源的占有和需求情况见下表，此刻系统可用资源向量为（2，1，2）。

  1. 将系统资源总数和此刻各进程对资源的需求数目用向量、矩阵表示出来。
  2. 如果此时P1和P2均发出资源请求向量Request（1，0，1），为了保持系统安全性，应该如何分配资源给这两个进程？
进程名 最大资源需求量 已分配的资源数量
P1 3 2 2 1 0 0
P2 6 1 3 4 1 1
P3 3 1 4 2 1 1
P4 4 2 2 0 0 2

例4: 在银行家算法中，系统的资源数量为（10，5，7）。经过一段时间的分配后，资源分配与占用情况见下表:

资源进程 已分配资源
A B C		 最大资源
A B C		 还需求资源
A B C		 可用资源量
A B C
P0 0 1 0 7 5 3 7 4 3 2 3 0
P1 3 0 2 3 2 2 0 2 0
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
  1. 请分析该状态是否是安全的？
  2. 若进程P0提出请求Request（0，1，0）后，系统能否将资源分配给它？

例5: 某系统中有5个进程和4类资源，在T0时刻的资源分配情况如下表：

资源进程 已分配资源
R1 R2 R3 R4		 还需求资源
R1 R2 R3 R4		 可用资源量
R1 R2 R3 R4
P0 0 0 3 2 0 0 1 2 1 6 2 2
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 3 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
  1. 该时刻系统是否安全？请分析。
  2. 如果进程P2提出请求（1, 2, 2, 2），系统能否将资源分配给它？