返回学习路线

十六毫秒CPU工作怎样分 ​

同一批工作，换一个派发次序就能让某些任务更早完成；让每人更早第一次运行，又可能推迟平均完成时间。这份任务要求画出执行轨迹、逐项核对服务守恒，再决定哪些保证依赖信息、成本或公平假设。最后用同一3:2:1权重比较随机抽签与确定步幅。

入口与可达到的终点 ​

先读上下文切换理路上下文切换与线程派发Context switch and dispatch · Ready running blocked用就绪、运行、阻塞三态解释CPU执行权交接，逐步核对用户trap frame、内核续点和地址空间恢复。理解READY、RUNNING与BLOCKED，再从服务账本理路CPU服务、就绪与时间账本CPU service accounting · CPU burst · Ready time · Preemptive scheduling model用实际服务量、剩余量和就绪等待刻画单核调度，固定同刻事件顺序，并把墙钟时间分成运行、阻塞和等待。、指标理路周转、响应与CPU利用率CPU scheduling metrics · Turnaround time · Scheduling response time · CPU utilization从同一执行轨迹分别计算完成、首次派发、就绪等待与整机吞吐，说明平均值、尾部与忙碌口径不能互相替代。进入FIFO/SJF理路FIFO与最短作业调度FIFO CPU scheduling · FCFS scheduling · Shortest job first · SJF · Shortest processing time用同一到达表比较FIFO与非抢占SJF，通过相邻交换证明同到达批作业的最短优先最优性，并给出晚到任务的边界。、SRTF理路最短剩余时间与到达时抢占Shortest remaining time first · SRTF · Shortest remaining processing time · SRPT · Shortest time-to-completion first · STCF每次到达或完成时选择剩余CPU服务最少者，逐段复算抢占轨迹，并用交换论证和持续短作业反例界定最优性与饥饿。、RR理路轮转时间片与切换成本Round-robin scheduling · RR scheduling · Time quantum · Time slicing按FIFO轮流交付有界时间片，复算到达与重排的同刻边界，并在有明确切换成本时核对响应上界和有效利用率。与MLFQ理路多级反馈队列与累计配额Multilevel feedback queue · MLFQ · Priority boost · CPU allotment让新任务从高优先级开始，按各层实际累计CPU服务降级，保留阻塞前的用量，并用明确boost规则追踪行为变化与饥饿边界。。比例份额分支是彩票理路彩票调度与随机服务份额Lottery scheduling · Proportional-share lottery scheduling · Lottery tickets用均匀抽签把正权重转成时间片选择概率，精算有限样本服务份额和连续未中签概率，区分概率无饥饿与确定等待界。和步幅理路步幅调度与虚拟服务账本Stride scheduling · Proportional-share stride scheduler · Virtual pass按票数倒数设置步幅，每次运行最小pass者并按实际服务推进，复算十二片序列，证明固定成员下的有界虚拟差并说明加入和短片边界。；概率计算可按需回读二项分布理路二项分布Binomial distribution固定次数独立同概率 Bernoulli 试验中成功总数的离散分布。，无需先把整条概率论路线走完。

完成后应能独立产出四份可检查结果：五种政策的时间线和逐任务指标；加入切换费用后的新账本；累计配额与boost的反例；12次彩票和stride的精确服务数。只复述算法名称不算到达终点。

固定输入与允许的动作 ​

SCHED-16为单核、单位服务速率。A、B、C、D的（到达时刻，CPU需求）依次是 $(0,9),(1,4),(2,2),(4,1)$，均无I/O、无锁、无迁移；时间单位毫秒。主线忽略切换成本，任务需求总和为16。

同一边界先结算运行并移除完成者，随后新到达者按名字入队，最后才重排时间片用尽的当前任务。FIFO与SJF不抢占；SJF只看已经到达者。SRTF每次到达和完成时选择剩余最少者，最小值相等时保留当前任务。RR时间片为2。

MLFQ固定Q0/Q1/Q2，时间片2/4/8，前两层累计配额2/4，底层轮转不再降级；新任务入Q0。12时刻结算后，全体未完成任务提升Q0并清零层/片用量，可运行者按任务名重排，总服务不重置。本文题目所需的boost只有这一处。

A. 用同一指标比较五种政策 ​

1. 画FIFO、SJF、SRTF、RR、MLFQ完整时间线；每段写起止时刻
2. 对A、B、C、D分别给首次运行 $F$、完成 $C$、周转 $T=C-a$、首次响应 $R=F-a$、就绪等待 $W=T-b$
3. 计算五种政策平均周转、平均响应和最大就绪等待。哪种在这个样本上最小化平均周转？这是否意味着每个任务都更早完成？
4. 解释为什么主线五种政策都在16完成全部工作，而此事实本身不能证明任何一种次序正确

B. 让交接真正收费 ​

RR仍用2毫秒片；每次从不同任务切到另一项收0.25毫秒；首次启动和继续同一任务免费，最终退出不收费。派发目标在切换开始时固定，期间新到达者进队尾。

1. 重画全部交接区间，算最终时刻、开销总和、有用利用率
2. 13和15附近只剩A时，为什么不能仅因时间片边界就多收一次不同任务交接费？
3. 长期每片跑满且必换人的近似公式 $q/(q+c)$，为什么不等于本次有限实验的利用率？

C. 三个容易被名字掩盖的错误 ​

1. SRTF在1暂停A后，若在8恢复时把A重新设为需要9，会违反哪项不变量？
2. Q0片长2、层配额4。G每次运行1.5后短暂阻塞。写出第三次运行最多还能在Q0使用多久，解释“每次I/O后层用量归零”的后果
3. 两个始终可运行的任务A、B，Q0片长2，boost周期1且每次按名字重排。给出前4毫秒轨迹，判断“有周期boost就不会饥饿”是否成立

D. 同一权重，两种服务合同 ​

另取三个始终可运行的长任务A、B、C，票数3、2、1，完整片长1且零费用，不与前面的有限任务生命周期混用。

彩票票区间为A:0–2、B:3–4、C:5；输入票序列为 $0,5,2,3,1,0,4,2,5,0,1,3$。映射出胜者、服务量和对理想份额的偏差；计算C连续12次未中的概率。至少多少次独立抽签，才能让C至少中一次的概率达到95%？

Stride取 $K=6$，步幅2、3、6，初始pass也是2、3、6，每次取最小pass并按A/B/C打破并列，运行后给胜者加其步幅。写前12次胜者和最后pass；再判断“每5片都精确按3:2:1分配”为什么不可能。

E. 迁移：只改一个参数 ​

把RR的时间片从2改为1，仍用SCHED-16、零开销和同刻次序。先自己预测平均首次响应、平均周转会不会都下降，再重画时间线。不要从“片更短”直接推出两项都改善。

答案与核验 ​

A：先保留每个人，再算平均 ​

• FIFO：A0–9，B9–13，C13–15，D15–16
• SJF：A0–9，D9–10，C10–12，B12–16
• SRTF：A0–1，B1–2，C2–4，D4–5，B5–8，A8–16
• RR：A0–2，B2–4，C4–6，A6–8，D8–9，B9–11，A11–16；A末段内部片边界13、15
• MLFQ：A0–2，B2–4，C4–6，D6–7，A7–11，B11–12，A12–14，B14–15，A15–16

以下向量均按A、B、C、D排列。

政策	首次运行 $F$	完成 $C$	周转 $T$	响应 $R$	等待 $W$
FIFO	(0,9,13,15)	(9,13,15,16)	(9,12,13,12)	(0,8,11,11)	(0,8,11,11)
SJF	(0,12,10,9)	(9,16,12,10)	(9,15,10,6)	(0,11,8,5)	(0,11,8,5)
SRTF	(0,1,2,4)	(16,8,4,5)	(16,7,2,1)	(0,0,0,0)	(7,3,0,0)
RR	(0,2,4,8)	(16,11,6,9)	(16,10,4,5)	(0,1,2,4)	(7,6,2,4)
MLFQ	(0,2,4,6)	(16,15,6,7)	(16,14,4,3)	(0,1,2,2)	(7,10,2,2)

政策	平均周转	平均首次响应	最大就绪等待
FIFO	11.5	7.5	11
SJF	10	6	11
SRTF	6.5	0	7
RR	8.75	1.75	7
MLFQ	9.25	1.25	10

SRTF在样本上平均周转最小，但A比FIFO晚7毫秒完成。所有主线在16完成，是因为服务需求16、单位速率、一直有可运行者、零开销且均工作保守。把所有工作排成另一条非法的“最短剩余”轨迹，也可能仍符合总量16，因此还须逐边界检查政策。

B：六次不同任务交接 ​

交接发生在2–2.25、4.25–4.5、6.5–6.75、8.75–9、10–10.25、12.25–12.5；任务运行与RR页一致。总开销为1.5，终点17.5，有用利用率 $16/17.5=32/35\approx 91.43\mathrm{\%}$。

最后A连续交付5毫秒，不因片边界变成不同任务交接。周期近似 $2/2.25=8/9$ 假设每片满且每片换人，本实验含D短片、首次免费和A独占尾段，所以分母不同。

C：政策计数与实际服务分开 ​

A在0–1已经取得1，恢复时只剩8；设回9会让它最终累计取得10，违反 $s_A+r_A=b_A=9$。这不是换一个调度次序能修复的误差。

G两次已累计3，第三次只许再用1，然后降级。阻塞时清零层用量会让它反复把连续服务切短，永不触及累计配额。

过密boost反例是A0–1、A1–2、A2–3、A3–4，B始终READY。每次重新按名字排序都把A放前面，有限两个任务也可能受饿。这个错误依赖明确的重排次序，不能用另一种保持队列次序的boost实现替它辩护。

D：一个是样本，一个是确定账本 ​

彩票胜者为A、C、A、B、A、A、B、A、C、A、A、B。服务7、3、2，理想6、4、2，偏差+1、−1、0。$\text{Pr}(C\text{前12次均未中})=(5/6{)}^{12}\approx 0.11216$；16次仍约0.05409未中，17次降至约0.04507，所以95%阈值是17次。不能把概率阈值说成确定等待界。

Stride胜者为A、B、A、A、B、C、A、B、A、A、B、C。服务6、4、2，最终pass14、15、18。第5片后服务3、2、0；5片的理想份额 $2.5,5/3,5/6$ 含非整数，单片不可分时本来就无法恰好实现。

E：更早开始，未必更早完成 ​

$q=1$时胜者逐毫秒为A、B、A、C、B、A、D、C、B、A、B、A、A、A、A、A。首次运行0、1、3、6，平均首次响应 $(0+0+1+2)/4=0.75$；完成16、11、8、7，周转16、10、6、3，平均仍为8.75。C更晚、D更早，平均周转的变化恰好抵消。

可执行复算与证据范围 ​

下载Python标准库复算脚本。运行后打印完整JSON时间线、逐项指标、彩票/stride表和断言结果，不需要网络或第三方包，不会修改文件。

脚本对256组四任务同时到达时长枚举全部排列验证SJF；对729组三任务整数到达/时长用独立动态规划枚举单位时间调度，验证SRTF总周转最优；对125组权重各运行1000片检查stride虚拟差不变量。有限检查能捕捉实现和算例错误，不能替代正文对任意输入的证明。

所有主实验均是教学模型，未在Linux或其他内核里运行，也没有以基准测试证明某种真实调度器普遍更快。参考原始算法和教材的精确章节列在八个条目末尾。