CPU调度

原文地址： https://qjm253.cn/2018/06/29/os_03/

CPU调度的基本概念

• 主要目标：使CPU的利用率最大化（也是多道程序设计的目标）

• 并行与并发

  • 并行

    并行指的是两个事件在同一时刻同时发送。

    并行图示
    => 如果两个进程需要并行运行的话，系统必须具有多处理器结构

  • 并发

    并发指的是两个事件在一个时间段内交替发生，在宏观上看，时间段内两个事件都发生了。

    并发图示
    => 上图以单核并发为例，两个进程在一个时间段内交替运行，快速切换，宏观上看起来是都在运行。（时分的思想）

• CPU-I/O 区间周期

  一个进程的运行周期是由CPU区间和I/O区间的交替序列组成的（也就是说，一个进程在使用CPU进行计算和进程I/O操作两种状态之间反复切换）

  CPU区间和I/O区间交替图示
  • I/O约束程序通常具有很多短CPU区间，CPU约束程序可能有少量长CPU区间。
  • 进程这种I/O区间和CPU区间交替分布，并且分布不均匀的特性，有助于选择合适的CPU调度算法

• CPU调度

  CPU调度 = CPU调度程序 + 派遣程序

  
  CPU调度的组成

• CPU调度程序

  CPU调度程序 也称 短期调度程序（short-term scheduler）。每当CPU空闲的时候，操作系统通过运行CPU调度程序从就绪队列当中选择一个进程来执行。

  • 调度的时机

    进程状态图
    1. Running => Waiting （非抢占点）
    2. Running => Ready （抢占点）
    3. Waiting => Ready （抢占点）
    4. Running => Terminated （非抢占点）

    => 其中抢占点是有可能发生抢占式调度的点

  • 抢占式调度与非抢占式调度

    • 非抢占式调度

      当线程终止或阻塞是发生调度 => “主动让出”

    • 抢占式调度

      允许逻辑上将可继续运行的线程在运行过程中暂停的调度方式 => “被迫让出”

• 派遣程序

  派遣程序（dispatcher）是一个模块，在调度程序选中 下一个要执行的进程后，派遣程序 负责将CPU的控制权交给选中的进程。

  • 任务

    • 切换上下文 => 如果需要的话保存旧进程的状态，恢复选中进程的状态
    • 切换到用户模式 => 调度程序是在内核态运行的，所以要恢复到用户模式以便选中进程执行
    • 跳转到应用程序的合适位置，开始执行 => 通常是跳到被选中进程的下一条待执行的指令处，开始执行。

  • 派遣延迟

    从就得任务暂停并保存状态，到新的任务在CPU上开始执行这段时间间隔

调度准则

如何判断调度算法的好坏？有何标准？

• CPU利用率

  CPU利用率（CPU utilization）=> 原则上，让CPU越忙越好，即CPU使用率越高越好

• 吞吐量

  吞吐量（throughput）指的是一个单位时间内完成的进程的数量 => 目标当然是让吞吐量越大越好

• 周转时间

  周转时间（Turnaround time）指的是一个进程从提交到执行完成所经历的时间。=> 目标当然是周转时间越短越好

• 等待时间

  等待时间（Waiting time）指的是进程在就绪队列里面等待的时间长度。（CPU调度算法 并不影响进程运行和执行I/O的时间，只会影响进程在就绪队列中等待所花的时间）=> 对于一个进程来说，等待时间当然是越短越好

• 响应时间

  响应时间（Response time）指的是在分时系统内，用户发出一个请求，到该请求得到响应的时间间隔长度

需要使得CPU的使用率和吞吐量最大化，而使周转时间、等待时间和响应时间最小化。但是这些因子有些是冲突的，比如如果想要让吞吐量最大化就势必要让短进程都优先执行，这样就会使得长进程的等待时间和响应时间增长。在绝大多数的情况下需要优化取平均值，而在一些特定情况可能只关心其中的一部分因子。

调度算法

• FCFS
• SJF
• SRTF
• Priority Scheduling
• Round-Robin

• 平均等待时间 = ((总的周转时间) - (总的执行时间)) / 完成的进程数量

• 先到先服务（First Come First Serve, FCFS）

  FCFS的思想很简单，就绪队列用一个FIFO（First In, First Out）队列实现。有新的进程到来就放到队列尾，每当有CPU空闲则将其分配给队头的进程。这种实现是非抢占式的，进程一旦分配到CPU，就会一直占有CPU直到进程执行完或者进程需要处理I/O主动放弃CPU的使用权。一旦等待I/O的进程处理完I/O，就会重新回到就绪队列当中，放到队列尾。

  FCFS示意图

  • 举个栗子

    下图为P₁、P₂、P₃三个进程执行所需要的时间，认为他们均在0时刻到来。(单位为ms)

    {% img /img/os/os_23.png %}

    • 假设到来的顺序为：P₁、P₂、P₃

      {% img /img/os/os_24.png 上述到来顺序的甘特图表示%}
      • 平均周转时间 = (24 + 27 + 30) / 3 = 27ms
      • 平均等待时间 = ((24 + 27 + 30) - (24 + 3 + 3)) / 3 = 17ms

    • 假设到来的顺序为：P₂、P₃、P₁

      {% img /img/os/os_25.png 上述到来顺序的甘特图表示%}
      • 平均周转时间 = (3 + 6 + 30) / 3 = 13ms
      • 平均等待时间 = ((3 + 6 + 30) - (24 + 3 + 3)) / 3 = 3ms

  • FCFS的问题

    • 受进程区间时间和到来顺序的影响较大

      从上面的栗子里面也可以看出，FCFS的性能受进程的区间时间和到来顺序的影响比较大。如果进程CPU的区间变动很大，那么性能也会飘忽不定。

    • 护航效应

      因为FCFS算法是非抢占式的，允许一个进程长期占有CPU时间。如果有一个很大的进程占据CPU，而其他进程都在等待这个长进程的结束，便产生了护航效应（convoy effect）。

• 短作业优先算法（Shortest-Job-First, SJF）

  • 如果以平均等待时间为指标，那SJF是最优的调度
  • SJF算法也是非抢占的

  每次进行调度的时候，优先选择下一个CPU周期（执行时间）最短的进程。也就是，调度的时候，系统去就绪队列里面找到执行所需要时间最短的进程，分配给它CPU让它去执行。

  • 栗子1

    下图为P₁、P₂、P₃、P₄四个进程执行所需要的时间，认为他们均在0时刻到来。(单位为ms)
    

    SJF调度示例1
    它们的到来顺序为P₁、P₂、P₃、P₄，则对应的Gant图如下：
    SJF调度Gant图1
    • 平均周转时间 = (3 + 9 + 16 + 24) / 4 = 13ms
    • 平均等待时间 = ((3 + 9 + 16 + 24) - (6 + 8 + 7 + 3)) / 4 = 7ms

  • 栗子2

    下图为P₁、P₂、P₃、P₄四个进程的到来时间和执行所需要的时间。（单位为ms）
    

    SJF调度示例2
    采用SJF调度，执行顺序对应的Gant图如下：
    SJF调度Gant图2
    • 平均周转时间 = (6 + (9 - 5) + (16 - 4) + (24 - 2)) / 4 = 11ms
    • 平均等待时间 = ((6 + (9 - 5) + (16 - 4) + (24 - 2)) - (6 + 8 + 7 + 3)) / 4 = 5ms

  • SJF调度算法存在的问题

    因为一个进程没有执行，所以我们并不知道它会运行多久，也就是说我们无法准确的知道进程的CPU周期长度。只能根据进程CPU周期的历史数据，堆下一个CPU周期长度进行预测。=> 采用指数平均方法（exponential averaging）

  • 指数平均方法

    τ_n+1 = α t_n + (1 - α) τ_n

    • t_n：第n个进程的CPU周期（actutal length of n^th CPU burst）
    • τ_n+1：对下一个进程的CPU周期的预测值（predicted value for the next CPU burst）
    • α：0 ≤ α ≤ 1。通常取 1/2
    • 离现在越久的历史数据，对预测结果的影响越弱
    采用指数平均的方法预测下一进程CPU周期

• 最短剩余时间算法（Shortest-Remain-Time-First scheduling, SRTF）

  SRTF算法实际上是一种特殊的SJF算法，它是一种允许抢占的SJF算法。

  • 每当一个新进程进入就绪队列，就会产生一个抢占点。

  • 如果就绪队列中的进程的剩余执行时间比正在执行的进程的短，就会抢占掉正在执行的进程。

  • 举个栗子

    下图为P₁、P₂、P₃、P₄四个进程的到来时间和执行所需要的时间。（单位为ms）
    

    SRTF调度示例
    采用SRTF调度，执行顺序对应的Gant图如下：
    SJF调度Gant图
    • 平均周转时间 = ((5 - 1) + (10 - 3) + (17 - 0) + (26 - 2)) / 4 = 13ms
    • 平均等待时间 = (((5 - 1) + (10 - 3) + (17 - 0) + (26 - 2)) - (8 + 4 + 9 + 5)) / 4 = 6.5ms

• 优先级调度算法（priority scheduling）

  优先级调度算法（priority scheduling）的核心思想是给每一个进程赋予一个优先级，每次调度的时候选择选中优先级最高的进程执行。

  • SJF是一种特殊的优先级调度算法

    SJF 也是基于优先级的，预测出的 下一个CPU周期越短，优先级越高

  • 抢占与非抢占

    • 非抢占式（Nonpreemptive）优先级调度

      非抢占的模式下，一个新进程到达，无论其优先级如何，都只是将其放到就绪队列等待。

    • 抢占式（Preemptive）优先级调度

      在抢占模式下，一个新进程到达，如果其优先级比正在执行的进程的优先级高，便会抢占正在执行进程的CPU

  • 优先级算法存在的问题

    优先级算法存在的主要问题是无穷阻塞（indefinite blocking）/ 饥饿（starvation）。=> 低优先级的进程可能永远得不到执行

  • 老化（Aging）=> 解决饥饿问题

    逐渐增加在系统中等待很长时间的进程的优先级，增加其执行的可能性。

  • 举个栗子

    下图为P₁、P₂、P₃、P₄、P₅五个进程的优先级和执行所需要的时间，认为他们均在0时刻到来。（单位为ms）
    优先级调度示例
    采用优先级调度，执行顺序对应的Gant图如下：
    优先级调度Gant图
    • 平均周转时间 = (1 + 6 + 16 + 18 + 19) / 5 = 12ms
    • 平均等待时间 = ((1 + 6 + 16 + 18 + 19) - (10 + 1 + 2 + 1 + 5)) / 5 = 8.2ms

• 轮转调度算法（Round Robin scheduling, RR）

  轮转调度（Round Robin, RR）的核心思想类似于FCFS，但是增加了抢占机制。定义一个较短的时间间隔，称为时间片（time quantum, or time slice）。进程每次在CPU上执行的时间间隔不会超过一个时间片的长度。

  • 执行过程

    • 首先就绪队列维护为一个FIFO队列，每次调度的时候从队首取一个进程*。
    • 一个新的进程被选中而得到执行时，会设置一个定时器在一个时间片之后中断。
    • 如果进程在一个时间片内执行完毕了，会主动释放CPU，调度程序会取出就绪队列中的下一个进程执行。
    • 如果进程执行满一个时间片，但是没有执行完。则定时器会超时并引发操作系统超时中断，然后进行上下文切换。进程被放到就绪队列 队尾，接着调度程序会选择就绪队列的下一个进程执行。

  • 轮转调度的效率问题

    时间片的大小通常在10~100ms

    • 时间片太大 => 等同于FCFS
    • 时间片太小 => 上下文切换过于频繁

  • 举个栗子

    下图为P₁、P₂、P₃三个进程的优先级和执行所需要的时间，认为他们均在0时刻到来。（单位为ms）
    

    RR调度示例
    采用RR调度，执行顺序对应的Gant图如下：
    RR调度Gant图

• 最高响应比优先调度算法（扩展）

  在批处理操作系统中，常用短作业优先调度算法。但短作业优先调度算法有一个致命的弱点，那就是长进程可能会被饿死

  最高响应比优先调度是对短作业优先调度的改进

  • 优先权

    P = (W + T) / T
    • W: 进程等待时间
    • T: 进程执行时间

  • 规则

    • 优先权P被称为响应比，又被称为进程的带权周转时间，响应比越大，调度优先权越高
    • 采取非抢占方式进行调度

• 多级队列调度（Multilevel Queue）

  多级队列（Multilevel Queue）的思想：将就绪队列拆分为多个，每个队列可以各自采取不同的调度算法，队列之前按优先级的高低来进行调度。

  多级队列调度

  对于如何在多个队列之间均衡时间，有下列两种方式：

  • 固定优先级：每个队列被赋予特定的优先级，高优先级队列中的进程先得到调度。可能存在饥饿问题（低优先级队列中的进程饿死）。
  • 时间片：给每个队列赋予一定的时间片，分配有一定的原则（并非完全等额分配）。例如可以80%的时间保证赋予前台进程，20%时间赋予后台进程

• 多级反馈队列（Multilevel Feedback Queue）

  多级反馈队列（Multilevel Feedback Queue）解决多级队列中存在的饥饿问题：将较长时间得不到调度的进程移动到更高优先级的队列

  多级反馈队列

线程调度（Thread Scheduling）

• 用户级线程与内核级线程的区别：内核对内核级线程进行调度（***Distinction between user-level and kernel-level threads ***）

• 当操作系统支持线程机制时，线程成为调度的基本单位（When threads supported, threads scheduled, not processes）

• 多对一、多对多线程模型中，线程库负责对轻量级线程上的多个用户线程进行调度（Many-to-one and many-to-many models, thread library schedules user-level threads to run on LWP）

• 内核级线程在全系统范围竞争CPU时间（***Kernel thread scheduled onto available CPU is system-contention scope (SCS) – competition among all threads in system ***）

• pthread线程库中允许在创建线程时指定竞争域（PCS/SCS）（API allows specifying either PCS or SCS during thread creation）