CPU调度¶

本章问题：几个任务都能运行时，CPU先给谁？怎样从时间线算响应、等待和完成时间？

学习顺序：

区分CPU计算段、I/O阻塞段与就绪等待段。
用明确起止点定义三个时间指标。
按到达、完成、抢占等事件推进调度图。
比较FCFS、短作业、轮转与反馈队列规则。
再考虑多核、实时截止期和优先级反转。

先看CPU段与等待¶

进程常交替经历CPU计算段（CPU burst）与I/O等待段。
调度器只从就绪任务中选下一位；
等设备的任务不能因为“优先级高”就立即计算。
抢占式调度可以中途收回CPU；
非抢占式通常等当前CPU段结束、阻塞或退出。

常用指标要分清起止点。设到达时刻 \(a\)、首次得到CPU时刻 \(f\)、完成时刻 \(c\)，则响应时间为 \(f-a\)，周转时间为 \(c-a\)；等待时间仅累计就绪队列中的时间。

在忽略其他开销、状态划分完整时，等待=周转−CPU总时间−I/O阻塞总时间。

例子与推演

例如A于0到达，CPU运行0—2，I/O为2—7，就绪等待7—10，CPU运行10—12后结束。响应0，周转12，就绪等待3毫秒。总共没占CPU的8毫秒包含5毫秒I/O，不能全算等待。

记指标时只问三件事：第一次得到CPU要多久是响应；
从到达到结束一共多久是周转；
条件已齐却排队等CPU多久是等待。
一个进程可多次进入就绪队列，所以等待时间要把各段加起来；
响应时间只看第一次。

flowchart LR
    A["到达：0"] --> C1["CPU：0到2"]
    C1 --> IO["I/O阻塞：2到7"]
    IO --> W["就绪等待：7到10"]
    W --> C2["CPU：10到12"]
    C2 --> E["完成：12"]

这条路径把周转12 ms拆成CPU 4 ms、阻塞5 ms、等待3 ms；相加还原总时间，是校验答案的一种方法。若题目给切换或其他开销，要按其归属另加，不能凭空把它归到某一项。

练习 1¶

题目

自编题：A到达0 ms，CPU运行0—2 ms，I/O阻塞2—7 ms，就绪等待7—10 ms，CPU运行10—12 ms后结束；无其他开销。某解答给出等待时间8 ms、响应时间12 ms。

① 修正等待、响应、周转三项并说明口径。
② 若设备晚2 ms完成但仍在10 ms恢复CPU，等待时间和周转时间如何变化？

参考解答

解答

原就绪等待只有7—10，共3 ms。
响应按首次得到CPU计，为\(0-0=0\) ms。
周转为\(12-0=12\) ms。
核对：\(12-4-5=3\) ms。
修改后I/O为2—9，共7 ms；
就绪等待9—10，降为1 ms。
完成时刻仍12，所以周转仍为12 ms。
阻塞更久不等于就绪等待更久。

判分要点

须剔除I/O阻塞，不能把全部未运行时间算等待。
须区分首次CPU响应与最终完成。
须正确预测修改后等待1 ms、周转12 ms。

各算法怎样选人¶

算法	选择规则	主要限制
FCFS	先进入就绪队列者先服务	长任务可能挡住短任务，形成护航效应
SJF	选择下一段CPU最短者，非抢占	需要估计未来CPU长度，长任务可能饥饿
SRTF	选择剩余CPU最短者，可抢占	新到短任务会触发重新比较
优先级	选最高优先级，可抢占或非抢占	低优先级可能饥饿，可用等待老化改善
RR	队首运行至多一个时间片，再轮转	片太长接近FCFS，太短增加切换成本
HRRN	非抢占，选响应比最高者	兼顾等待和服务长度

HRRN的响应比 \(R=(W+S)/S=1+W/S\)，\(W\) 是当前等待时间，\(S\) 是预计服务时间，二者单位相同；每次做选择时重算。它与首次响应时间不是一个量。

同在0时到达、CPU分别需6、2、1毫秒的A、B、C，FCFS按A、B、C运行，等待为0、6、8；SJF按C、B、A运行，等待为0、1、3，平均更小。

但SJF的优势依赖该批任务和已知长度等模型条件。

甘特图按事件画¶

甘特图用横轴表示时间，在每一段标出谁占用CPU。画图无需逐毫秒猜测，采用“跳到下一个事件”的方法：

列当前就绪队列与每个任务剩余CPU量。
按算法选运行者，并求它最早可能结束、阻塞或耗尽时间片的时刻。
若中途有任务到达或I/O完成，先推进到那个事件；抢占式算法此时重新选择。
更新CPU剩余量与队列，再重复。

例子与推演

例如RR中，一个任务剩3 ms、时间片2 ms，最多先运行2 ms，剩1 ms后回队；若只剩1 ms，就在1 ms后完成CPU段，不再因时间片还有余量继续占着CPU。

每走一步写清“时刻、就绪队列、当前CPU剩余量、下一事件”。下一事件可能是到达、I/O完成、CPU段结束或时间片用尽。同刻谁先入队、是否计算切换耗时，必须先用题目约定。

例子与推演

例：RR时间片2毫秒；A于0到达，需CPU 2→I/O 2→CPU 1；B于0到达，需CPU 4；C于2到达，需CPU 1。A先于B，同刻新到达和I/O完成先入队，再放回片耗尽者。

CPU区间/ms	原因
A：0—2	CPU段完成，去做I/O 2—4
B：2—4	C在2时排到B后面
C：4—5	4时队列为C、A、B
A：5—6	完成最后1毫秒
B：6—8	完成剩余2毫秒

A等待1毫秒，B等待4毫秒，C等待2毫秒。核对各任务CPU段总量，再按各自到达时间计算指标。CPU段完成与时间片结束同刻时，已完成的段不能再错误入队。

练习 2¶

题目

自编题：单CPU，RR时间片2 ms，切换耗时0。A于0到达：CPU 2→I/O 2→CPU 1。B于0到达：CPU 4；C于2到达：CPU 1。0时A先于B；I/O立即开始且无设备排队。同刻新到达和I/O完成先入队，再入片耗尽者；CPU段完成优先于片耗尽。所有区间左闭右开。

① 画CPU时间线，写出4 ms处的就绪队列。
② 求A、B、C各自的就绪等待和响应时间。

参考解答

解答

CPU：A 0—2；
B 2—4；
C 4—5；
A 5—6；
B 6—8。
A的I/O为2—4。
2时A完成CPU段，进入I/O而非重复入队，队列B、C。
4时原队列C；
A先回队，B后回队，所以选择前队列C、A、B。
等待：A等4—5，为1 ms；
B等0—2及4—6，为4 ms；
C等2—4，为2 ms。
响应：A为0，B为2，C为2 ms。
周转核对A为6，B为8，C为3 ms。

判分要点

须得到C、A、B的4 ms队列及完整甘特图。
须把A的2 ms I/O排除在就绪等待外。
须按各自到达时刻计算响应，而非直接抄首次时刻。

预测与反馈队列¶

老化逐渐提高长期等待者的优先级，用于缓解饥饿；反馈根据任务表现调整它所在队列，用于兼顾交互任务与长计算。二者都要有明确更新规则。

解反馈队列题可为每个任务加两栏：“任务还需CPU多少”和“这一层还允许用多少”，每执行1 ms两栏同时减1。

下一段CPU长度常用指数平均估计：

\[\tau_{n+1}=\alpha t_n+(1-\alpha)\tau_n.\]

\(t_n\) 为本段实际耗时，\(\tau_n\) 为旧预测，\(0\le\alpha\le1\) 决定重视新数据的程度。旧预测6、实际2、权重0.5，得到新预测4毫秒；预测不保证未来真实值就是4。

多级队列把任务固定分组；
多级反馈队列（MLFQ）允许任务在层间移动。
例如新任务进高层，用完配额降层；
高层到达可抢占低层，长期等待者周期提升。
做题必须分别记录CPU剩余量与本层剩余配额，并按题意决定阻塞或抢占后是否重置，不能默认“每回来就拿全新配额”。

练习 3¶

题目

自编题：突发预测用新值=0.5×实际值+0.5×旧值。旧预测6 ms，本次实际2 ms。MLFQ另独立计算：Q0配额2，Q1配额4 ms；先选高队列，同层FIFO，全部任务无I/O。新任务进入Q0，可抢占Q1；被抢占者保留配额，留在Q1队首；用完Q0配额者降至Q1队尾。同刻先加入新任务，再处理配额耗尽者；CPU段完成优先于配额耗尽，切换成本0。A于0到达需CPU 6，B于3到达需CPU 1 ms。

① 求新预测，说明预测是否等于已知真实未来。
② 列CPU区间、队列层级和A被抢占后的剩余配额。

参考解答

解答

新预测0.5×2+0.5×6=4 ms；
它是历史加权估计，不保证下一段真实长度为4。
A在Q0运行0—2，剩CPU 4，降至Q1。
A在Q1运行2—3，剩CPU 3、配额3。
B进入Q0，抢占A并运行3—4后完成。
A从Q1恢复4—7，用剩余配额3并完成。
不能在3时重置A的配额，也不必退回Q0。
总CPU时间6+1=7 ms，无空闲。

判分要点

正确代入预测，并指出估计不等于真实未来。
区间与Q0/Q1对应，3时抢占由高队列触发。
保留A剩余配额3，7时完成不再错误重排队。

多核与实时约束¶

多核调度要平衡负载，也要考虑CPU亲和性：尽量留在原核运行可复用缓存，迁移则有机会消除某核忙、某核闲。

NUMA（非统一内存访问）机器上，CPU访问本地内存和远端内存的成本不同，因此只平衡任务数量未必足够。

实时调度中，EDF优先最早截止者；
周期任务的速率单调策略给周期较短者更高固定优先级。
需逐个检查完成时刻是否超过截止期。
A需2毫秒、截止3，B需1毫秒、截止1，均在0到达，排B 0—1、A 1—3可满足；
先完整执行A会让B迟到。

低优先级L持锁，高优先级H等锁，中优先级M不断抢占L，会造成优先级反转。

优先级继承让L临时获得H的优先级，先运行到解锁；它不允许H绕过互斥，也不保证任何负载下都能按时完成。

评价方案还要比较吞吐量、平均等待、最坏响应、公平性与切换成本，不能只看一项。

练习 4¶

题目

自编题：独立场景一：2核，四个任务均需CPU 3 ms。初始核0排三个，核1排一个；不可并行拆任务。忽略迁移开销，两核同时开始、各自FCFS。

① 不迁移与开始前迁移一个到核1，各自最晚完成时刻是多少？场景二：单CPU，任务均0时到达，可抢占。A需2 ms、截止3；B需1 ms、截止1。
② 给能满足截止期的时间线；A先能否满足？
③ 低优先级L持锁，高优先级H等锁，中优先级M一直抢占L，优先级继承改变什么？

参考解答

解答

不迁移负载9与3 ms，最晚完成9 ms。
迁移后两核负载6与6 ms，最晚完成6 ms。
实时场景：B 0—1，A 1—3，均按时完成。
若A先运行0—2，再B 2—3，B错过截止1。
优先级继承让持锁L临时继承H的优先级，避免M继续把L压住，使L有机会完成并解锁。
继承不允许H在L释放前破坏互斥直接进临界区；
也不单独保证任何负载下都满足全部截止期。

判分要点

按每核总负载算最后完成，不能除以任务数。
分别比较每个任务的完成时刻与截止期。
明确提升持锁者而非跳过锁，并保留保证边界。

记忆要点¶

本章记忆要点

调度只从就绪任务中选择；I/O未完成者仍在阻塞。
响应看首次CPU，周转看到达至完成，等待只加就绪队列时间。
每次只推进到下一个事件，同刻入队顺序先按题设确定。
RR记剩余CPU与时间片；MLFQ还要记所在层和剩余配额。
实时逐任务核对截止期；优先级继承提升持锁者，帮助它尽快解锁。