2.2 CPU调度
2026 旧版 · 非 2027 主源 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 2.2 CPU调度
在学习本节时，请读者思考以下问题：
1）为什么要进行CPU调度？
2）调度算法有哪几种？结合第1章学习的分时操作系统和实时操作系统，思考哪种调度算法比较适合这两种操作系统。
希望读者能够在学习调度算法前，先自己思考一些调度算法，在学习的过程中注意将自己的想法与这些经典的算法进行比对，并学会计算一些调度算法的周转时间。
## 2.2.1 调度的概念
### 1. 调度的基本概念
在多道程序系统中，进程的数量往往多于CPU的个数，因此进程争用CPU的情况在所难免。CPU调度是对CPU进行分配，即从就绪队列中按照一定的算法（公平、高效的原则）选择一个进程并将CPU分配给它运行，以实现进程并发地执行。
CPU调度是多道程序操作系统的基础，是操作系统设计的核心问题。
### 2. 调度的层次
一个作业从提交开始直到完成，往往要经历以下三级调度，如图2.7所示。
图2.7 CPU的三级调度
### （1）高级调度（作业调度）
按照某种规则从外存上处于后备队列的作业中挑选一个（或多个），给它（们）分配内存、
<!-- page: 78 -->
I/O 设备等必要的资源，并建立相应的进程，以使它（们）获得竞争 CPU 的权利。简言之，作业调度就是内存与辅存之间的调度。每个作业只调入一次、调出一次。
多道批处理系统中大多配有作业调度，而其他系统中通常不需要配置作业调度。
（2）中级调度（内存调度）
引入中级调度的目的是提高内存利用率和系统吞吐量。为此，将那些暂时不能运行的进程调至外存等待，此时进程的状态称为挂起态。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定将外存上的那些已具备运行条件的挂起进程再重新调入内存，并修改其状态为就绪态，挂在就绪队列上等待。中级调度实际上是存储器管理中的对换功能。
（3）低级调度（进程调度）
按照某种算法从就绪队列中选取一个进程，将 CPU 分配给它。进程调度是最基本的一种调度，在各种操作系统中都必须配置这级调度。进程调度的频率很高，一般几十毫秒一次。
3. 三级调度的联系
作业调度从外存的后备队列中选择一批作业进入内存，为它们建立进程，这些进程被送入就绪队列，进程调度从就绪队列中选出一个进程，并将其状态改为运行态，将 CPU 分配给它。中级调度是为了提高内存的利用率，系统将那些暂时不能运行的进程挂起来。
1）作业调度为进程活动做准备，进程调度使进程正常活动起来。
2）中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间。
3）作业调度次数少，中级调度次数略多，进程调度频率最高。
4）进程调度是最基本的，不可或缺。
2.2.2 调度的实现
1. 调度程序（调度器）
用于调度和分派 CPU 的组件称为调度程序，它通常由三部分组成，如图 2.8 所示。
图 2.8 调度程序的结构
1）排队器。将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便于调度程序选择。每当有一个进程转变为就绪态时，排队器便将它插入相应的就绪队列。
2）分派器。依据调度程序所选的进程，将其从就绪队列中取出，将 CPU 分配给新进程。
3）上下文切换器。在对 CPU 进行切换时，会发生两对上下文的切换操作：第一对，将当前进程的上下文保存到其 PCB 中，再装入分派程序的上下文，以便分派程序运行；第二对，移出分派程序的上下文，将新选进程的 CPU 现场信息装入 CPU 的各个相应寄存器。
在上下文切换时，需要执行大量 load 和 store 指令，以保存寄存器的内容，因此会花费较
<!-- page: 79 -->
多时间。现在已有硬件实现的方法来减少上下文切换时间。通常采用两组寄存器，其中一组供内核使用，一组供用户使用。这样，上下文切换时，只需改变指针，让其指向当前寄存器组即可。
## 2. 调度的时机、切换与过程
调度程序是操作系统内核程序。请求调度的事件发生后，才可能运行调度程序，调度了新的就绪进程后，才会进行进程切换。理论上这三件事情应该顺序执行，但在实际的操作系统内核程序运行中，若某时刻发生了引起进程调度的因素，则不一定能马上进行调度与切换。
### 创建篇章 > 可以进行CPU调度的事件或时机（2012、2021）
现代操作系统中，应该进行进程调度与切换的情况如下：
1）创建新进程后，父进程和子进程都处于就绪态，因此需要决定是运行父进程还是运行子进程，调度程序可以合法地决定其中一个进程先运行。
2）进程正常结束或异常终止后，必须从就绪队列中选择某个进程运行。若没有就绪进程，则通常运行一个系统提供的闲逛进程。
3）当进程因I/O请求、信号量操作或其他原因此被阻塞时，必须调度其他进程运行。
4）当I/O设备准备就绪后，发出I/O中断，原先等待I/O的进程从阻塞态变为就绪态，此时需要决定是让新的就绪进程投入运行，还是让中断发生时运行的进程继续执行。
此外，在有些系统中，当有更紧急的任务（如更高优先级的进程进入就绪队列）需要处理时，或者当前进程的时间片用完时，也会被强行剥夺CPU。
进程切换往往在调度完成后立刻发生，它要求保存原进程当前断点的现场信息，恢复被调度进程的现场信息。现场切换时，操作系统内核将原进程的现场信息推入当前进程的内核堆栈来保存它们，并更新堆栈指针。内核完成从新进程的内核栈中装入新进程的现场信息、更新当前运行进程空间指针、重设PC寄存器等相关工作之后，开始运行新的进程。
不能进行进程的调度与切换的情况如下：
1）在处理中断的过程中。中断处理过程复杂，在实现上很难做到进程切换，而且中断处理是系统工作的一部分，逻辑上不属于某一进程，不应被剥夺CPU资源。
2）需要完全屏蔽中断的原子操作过程中。如加锁、解锁、中断现场保护、恢复等原子操作。在原子过程中，连中断都要屏蔽，更不应该进行进程调度与切换。
若在上述过程中发生了引起调度的条件，则不能马上进行调度和切换，应置系统的请求调度标志，直到上述过程结束后才进行相应的调度与切换。
## 3. 进程调度的方式
所谓进程调度方式，是指当某个进程正在 CPU 上执行时，若有某个更为重要或紧迫的进程需要处理，即有优先权更高的进程进入就绪队列，此时应如何分配 CPU。
通常有以下两种进程调度方式：
1）非抢占调度方式，也称非剥夺方式。是指当一个进程正在CPU上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程运行完成（如正常结束、异常终止）或发生某种事件（如等待I/O操作、在进程通信或同步中执行了Block原语）而进入阻塞态时，才将CPU分配给其他进程。
非抢占调度方式的优点是实现简单、系统开销小，适用于早期的批处理系统，但它不能用于分时系统和大多数的实时系统。
<!-- page: 80 -->
2）抢占调度方式，也称剥夺方式。是指当一个进程正在CPU上执行时，若有某个更为重要或紧迫的进程需要使用CPU，则允许调度程序根据某种原则去暂停正在执行的进程，将CPU分配给这个更为重要或紧迫的进程。
抢占调度方式对提高系统吞吐率和响应效率都有明显的好处。但“抢占”不是一种任意性行为，必须遵循一定的原则，主要有优先权、短进程优先和时间片原则等。
## 4. 阈迹进程
当进程切换时，若系统中没有就绪进程，则会调度阈迹进程（Idle Process）运行，它的PID为0。若没有其他进程就绪，则该进程就一直运行，并在指令周期后测试中断。阈逛进程的优先级最低，没有就绪进程时才会运行阈逛进程，只要有进程就绪，就会立即让出CPU。
阈逛进程不需要CPU之外的资源，它不会被阻塞。
## 5. 两种线程的调度
1）用户级线程调度。因为内核并不知道线程的存在，所以内核还是和以前一样，选择一个进程，并给予时间控制。由进程中的调度程序决定哪个线程运行。
2）内核级线程调度。内核选择一个特定线程运行，通常不用考虑该线程属于哪个进程。对被选择的线程赋予一个时间片，若超过了时间片，则会强制挂起该线程。
用户级线程的线程切换在同一进程中进行，仅需少量的机器指令；内核级线程的线程切换需要完整的上下文切换、修改内存映像、使高速缓存失效，这就导致了若干数量级的延迟。
## 2.2.3 调度的目标
不同的调度算法具有不同的特性，在选择调度算法时，必须考虑算法的特性。为了比较CPU调度算法的性能，人们提出了很多评价标准，下面介绍其中主要的几种：
**前提建议** 作业执行的相关计算（2012、2016、2018、2019、2023、2024）
1）CPU利用率。CPU是计算机系统中最重要和昂贵的资源之一，所以应尽可能使CPU保持“忙”状态，使这一资源利用率最高。CPU利用率的计算方法如下：
$$
\text{CPU的利用率} = \frac{\text{CPU有效工作时间}}{\text{CPU有效工作时间} + \text{CPU空闲等待时间}}
$$
**注意**
计算作业完成时间时，要注意CPU与设备、设备与设备之间是可以并行的。
2）系统吞吐量。表示单位时间内CPU完成作业的数量。长作业需要消耗较长的CPU时间，因此会降低系统的吞吐量。而对于短作业，需要消耗的CPU时间较短，因此能提高系统的吞吐量。调度算法和方式的不同，也会对系统的吞吐量产生较大的影响。
3）周转时间。指从作业提交到作业完成所经历的时间，是作业等待、在就绪队列中排队、在CPU上运行及I/O操作所花费时间的总和。周转时间的计算方法如下：
$$
\text{周转时间} = \text{作业完成时间} - \text{作业提交时间}
$$
平均周转时间是指多个作业周转时间的平均值：
$$
\text{平均周转时间} = (\text{作业1的周转时间} + \dots + \text{作业n的周转时间}) / n
$$
带权周转时间是指作业周转时间与作业实际运行时间的比值：
<!-- page: 81 -->
$$
\text{带权周转时间} = \frac{\text{作业周转时间}}{\text{作业实际运行时间}}
$$
平均带权周转时间是指多个作业带权周转时间的平均值：
平均带权周转时间 = (作业1的带权周转时间 + … + 作业n的带权周转时间)/n
4）等待时间。指进程处于等待CPU的时间之和，等待时间越长，用户满意度越低。CPU调度算法实际上并不影响作业执行或I/O操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法的优劣，常常只需简单地考察等待时间。
5）响应时间。指从用户提交请求到系统首次产生响应所用的时间。在交互式系统中，周转时间不是最好的评价准则，一般采用响应时间作为衡量调度算法的重要准则之一。从用户角度来看，调度策略应尽量降低响应时间，使响应时间处在用户能接受的范围之内。
要想得到一个满足所有用户和系统要求的算法几乎是不可能的。设计调度程序，一方面要满足特定系统用户的要求（如某些实时和交互进程的快速响应要求），另一方面要考虑系统整体效率（如减少整个系统的进程平均周转时间），同时还要考虑调度算法的开销。
## 2.2.4 进程切换
**前期通话** 进程调度前后CPU模式的变化（2023）
对通常的进程而言，其创建、撤销及要求由系统设备完成的I/O操作，都是利用系统调用而进入内核，再由内核中的相应处理程序予以完成的。进程切换同样是在内核的支持下实现的，因此可以说，任何进程都是在操作系统内核的支持下运行的，是与内核紧密相关的。
### （1）上下文切换
**前期通话** 切换进程时的操作（2024）
切换CPU到另一个进程需要保存当前进程状态并恢复另一个进程的状态，这个任务称为上下文切换。进程上下文采用进程PCB表示，包括CPU寄存器的值、进程状态和内存管理信息等。当进行上下文切换时，内核将旧进程状态保存在其PCB中，然后加载经调度而要执行的新进程的上下文。在切换过程中，进程的运行环境产生实质性的变化。上下文切换的流程如下：
1）挂起一个进程，将CPU上下文保存到PCB，包括程序计数器和其他寄存器。
2）将进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列。
3）选择另一个进程执行，并更新其PCB。
4）恢复新进程的CPU上下文。
5）跳转到新进程PCB中的程序计数器所指向的位置执行。
### （2）上下文切换的消耗
上下文切换通常是计算密集型的，即它需要相当可观的CPU时间，在每秒几十上百次的切换中，每次切换都需要纳秒量级的时间，所以上下文切换对系统来说意味着消耗大量的CPU时间。有些CPU提供多个寄存器组，这样，上下文切换就只需要简单改变当前寄存器组的指针。
### （3）上下文切换与模式切换
模式切换与上下文切换是不同的，模式切换时，CPU逻辑上可能还在执行同一进程。用户进程最开始都运行在用户态，若进程因中断或异常进入内核态运行，执行完后又回到用户态刚被中断的进程运行。用户态和内核态之间的切换称为模式切换，而不是上下文切换，因为没有改变当前的进程。上下文切换只能发生在内核态，它是多任务操作系统中的一个必需的特性。
关注公众号[考研小肖]免费考研资料&无水印PDF
<!-- page: 82 -->
# 注意
调度和切换的区别；调度是指决定资源分配给哪个进程的行为，是一种决策行为；切换是指实际分配的行为，是执行行为。一般来说，先有资源的调度，然后才有进程的切换。
## 2.2.5 CPU调度算法
**简易调度** ▶ 各种调度算法的特点与对比（2009、2011、2014）
操作系统中存在多种调度算法，有的调度算法适用于作业调度，有的调度算法适用于进程调度，有的调度算法两者都适用。下面介绍几种常用的调度算法。
### 1. 先来先服务（FCFS）调度算法
FCFS 调度算法是一种最简单的调度算法，它既可用于作业调度，又可用于进程调度。
**简易调度** ▶ FCFS 调度算法的思想（2017）
在作业调度中，FCFS 调度算法每次从后备作业队列中选择最先进入该队列的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。
在进程调度中，FCFS 调度算法每次从就绪队列中选择最先进入该队列的进程，将CPU分配给它，使之投入运行，直到运行完成或因某种原因此阻塞时才释放CPU。
**简易调度** ▶ 批处理系统中作业完成时间的分析（2012、2016）
下面通过一个实例来说明 FCFS 调度算法的性能。假设系统中有 4 个作业，它们的提交时间分别是 8, 8.4, 8.8, 9，运行时间依次是 2, 1, 0.5, 0.2，系统采用 FCFS 调度算法，这组作业的平均等待时间、平均周转时间和平均带权周转时间见表 2.2。
FCFS 调度算法属于不可剥夺算法。从表面上看，它对所有作业都是公平的，但若一个长作业先到达系统，就会使后面的许多短作业等待很长时间，因此它不能作为分时系统和实时系统的主要调度策略。但它常被结合在其他调度策略中使用。例如，在使用优先级作为调度策略的系统中，往往对多个具有相同优先级的进程按 FCFS 原则处理。
FCFS 调度算法的特点是算法简单，但效率低；对长作业比较有利，但对短作业不利（相对 SJF 和高响应比）；有利于 CPU 繁忙型作业，而不利于 I/O 繁忙型作业。
表 2.2 FCFS 调度算法的性能
[tbl-3.md](tbl-3.md)
平均等待时间 $t = (0 + 1.6 + 2.2 + 2.5) / 4 = 1.575$；平均周转时间 $T = (2 + 2.6 + 2.7 + 2.7) / 4 = 2.5$；
平均带权周转时间 $W = (1 + 2.6 + 5.4 + 13.5) / 4 = 5.625$。
### 2. 短作业优先（SJF）调度算法
**简易调度** ▶ SJF 调度算法的思想（2017）
短作业（进程）优先调度算法是指对短作业（进程）优先调度的算法。短作业优先（SJF）调度算法从后备队列中选择一个或几个估计运行时间最短的作业，将它们调入内存运行；短进程
<!-- page: 83 -->
优先（SPF）调度算法从就绪队列中选择一个估计运行时间最短的进程，将CPU分配给它，使之立即执行，直到完成或发生某事件而阻塞时才释放CPU。
例如，考虑表2.2中给出的一组作业，若系统采用短作业优先调度算法，其平均等待时间、平均周转时间和平均带权周转时间见表2.3。
表 2.3 SJF 调度算法的性能
[tbl-4.md](tbl-4.md)
平均等待时间 $t = (0 + 2.3 + 1.4 + 1) / 4 = 1.175$；平均周转时间 $T = (2 + 3.3 + 1.9 + 1.2) / 4 = 2.1$；
平均带权周转时间 $W = (1 + 3.3 + 3.8 + 6) / 4 = 3.525$。
SJF 算法也存在不容忽视的缺点：
**创意调度** ➤ 饥饿现象的含义（2016）
1）该算法对长作业不利，由表2.2和表2.3可知，SJF调度算法中长作业的周转时间会增加。更严重的是，若有一长作业进入系统的后备队列，由于调度程序总是优先调度那些（即使是后进来的）短作业，将导致长作业长期不被调度，产生饥饿现象（注意区分死锁，后者是系统环形等待，前者是调度策略问题）。
2）该算法完全未考虑作业的紧迫程度，因此不能保证紧迫性作业会被及时处理。
3）由于作业的长短是根据用户所提供的估计执行时间而定的，而用户又可能有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。
SPF算法也可以是抢占式的（若未特别说明，则默认为非抢占式）。当一个新进程到达就绪队列时，若其估计执行时间比当前进程的剩余时间小，则立即暂停当前进程，将CPU分配给新进程。因此，抢占式SPF调度算法也称最短剩余时间优先调度算法。
**注意**
短作业（SJF）调度算法的平均等待时间、平均周转时间是最优的。
## 3. 高响应比优先调度算法
高响应比优先调度算法主要用于作业调度，是对FCFS调度算法和SJF调度算法的一种综合平衡，同时考虑了每个作业的等待时间和估计的运行时间。在每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。
响应比的变化规律可描述为
$$
\text {响 应 比} R _ {F} = \frac {\text {等 待 时间} + \text {要求 服 务 时间}}{\text {要 求 服 务 时间}}
$$
根据公式可知：①作业的等待时间相同时，要求服务时间越短，响应比越高，有利于短作业，因此类似于SJF。②要求服务时间相同时，作业的响应比由其等待时间决定，等待时间越长，其响应比越高，因此类似于FCFS。③对于长作业，作业的响应比可以随等待时间的增加而提高，当其等待时间足够长时，也可获得CPU，克服了“饥饿”现象。
## 4. 优先级调度算法
优先级调度算法既可用于作业调度，又可用于进程调度。该算法中的优先级用于描述作业的
<!-- page: 84 -->
紧迫程度。在作业调度中，优先级调度算法每次从后备作业队列中选择优先级最高的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。在进程调度中，优先级调度算法每次从就绪队列中选择优先级最高的进程，将CPU分配给它，使之投入运行。
根据新的更高优先级进程能否抢占正在执行的进程，可将该调度算法分为如下两种：
**新增进程** ▶ 非抢占式优先级调度算法的应用分析（2018）
1）非抢占式优先级调度算法。当一个进程正在CPU上运行时，即使有某个优先级更高的进程进入就绪队列，仍让正在运行的进程继续运行，直到由于其自身的原因此让出CPU时（任务完成或等待事件），才将CPU分配给就绪队列中优先级最高的进程。
**新增进程** ▶ 抢占式优先级调度算法的应用分析（2022、2023）
2）抢占式优先级调度算法。当一个进程正在CPU上运行时，若有某个优先级更高的进程进入就绪队列，则立即暂停正在运行的进程，将CPU分配给优先级更高的进程。
而根据进程创建后其优先级是否可以改变，可将进程优先级分为以下两种：
**新增进程** ▶ 静态优先级和动态优先级的分析（2016）
1）静态优先级。优先级是在创建进程时确定的，且在进程的整个运行期间保持不变。确定静态优先级的主要依据有进程类型、进程对资源的要求、用户要求。优点是简单易行，系统开销小；缺点是不够精确，可能出现优先级低的进程长期得不到调度的情况。
**新增进程** ▶ 调整进程优先级的合理时机（2010）
2）动态优先级。创建进程时先赋予进程一个优先级，但优先级会随进程的推进或等待时间的增加而改变，以便获得更好的调度性能。例如，规定优先级随等待时间的增加而提高，于是，对于优先级初值较低的进程，在等待足够长的时间后也可获得CPU。
一般来说，进程优先级的设置可以参照以下原则：
1）系统进程 > 用户进程。系统进程作为系统的管理者，理应拥有更高的优先级。
2）交互型进程 > 非交互型进程（或前台进程 > 后台进程）。大家平时在使用手机时，在前台运行的正在和你交互的进程应该更快速地响应你，因此自然需要被优先处理。
**新增进程** ▶ 进程优先级的设置：I/O 型和计算型（2013）
3）I/O 型进程 > 计算型进程。所谓 I/O 型进程，是指那些会频繁使用 I/O 设备的进程，而计算型进程是那些频繁使用 CPU 的进程（很少使用 I/O 设备）。我们知道，I/O 设备（如打印机）的处理速度要比 CPU 慢得多，因此若将 I/O 型进程的优先级设置得更高，就更有可能让 I/O 设备尽早开始工作，进而提升系统的整体效率。