526互联

2023Fal-操作系统-Chapter3-处理机调度与死锁

发布时间 2023-10-28 15:35:19作者: O2iginal

本文为笔者的课程学习记录，用于复习与查阅，如有错误，烦请指正。

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

1.1 何为调度？

在多道程序系统中，调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。

1.2 何为调度算法？

处理机调度算法是指根据处理机分配策略所规定的处理机分配算法。

1.3 处理机调度层次

  • 调度层次分为高、中、低3层调度机制；

  • a 高级调度（作业调度）

    • 决定把外存上处于后备队列中的哪些作业调入内存，分配资源、创建进程，等待；
    • 频率很低，几分钟一次；
    • 作业调度仅存在与批处理系统中，在我们常用的分时系统不常用；

  • b 中级调度（内存调度）

    • 挂起与激活的调度，将进程在外存和内存中转移；
    • 交换调度的目的是为了解决内存紧张问题，常用于分时系统及具有虚拟存储器的系统；

  • c 低级调度（进程调度）

    • 分配CPU时间，在就绪队列中选择进程分配处理机资源；
    • 最基本的调度；
    • 高频，需要简单的调度算法，以免占用过多时间；
    • 两种低级调度方式：
      1. 非抢占式：进程获得CPU后，除非主动让出，否则其他进程不能得到CPU；
      2. 抢占式：系统可根据某种原则，暂停正在占用CPU的进程，将CPU分配给其他进程；
        • 常见抢占原则：
          • 优先权原则；
          • 短作业原则；
          • 时间片原则；

1.4 调度算法目标

  1. 共同目标
    1. 资源利用率（包含CPU与其他资源的利用率）
      • CPU利用率计算 = 工作时间 / （工作时间 + 空闲时间）
    2. 公平性
      • 对所有进程公平分配CPU，不造成个别进程的饥饿现象；
      • 根据进程的优先级的不同，可有所侧重；
    3. 平衡性
      • 均衡不同类型的进程调度（计算型进程、IO型进程）；
      • 使得CPU和各种外部设备均衡使用，经常处于忙碌状态；
    4. 策略强制执行
      • 对于重要策略（如安全），需要时则强制执行，即便造成某些工作延迟执行；
  2. 批处理系统目标（不同的目标导致不同的调度策略）
    1. 平均周转时间短
      • 周转时间：作业提交给系统 - 作业完成 所用时间；
      • 平均周转时间：n个作业的周转时间的平均值；
      • 带权周转时间：W = 周转时间T / 系统为其提供服务的时间 Ts ；
        • W必然不小于1；
      • 平均带权周转时间：n各作业的带权周转时间的平均值；
    2. 系统吞吐量高
      • 吞吐量：单位时间内系统所完成的作用数（强调个数）；
      • 与作用长度有关，如果想要提高吞吐量，则应选择短作业执行；
    3. 处理机利用率高
      • 若想单纯提高处理机利用率，则应选择计算量大的进程优先执行；
      • 可见，这些目标间存在矛盾；
  3. 分时系统目标
    1. 响应时间快
      • 响应时间：用于键盘输入请求 - 屏幕显示结果 所用时间；
      • 包含3部分：请求输入 + 处理机处理 + 相应信息显示到屏幕；
    2. 均衡性
      • 响应时间的快慢应与用户所请求服务的复杂性相适应；
      • 即简单服务相应快，复杂服务可适当相应慢（因为用于对此有心理预期）；
  4. 实时系统的目标
    1. 截止时间保证
      1.截止时间：指任务最迟执行时间或最迟完成时间；
      2. 实时系统调度算法的主要目标是保证截止时间；
    2. 可预测性
      • 请求可预测性，如电影的连续播放。若使用双缓冲，可对连续两帧并行处理，提高实时性；

02 作业与作业调度

2.1 批处理系统中的作用

  1. 何时需要进行作业调度 ？
    批处理系统中，外存调入内存；
  2. 作业与作业布的概念
    • 作业：包含程序、数据、作业说明书；批处理系统中，以作业为基本单位从外存调入内存；
    • 作业步：作业可分为若干相互独立同时相互关联的顺序步骤，这些步骤称为作业步；
  3. 作业控制块
    • JCB：job control block；
    • 包含：作业标识、用户名称、用户账号、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业运行时间)、资源需求(预计运行时间、要求内存大小等)、资源使用情况等
  4. 作业运行的三个阶段和三种状态
    作业从进入系统到运行结束，通常需要经历收容、运行和完成三个阶段。相应的作业也就有“后备状态”、“运行状态”和“完成状态”；

2.2 作业调度的主要任务

  1. 主要任务：
    • 根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求，
    • 按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，
    • 为它们创建进程、分配必要的资源，
    • 再将新创建的进程排在就绪队列上等待调度；
      总结即为：作业调度决定调度几个作业，哪几个被调度；

2.3 作业调度算法

主要有4种算法：

  1. 先来先服务FCFS调度算法；
    • 按照作业到达的先后次序来进行调度；
    • 这种调度方式，在所有作业的耗时相当时，基本公平；
    • 但是当有长耗时夹杂在其中是，会使得长作业长期占用CPU，使得短作业长时间等待；
  2. 短作业优先SJF调度算法；
    • 作业越短，其优先级越高；
    • 作业长短衡量标准：作业所要求的运行时间；
    • 可以分别用于作业调度和进程调度；
    • 缺点：
      1. 必须预知作业的运行时间（用于选择短作业）；
      2. 对长作业不利，长作业周转时间明显增长，出现饥饿；
      3. 完全未考虑作业的紧迫程度，紧迫性作业不能得到优先处理；
  3. 优先级调度算法；
    • 根据优先级进行作业调度（也可用于进程调度）；
    • 本质上这些算法都是根据优先级调度，而对于优先级的定义不同；
  4. 高响应比优先调度算法；
    • (Highest Response Ratio Next ，HRRN）；
    • 对比：
      • FCFS算法所考虑的只是作业的等待时间，而忽视了作业的运行时间；
      • SJF算法正好与之相反，只考虑作业的运行时间，而忽视了作业的等待时间；
      • 而高响应比优先调度算法则是兼顾了等待与运行时间两个方面；
    • 特点：动态优先级，作业的优先级随着等待时间的增加，且不同长度作业的优先级增加速度不同；
    • 计算：\(优先级R_p = \frac{等待之间 + 要求服务时间}{要求服务时间} = \frac{相应时间}{要求服务时间}\)

03 进程调度

3.1 进程调度的任务

  1. 保存当前进程的现场信息（处理机、寄存器等等）；
  2. 根据某种算法选择调度进程；
  3. 将处理机分配给此进程；

3.2 进程调度机制

image

3.3 进程调度方式

调度方式可分为两类：

  1. 抢占式方式
  2. 非抢占式方式

对于非抢占式方式，其引起调度（主动让出CPU）的因素有：

  1. 进程结束；
  2. 提出IO请求；
  3. 在进程通信和同步过程中，执行力某些源于；

对于抢占式方式，常见的抢占原则有：

  1. 优先权原则；
  2. 短进程优先原则；
  3. 时间片原则；

3.4 进程调度算法

  1. 时间片轮转调度算法(Round Robin)；
    • 划分时间片，进程排队使用时间片。时间片用完后回到队尾；
    • 进程切换时机：
      1. 时间片用完；
      2. 进程执行完毕；
    • 时间片大小确定：
      • 过长：退化为FCFS；
      • 过短：上下文切换次数多，增加切换系统开销；
  2. 优先级调度算法
    • 优先级调度算法类型：
      1. 抢占式；
      2. 非抢占式；
    • 优先级类型
      1. 静态优先级
      2. 动态优先级；
  3. 多队列调度算法
    • 设置多个就绪队列，每个队列可以实施不同的调度算法；
    • 系统针对不同用户进程的需求提供多种调度策略；
  4. 多级反馈队列调度算法
    • 与多队列调度算法区分：
      • 进程在一个队列得到时间片后，会进入下一个队列尾，而不是回到同一个队列；
      • 队列的优先级递减，时间片大小递增；
    • 新进程加入调度的方法：首先放入优先级最高的队列进行等待，当轮到此进程并将时间片用完后，则放入优先级第二的队列， 以此类推；
    • 优点：
      • 不需要知道此进程的预期服务所需时间，所有进程的策略相同；
      • 在多级反馈队列调度算法中，如果规定第一个队列的时间片略大于多数人机交互所需之处理时间时，便能较好地满足各种类型用户的需要；
    • 注意：只有第\(i\)高优先级队列之前的队列（\(1\)~\(i-1\)）都调度完毕（队列为空）时，才会开始调度第\(i\)个队列；
      image
  5. 保证调度算法
  • 在系统中有n个相同类型的进程同时运行，为公平起见，须保证每个进程都获得相同的处理机时间1/n；
  • 调度程序应选择比率最小的进程将处理机分配给它，并让该进程一直运行，直到超过最接近它的进程比率为止；
  1. 公平分享调度算法
  • 公平分享调度算法中的公平性主要针对用户而言，使所有用户能获得相同的处理机时间，或所要求的时间比例；

04 实时调度

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

  1. 非抢占式；
    • 任务的开始截止时间来确定任务的优先级；
    • 开始截止时间：任务在某时间以前必须开始执行；
  2. 抢占式；
    • 抢占式调度用于周期实时任务；
    • 根据任务的最早完成截止时间来确定任务的优先级；

例如：有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间为25ms；
image

4.2 最低松弛度优先算法

  • 最低松弛度优先LLF(Least Laxity First)；
  • 任务的紧急程度愈高，为该任务所赋予的优先级就愈高，使之优先执行。
    • 松弛度=必须完成时间-其本身的运行时间-当前时间；
    • 松弛度，也就是还可以等待的最大时间；
  • 主要用于抢占式调度方式；

有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间为25ms；
image
注意：

  • 在20ms时，这里虽然A的松弛度更低，但因切换进程有所花销，且A进程松弛度仍有剩余，因此不进行切换，继续进行B，等到必须执行A是再切换。
  • 也就是尽量减少切换，同时在一定程度上使用松弛度作为优先级依据。

4.3 问题：优先级倒置

  • 何为优先级倒置？
    高优先级进程(或线程)被低优先级进程(或线程)延迟或阻塞；
  • 解决方法：
    • 总体方法：进入临界区后的进程所占有的处理机不允许被抢占；
    • 具体方法1：将申请某资源的任务的优先级提升到可能访问该资源的所有任务中最高优先级任务的优先级。（这个优先级称为该资源的优先级天花板）；
    • 具体方法2：动态优先级继承：当发现高优先级的任务因为低优先级任务占用资源而阻塞时，就将低优先级任务的优先级提升到等待它所占有的资源的最高优先级任务的优先级；
    • 注意区分这两种方法的区别：优先级提升的时机不同；

05 死锁概述

06 预防死锁

07 避免死锁

08 死锁检测与解除