表2.4总结了几种常见进程调度算法的特点，读者要在理解的基础上掌握。
<!-- page: 87 -->
表 2.4 几种常见进程高度算法的特点
[tbl-5.md](tbl-5.md)
## 2.2.6 多处理机调度
多处理机系统的调度较单处理机系统复杂，它与系统结构有关。
非对称多处理机（Asymmetric MultiProcessing，AMP）大多采用主从式操作系统，内核驻留在主机上，而从机上只运行用户程序，进程调度由主机负责。当从机空闲时，便向主机发送一个索求进程的信号，在主机中有一个就绪队列，只要队列不为空，主机便从队首摘下一个进程分配给索求进程的从机。这种分配方式实现简单，缺点是主机太忙，容易成为系统瓶颈。
对称多处理机（Symmetric MultiProcessing，SMP）的所有处理机都是相同的，因此由调度程序将任何一个进程分配给任何一个CPU。本节主要讨论SMP系统的调度问题。
### 1. 亲和性和负载平衡
当一个进程从一个CPU移到其他CPU上时，应将第一个CPU的缓存设置为无效，然后重新填充第二个CPU的缓存，这种操作的代价较高，因此系统应尽量避免将进程从一个CPU移到另一个CPU，而应试图让一个进程运行在同一个CPU上，这称为处理器亲和性。
对于SMP系统，应尽量保证所有CPU的负载平衡（也称负载均衡），以便充分利用多处理机的优点，否则，一个或多个CPU会空闲，而其他CPU会处于高负载状态，且有一些进程处于等待状态。负载平衡应设法将负载平均分配到SMP系统的所有CPU上。
然而，负载平衡通常会抵消处理器亲和性带来的好处，保持一个进程运行在同一个CPU上的好处是可以利用它在该CPU的缓存。而将进程从一个CPU迁移到另一个CPU会失去这个好处。因此，在某些系统中，只有当不平衡达到一定程度后才移动进程。
### 2. 多处理机调度方案
#### 方案一：公共就绪队列
系统中仅设置一个公共就绪队列，所有CPU共享同一个就绪队列。这种方案很好地实现了负载平衡，因为CPU一旦空闲，它就立刻从公共就绪队列中选择一个进程运行。缺点是各进程可能频繁地在不同的CPU上运行，处理器亲和性不好。
提升处理器亲和性的方法有两种：软亲和和硬亲和。软亲和是指由调度程序尽量保持一个进程到某个CPU上，但这个进程也可以迁移到其他CPU上。硬亲和是指由用户进程通过系统调用，主动请求系统分配到固定的CPU上。例如，Linux系统实现了软亲和，也支持硬亲和的系统调用。
#### 方案二：私有就绪队列
系统为每个CPU设置一个私有就绪队列，当CPU空闲时，就从各自的私有就绪队列中选择一个进程运行。这种方案很好地实现了处理器亲和性，缺点是必须进行负载平衡。
平衡负载的方法通常有两种：推迁移和拉迁移。对于推迁移，一个特定的系统程序周期性检查每个CPU的负载，若发现不平衡，则从超载CPU的就绪队列中“推”一些进程到空闲CPU的
<!-- page: 88 -->
77
就绪队列，从而平均分配负载。若一个CPU负载很低，则从超载CPU的就绪队列中“拉”一些进程到自己的就绪队列，发生拉迁移。在系统中，推迁移和拉迁移常被并行实现。
## 2.2.7 本节小结
本节开头提出的问题的参考答案如下。
1）为什么要进行CPU调度？
若没有 CPU 调度，则意味着要等到当前运行的进程执行完毕后，下一个进程才能执行，而实际情况中，进程时常需要等待一些外部设备的输入，而外部设备的速度与 CPU 相比是非常缓慢的，若让 CPU 总是等待外部设备，则对 CPU 的资源是极大的浪费。而引进 CPU 调度后，可在运行进程等待外部设备时，将 CPU 调度给其他进程，从而提高 CPU 的利用率。用一句简单的话说，就是为了合理地处理计算机的软/硬件资源。
2）调度算法有哪几种？结合第1章学习的分时操作系统和实时操作系统，思考有没有哪种调度算法比较适合这两种操作系统。
本节介绍的调度算法有先来先服务调度、短作业优先调度、优先级调度、高响应比优先调度、时间片轮转调度、多级队列调度、多级反馈队列调度7种。
先来先服务算法和短作业优先算法无法保证及时地接收和处理问题，因此无法保证在规定的时间间隔内响应每个用户的需求，也同样无法达到实时操作系统的及时性需求。优先级调度算法按照任务的优先级进行调度，对于更紧急的任务给予更高的优先级，适合实时操作系统。
高响应比优先调度算法、时间片轮转调度算法、多级反馈队列调度算法都能保证每个任务在一定时间内分配到时间片，并轮流占用CPU，适合分时操作系统。
本节主要介绍了CPU调度的概念。操作系统主要管理CPU、内存、文件、设备几种资源，只要对资源的请求大于资源本身的数量，就会涉及调度。例如，在单处理器系统中，CPU只有一个，而请求的进程却有多个，因此就需要CPU调度。出现调度的概念后，又有了一个问题，即如何调度、应该满足谁、应该让谁等待，这是调度算法所面对的问题；而应该满足谁、应该让谁等待，要遵循一定的准则。调度这一概念贯穿于操作系统的始终，读者在接下来的学习中，将接触到几种资源的调度问题。将它们与CPU调度的内容相对比，将发现有异曲同工之妙。
## 2.2.8 本节习题精选
### 一、单项选择题
01. 中级调度的目的是（ ）。
A. 提高 CPU 的效率
B. 降低系统开销
C. 提高 CPU 的利用率
D. 节省内存
02. 进程从创建态转换到就绪态的工作由（ ）完成。
A. 进程调度
B. 中级调度
C. 高级调度
D. 低级调度
03. 下列哪些指标是调度算法设计时应该考虑的？（ ）
I. 公平性
II. 资源利用率
III. 互斥性
IV. 平均周转时间
A. I、II
B. I、II、IV
C. I、III、IV
D. 全部都是
04. 时间片轮转调度算法是为了（ ）。
A. 多个用户能及时干预系统
B. 使系统变得高效
C. 优先级较高的进程得到及时响应
D. 需要 CPU 时间最少的进程最先做
05. 在单处理器系统中，进程什么时候占用处理器及占用时间的长短是由（ ）决定的。
<!-- page: 89 -->
A. 进程相应的代码长度
B. 进程总共需要运行的时间
C. 进程特点和进程调度策略
D. 进程完成什么功能
06. 在菜单处理器系统中，若此刻有多个就绪态进程，则下列叙述中错误的是（ ）。
A. 进程调度的目标是让进程轮流使用处理器
B. 当一个进程运行结束后，会调度下一个就绪进程运行
C. 上下文切换是进程调度的实现手段
D. 处于临界区的进程在退出临界区前，无法被调度
07. 下列内容中，不属于进程上下文的是（ ）。
A. 进程现场信息
B. 进程控制信息
C. 中断向量
D. 用户堆栈
08. 下列关于进程上下文切换的叙述中，错误的是（ ）。
A. 进程上下文指进程的代码、数据以及支持进程执行的所有运行环境
B. 进程上下文切换机制实现了不同进程在一个处理器中交替运行的功能
C. 进程上下文切换过程中必须保存换下进程在切换处的程序计数器的值
D. 进程上下文切换过程中必须将换下进程的代码和数据从主存保存到磁盘
09. 在支持页式存储管理和多线程技术的系统中，当一个进程中的线程 $\mathrm{T}_{1}$ 切换到同一个进程中的线程 $\mathrm{T}_{2}$ 执行时，操作系统需要执行的操作是（ ）。
I. 更新程序计数器的值
II. 更新残基址寄存器的值
III. 更新页基址寄存器的值
IV. 更新进程打开文件表
A. I、II、III、IV
B. II、IV
C. I、II
D. I、III、IV
10. （）有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业。
A. 时间片轮转调度算法
B. 先来先服务调度算法
C. 短作业（进程）优先算法
D. 优先权调度算法
11. 下面有关选择进程调度算法的准则中，不正确的是（ ）。
A. 尽快响应交互式用户的请求
B. 尽量提高处理器利用率
C. 尽可能提高系统吞吐量
D. 适当增长进程就绪队列的等待时间
12. 实时系统的进程调度，通常采用（ ）算法。
A. 先来先服务
B. 时间片轮转
C. 抢占式的优先级高者优先
D. 高响应比优先
13. 支持多道程序设计的操作系统在运行过程中，不断地选择新进程运行来实现 CPU 的共享，但其中（ ）不是引起操作系统选择新进程的直接原因。
A. 运行进程的时间片用完
B. 运行进程出错
C. 运行进程要等待某一事件发生
D. 有新进程被创建进入就绪态
14. 进程（线程）调度的时机有（ ）。
I. 运行的进程（线程）运行完毕
II. 运行的进程（线程）所需资源未准备好
III. 运行的进程（线程）的时间片用完
IV. 运行的进程（线程）自我阻塞
V. 运行的进程（线程）出现错误
A. II、III、IV和V
B. I和III
C. II、IV和V
D. 全部都是
15. 设有4个作业同时到达，每个作业的执行时间均为 $2\mathrm{h}$，它们在一台处理器上按单道式运行，则平均周转时间为（ ）。
A. 1h
B. 5h
C. 2.5h
D. 8h
16. 若每个作业只能建立一个进程，为了照顾短作业用户，应采用（ ）；为了照顾紧急作
<!-- page: 90 -->
79
业用户，应采用（）；为了能实现人机交互，应采用（）；而能使短作业、长作业和交互作业用户都满意，应采用（）。
A. FCFS调度算法
B. 短作业优先调度算法
C. 时间片轮转调度算法
D. 多级反馈队列调度算法
E. 刹夺式优先级调度算法
17. （）优先级是在创建进程时确定的，确定之后在整个运行期间不再改变。
A. 先来先服务
B. 动态
C. 短作业
D. 静态
18. 现在有三个同时到达的作业 $J_1, J_2$ 和 $J_3$，它们的执行时间分别是 $T_1, T_2, T_3$，且 $T_1 < T_2 < T_3$。系统按单道方式运行且采用短作业优先调度算法，则平均周转时间是（）。
A. $T_{1} + T_{2} + T_{3}$
B. $(3T_{1} + 2T_{2} + T_{3}) / 3$
C. $(T_{1} + T_{2} + T_{3}) / 3$
D. $(T_{1} + 2T_{2} + 3T_{3}) / 3$
19. 设有三个作业，其运行时间分别是 $2\mathrm{h}, 5\mathrm{h}, 3\mathrm{h}$，假定它们同时到达，并在同一台处理器上以单道方式运行，则平均周转时间最小的执行顺序是（）。
A. $J_{1}, J_{2}, J_{3}$
B. $J_{3}, J_{2}, J_{1}$
C. $J_{2}, J_{1}, J_{3}$
D. $J_{1}, J_{3}, J_{2}$
20. 采用时间片轮转调度算法分配 CPU 时，当处于运行态的进程用完一个时间片后，它的状态是（）状态。
A. 阻塞
B. 运行
C. 就绪
D. 消亡
21. 一个作业 $8:00$ 到达系统，估计运行时间为 $1\mathrm{h}$。若 $10:00$ 开始执行该作业，其响应比是（）。
A. 2
B. 1
C. 3
D. 0.5
22. 关于优先权大小的论述中，正确的是（）。
A. 计算型作业的优先权，应高于 I/O 型作业的优先权
B. 用户进程的优先权，应高于系统进程的优先权
C. 在动态优先权中，随着作业等待时间的增加，其优先权将随之下降
D. 在动态优先权中，随着进程执行时间的增加，其优先权降低
23. 下列调度算法中，（）调度算法是绝对可抢占的。
A. 先来先服务
B. 时间片轮转
C. 优先级
D. 短进程优先
24. 作业是用户提交的，进程是由系统自动生成的，除此之外，两者的区别是（）。
A. 两者执行不同的程序段
B. 前者以用户任务为单位，后者以操作系统控制为单位
C. 前者是批处理的，后者是分时的
D. 后者是可并发执行，前者则不同
25. 进程调度算法采用固定时间片轮转调度算法，当时间片过大时，就会使时间片轮转法算法转化为（）调度算法。
A. 高响应比优先
B. 先来先服务
C. 短进程优先
D. 以上选项都不对
26. 有以下的进程需要调度执行（见下表）：
[tbl-6.md](tbl-6.md)
<!-- page: 91 -->
1）若用非抢占式短进程优先调度算法，问这5个进程的平均周转时间是多少？
2）若采用抢占式短进程优先调度算法，问这5个进程的平均周转时间是多少？
A. 8.62; 6.34
B. 8.62; 6.8
C. 10.62; 6.34
D. 10.62; 6.8
27. 有 5 个批处理作业 A, B, C, D, E 几乎同时到达，其预计运行时间分别为 10, 6, 2, 4, 8，其优先级（由外部设定）分别为 3, 5, 2, 1, 4，这里 5 为最高优先级。以下各种调度算法中，平均周转时间为 14 的是（ ）调度算法。
A. 时间片轮转（时间片为 1）
B. 优先级调度
C. 先来先服务（按照顺序 10, 6, 2, 4, 8）
D. 短作业优先
28. 使用抢占式最短剩余时间优先调度算法对下列进程进行调度，总周转时间是（ ）。
[tbl-7.md](tbl-7.md)
A. 25h
B. 26h
C. 27h
D. 28h
29. 假设系统采用多级反馈队列调度算法，系统中设置了三个不同优先级的队列 A、B 和 C，优先级 A > B > C，A 的时间片为 10ms，B 的时间片为 20ms，C 的时间片为 30ms。当 t = 0 时，进程 P₁ 到达，P₁ 所需的运行时间为 90ms；当 t = 30ms 时，进程 P₂ 到达，P₂ 所需的运行时间为 30ms，不考虑任何其他系统开销，进程 P₁ 的周转时间为（ ）。
A. 90ms
B. 100ms
C. 110ms
D. 120ms
30. 分时操作系统通常采用（ ）调度算法来为用户服务。
A. 时间片轮转
B. 先来先服务
C. 短作业优先
D. 优先级
31. 在进程调度算法中，对短进程不利的是（ ）。
A. 短进程优先调度算法
B. 先来先服务调度算法
C. 高响应比优先调度算法
D. 多级反馈队列调度算法
32. 假设系统中所有进程同时到达，则使进程平均周转时间最短的是（ ）调度算法。
A. 先来先服务
B. 短进程优先
C. 时间片轮转
D. 优先级
33. 多级反馈队列调度算法不具备的特性是（ ）。
A. 资源利用率高
B. 响应速度快
C. 系统开销小
D. 并发度高
34. 下列调度算法中，系统开销最小的调度算法是（ ）。
A. 高响应比优先调度算法
B. 多级反馈队列调度算法
C. 先来先服务调度算法
D. 时间片轮转调度算法
35. 下列进程调度算法中，可能导致饥饿现象的有（ ）。
I. 先来先服务调度算法
II. 短作业优先调度算法
III. 优先级调度算法
IV. 时间片轮转调度算法
A. I 和 II
B. II 和 III
C. II, III 和 IV
D. III
36. 与单处理机调度相比，多处理机调度需要额外考虑的调度目标是（ ）。
I. 负载平衡
II. 处理器亲和性
III. 进程周转时间
A. I 和 II
B. II 和 III
C. I 和 III
D. I, II 和 III
37. 【2009 统考真题】下列进程调度算法中，综合考虑进程等待时间和执行时间的是（ ）。
A. 时间片轮转调度算法
B. 短进程优先调度算法
<!-- page: 92 -->
C. 先来先服务调度算法
D. 高响应比优先调度算法
38.【2010统考真题】下列选项中，降低进程优先级的合理时机是（）。
A. 进程时间片用完
B. 进程刚完成I/O操作，进入就绪队列
C. 进程长期处于就绪队列
D. 进程从就绪态转为运行态
39.【2011统考真题】下列选项中，满足短作业优先且不会发生饥饿现象的是（）调度算法。
A. 先来先服务
B. 高响应比优先
C. 时间片轮转
D. 非抢占式短作业优先
40.【2012统考真题】一个多道批处理系统中仅有 $\mathrm{P_1}$ 和 $\mathrm{P_2}$ 两个作业， $\mathrm{P_2}$ 比 $\mathrm{P_1}$ 晚 $5\mathrm{ms}$ 到达，它的计算和I/O操作顺序如下：
$\mathrm{P_1}$ : 计算 $60\mathrm{ms}$ ，I/O $80\mathrm{ms}$ ，计算 $20\mathrm{ms}$
$\mathrm{P_2}$ : 计算 $120\mathrm{ms}$ ，I/O $40\mathrm{ms}$ ，计算 $40\mathrm{ms}$
若不考虑调度和切换时间，则完成两个作业需要的时间最少是（）。
A. $240 \mathrm{~ms}$
B. $260 \mathrm{~ms}$
C. $340 \mathrm{~ms}$
D. $360 \mathrm{~ms}$
41.【2012统考真题】若菜单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是（）。
A. 在进程结束时能进行处理机调度
B. 创建新进程后能进行处理机调度
C. 在进程处于临界区时不能进行处理机调度
D. 在系统调用完成并返回用户态时能进行处理机调度
42.【2013统考真题】某系统正在执行三个进程 $\mathrm{P_1}$ , $\mathrm{P_2}$ 和 $\mathrm{P_3}$ ，各进程的计算（CPU）时间和I/O时间比例如下表所示。
[tbl-8.md](tbl-8.md)
为提高系统资源利用率，合理的进程优先级设置应为（）。
A. $\mathrm{P}_{1} > \mathrm{P}_{2} > \mathrm{P}_{3}$
B. $\mathrm{P}_{3} > \mathrm{P}_{2} > \mathrm{P}_{1}$
C. $\mathrm{P}_{2} > \mathrm{P}_{1} = \mathrm{P}_{3}$
D. $\mathrm{P}_{1} > \mathrm{P}_{2} = \mathrm{P}_{3}$
43.【2014统考真题】下列调度算法中，不可能导致饥饿现象的是（）。
A. 时间片轮转
B. 静态优先数调度
C. 非抢占式短任务优先
D. 抢占式短任务优先
44.【2016统考真题】菜单CPU系统中有输入和输出设备各1台，现有3个并发执行的作业，每个作业的输入、计算和输出时间均分别为 $2\mathrm{ms}$ ， $3\mathrm{ms}$ 和 $4\mathrm{ms}$ ，且都按输入、计算和输出的顺序执行，则执行完3个作业需要的时间最少是（）。
A. $15 \mathrm{~ms}$
B. $17 \mathrm{~ms}$
C. $22 \mathrm{~ms}$
D. $27 \mathrm{~ms}$
45.【2017统考真题】假设4个作业到达系统的时刻和运行时间如下表所示。
[tbl-9.md](tbl-9.md)
系统在 $t = 2$ 时开始作业调度。若分别采用先来先服务和短作业优先调度算法，则选中
<!-- page: 93 -->
的作业分别是（）。
A. $\mathrm{J}_2, \mathrm{J}_3$
B. $\mathrm{J}_{1}, \mathrm{J}_{4}$
C. $\mathrm{J}_{2}, \mathrm{J}_{4}$
D. $\mathrm{J}_{1}, \mathrm{J}_{3}$
46. 【2017 统考真题】下列有关基于时间片的进程调度的叙述中，错误的是（）。
A. 时间片越短，进程切换的次数越多，系统开销越大
B. 当前进程的时间片用完后，该进程状态由执行态变为阻塞态
C. 时钟中断发生后，系统会修改当前进程在时间片内的剩余时间
D. 影响时间片大小的主要因素包括响应时间、系统开销和进程数量等
47. 【2018 统考真题】某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系统时间开销为 $1 \mu \mathrm{s}$ 。在 $T$ 时刻就绪队列中有 3 个进程 $\mathrm{P}_{1}$ , $\mathrm{P}_{2}$ 和 $\mathrm{P}_{3}$ , 其在就绪队列中的等待时间、需要的 CPU 时间和优先权如下表所示。
[tbl-10.md](tbl-10.md)
若优先权值大的进程优先获得CPU，从 $T$ 时刻起系统开始进程调度，则系统的平均周转时间为（）。
A. $54\mu \mathrm{s}$
B. $73\mu \mathrm{s}$
C. $74\mu \mathrm{s}$
D. $75\mu \mathrm{s}$
48. 【2019 统考真题】系统采用二级反馈队列调度算法进行进程调度。就绪队列 $Q_{1}$ 采用时间片轮转调度算法，时间片为 $10\mathrm{ms}$ ；就绪队列 $Q_{2}$ 采用短进程优先调度算法；系统优先调度 $Q_{1}$ 队列中的进程，当 $Q_{1}$ 为空时系统才会调度 $Q_{2}$ 中的进程；新创建的进程首先进入 $Q_{1}$ ； $Q_{1}$ 中的进程执行一个时间片后，若未结束，则转入 $Q_{2}$ 。若当前 $Q_{1}$ ， $Q_{2}$ 为空，系统依次创建进程 $P_{1}$ ， $P_{2}$ 后即开始进程调度， $P_{1}$ ， $P_{2}$ 需要的CPU时间分别为 $30\mathrm{ms}$ 和 $20\mathrm{ms}$ ，则进程 $P_{1}$ ， $P_{2}$ 在系统中的平均等待时间为（）。
A. $25\mathrm{ms}$
B. $20\mathrm{ms}$
C. $15\mathrm{ms}$
D. $10\mathrm{ms}$
49. 【2020 统考真题】下列与进程调度有关的因素中，在设计多级反馈队列调度算法时需要考虑的是（）。
I. 就绪队列的数量
II. 就绪队列的优先级
III. 各就绪队列的调度算法
IV. 进程在就绪队列间的迁移条件
A. 仅 I、II
B. 仅 III、IV
C. 仅 II、III、IV
D. I、II、III和IV
50. 【2021 统考真题】在下列内核的数据结构或程序中，分时系统实现时间片轮转调度需要使用的是（）。
I. 进程控制块
II. 时钟中断处理程序
III. 进程就绪队列
IV. 进程阻塞队列
A. 仅 II、III
B. 仅 I、IV
C. 仅 I、II、III
D. 仅 I、II、IV
51. 【2021 统考真题】下列事件中，可能引起进程调度程序执行的是（）。
I. 中断处理结束
II. 进程阻塞
III. 进程执行结束
IV. 进程的时间片用完
A. 仅 I、III
B. 仅 II、IV
C. 仅 III、IV
D. I、II、III和IV
52. 【2022 统考真题】进程 $\mathrm{P_0}$ ， $\mathrm{P_1}$ ， $\mathrm{P_2}$ 和 $\mathrm{P_3}$ 进入就绪队列的时刻、优先级（值越小优先权越高）及 CPU 执行时间如下表所示。
[tbl-11.md](tbl-11.md)
<!-- page: 94 -->
若系统采用基于优先权的抢占式进程调度算法，则从0ms时刻开始调度，到4个进程都运行结束为止，发生进程调度的总次数为（）。
A. 4
B. 5
C. 6
D. 7
53.【2023统考真题】进程 $\mathrm{P_1}$，$\mathrm{P_2}$ 和 $\mathrm{P_3}$ 进入就绪队列的时刻、优先级（值越大优先权越高）和CPU执行时间如下表所示。
[tbl-12.md](tbl-12.md)
若系统采用基于优先权的抢占式CPU调度算法，从0ms时刻开始进行调度，则 $\mathrm{P_1}$、$\mathrm{P_2}$ 和 $\mathrm{P_3}$ 的平均周转时间为（）。
A. 60ms
B. 61ms
C. 70ms
D. 71ms
54.【2024统考真题】假设某系统使用时间片轮转调度算法进行CPU调度，时间片大小为5ms，系统共有10个进程，初始时均处于就绪队列，执行结束前仅处于执行态或就绪态。若队尾的进程P所需的CPU时间最短，时间为25ms，不考虑系统开销，则进程P的周转时间为（）。
A. 200ms
B. 205ms
C. 250ms
D. 295ms
55.【2024统考真题】在支持页式存储管理的系统中，进程切换时操作系统需要执行的操作是（）。
I. 更新程序计数器的值
II. 更新线基址寄存器的值
III. 更新页表基地址寄存器的值
A. 仅 III
B. 仅 I、II
C. 仅 I、III
D. I、II、III