Version: Next
处理机调度
处理机调度的三个层次：
- 高级调度——作业调度
- 中级调度——内存调度
- 低级调度——进程调度
补充
- 进程的
挂起态- 七状态模型
调度的基本概念
- 当有一堆任务要处理，而资源有限，无法同时处理：需要确定
某种规则来决定处理这些任务的顺序，这就是调度研究的问题
处理机调度的概念
- 在多道程序系统中，进程的数量往往是多于处理机的个数的，这样不可能同时并行地处理各个进程
处理机调度：从就绪队列中 按照一定的算法选择一个进程，并 将处理机分配给它 运行，以实现进程的并发执行
进程的七状态模型
高级调度——作业调度
按照一定原则，从外存上处于后背队列的作业中挑选出一个或多个作业，给他们分配内存等必要资源，并建立相应的进程（建立 PCB），使他们 获得竞争处理机的权利
- 高级调度是外存与内存之间的调度，每个作业只调入一次，调出一次
- 作业调入时会建立相应的 PCB，作业调出时才撤销 PCB
- 高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，调出时机必然是作业运行结束之后
中级调度——内存调度
引入虚拟存储技术后，可以将暂时不能运行的进程调到外存等待，等它们重新具备了运行条件且内存有有所空闲时，再重新调入内存。这样做的目的是为了 提高内存利用率 和 系统吞吐量
进程挂起态
- 暂时调到外存等待的进程状态为
挂起态 PCB并不会一起调到外存，而是会常驻在内存中- PCB 中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的 PCB 来保持对各个进程的监控、管理
- 被挂起的进程 PCB 会被存放到
挂起队列中 - 中级调度（内存调度），就是要决定将哪个处于挂起态的进程重新调入内存
- 一个进程可能被多次调出、多次调入内存，因此中级调度发生的频率要比高级调度更高
低级调度——进程调度
- 主要任务是按照某种方法、策略从就绪队列中选取一个进程，将处理机分配给它
- 进程调度是操作系统中 最基本的一种调度，在一般的操作系统中都必须配置进程调度
- 进程调度的频率很高，一般几十毫秒一次
| 要做什么 | 调度发生时刻 | 发生频率 | 对进程状态的影响 | |
|---|---|---|---|---|
| 高级调度 作业调度 | 按照某种规则，从后备队列中选择 合适的作业将其调入内存，并为其创建进程 | 外存→内存 面向作业 | 最低 | 无→创建态→就绪态 |
| 中级调度 内存调度 | 按照某种规则，从挂起队列中选择 合适的进程将其数据调回内存 | 外存→内存 面向进程 | 中等 | 挂起态→就绪态 阻塞挂起→阻塞态 |
| 低级调度 进程调度 | 按照某种规则，从就绪队列中选择 一个进程将其分配给处理机 | 内存→CPU | 最高 | 就绪态→运行态 |
进程调度时机
进程调度（低级调度）：按照一定的算法从就绪队列中选择一个进程为其分配处理机
需要进行 进程调度与切换的情况
- 当前运行的进程
主动放弃处理机
- 进程正常终止
- 进程运行过程中发生异常终止
- 进程主动请求阻塞（如等待 IO）
- 当前运行的进程
被动放弃处理机
- 分给进程的时间片用完
- 有更紧急的事需要处理（如 IO 中断）
- 有更高优先级的进程进入就绪队列
不能进行 进程调度与切换的情况
- 在 处理中断的过程中：中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换
- 进程在 操作系统内核程序临界区 中
- 在 原子操作过程中（原语）
临界资源与临界区
- 正确表述：进程在操作系统
内核程序临界区中不能进行调度和切换 错误表述：进程处于临界区时不能进行处理机调度
- 临界资源：一个时间段内只允许一个进程使用的资源，各进程需要
互斥地访问临界资源- 临界区：访问临街资源的那段代码
- 内核程序临界区：一般用来访问 某种内核数据结构。比如进程的就绪队列（由就绪进程的 PCB 组成）
进程切换
狭义调度与切换的区别
- 狭义的进程调度：指从就绪队列中 选中一个要运行的过程，这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就要进行
进程切换- 进程切换：指一个进程让出处理机，由另一个进程占用处理机的过程
- 广义进程调度：包含了
选择一个进程和进程切换两个步骤
进程切换的过程
进程切换的过程主要完成了：
- 对原来运行进程各种数据的保存
- 对新的进程各种数据的恢复
进程的切换是由代价的，因此如果过于频繁的进行进程调度、切换，必然会降低整个系统的效率
进程切换的方式
非剥夺调度方式（非抢占式）
- 只允许进程主动放弃处理机
- 在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态
剥夺调度方式（抢占式）
- 当一个进程正在处理机上运行时，如果有一个更重要或更紧急的进程需要使用处理机，则立刻展厅正在执行的过程，将处理机分配给更重要、更紧迫的那个进程
调度算法的评价指标
CPU 利用率：
利用率=忙碌时间/总时间系统吞吐量：单位时间内完成作业的数量
吞吐量=总完成作业数/总时间周转时间：作业被提交给操作系统开始，到作业完成为止的这段时间间隔
包括四个部分：1. 作业在外存后备队列上等待作业调度（高级调度）的时间。 2. 进程在就绪队列上等待进程调度（低级调度）的时间。 3. 进程在 CPU 上执行的时间。 4. 进程等待 I/O 操作完成的时间。 后三项在一个作业的整个处理过程中，可能多次发生
周转时间=作业完成时间-作业提交时间
平均周转时间=各作业周转时间和/作业数
带权周转时间= (作业完成时间-作业提交时间) /作业实际运行时间平均带权周转时间
等待时间：指 进程 / 作业 处于 等待处理机状态时间之和，等待时间越长，用户满意度越低
响应时间：从用户提交请求到首次产生响应经过的时间
调度算法
先来先服务 FCFS
算法思想
- 主要从公平的角度考虑
算法规则
- 按照作业/进程到达的先后顺序进行服务
应用场合
- 用于作业调度时：考虑的是哪个作业先到达后备队列
- 用于进程调度时：考虑的是哪个线程先到达就绪队列
是否可抢占
- 非抢占式算法
优缺点
- 优点：公平、算法实现简单
- 缺点：排在长时间（进程）后面的短作业需要等待很长时间，带劝周转时间很大，对短作业来说用户体验不好。即 对长作业有利，对短作业不利
是否会导致饥饿
饥饿：某进程/作业长期得不到服务- 不会导致饥饿
短作业优先 SJF
算法思想
- 追求最少的平均等待时间，最少的平均周转时间、最少的平均带权周转时间
算法规则
- 最短的作业/进程优先得到服务，最短是指要求服务时间最短
应用场合
- 用于作业调度，也可用于进程调度
- 用于进程调度时，称为
短进程优先SPF 算法
是否可抢占
- 默认为非抢占式
- 存在抢占式版本——最短剩余时间优先算法 SRTN Shortest Remaining Time Next
优缺点
- 优点：“最短的”平均等待时间、平均周转时间
- 缺点：不公平。对短作业有利，对长作业不利
是否会导致饥饿
- 可能会
高响应比优先 HRRN
算法思想
- 综合考虑作业/进程的等待时间和要求服务时间
算法规则
- 在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
响应比= (等待时间+要求服务时间) /要求服务时间
应用场合
- 用于作业调度，也可用于进程调度
是否可抢占
- 非抢占式
优缺点
- 综合考虑了等待时间和要求服务时间
- 等待时间相同时，要求服务时间短的优先，SJF 的优点
- 要求服务时间相同时，等待时间长的优先，FCFS 的优点
- 对于长作业来说，随着等待时间越来越大，其响应比也来越大，从而避免了长作业饥饿问题
是否会导致饥饿
- 不会
| 算法 | 思想/规则 | 是否抢占 | 优点 | 缺点 | 考虑等待时间/运行时间 | 导致饥饿 |
|---|---|---|---|---|---|---|
| FCFS | 主要从公平的角度考虑 按照作业/进程到达的先后顺序进行服务 | 非抢占式 | 公平，实现简单 | 对短作业不利 | 等待时间 √ 运行时间 × | 不会 |
| SJF/SPF | 追求最少的平均等待时间，最少的平均周转时间、最少的平均带权周转时间 最短的作业/进程优先得到服务，最短是指要求服务时间最短 | 默认为非抢占 抢占式版本为最短剩余时间优先算法 SRTN | “最短的”平均等待时间/周转时间 | 堆场作业不利，可能导致饥饿。难以做到真正恶短作业优先 | 等待时间 × 运行时间 √ | 会 |
| HRRN | 综合考虑作业/进程的等待时间和要求服务时间 在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务 | 非抢占式 | 上述两种算法的权衡这种，综合考虑等待时间和运行时间 | 等待时间 √ 运行时间 √ | 不会 |
注意
这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但不关心响应时间，也不区分任务的紧急程度，因此对用户来说，交互性很糟糕
- 这三种算法一般适用于早期的批处理系统
- 接下来介绍适用于交互式系统的调度算法
时间片轮转调度算法 Round-Robin
算法思想
- 公平的、轮流的为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
算法规则
- 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个
时间片- 若进程未在一个时间片内执行完毕，则剥夺处理机，将进程重新放到就绪队列尾部重新排队
应用场合
- 用于进程调度（只有作业放入了内存建立了响应进程后，才能被分配处理机时间片）
是否可抢占
- 抢占式
- 由时钟装置发出
时钟中断来通知 CPU 时间片已到
优缺点
- 优点：公平、响应快，适用于分时操作系统
- 缺点：频繁的进程切换，增加系统开销；不区分任务的紧急程度
是否会导致饥饿
- 不会
优先级调度算法
算法思想
- 随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
算法规则
- 每个作业/进程都有各自的优先级，调度时选择优先级最高的作业/进程
应用场合
- 作业调度、进程调度
- 也可用于 IO 调度
是否可抢占
- 抢占式、非抢占式都有
优缺点
- 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统；可灵活的调整对各作业、进程的偏好程度
- 缺点：若源源不断的有高优先级进程到来，则可能导致解
是否会导致饥饿
- 可能会
多级反馈队列调度算法
算法思想
- 对其他调度算法的折中权衡
算法规则
- 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
- 新进程到达先进入第 1 级队列，按 FCFS 原则排队等待被分配时间片，若用完时间片进程还未结束，则 进程进入下一级队列队尾；如果此时就是最下级的队列，则重新放回该队列队尾
- 只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片
应用场合
- 用于进程调度
是否可抢占
- 抢占式
- 在 k 即队列进程运行过程中，若更上级的队列 (1 ~ k-1 级)中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回 k 级队列队尾
优缺点
- 优点：
- 对各类型进程相对公平（FCFS 的优点）
- 每个新到达的进程都可以很快得到响应 （Round-Robin 优点）
- 短进程只用较少的时间就可以完成（SPF 的优点）
- 不必实现估计进程的运行时间（避免用户作假）
- 可灵活调整对各种进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程
是否会导致饥饿
- 可能会
| 算法 | 思想/规则 | 是否抢占 | 优点 | 缺点 | 导致饥饿 |
|---|---|---|---|---|---|
| 时间片轮转 | 公平的、轮流的为各个进程服务，让 每个进程在一定时间间隔内都可以得 到响应。按照各进程到达就绪队列的 顺序，轮流让各个进程执行一个 时间片若进程未在一个时间片内执行完毕，则剥夺处 理机，将进程重新放到就绪队列尾部重新排队 | 抢占式 | 公平、适用于分时系统 | 频繁切换进程带来系统开销 | 不会 |
| 优先级调度 | 每个作业/进程都有各自的优先级，调 度时选择优先级最高的作业/进程 | 都有 | 区分优先级、适用于实时系统 | 可能导致饥饿 | 会 |
| 多级反馈队列 | 设置多级就绪队列，各级队列优先级从 高到低，时间片从小到大。新进程到达 先进入第 1 级队列，按 FCFS 原则排 队等待被分配时间片，若用完时间片进程 还未结束，则 进程进入下一级队列 队尾；如果此时就是最下级的队列，则重新 放回该队列队尾。只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片 | 抢占式 | 牛逼 | 可能导致饥饿 | 会 |