• 吞吐量：每单位时间完成的进程数目 * 周转时间：每个进程提出请求到运行完成的时间
• 响应时间：从提出请求到第一次回应的时间
• 其他
  • cpu 利用率： cpu 做有效工作的时间比例
  • 等待时间：每个进程在就绪队列中等待的时间 #

二、设计调度算法前的要点

• 进程控制块中需要记录哪些与 cpu 调度有关的信息
• 进程优先级就绪队列的组织
• 抢占式调度与非抢占式调度
• I/O 密集型与 cpu 密集型进程
• 时间片

2.1 进程优先级（数）

优先级和优先数是不同的，优先级表现了进程的重要性和紧迫性，优先数实际上是一个数值，反映了某个优先级。

• 静态优先级 进程创建时指定，运行过程中不再改变
• 动态优先级 进程创建时指定了一个优先级，运行过程中可以动态变化。如：等待时间较长的进程可提升其优先级。

2.2 进程就绪队列组织

• 按优先级排队方式

说明： 创建多个进程后按照不同的优先级进行排列， cpu 调度优先级较高的进程进行执行。

• 另一种排队方式

说明： 所有进程创建之后都进入到第一级就绪队列，随着进程的运行，可能会降低某些进程的优先级，如某些进程的时间片用完了，那么就会将其降级。

2.3 占用cpu的方式 通常有两种方式，即抢占式和非抢占式。

• 抢占式（可剥夺式） 当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的 cpu ，提供给具有更高优先级的进程使用。
• 不可抢占式 某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去。

2.4 I/O密集型与cpu密集型进程 按进程执行过程中的行为划分：

• I/O 密集型或 I/O 型（ I/O-bound ） 频繁的进程 I/O ，通常会花费很多时间等待 I/O 操作的完成。
• cpu 密集型或 cpu 型或计算密集型（ cpu-bound ） 需要大量的 cpu 时间进行计算

2.5 时间片（Time slice或quantum）

一个时间段，分配给调度上 cpu 的进程，确定了允许该进程运行的时间长度。那么如何选择时间片？有一下需要考虑的因素：

• 进程切换的开销
• 对响应时间的要求
• 就绪进程个数
• cpu 能力
• 进程的行为

三、批处理系统中常用的调度算法

引起低级调度的原因 有四种情况都会发生CPU调度 当一个进程从运行态切换成等待态时 当一个进程从运行态切换成就绪态时 当一个进程从等待态切换成就绪态时 当一个进程中止时。也就是说当一个进程由运行状态变为非运行状态 或者一个进程变为就绪状态时都会引起低级调度 .

• 先来先服务（ FCFS-First Come First Serve ） (作业调度,进程调度)
• 最短作业优先（ SJF-Shortest Job First ） (作业调度,进程调度)
• 最短剩余时间优先（ FRTN-Shortest Remaining Time Next ）
• 最高响应比优先（ HRRN-Highest Response Ratio Next ） 在批处理系统中调度算法主要考虑的是吞吐量、周转时间、 cpu 、公平/平衡。

3.1 先来先服务算法

• 按照进程就绪的先后顺序使用 cpu
• 非抢占式
  • 优点
    • 公平
    • 实现简单
  • 缺点 长进程后面的短进程需要等很长时间，不利于用户体验
    • 最短的平均周转时间 在所有进程同时可运行时，采用 SJF 调度算法可以得到最短的平均周转时间
    • 不公平 源源不断的短任务到来，可能使长的任务长时间得不到运行，导致产生“饥饿”现象

    3.3 最高响应比优先 (重点)

    • 一个综合的算法 调度时，首先计算每个进程的响应比 R 之后，总是选择 R 最高的进程执行。
    • 响应比 = 周转时间/处理时间 = （处理时间+等待时间）/处理时间 = 1+（等待时间/处理时间）

    四、交互式系统的调度算法

    • 轮转调度（ RR-Round Robin ）
    • 最高优先级调度（ HPF-Highest Priority First ）
    • 多级反馈队列（ Multiple feedback queue ）
    • 最短进程优先（ Shortest Process Next ） ## 4.1 时间片轮转调度算法 说明： 按照之前的时间片算法，对于 I/O 型进程时是不公平的，因为它总是用不完时间片，但是调度之后都要重新进入就绪队列进行排队，这样显然不公平。于是就设计了上图的调度算法。为 I/O 型进程专门设计了一个辅助队列，当一个 I/O 进程运行完之后不进入就绪队列，而是进入辅助队列，同时 cpu 也优先去调度辅助队列中的进程，知道辅助队列中为空，才去就绪队列中选择进程。 ## 4.2 最高优先级调度算法 * 选择优先级最高的进程投入运行 * 通常：系统进程优先级高于用户进程；前台进程优先级高于后台进程；操作系统更偏好 I/O 型进程。 * 优先级可以是静态的，也可以动态调整，优先数可以决定优先级 * 就绪队列可以按照优先级组织 * 实现简单，但是不公平 优先级反转问题： 主要出现在基于优先级的抢占式调度算法中。表现为，一个低优先级进程持有一个高优先级进程所需要的资源，使得高优先级进程等待低优先级进程运行。例如：

      

      • 影响 是一个系统错误；高优先级进程停滞不前，导致系统性能降低。 * 解决方案 设置优先级上限：凡是进入临界区的进程的优先级都是最高的 优先级继承：低优先级继承高优先级进程的优先级 使用中断禁止：凡是进入临界区的进程都不再响应中断，直到出了临界区

      五、多级反馈队列调度算法(重点)

      • UNIX 的一个分支 BSD5.3 版所采用的调度算法
      • 一个综合调度算法（折中权衡）
      • 设置多个就绪队列，第一级队列优先级最高
      • 给不同就绪队列的进程分配长度不同的时间片，第一级队列时间片最小；随着队列优先级别的降低，时间片增大。
      • 当第一级队列为空时，就在第二级队列调度，以此类推
      • 各级队列按照时间片轮转方式进行调度
      • 当一个新创建进程就绪后，进入第一级队列
      • 进程用完时间片而放弃 cpu ，进入下一级就绪队列
      • 由于阻塞而放弃 cpu 的进程进入相应的等待队列，一旦等待的事件发生，该进程回到原来一级就绪队列

      以上所说都是属于非抢占式的，如果允许抢占，则当有一个优先级更高的进程就绪时，可以抢占 cpu ，被抢占的进程回到原来一级就绪队列的末尾。

      

      说明： 当一个进程总是用完时间片，那么其就会一直降级，这样我们就可以知道这是一个 cpu 型进程，于是就区分出了 cpu 型和 I/O 型进程，同时可以知道这种调度算法偏好 I/O 型进程。当然也做了一些弥补，即优先级低的进程时间片较大。

      

      各种调度算法的比较

      七、多处理器调度算法设计

      • 不仅要决定选择哪一个进程执行，还需要决定在哪一个 cpu 上执行
      • 要考虑进程在多个 cpu之 间迁移时的开销 1、高速缓存失效、 TLB 失效 2、尽可能使进程总是在同一个 cpu 上执行
        • 如果每个进程可以调度到所有 cpu 上，假如进程上次在 cpu1 上执行，本次被调度到 cpu2 ，则会增加高速缓存失效、 TLB 失效；如果每个进程尽量调度到指定的 cpu 上，各种失效就会减少。
      • 考虑 负载均衡 问题

      7.1 典型系统所采用的调度算法

      • UNIX： 动态优先数法
      • BSD5.3：多级反馈队列法
      • Linux：抢占式调度
      • Windows：基于优先级的抢占式多任务调度
      • Solaris：综合调度算法

      7.2 Windows线程调度

      • 调度单位是线程
      • 采用基于动态优先级的、抢占式调度，结合时间配额的调整

      基本思想：

      • 就绪线程按优先级进入相应的队列
      • 系统总是选择优先级最高的就绪线程运行
      • 同一优先级的各线程按时间片轮转进行调度
      • 多 cpu 系统中允许多个线程并行运行

      引发线程调度的条件： 之前我们提到了四个条件：

      • 线程正常终止或由于某种错误而终止
      • 新线程创建或一个等待的线程变成就绪
      • 当一个线程从运行态进入阻塞态
      • 当一个线程从运行态变为就绪态

      这里还有两个条件：

      • 一个线程的优先级改变
      • 一个线程改变了它的亲和（ Affinity ）处理机集合（比如允许一个线程在多个处理机上执行，但是如果其他的处理机空闲，则此线程也不能在其上进行执行）

      Windows线程优先级：

      • 分成了三类： <div class="image-package"> <div class="image-caption">3</div>

      线程的时间配额：

      • 时间配额不是一个时间长度值，而一个称为配额单位的整数
      • 一个线程用完了自己的时间配额时，如果没有其他相同优先级的线程， Windows 将重新给该线程分配一个新的时间配额，让它继续执行。实质就是不会一定让一个线程一直运行直到其结束，首先给其分配一个时间配额，运行完之后再次检查，如果没有运行完则再次分配时间配额，让其运行，这个过程不是连续的，是有间断的。

      时间配额的一种特殊作用：

      • 假设用户首先启动了一个运行时间很长的电子表格计算程序，然后切换到一个游戏程序（需要复杂图形计算并显示，是 CPU 型）
      • 如果前台的游戏进程提高它的优先级，则后台的电子表格计算进程就几乎得不到 CPU 时间了
      • 但增加游戏进程的时间配额，则不会停止执行电子表格计算，只是给游戏进程的 CPU 时间多一些而已。

      调度策略：

      • 主动切换 某个线程可能在运行过程中需要输入输出，此时进入阻塞态，此时 cpu 会选择新的线程进行执行。
      • 抢占 如果上面所说的阻塞线程被唤醒，同时其优先级又更高，那么就会去抢占执行。当线程被抢占时，它被放回相应优先级的就绪队列的队首
        • 处于实时优先级的线程在被抢占时，时间配额被重置为一个完整的时间配额
        • 处于可变优先级的线程在被抢占时，时间配额不变，重新得到 cpu 后将运行剩余的时间配额 这里的实时优先级和可变优先级有什么区别？？？？难道实时优先级就是按创建顺序产生的优先级，而可变优先级就是优先级可变的？
      • 时间配额用完 假设线程 A 的时间配额用完
        • A 的优先级没有降低 1、如果队列中有其他就绪线程，选择下一个线程执行， A 回到原来的就绪队列末尾 2、如果队列中没有其他就绪线程，系统会给A重新分配时间配额，让其继续执行
        • A 的优先级降低，此时 Windows 将选择一个更高优先级的线程执行

      线程优先级提升与时间配额调整： 为什么一个线程的时间配额用完后其优先级会被降低，这是因为之前此线程的优先级被提升过。

      • Windows 的调度策略
        • 如果体现对某类线程具有倾向性？
        • 如何解决由于调度策略中潜在的不公平性而带来的饥饿现象？
        • 如何改善系统吞吐量、响应时间等整体特征？
      • 解决方案
        • 提升线程的优先级 下列五种情况， Windows 会提升线程的当前优先级： 1、 I/O 操作完成