操作系统 第三章 处理机调度与死锁

操作系统 评论

第三章 处理机调度与死锁

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

1.1 处理机调度的层次

1. 高级调度

高级调度又称长程调度或作业调度，主要功能是根据算法决定外存上位于后备队列的哪几个作业调入内存，为它们创建进程，分配必要资源，放入就绪队列

主要用于多道批处理系统，分时和实时系统中 不设置

2. 低级调度

低级调度又称进程调度或短程调度。根据算法决定就绪队列中哪个进程获得处理机，并由分派程序将处理机分配给被选中的进程

是最基本的一种调度

3. 中级调度

中级调度又称内存调度。用于提高内存利用率和系统吞吐量。把暂时不能运行的的进程调至外存等待，此时进程中的状态称为就绪外存状态（或挂起状态）。当它们已具备运行条件且内存有稍有空闲时就由中级调度决定把哪些外存上的就绪进程重新调入内存，并修改其状态为就绪状态

1.2 处理机调度算法的目标

1. 处理机调度算法的共同目标

  1. 资源利用率 利用率有效工作时间有效工作时间空闲等待时间

  2. 公平性：诸进程都获得合理的 CPU 时间，不会发生进程饥饿现象

  3. 平衡性：对于多种类型的进程，有的属于计算型，有的属于 I/O 型，应尽可能保证系统资源利用的平衡性

  4. 策略强制执行：只要需要，就必须予以准确地执行，及时造成某些工作的延迟也要执行

2. 批处理系统的目标

  1. 平均周转时间短
  2. 系统吞吐量高
  3. 处理机利用率高

3. 分时系统的目标

  1. 响应时间快
  2. 均衡性

4. 实时系统的目标

  1. 截止时间的标准
  2. 可预测性

二、作业与作业调度

2.1 批处理系统中的作业

1. 作业和作业步

  1. 作业：作业是比程序更为广泛的概念，不仅包含了通常的程序和数据，还配有一份作业说明书。在批处理系统中，以作业为基本单位存外存调入内存
  2. 作业步：通常在作业运行期间，每个作业都必须经过若干相对独立又相互关联的顺序加工步骤才能得到结果。我们吧其中的每一个加工步骤称为一个作业步，各作业步之间存在着相互联系，常常是上一个作业步的输出做下一个作业步的输入，如“编译”、“链接装配”、“运行”作业步。

2. 作业控制块（JCB）

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

每当一个作业进入系统时，便由作业注册程序为该作业建立一个作业控制块，再根据作业类型将它放在对应的作业后备队列中等到调度。调度程序依据一定的调度算法调度他们，将被调度的作业装入内存。在作业运行期间，系统按照 JCB 中的信息和作业说明书对作业进行控制。当一个作业执行结束进入完成状态时，系统负责回收已分配的资源，撤销作业控制块

3. 作业运行的三个阶段和三种状态

三阶段：收容、运行、完成

  1. 收容阶段：操作员将用户提交的作业输入到硬盘上，再为该作业建立 JCB，并将它发缓释作业后备队列中，此时作业的状态为后备状态
  2. 运行阶段：一个作业从第一次进入就绪状态开始，直到运行结束前，在此期间都处于运行状态
  3. 完成阶段：当作业运行完成或发生异常情况提前结束时，作业便进入完成阶段，相应的作业状态为完成状态

2.2 作业调度的主要任务

1. 接纳多少个作业

2. 接纳哪些作业

2.3 先来先服务（FCFS）和短作业优先（SJF）调度算法

1. 先来先服务

FCFS 在单处理机系统中已很少作为主调度算法，但进程把它与其他调度算法结合使用形成一种更有效的调度算法，例如可以在系统中按晋城的优先级设置多个队列，每个优先级一个队列，其中每个队列的调度都给予 FCFS 算法

2. 短作业优先

实际情况中，短作业占有很大比例，为使他们比长作业优先执行产生了短作业优先算法

缺点

  • 必须阈值作业的运行时间。如果估计过低，系统可能按估计的世界终止作业的运行，但此时作业并未完成，故一般都会片场估计
  • 对长作业非常不利，长作业的周转时间会明显增长。可能使作业等待时间过长，出现饥饿现象
  • 采用 SJF 算法时，人机无法实现交互
  • 该调度算法完全未考虑作业的紧迫程度，不能保证紧迫性作业能获得及时处理

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

1. 优先级调度算法（PSA）

优先级调度算法中基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法根据该优先级进行调度。PSA 可以作为作业调度算法或进程调度算法。

当作为作业调度算法时，系统从后备队列中选择若干个优先级最高的作业装入内存。

2. 高响应比优先调度算法（HRRN）

高响应比优先算法引入一个动态优先级，随等待时间延长而增加 优先权等待时间要求服务时间要求服务时间 由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先级由相当于响应比 。因此优先级又可表示为 等待时间要求服务时间要求服务时间响应时间要求服务时间

  1. 如果作业的等待时间相同，则要求服务时间的越短优先级越高，类似于 SJF，有利于短作业
  2. 当要求服务时间相同，作业优先级决定于等待时间，类似于 FCFS
  3. 对场左右的优先级，可以随等待时间的增加而提高，当其等待时间足够长时也可获得处理机，因此该算法实现了较好的折中。但是每次要进行调度前要先进行响应比的计算，增加了系统开销

三、进程调度

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

1. 进程调度的任务

  1. 保存处理机的现场信息
  2. 按某种算法选取进程
  3. 把处理机分配给进程

2. 进程调度机制

  1. 排队器：为提高进程调度的效率，应先将系统中的所有就绪进程按照一定的策略排成一个或多个队列以便调度程序能最快找到它
  2. 分派器：分配器根据进程调度所选定的进程将其从就绪队列中取出，然后进行从分配器到新选出进程的上下文切换，将处理机分配给辛选出的进程
  3. 上下文切换器：对处理机切换时会发生两对上下文的切换操作
    1. 第一对上下文切换时，OS 保存当前进程的上下文，在装入分配程序的上下文以便分配程序运行
    2. 第二次上下文切换时，移出分配程序的上下文，吧新选进程的 CPU 现场信息装入到处理机的各个相应寄存器中，以便新选进程进行

3. 进程调度方式

  1. 非抢占方式

    在采用这种调度方式时，一旦被处理机分配给某进程后，就一直让它运行，知道该进程完成或发生某事件被阻塞时，才把处理机分配给其他进程

    可能引起进程调度的因素可归结为

    1. 正在执行的进程运行完毕，或因某时间使其无法继续运行
    2. 正在执行的进程因提出 I/O 请求暂停执行
    3. 在进程通信或同步过程中执行了某种原语操作，如 Block 原语。

    优点是实现简单，系统开销小，适用于大多数的批处理系统

  2. 抢占方式

    这种调度方式允许调度程序根据某种原则暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。

    对于批处理机系统，可以防止一个长进程长时间占用处理机，以确保处理机能为所有进程提供更为公平的服务

    在分时系统中，只有采用抢占方式才可能实现人机交互

    在实时系统中，抢占方式能满足实时系统的需求。但抢占方式比较复杂，所需付出的系统开销也较大

    抢占的主要原则有

    1. 优先级原则
    2. 短进程优先原则
    3. 时间片原则，即个进程按时间片轮转运行时，当正在执行的进程的一个时间片用完后，便停止该进程的执行而重新进程调度

3.2 轮转调度算法

1. 轮转法的原理

在轮转法（RR）中，系统根据 FCFS 策略，将所有的就绪进程排成一个就绪队列，并可设置每隔一段时间间隔产生一个中断，激活系统中的进程调度程序 ，完成一次调度，将 CPU 分配给队首进程，令其执行。当晋城的时间片耗尽或运行完毕时，系统再次将 CPU 分配给新的队首进程

2. 进程切换时机

  1. 若一个时间片尚未用完，正在运行的进程便已完成，就立即激活调度程序
  2. 在一个时间片用完时

3. 时间片大小的确定

时间片小，有利于短作业，因为它能在该时间片内完成，但会频繁执行进程调度和上下文切换，增加系统开销

时间片长，每个进程都能在一个时间片内完成，RR 算法则退化为 FCFS 算法，无法满足短作业和交互式用户的需求

一个可去的大小是略大于一个典型的交互所需的时间，使大多数交互式进程能在一个时间片内完成，从而获得很小的响应时间

3.3 优先级调度算法

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

  1. 非抢占式优先级调度算法
  2. 抢占式优先级调度算法

2. 优先级的类型

  1. 静态优先级

    创建进程时确定，在进程的整个运行期间不变，依据为

    1. 进程类型。系统>用户
    2. 进程对资源的需求。资源要求少优先级高
    3. 用户要求

    金泰优先级法简单易行，系统开销小，但不够精确，可能会出现优先级低的进程长时间没有被调度的情况

  2. 动态优先级

    可以规定就绪队列中的进程随等待时间的延长优先级相应提高。

    当采用抢占式调度方式时，规定当前进程的优先级随运行时间推移而下降，可防止一个长作业长期垄断处理机

3.4 多队列调度算法

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

3.5 多级反馈队列调度算法

1. 调度机制

  1. 设置多个就绪队列。优先级从高到低，时间片长度依次翻倍
  2. 每个队列采用 FCFS 算法，当新进程进入内存后，首先放入第一队列的末尾。当进程时间片完成仍为执行完成后扔在下一队列，直到最后第 队列按 RR 方式运行
  3. 按队列优先级调度。即当 的所有队列均空时，才会调度第 队列的进程。当处理机正在处理第 队列的某进程时又有新进程进入任一优先级较高的队列时，将正在运行的队列方位第 队列的末尾，将处理机分配给新到的高优先级进程

2. 调度算法的性能

  1. 终端型用户：交互性作业通常能在第一队列规定的时间片内完成
  2. 段批处理作业用户：对于这类作业如果在第一队列中完成便可获得与终端型作业一样的响应时间。对于稍长的短作业也只需在第二三队列各执行一时间片，周转时间仍较短
  3. 长批处理作业：对于长作业，将依次在 中，然后再按、轮转方式运行，不必担心得不到处理

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

1. 保证调度算法

当有 个相同类型的进程同时运行，为公平起见保证每个进程都获得相同的处理及时间

2. 公平分享调度算法

若用户所拥有的进程时不同，则对用户不公平。

可以考虑每一个用户所拥有的进程数目

四、实时调度

4.1 实时调度的条件

1. 提供必要的信息

  1. 就绪时间
  2. 开始截止时间和完成截止时间
  3. 处理时间
  4. 资源要求
  5. 优先级

2. 系统处理能力强

假定系统有 个周期性的硬实时任务 HRT，处理时间为 ，周期时间为 ，则在单处理机情况下，满足以下限制条件才可调度 多处理机的情况则

3. 采用抢占式调度机制

4. 具有快速切换机制

4.2 实时调度算法的分类

1. 非抢占式调度算法

  1. 非抢占式轮转调度算法

    数秒至数十秒的响应时间

  2. 非抢占式优先调度算法

    数秒至数百毫秒

2. 抢占式调度算法

  1. 基于时钟中断的抢占式优先级调度算法

    几十至几毫秒

  2. 立即抢占的优先级调度算法

    几毫秒至100微妙

4.3 最早截止时间优先（EDF）算法

1. 非抢占式调度方式用于非周期实时任务

2. 抢占式调度方式用于周期实时任务

通常的优先级调度不能使用于实时系统

4.4 最低松弛度优先（LLF）算法

松弛度（紧急程度）=截止时间-执行时间

松弛度低排最前

4.5 优先级倒置

1. 优先级倒置的形成

P1，P3 共享临界资源，P3 先到，再来 P3，P1 被阻塞完成 P2 和 P3 后再完成 P1，倒置

2. 解决办法

简单的方法：进入临界区后不允许抢占。但如果 P3 临界区很长则高优先级进程扔等待很长时间，无法令人满意

使用的方法：当 P1 要用的临界资源被 P3 占用时，由 P3 继承 P1 的优先级，避免了 P2 的插入

五、死锁概述

5.1 资源问题

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

  1. 可重用性资源

    是一种可供用户重复使用多次的资源，性质有

    1. 每一个可重用性资源的单元只能分配给一个进程，不允许多个进程共享
    2. 进程在使用可重用性资源时，必须要
      1. 请求资源
      2. 使用资源
      3. 释放资源
    3. 系统中每一类可重用性资源的单元数相对固定

  2. 可消耗性资源

    又称临时性资源，有进程在运行期间动态创建和消耗的资源，例如进程间通信的消息。性质有

    1. 每一类可消耗资源单元数目在运行期间可以不断变换
    2. 进程运行时可以不断创造可消耗性资源
    3. 进程在运行过程中可请求若干可消耗性资源单元用于自己的消耗

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

  1. 可抢占性资源

    某进程在获得这类资源后，该资源可以再被其他进程或系统抢占。如优先极高的进程可以抢占低的处理机。在内存紧张时把一个进程从内存掉出道外存，即抢占该进程在内存的空间，对于这类资源不会引起死锁

  2. 不可抢占性资源

    即一旦系统吧资源分配给某进城后，不能将它强行收回，只能在进程用完后自行释放。例如刻录光盘，磁带机，打印机等

5.2 计算机系统中的死锁

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

2. 进程可消耗资源引起死锁

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

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

1. 死锁的定义

如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的时间，那么该组进程是死锁的

2. 产生死锁的必要条件

  1. 互斥条件。进程对所分配到的资源进行排他性使用
  2. 请求和保持条件。进程以保持了至少一个资源但又提出了新的资源请求
  3. 不可抢占条件。进程已获得的资源在使用完之前不可抢占
  4. 循环等待条件。在发生死锁时，必定存在一个进程——资源的循环链

3. 处理死锁的方法

  1. 预防死锁：设置某些限制条件，破坏四个必要条件之一或多个
  2. 避免死锁：在自愿的动态分配时用某种方法防止系统进入不安全状态
  3. 检测死锁：无需任何先执行措施，运行发生死锁。但可通过检测机构及时检测出死锁的发生然后采取恰当措施解决进程
  4. 解除思索：当检测到死锁时则采取相应措施解脱进程。常用的方式是侧小一些进程，回收他们的资源，分配给已处于阻塞状态的进程使其能继续执行

六、预防死锁

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

1. 第一种协议

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

简单，易行，安全

缺点

  1. 资源被严重浪费，严重饿坏了资源利用率
  2. 进程经常会发生饥饿现象

2. 第二种协议

运行一个进程自获得运行处其所需的资源后开始运行。运行过程中在逐步释放已分配给自己的，已用毕的全部资源，然后请求新的所需资源

6.2 破坏“不可抢占”条件

协议中规定当一个已经保持了某些不可被抢占资源的进程提出新的资源请求而不能被满足时，必须释放已保持的所有资源，一代需要时重新申请

实现起来不较复杂且需付出很大的代价

6.3 破坏“循环等待”条件

对所有资源进行线性排序，并赋予不同的序号

规定每个进程必须按序号递增的顺序请求资源

多个同类资源单元必须一起请求

当有高资源要低资源时必须释放所有相同和更高序号的资源

相比强两种策略，资源利用率he系统吞吐量都有明显改善

缺点

  1. 系统中各类自愿的序号必须相对稳定，限制了新类型设备的添加
  2. 尽管分配序号是考虑到大多数作业在实际使用这些资源的顺序，但会发生：作业使用各类自愿的顺序与系统规定的顺序不同，造成对自愿的浪费
  3. 为方便用户，系统对用户编程的限制条件应尽可能少，但这种方法会限制用户简单、自主地编程

七、避免死锁

7.1 系统安全状态

1. 安全状态

安全状态，是指系统能按照某种进程推进顺序 为每个进程分配器所需资源直至满足每个进程对自愿的最大需求，此时称 为安全序列。如果系统找不到安全序列则称系统处于不安全状态

不安全状态不一定会产生死锁，但安全状态一定不会产生思索

2. 安全状态之例

进程 最大需求 已分配 可用
P1 10 5 3
P2 4 2
P3 9 2

此时存在一个安全序列

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

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

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

  1. 可利用资源向量 ，含有 个元素的数组，当 则系统中有 个 类资源

  2. 最大需求矩阵 ，这是一个 的矩阵，定义了 个进程对 类自愿的最大需求

  3. 分配矩阵 ，也是一个 的矩阵，定义了当前系统已分配给每一进程的资源数

  4. 需求矩阵 ，也是一个 的矩阵，表示每个进程尚需的各类资源

2. 银行家算法

设 是进程 的请求向量，当 发出资源请求时，系统按以下步骤检查

  1. 如果 则继续，否则出错，需求资源超过宣称最大值

  2. 如果 则继续，否则尚无足够资源

  3. 尝试分配资源 ，修改数据结构的值

  4. 系统执行安全性算法检查此次资源分配后系统是否处于安全状态

3. 安全型算法

  1. 设置两个向量

    1. 工作向量 表示系统可提供给进程继续运行所需的各类资源数目，开始时
    2. 表示系统是否有足够的资源分配给该进程，开始时

  2. 从进程集合中找到一个能满足以下条件的进程

    3. 若找到步骤3，否则步骤4

  3. 当进程 获得资源后，执行直至释放资源，所以 $$

    $$

  4. 如果所有进程的 满足则系统处于安全状态，反之不安全状态

八、死锁的检测与解除

8.1 死锁的检测

1. 资源分配图

进程结点和资源节点，

请求边表示资源请求进程，分配边表示资源分配

2. 死锁定理

简化资源分配图，略

8.2 死锁的解除

  1. 抢占资源：从一个或多个进程中抢占足够数量的资源分配给死锁进程
  2. 终止（撤销）进程：终止（撤销）系统中的若干死锁进程

1. 终止进程的方法

  1. 终止所有死锁进程

  2. 逐个终止进程

    代价可以为

    1. 进程的优先级大小
    2. 进程执行时间，还需多少时间
    3. 进程已使用资源，还需多少资源
    4. 进程时交互式的还是批处理使得

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

每次选解除代价最小的解除即可

不知不觉Acmer & Student

Never Settle