处理机（CPU）调度

一. 调度的概念

多道程序系统中，进程数量往往多于CPU数量，因此经常出现进程争用CPU的情况，由此出现CPU调度的概念。

基本概念

CPU调度：对CPU进行分配，即从就绪队列中按照一定的算法（公平，高效原则）选择一个进程并将CPU分配给它运行，以实现进程并发执行。

调度的层次

• 高级调度（作业调度）
  • 按照某种规则从后备队列的作业中选择一个或多个，给它们分配内存，I/O设备等必要资源，并建立相应进程，使得它们能够竞争CPU使用权。
  • 是内存——辅存之间的调度。
  • 每个作业只能调入一次，调出一次。

作业：需要完成的某一个具体任务。

• 中级调度（内存调度）
  • 为了提高内存利用率和系统吞吐量，将暂时不能运行的程序调至外存等待，此时的进程状态称为挂起态。

被挂起进程的PCB被组织成挂起队列。

• 当挂起态的进程具备运行条件+内存有空闲，由中级调度决定将它们从外存调入内存，修改状态为就绪态，挂在就绪队列等待。
• 实质上是存储器管理中的对换功能

补充：七状态模型

• 低级调度（进程调度/处理机调度）
  • 按照某种算法，从就绪队列选取一个进程分配给CPU。
  • 进程调度是最基本的调度，各种OS都必须配置。
  • 使用频率很高，以便几十毫秒一次。

三级调度的联系

• 作业调度：为进程活动做准备；进程调度：使得进程正常活动起来。
• 中级调度：挂起暂时不能运行的进程，处于作业调度和进程调度之间。
• 作业调度次数少，中级调度次数略多，进程调度频率最高。
• 进程调度是最基本的，不可或缺。

二. 调度的实现

这里的调度是指 内存调度（即低级调度）：按照某种算法从就绪队列选择一个进程为其分配处理机（CPU）。

调度程序（调度器）

定义：用于调度和分派CPU的组件。结构组成：排队器，分派器，上下文切换器。

结构如图所示：

• 排队器
  • 将系统中所有就绪进程排成一个或多个就绪队列，以便调度程序选择。
  • 出现一个就绪进程，就把它插入相应的就绪队列。
• 分派器
  • 依据调度程序选择的进程，将它从就绪队列取出，将CPU分配给（它）新进程。
• 上下文切换器：对CPU进行切换时，会发生两对上下文切换操作。
  • 第一对：将当前进程的上下文保存到它的PCB中，再装入分配派程序的上下文，以便分派程序的运行。
  • 第二对：移除分派程序的上下文，将新选进程CPU的现场新选装入CPU各个寄存器。

上下文切换时，需要执行大量load指令和store指令，以保存寄存器的内容，会花费较多时间。
现在已有硬件实现方法来减少上下文切换时间：采用两组寄存器，一组供内核使用，另一组供用户使用。----> 切换上下文只需要改变指针，将其指向当前寄存器组。

调度时机，切换与过程

调度程序是操作系统的 内核程序。正常执行顺序：请求调度事件发生 -----> 运行调度程序----->调度新的就绪程序-----> 进行进程切换
实际上，若在OS中，某时刻发生了引起进程调度的因素，则不一定能马上进行调度与切换。

• 创建新进程后，由于子父进程都处于就绪状态，此时需要决定运行哪一个进程。
• 进程正常结束或异常终止后，必须从就绪队列选择一个进程。如果就绪队列为空，则运行闲逛进程。
• 进程由于I/O请求、信号量操作或其他原因被阻塞，必须调度其他程序运行。
• I/O设备完成后，发出I/O中断，原先等待I/O的进程从阻塞态转变为就绪态，此时需要决定 让新的就绪进程投入运行 还是 让中断发生时运行的进程继续执行。

进程调度方式

即当某个进程正在CPU上执行时，若有优先级更高的进程进入就绪队列，应该如何分配CPU。

• 非抢占调度方式（非剥夺方式）
  • 一个进程正在CPU上运行时候，即使有某个更紧急的进程需要处理，依然让当前进程继续执行，直到运行结束（正常结束或异常终止）或发生某种事件（如等待I/O操作，进程通信或同步中执行Block原语）而进入阻塞态，才将CPU分配给其他进程。
  • 优点：实现简单，开销小，适用于早期的批处理系统。
  • 缺点：不能用于分时操作系统和大多数实时操作系统。
• 抢占调度方式（剥夺方式）
  • 一个进程正在CPU上运行时候，如果有某个更紧急的进程需要处理，运行调度程序暂停当前进程，将CU分配给更紧急的进程。
  • 特点：能够提高系统吞吐率和响应效率。遵循一定的原则"抢占"CPU，如：优先权原则，短进程优先原则，时间片原则等。

闲逛进程

进程切换时，如果系统中没有就绪进程，就会调度 闲逛进程（Idle Process） 运行，它的** PID=0**。如果没有其他就绪进程，该进程一直运行，并在指令周期后测试中断。

• 优先级最低
• 不需要CPU以外的资源，不会被阻塞。

两种线程的调度

三. 调度算法的评价指标

CPU利用率

系统吞吐量

周转时间

等待时间

响应时间

四. 典型调度算法

先来先服务（FCFS）调度算法

是最简单的一种调度算法，可以用于作业调度和进程调度。

• 表面上看，绝对公平，但如果一个长作业优先到达系统，就会使得后面的短作业等待很长时间，因此不能作为分时系统和实时系统的主要调度策略。
• 常被结合在其他调度策略中使用。如：使用优先级调度策略的系统中，对多个具有相同优先级的采用FCFS原则。

• FCFS属于不可剥夺算法。
• 算法简单，效率低；对长作业 有利，对短作业不利（相对于SJF和高响应比）
• 有利于CPU繁忙型作业，不利于I/O繁忙型作业。

短作业优先（SJF）调度算法

• 短作业优先（SJF）：从后备队列中选择一个或多个估计运行时间最短的作业，调入内存开始运行。
• 短进程优先（SPF）：从就绪队列选择一个估计运行时间最短的进程，分配CPU，使之立即执行。

SPF算法可以是抢占式（默认是非抢占式）：新进程的预估执行时间比当前进程剩余时间短，就会暂停当前进程，分配CPU给新进程。因此，抢占式SPF调度算法也称为最短剩余时间优先调度算法。

短作业（SJF）调度算法的平均等待时间、平均周转时间是最优的。

• SJF的缺点：
  • 该算法对长作业不利。SJF调度算法中长作业的周转时间增加，可能导致长作业长期不被调度，产生**”饥饿“现象**。
  • 未完全考虑作业紧迫程度，不保证紧迫作业被及时处理。
  • 由于作业长短是根据用户提供的估计执行时间确定的，不一定能真正做到短作业优先。

高响应比优先调度算法

• 主要用于作业调度，是对FCFS，SJF的综合利用。选出作业响应比最高的投入运行。

• 作业等待时间相同：有利于短作业，类似于SJF。
• 要求服务时间相同：等待时间越长相应比越大，类似于FCFS。
• 对于长作业，作业的响应比可以随着等待时间增加而增大，克服了”饥饿“现象。

优先级调度算法

可以用于作业调度和进程调度。作业的紧迫程度用优先级描述。优先级最高的进程/线程最先被投入运行。

• 非抢占式优先级调度算法：当CPU上存在进程运行时，如果有一个新的进程优先级很高，依然等待当前进程运行完毕后才分配CPU。
• 抢占式优先级调度算法：当CPU上存在进程运行时，如果有一个新的进程优先级很高，将立刻暂停当前进程，分配CPU给新进程。

进程的优先级

• 静态优先级：优先级在创建进程时候确定，整个运行期间保持不变。【确定依据：进程类型，对资源的要求，用户要求】
  • 优点：简单易行，开销小。
  • 缺点：不够精确，可能出现低优先级进程长期得不到调度。
• 动态优先级：创建进程时候先赋予一个优先级，该优先级会随着进程的推进或等待时间增加而改变，以便获得更好的调度性能。

一般而言：

• 系统进程 > 用户进程。
• 交互型进程 > 非交互型进程
• I/O型进程 > 计算型进程

时间片轮转（RR）调度算法

• 主要适用于分时操作系统。
• 就绪进程按照FCFS策略排为就绪队列。
• 间隔一定时间产生一次时钟中断，激活调度程序进行调度。使用 FCFS 策略调度进程。
• 如果当前进程在执行完一个时间片后依然没有运行完成，则产生时钟中断，由时钟中断处理程序激活调度程序。进程中断运行，插入队尾等待下一次的时间片。
• 如果时间片未用完，但是进程已经运行完毕，则立即激活调度程序。

特点：

• 时间片大小影响系统的性能。【时间片大：退化为 FCFS 调度算法；时间片小：CPU频繁切换进程，开销大】
• 时间片确定因素：系统响应时间，就绪队列中的进程数量，系统处理能力。

多级队列调度算法

• 设置多个就绪队列。将不同类型或性质的进程分配到不同的就绪队列。
• 每个队列可以实施不同的调度算法
• 不同队列也可以设置不同的优先级。

多CPU系统中，可以很方便地为每个CPU设置一个单独的就绪队列。这样就可以根据用户需求将多个线程分配到一个或多个CPU运行。

多级反馈队列调度算法（融合前几种算法优点）

综合 时间片轮转调度算法和优先级调度算法，动态调整进程优先级和时间片大小。不必事先估计进程的执行时间。

• 设置多个就绪队列，每个队列设置不同的优先级。
• 赋予各个队列的进程运行时间片大小各不相同。队列优先级越高，进程的时间片越小。
• 每个队列都采用 FCFS 调度算法
• 按队列优先级执行调度：先执行优先级高的队列的进程。【如果当前运行低优先级进程，则立即中断】
• 优点：
  • 终端型作业用户：短作业优先。
  • 短批处理作业用户：周转时间较短。
  • 长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理。

** 总结**