第3章笔记：CPU调度：从队列到响应时间

本章问题

会画甘特图、计算指标并解释交互、公平和吞吐之间的冲突。 本章不是七个术语的并列清单，而是一条从可观察现象到内部状态、从内部状态到工程证据的因果链。学习时始终标出对象身份、队列或表项、触发事件、权限边界和不可破坏的不变量。

七节机制连接

• 调度层次与评价指标：长期、内存与短期调度控制进入系统、驻留集合与CPU选择；指标需区分周转、等待、响应和吞吐；实验入口为对三个到达时间不同的作业画就绪队列，逐项计算首次响应、完成、等待与带权周转；反查边界是平均值会掩盖饥饿与尾部；CPU利用率高也可能伴随交互响应极差。
• FCFS与护航效应：先来先服务简单且非抢占，但长作业可让短作业整体排队；实验入口为对到达/服务时间(0,8),(1,2),(2,1)画甘特图并计算平均等待；反查边界是FCFS中的先来按到达就绪队列定义，不是按进程编号；I/O返回会重新排队。
• SJF、SRTF与长度预测：短作业优先最小化已知服务时间下的平均等待，抢占版本在新短任务到达时重新选择；实验入口为用指数平均预测下一CPU burst，比较预测误差如何改变SRTF决策；反查边界是真实系统不知道未来长度；长期任务可能饥饿，需要老化或服务保证。
• 时间片轮转与交互权衡：RR按时间片轮换就绪任务，时间片小改善首响却增加切换，过大则退化为FCFS；实验入口为固定上下文切换0.2ms，对1、4、20ms时间片计算有效CPU比例与响应序列；反查边界是到达事件与时间片结束同刻时必须声明入队规则，否则答案不唯一。
• 优先级、多级反馈与公平：动态优先级和多级反馈用行为近似任务类型，老化抑制长期饥饿；实验入口为推演CPU密集任务与交互任务在三层队列中的升降级，并检查每个任务的最长等待；反查边界是优先级反转不是普通饥饿；共享锁会让高优先级任务等待低优先级持锁者。
• 实验：FCFS与SJF指标比较：调度模拟器必须显式处理到达、空闲、选择和完成四类事件；实验入口为输入若干到达/服务时间，分别输出FCFS与非抢占SJF平均等待时间；反查边界是服务时间相同时需稳定定义到达与编号次序，空闲区间不能算作某进程等待。
• 实验：RR甘特图模拟：离散事件循环维护当前时刻、就绪队列、剩余时间和新到达任务；实验入口为输入进程到达、服务与时间片，输出执行片段序列以及每个进程完成时刻；反查边界是先处理片段内到达再决定重排；零服务任务与同刻到达必须有明确规则。

请给七节画依赖箭头：前一节留下的状态或接口怎样成为下一节输入？每条箭头补单位、事件或保护条件。若任何一节可以随意搬走且不影响上下文，说明你还没有建立章内联系。

章内实验

选择本章至少一个代码实验，从空环境运行全部内联测试，再新增一个资源耗尽、非法迁移、同刻事件或崩溃输入。保存输入、输出、参考模型、首个偏差和修复后的回归证据。不可复现的睡眠竞态或人工截图不算实验结果。

错题闭环

把错误编码为对象混淆、状态跳步、单位错误、队列顺序、竞态遗漏、权限越界或恢复假设。不要只写粗心。一周后更换数字和事件顺序重做阶段卷；能在新输入下重建机制而非记住答案，才算迁移成功。