调度算法

调度算法的评价指标

CPU利用率

CPU利用率：指 CPU 忙碌的时间占总时间的比例。

题目：某计算机只支持单道程序，某个作业刚开始需要在 CPU 上运行 5 秒，再用打印机打印输出 5 秒，之后再执行 5 秒，才能结束。在此过程中，CPU 利用率、打印机利用率分别是多少呢？

CPU 利用率 = (5 + 5) / (5 + 5 + 5) = 66.66%

打印机利用率 = 5 / 15 = 33.33%

通常会考察多道程序并发执行的情况，可以用“甘特图”来辅助计算。

系统吞吐量

系统吞吐量：单位时间内完成作业的数量

题目：某计算机系统处理完 10 道作业，共花费 100 秒，则系统吞吐量为？

系统吞吐量 = 10 / 100 = 0.1道/秒

周转时间

周转时间：指从作业被提交给系统开始，到作业完成为止的这段时间间隔。

包括四个部分：

• 作业在外存后备队列上等待作业调度（高级调度）的时间
• 进程在就绪队列上等 待进程调度（低级调度）的时间
• 进程在CPU上执行的时间
• 进程等待I/O操作完成的时间

后三项在一个作业的整个处理过程中，可能发生多次。

注意：

• 带权周转时间和周转时间都是越小越好

等待时间

计算机的用户希望 自己的作业尽可能少的等待处理机（CPU）。

等待时间：指进程 / 作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低

• 对于 进程 来说，等待时间就是指进程建立后 等待被服务的时间之和，在等待 I/O 完成的期间其实进程也是在被服务的，所以不计入等待时间
• 对于 作业 来说，不仅要考虑 建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间

一个作业总共需要被 CPU 服务多久，被 I/O 设备服务多久一般是确定不变的，因此调度算法其实只会影响作业/进程的等待时间。当然，与前面指标类似，也有“平均等待时间”来评价整体性能

响应时间

对于计算机用户来说，会希望自己的提交的请求（比如通过键盘输入了一个调试命令）尽早地开始被系统服务、回应
响应时间：指从用户提交请求到首次产生响应所用的时间

调度算法

学习思路：

1. 算法思想
2. 算法规则
3. 这种调度算法是用于作业调度还是进程调度
4. 抢占式还是非抢占式？
5. 优点和缺点
6. 是否会导致饥饿（某进程/作业长期得不到服务）

先来先服务法 FCFS

例子：

本例中的进程都是纯计算型的进程，一个进程到达后要么在等待，要么在运行。如果是又有计算、又有 I/O 操作的进程，其等待时间就是 周转时间 - 运行时间 - I/O 操作的时间。

短作业优先法 SJF

说明：

1. 如果未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的
2. 很多书上都会说“SJF 调度算法的平均等待时间、平均周转时间最少”
   • 严格来说，这个表述是错误的，不严谨的。之前的例子表明，最短剩余时间优先算法得到的平均等待时间、平均周转时间还要更少
   • 应该加上一个条件“在所有进程同时可运行 时，采用 SJF 调度算法的平均等待时间、平均周转时间最少”
   • 或者说“在 所有进程都几乎同时到达 时，采用SJF调度算法的平均等待时间、平均周转时间最少”
   • 如果不加上述前提条件，则应该说“抢占式的短作业/进程优先调度算法（最短剩余时间优先, SRNT算法）的平均等待时间、平均周转时间最少”
3. 虽然严格来说，SJF的平均等待时间、平均周转时间并不一定最少，但相比于其他算法（如FCFS）， SJF依然可以获得较少的平均等待时间、平均周转时间
4. 如果选择题中遇到“SJF 算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项

SJF（Short Job First）

短作业/进程优先调度算法：每次调度时选择 当前已到达 且 运行时间最短 的作业/进程

SRTN

最短剩余时间优先算法：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程 剩余时间 比当前运行的进程剩余时间 更短，则由新进程 抢占 处理机，当前运行进程重新回到就绪队列。另外，当 一个进程完成时也需要调度。

高响应比优先法 HRRN

高响应比优先算法：非抢占式的调度算法，只有当前运行的进程 主动放弃CPU时（正常/异常完成，或主动阻塞），才需要进行调度，调度时 计算所有就绪进程的响应比，选响应比最高的 进程上处理机。

时间片轮转法 RR

如果 时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法 退化为先来先服务 调度算法，并且会增大进程响应时间。因此时间片不能太大。

另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境），因此如果 时间片太小，会导致 进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见 时间片也不能太小。

优先级调度算法

重点：

根据优先级是否可以动态改变，可将优先级分为 静态优先级 和 动态优先级 两种

• 静态优先级：创建进程时确定，之后一直不变
• 动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级

如何合理设置各类进程的优先级？

• 系统进程优先级 高于 用户进程
• 前台进程优先级 高于 后台进程
• 操作系统更 偏好 I/O 型进程（I/O 繁忙型进程）
  • I/O设备和CPU可以并行工作。如果优先让I/O繁忙型进程优先运行的话，则越有可能让I/O设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升

如果采用的是动态优先级，什么时候应该调整？

• 可以从追求公平、提升资源利用率等角度考虑
• 如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级
• 如果某进程占用处理机运行了很长时间，则可适当降低其优先级
• 如果发现一个进程频繁地进行I/O操作，则可适当提升其优先级

非抢占式

抢占式

多级反馈队列法

知识回顾