处理机调度

真题练习

本节重点掌握 调度指标的计算、各种调度算法的选择过程 和一次完整执行轨迹，同时理解调度、分派与上下文切换的边界。

调度指标

在操作系统里，调度（Scheduling） 是把 CPU 时间合理分配给多个进程（或线程）的核心机制。调度的好坏直接决定系统的响应速度、吞吐能力以及资源利用效率。为了衡量调度策略的优劣，我们通常用一组 调度指标 来量化：

1. 系统层面的宏观指标——关注整个计算机系统的运行状态，如 CPU 的利用率、系统整体的吞吐量等。这类指标帮助我们了解系统在整体负载下是否“忙碌”或出现瓶颈。
2. 进程层面的微观指标——关注单个进程在调度器眼中的表现，包括它何时进入调度队列、等待多久才被分配 CPU、实际执行多长时间以及最终何时完成等。这类指标可以帮助我们比较不同调度算法（FCFS、SJF、RR、优先级调度等）对单个作业的影响。

系统层面

系统层面主要关注 CPU 利用率和吞吐量这两个指标：

系统指标	含义
CPU 利用率	CPU 忙碌时间与总观察时间之比，通常用百分比表示
系统吞吐量	单位时间内完成的作业数或工作量

进程层面

从进程视角而言，进程从被创建到执行结束会有一系列时间周期作为指标：

进程调度指标	英文	含义与计算
到达时间	AT, Arrival Time	进程进入就绪队列的时刻
等待时间	WT, Waiting Time	进程在就绪队列中等待 CPU 的累计时间
要求服务时间	BT, Burst Time	题设给出的 CPU 服务时间
完成时间	CT, Completion Time	进程最后一次运行结束的时刻
周转时间	TAT, Turnaround Time	$TAT=CT-AT=WT+BT$
带权周转时间	W-TAT, Weighted Turnaround Time	$W\text{-}TAT=\frac{TAT}{BT}$

若共有 $n$ 个进程，则平均周转时间和平均带权周转时间分别为：

系统调度过程

为了有效地管理和调度进程，操作系统通常采用多级调度机制。这些调度机制分为三个层次：高级调度、中级调度和初级调度。

1. 高级调度（长程调度，Long-term Scheduling）:
   • 功能：高级调度 主要决定哪些进程应当被加载到内存中成为一个可运行的进程。
   • 主要目标：保持内存中适当数量的进程。不要过多也不要过少。
   • 当进程首次进入系统时，它们首先被放置在磁盘的一个区域，称为作业池。高级调度器从作业池中选择进程，根据某种策略将其加载到内存中，从而使其成为一个可运行的进程。
2. 中级调度（中程调度，Mid-term Scheduling）:
   • 功能：中级调度 涉及进程的暂时换出与重新换入。当内存压力较大时，中级调度器可把某些进程的地址空间换出到外存，使其进入挂起状态；这属于进程交换，不等同于页面置换算法。
   • 主要目标：为高级调度和初级调度器优化内存使用。
   • 中级调度器在必要时将进程从内存交换到磁盘，并在适当的时机将其交换回内存。
3. 初级调度（短程调度，Short-term Scheduling）:
   • 功能：初级调度 决定哪个进程应当被赋予 CPU 时间片，即决定下一个运行在处理器上的进程。
   • 主要目标：确保 CPU 的高效利用。
   • 它的决策频率非常高，因为在多任务环境中，每个时间片的长度可能只有几十毫秒。因此，初级调度器必须是非常快速的。

调度的实现

调度器：内核中的选择逻辑

调度器/调度程序（scheduler）是操作系统中负责决定下一个要执行的进程或线程的内核代码。它不是一个与用户程序并列的普通进程；长程、中程、短程调度器是按职责划分的逻辑功能，在具体系统中可以由内核的不同模块共同实现。

常见问题	应如何理解
调度器运行在哪里？	运行在内核地址空间中，直接访问就绪队列、PCB、定时器和调度策略数据；用户态程序不能直接修改这些结构。
使用什么特权集？	短程调度、更新 PCB、切换页表/内核栈等操作都在内核态完成。用户态只能通过系统调用、异常或中断进入内核，再由内核决定是否调度。
什么时候被加载？	引导加载器把内核映像装入内存并转交控制权后，内核初始化中断、PCB/队列和调度数据结构；调度器代码此时已经随内核就绪，不是“发生调度时才临时加载”。
调度器和分派程序一样吗？	不完全一样。调度器按算法选出下一个实体；分派程序执行保存现场、恢复现场、切换地址空间并返回新实体的低层动作。

调度器的选择依据可以是轮转、优先级、预计服务时间等；但无论使用哪种算法，都只能从就绪态实体中选择。阻塞态实体尚未具备运行条件，不能被直接分派给 CPU。

调度时机：先看状态变化，再看是否需要重新选择

并非每次进入内核都会发生进程切换。先有中断、异常或系统调用等入口，内核再根据当前状态和调度方式判断是否需要重新选择。

具体 case	当前实体发生什么	是否必须作出调度选择	抢占/非抢占的差异
当前实体请求 I/O、等待资源或条件	运行态 $\rightarrow$ 阻塞态	必须，它不能继续占用 CPU；无普通就绪实体时选择闲逛进程	两种方式都需要选择
当前实体正常结束/被终止	运行态 $\rightarrow$ 终止态	必须，需要回收并选择下一实体或闲逛进程	两种方式都需要选择
时间片耗尽、时钟中断	运行态 $\rightarrow$ 就绪态	分时系统通常需要；当前实体会回到相应队列	非抢占算法可不因时间片改换执行流
I/O 完成、资源可用、新任务到达	阻塞态/新建态 $\rightarrow$ 就绪态	可能，至少要入就绪队列	抢占式策略可能立刻比较优先级并抢占；非抢占式通常等待当前实体主动让出 CPU
系统调用/异常处理完毕	通常仍是原实体	不一定；可能只是处理后返回原程序	只有出现“需要重新调度”的原因才切换

一次短程调度的过程流

1. 进入内核：时钟中断、设备中断、异常或系统调用使 CPU 从用户态陷入内核态；硬件和入口代码先保留最小返回现场。
2. 确认原因并记账：内核确认是时间片到、I/O 完成、阻塞请求还是结束，更新运行时间、剩余时间片等调度信息。
3. 更新旧实体状态：若旧实体阻塞，则挂到相应等待队列；若被抢占或时间片到，则置为就绪并按规则入就绪队列；若结束则进入终止/回收流程。
4. 选择候选者：短程调度器在可运行队列中按算法选取一个实体；没有普通候选者时选择闲逛进程。
5. 分派与上下文切换：若候选者不是当前执行流，分派程序把寄存器、程序计数器、栈指针等现场保存到旧 PCB，再从新 PCB 恢复现场，必要时切换地址空间。
6. 返回执行：通过中断返回/系统调用返回等机制，以新实体的现场回到用户态，或留在内核态执行闲逛循环。

易混点：“用户态进入内核态”是特权级切换；只有第 5 步选中了另一个执行流，才发生进程/线程上下文切换。一次系统调用可以只进入内核后又返回原进程。

调度方式

• 抢占式调度（Preemptive）：在这种调度方式下，当一个进程正在执行时，操作系统可以中断该进程的执行并将 CPU 分配给另一个进程。这常常发生在一个更高优先级的进程变为就绪状态时。
• 非抢占式调度（Non-Preemptive）：在这种方式下，一旦 CPU 分配给一个进程，它会继续运行直到完成或者转为非运行状态（例如，等待 I/O 操作）。

闲逛进程

闲逛进程（Idle Process）是系统为每个 CPU 准备的兜底执行上下文：当普通就绪队列为空时，短程调度器选择它。它不表示 CPU 在做有用的用户计算；典型实现会执行 halt / wait for interrupt 一类低功耗等待指令，直到时钟、I/O 或其他中断到来。

参与方	此时负责什么
短程调度器	检查可运行队列，空时选择闲逛进程；普通任务重新就绪后重新评估。
闲逛进程 P0	保持合法的当前执行上下文，并让 CPU 以等待中断的方式降低无效消耗。
设备/定时器中断	报告 I/O 完成、时间到等事件，把等待条件满足的普通任务转为就绪态。
普通任务的 PCB 与就绪队列	记录已保存现场；被唤醒后先进入就绪队列，而不是绕过调度器直接“抢到 CPU”。

在 Linux 中常把启动阶段的第一个任务/每 CPU 的 idle task 与 PID 0 联系起来；在 Windows 中可看到 System Idle Process 的统计项。它们的名称与实现细节可以不同，但抽象规则相同：没有普通可运行实体时运行 idle；普通实体就绪后，由内核重新分派。

两种线程的调度

• 内核级线程：由操作系统内核直接支持的线程。操作系统知道这些线程的存在，并可以直接进行调度。
• 用户级线程：完全在用户空间中实现的线程，不需要内核的介入。
• 对于 内核级线程，操作系统可以直接调度它们，并可以利用多核或多处理器的优势。
• 对于 用户级线程，内核不能直接选择某一个用户级线程，而是调度其所映射的内核级执行实体。用户态线程切换通常开销较小；在多对一映射中，同一进程的用户级线程不能同时运行在多个处理器上，一对一或多对多映射则没有这一固有限制。

调度算法

根据是否允许剥夺正在运行进程的 CPU，可作如下分类：

调度算法	常见方式	选择依据与主要边界
FCFS	非抢占	按到达顺序，可能产生护航效应
SJF	非抢占	选择预计服务时间最短者；抢占版本为最短剩余时间优先（SRTF）
HRRN	非抢占	选择响应比最高者，兼顾等待时间与服务时间
优先级调度	可抢占或非抢占	优先级数值与高低的对应关系必须以题设为准
RR	抢占	时间片耗尽后回到就绪队列队尾
多级反馈队列	通常抢占	高优先级队列先运行，不同队列使用不同时间片和降级规则

先来先服务

先来先服务（First-Come, First-Served，FCFS）按照进程到达的顺序 分配依次执行。先到达的进程先执行，后续进程等待直到前一个进程执行才能进一步执行。

最短作业优先

最短作业优先（Shortest Job First，SJF）算法在从就绪队列中选择进程时，会 选择运行时间最短 的进程进行执行。

在题目中进程的运行时间一般都是给定的，所以 SJF 算法比较容易实现。但是在真实的系统中进程的运行时间是不确定的，所以在使用该算法时操作系统需要对进程的运行时间进行预估。

最高响应比优先

最高响应比优先（Highest Response Ratio Next，HRRN）算法从就绪队列中选择 响应比 最高的进程进行执行。

其中 响应比（Response Ratio）的计算公式如下：

其中 $WT$（Waiting Time）为进程的等待时间，$BT$（Burst Time）为要求服务时间，$TAT$ 为周转时间。计算响应比时，等待时间应取“当前调度时刻减到达时刻”；已经完成的进程不再参与比较。

这种计算策略可以有效地避免饥饿现象，即一个进程等待了很长时间但仍没有得到执行。一个进程的等待时间越长，其 响应比 就会更大，进而优先得到执行机会。一个进程的执行时间很长，其 响应比 就会越小，会优先调度其他进程。

---

• 时刻 0：只有 P1 到达，执行 P1。
• 时刻 5：P1 执行完成。P2 的响应比为 $\frac{4+3}{3}\approx2.33$，P3 为 $\frac{3+8}{8}=1.375$，P4 为 $\frac{2+6}{6}\approx1.33$，因此执行 P2。
• 时刻 8：P2 执行完成。P3 的响应比为 $\frac{6+8}{8}=1.75$，P4 为 $\frac{5+6}{6}\approx1.83$，因此执行 P4。
• 时刻 14：P4 执行完成，只剩下 P3 了，最后执行 P3。

所以进程的执行顺序为 P1、P2、P4、P3，每个进程的时间指标如下表所示：

进程号	到达时间	要求服务时间	完成时间	周转时间	等待时间
P1	0	5	5	5	0
P2	1	3	8	7	4
P4	3	6	14	11	5
P3	2	8	22	20	12

优先级调度

优先级调度是一种基于进程优先级的调度算法，广泛应用于操作系统中。根据是否允许中断当前正在执行的进程，优先级调度可分为 非抢占式优先级调度 和 抢占式优先级调度 两种形式。

非抢占式优先级调度

在 非抢占式优先级调度 中，调度器总是从就绪队列（等待队列）中选择优先级最高的进程执行。一旦某个进程开始执行，它将持续运行直到完成（或主动释放 CPU，例如进入等待 I/O 状态）。在此期间，即使有更高优先级的进程到达并加入就绪队列，当前进程也不会被中断，而是继续执行直到结束。

注意

“优先级数值越小，优先级越高”是许多题目采用的约定，但不是普遍规律；解题必须先读清题设对数值方向的定义。

比如对于 Unix 系统，使用 nice 值来表示优先级：

• nice 值越低，进程获得 CPU 时间的机会越多。

抢占式优先级调度

抢占式优先级调度旨在确保系统中任何时刻运行的进程始终是优先级最高的。当一个更高优先级的进程到达时，调度器会立即暂停当前运行的低优先级进程（将其挂起并加入就绪队列），然后将 CPU 分配给新到达的高优先级进程。

下图给出了两种优先级调度方式的实例对比，其中绿色的进程表示执行态，黄色表示就绪态：

时间片轮转

时间片轮转（Round Robin，RR）这是一种基于 时间片 的算法，每个进程被分配一个固定的时间片，当时间片用完时，进程被放回队列尾部，下一个进程开始执行。这样可以实现公平的 CPU 时间分配。

下面的例子统一采用时间片 (q=3)。为了让“谁在队头、谁在队尾”可核对，先把旧图中使用的到达时间和服务时间列成表；后面的逐步面板展示每个 CPU 片段结束后的完整队列。

进程	到达时间	要求服务时间	进程	到达时间	要求服务时间
P1	0	1	P6	11	8
P2	0	2	P7	11	6
P3	0	4	P8	11	4
P4	0	6	P9	11	2
P5	0	8	P10	11	2

在这个例子中，P6—P10 在时刻 11 到达，早于 P5 的第一个时间片结束时刻 12，因此它们先接在已经等待的 P3、P4 之后；P5 在时刻 12 尚未完成，才追加到这些新到达进程之后。全部进程在时刻 43 完成。

调度器按就绪队列顺序轮流分配 CPU；进程用完时间片但尚未完成时进入 就绪态 并排到队尾，只有等待 I/O 或事件时才进入阻塞态。点击任一步时，同时检查 CPU、队列从队头到队尾的顺序、到达/完成事件与每个进程的剩余服务时间。

多级反馈队列

多级反馈队列（Multilevel Feedback Queue，MLFQ）不是“固定的一条公式”，而是一组把优先级队列 + 不同时间片 + 进程行为反馈组合起来的策略。它把任务放入多个就绪队列；高优先级队列先运行，时间片通常更短，低优先级队列的时间片更长。

常见的一组规则如下。题目若另行规定，应以题设的入队、降级、抢占和提升规则为准：

机制	常见做法	想解决的问题
新任务入队	先进入最高优先级队列	新到达或交互任务能快速得到首次响应
用完整个时间片	降到下一队列	长时间占用 CPU 的计算密集型任务逐步让出高优先级
主动因 I/O 阻塞	不降级，或在返回时保留/提升优先级	频繁等待输入输出的交互任务不应被误判为 CPU 密集型
高优先级队列重新非空	可抢占低优先级当前任务	保证高优先级响应；是否“立即抢占”取决于具体策略
长时间等待	周期性全体提升（priority boost）	防止低优先级任务永久饥饿

高优先级队列优先调度、低优先级队列时间片更长的设计，兼顾了快速响应、公平性和资源利用率；但必须把“本题是否允许 I/O 返回提升、是否有全局提升、队列间是否立即抢占”读清楚，不能凭名称自行补规则。

下面的示例采用 $Q_0$ 时间片 2、$Q_1$ 时间片 4、$Q_2$ 时间片 8；B 在未用完 $Q_0$ 时间片前请求 I/O，I/O 完成后回到 $Q_0$，并打断正在 $Q_1$ 运行的 A。它不是唯一的 MLFQ 变体，而是把“降级、阻塞、唤醒、队列间抢占”放到同一条可核对轨迹中。

上下文切换

进程的上下文是进程执行的环境。在操作系统中，它指的是一个进程在特定时间点上的系统状态，包括多种信息，这些信息使得进程在被中断后可以再次恢复并继续执行。当操作系统从一个进程切换到另一个进程时，它会保存当前进程的上下文并恢复下一个进程的上下文。这个过程被称为 上下文切换。

进程上下文内容

1. 寄存器值：这包括通用寄存器、程序计数器、栈指针、状态寄存器等。它们保存了进程的当前执行位置和状态。
2. 程序计数器：表示进程的下一个指令的位置。
3. 虚拟内存信息：这包括进程的页表、页目录等信息，描述了进程的地址空间布局。
4. I/O 状态信息：包括打开的文件描述符、网络连接、I/O 指针等。
5. CPU 调度信息：例如进程优先级、计划器状态等。
6. 资源使用情况：这可能包括该进程所使用的各种资源的跟踪信息，如内存、文件句柄等。

上下文切换流程

1. 保存当前进程的状态：操作系统保存当前正在运行的进程的上下文。这意味着它会将当前的寄存器值、程序计数器等保存到进程的进程控制块（PCB）中。
2. 选择下一个要执行的进程：调度器决定下一个要运行的进程。
3. 恢复下一个进程的状态：操作系统从新进程的 PCB 中恢复其上下文信息，包括寄存器值、程序计数器等。
4. 开始执行新进程。

把一次由时钟中断触发的切换拆开看，会更容易区分“CPU 上的瞬时寄存器”和“内存中 PCB 保存的现场”：

阶段	CPU 所处特权态	CPU / 寄存器发生什么	PCB / 队列发生什么
P1 正在执行	用户态	PC 指向 P1 下一条指令；SP、通用寄存器和 PSW 都属于 P1 的现场	P1 的 PCB 记录它是运行态
时钟中断入口	内核态	CPU 转入内核入口，使用内核栈；保存返回所需的最小现场	内核获得检查时间片和调度标志的机会
保存 P1	内核态	把 P1 的 PC、SP、通用寄存器、PSW 等写入 P1 的 PCB	若时间片到，P1 改为就绪态并入就绪队列
调度选择 P2	内核态	调度器读取队列与策略数据	P2 从就绪队列取出，标为运行态
恢复 P2	内核态	从 P2 的 PCB 装入它自己的 PC、SP、寄存器、页表相关信息	P1 已保存，P2 的 PCB 成为当前执行实体
返回 P2	用户态	中断返回后 CPU 继续执行 P2 的下一条指令	两个 PCB 都仍在内存中，等待下次事件