处理机调度

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

处理机调度的层次

在多道批处理系统中，一个作业从提交、执行到完成，需要经历多级处理机调度。

  • 高级调度：即作业调度，根据算法决定将处于外存后备队列中的作业调入内存，并为它们创建进程，放入就绪队列。高级调度主要用于多道批处理系统，在实时和分时系统中不设置高级调度。
  • 低级调度：即进程调度，决定就绪队列中哪个进程获得处理机，是最基本的一种调度。
  • 中级调度：即内存调度，即存储器管理中的对换功能，在内存和外存间调换进程（即挂起和激活），以提高内存利用率和系统吞吐量。

处理机调度算法的目标

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

  • 资源利用率：最重要的是处理机利用率
  • 公平性：使不同重要程度和紧急程度的进程获得相应的合理 的CPU 时间
  • 平衡性：平衡不同种类进程的 CPU 占用时间
  • 策略强制执行：对所制定的策略（包括安全策略）必须准确执行

批处理系统目标

  • 平均周转时间短：周转时间包括作业在外存后备队列上等待调度的时间、进程在就绪队列等待调度的时间、进程在 CPU 上执行的时间和进程等待 I/O 操作完成的时间，可用加权平均周转时间（权重为系统为作业提供服务时间的倒数）衡量调度性能。
  • 系统吞吐量高：即单位时间系统所完成的作业数
  • 处理机利用率

分时系统目标

  • 响应时间快：响应时间指请求信息输入到终端显示结果的时间
  • 均衡性：系统响应时间与用户请求服务的复杂程度相适应

实时系统目标

  • 截止时间的保证：截止时间指某任务开始的最迟时间或完成的最迟时间，对 HRT 任务要求必须保证截止时间要求，对 SRT 任务要求基本保证截止时间要求
  • 可预测性：提前预测用户请求

1. 作业调度

1.1. 作业

作业是用户提交给系统一项相对独立的工作，包括程序、数据和一份作业说明书。在批处理系统中，是以作业为基本单位从外存调入内存的。作业又分为若干个相对独立又相互关联的顺序加工步骤，即作业步。

作业控制块

在多道批处理系统中，每个作业都设置有一个作业控制块 JCB（Job Control Block），它是作业在系统中存在的标志，包含作业标识、用户名称、用户账号、作业类型（CPU 繁忙型、I/O 繁忙型、批量型、终端型）、作业状态、调度信息（优先级、作业运行时间）、资源需求（预计运行时间、需要内存大小等）、资源使用情况等。

作业运行的三阶段和三状态

作业从进入系统到运行结束，通常经历收容、运行和完成三个阶段，对应的状态分别是后备状态、运行状态和完成状态。

  • 收容阶段：用户提交的作业通过某种输入方式或 SPOOLing 系统被输入到硬盘上，再为作业建立 JCB 并放入后备队列
  • 运行阶段：作业被调度后，系统为其建立进程并放入就绪队列，直到运行结束
  • 完成阶段：作业运行完成或发生异常提前结束时，作业的作业控制块和所有资源被收回，并将运行结果信息形成输出文件后输出

1.2. 作业调度

作业调度的任务是确定接纳的作业数目和具体作业。作业接纳多了，容易引起进程因运行内存不足而发生中断并急剧增加。常见的作业调度算法有：

  • FCFS：先来先服务调度算法（first-come first-served），一般结合其他算法使用
  • SJF：短作业优先调度算法（short job first），基于实际中短作业占很大比例
  • PSA：优先级调度算法（priority-scheduling algorithm），基于作业的紧迫程度
  • HRRN：高响应比优先调度算法（Hightest Response Ratio Next），响应比=响应时间/要求服务时间

2. 进程调度

2.1. 进程调度

进程调度的主要任务是

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

进程调度机制

  • 排队器：将所有就绪进程按照一定的策略事先排成一个或多个队列
  • 分派器：从就绪队列取出选定的进程，并进行从分派器到新选出进程间的上下文切换，将处理机分配给新选出的进程
  • 上下文切换器：两次上下文切换操作
    • 当前进程与分派程序的上下文切换：保存当前进程的处理机寄存器内容到 其PCB，并装入分派程序的上下文
    • 分派程序与新进程的上下文切换：移除分派程序的上下文，将新进程的 CPU 现场信息装入处理机各寄存器

s2018-08-17_3

进程调度方式

  • 非抢占方式（Nonpreemptive Mode）：一旦将处理机分配给某进程，进程将会一直运行下去，直到
    • 进程运行完毕或因发生某事件而异常结束
    • 提出 I/O 请求而自行阻塞
    • 在通信或同步过程中执行的某种原语操作
  • 抢占方式（Preemptive Mode）:根据一定原则（优先权原则、短进程优先原则、时间片原则）去暂停正在执行的进程，将处理机重新分配给另一进程

2.2. 进程调度算法

轮转 RR（round robin）调度算法

让就绪队列上的每个进程每次运行一个时间片（进程提前运行完毕，则提前调度进程），时间片时长一般选择略大于一次典型交互所需时间。

优先级调度算法

按进程调度方式分为非抢占和抢占两种，按优先级类型可分为静态优先级和动态优先级。

静态优先级是在创建进程时按照进程类型（系统进程高于一般用户进程）、进程对资源的需求（资源需求小的优先级高）和用户要求（进程的紧迫程度）确定，用一定范围的整数表示，并保持不变；动态优先级在进程创建时赋一初始值，随时间推进而改变。

多队列调度算法

不同就绪队列可采用不同的调度算法，就绪队列本身也可设置优先级。

多级反馈队列（multileved feedback queuq）调度算法

不必事先知道各进程所需的执行时间，是目前公认较好的进程调度算法。

  • 设置 N 个就绪队列，优先级一次降低，时间片长度逐个增加一倍，每个队列采用 FCFS 算法。
  • 当新进程进入内存后，先将其放至第一个就绪队列末尾，轮到该进程执行时，若进程在时间片内完成，则撤离系统，否则放入下一个就绪队列末尾；第 N 个队列采用 RR 调度方式。
  • 按队列优先级调度：当第1~(i-1) 就绪队列均为空时，系统才会调度第 i 队列；当优先级更高的队列有新进程时，把当前执行的进程放入其所在队列末尾，立即去调用优先级更高的进程。

s2018-08-17_4

基于公平原则的调度算法

  • 保证调度算法：若系统中有 N 个相同类型的进程同时运行，必须保证每个进程都获得相同的处理机时间 1/N，实现方式是
    • 跟踪计算每个进程自创建以来已执行的处理时间
    • 计算每个进程应获得的处理机时间，即进程创建以来的时间除以 N
    • 计算进程实际执行的处理时间和应获得的处理机时间的比率
    • 比较该比率，比率小的优先调用，直到其比率不再最小
  • 公平分享调度算法：若考虑各作业、各用户的公平，则需要统计其各自的进程数，为其赋予相应的比率倍数。

3. 实时调度

实时调度的基本条件

  • 提供必要的信息：包括就绪时间、开始截止时间（和完成截止时间）、处理时间、资源要求、优先级
  • 系统处理能力强：若系统中有 m 个周期性的 HRT，它们的处理时间表示为 Ci，周期时间表示为 Pi，处理机数为 N，则必须满足
  • 采用抢占式调度机制
  • 快速切换机制：中断的快速响应能力（要求有硬件中断机构，且禁止中断的时间间隔尽量短）和快速的任务分派能力（应使系统中的每个运行功能单位适当的小）

实时调度算法分类

s2018-08-17_5

3.1. 实时调度算法

最早截止时间优先EDF（Earliest Deadline First）算法

有非抢占式和抢占式两种

最低松弛度优先 LLF（Least Laxity First）算法

紧急（松弛）程度 = 任务必须完成时间 - 任务本身运行所需时间 - 当前时间，系统按照松弛度的大小来抢占调度进程。

3.2. 优先级倒置

即高优先级进程（线程）被低优先级进程（线程）延迟或阻塞的现象。

例如：

  1. P1、P2、P3 的优先级逐个降低，P1 和 P3 通过共享的一个临界资源进行交互，若 P3 先执行，并执行了 P(mutex) 操作；
  2. 此时 P2 就绪，P2 抢占 P3 的处理机而运行；
  3. 此时 P1 就绪，P1 抢占 P2 的处理机而运行，P1 运行至 P(mutex) 阻塞；
  4. 此时 P2 继续运行至结束，然后由 P3 接着运行至退出临界区，这时才轮到 P1 运行

解决方法是建立动态优先级继承：当一个优先级较高的进程要进入临界区，若一个优先级较低的进程正在使用相同的临界资源，则让后者继承前者的优先级直至退出临界区。

4. ChangeLog

2018.08.22 初稿

results matching ""

    No results matching ""