进程调度这道题我在操作系统课上做过一遍后来给下一届当助教批改又看了几百份最直观的感受是同一张进程表、同一套算法名称最后交上来的答案能有三四种。有人算出平均周转时间 8.75有人算出 9.0还有人算出 6.75而且每个人都能把自己的推导过程写得头头是道。问题往往不出在公式上而出在几条规定从来没被写下来——时间片用完的那一刻和新进程到达的那一刻撞在一起谁先进就绪队列抢占是发生在到达瞬间还是下一个时间片边界这些细节一旦含糊整道题的结果就全歪了。这篇就把课堂练习 3.3进程的调度这类练习从头到尾拆一遍。我会用一张固定的样例进程表把先来先服务、短作业优先、最短剩余时间优先、时间片轮转、优先级调度这几种算法的完整推演过程走一遍每一步的算式都摊开写中间那些教材上往往一笔带过的约定我会单独拎出来讲清楚。不管你是正在赶这份作业的学生还是想重新捡起操作系统基础的人只要跟着算一遍后面遇到同类题目基本就不会再翻车。1. 一道调度题为什么能算出四五种答案先厘清考核口径批改时我见过最离谱的一份卷子前面 FCFS 算得完全正确到时间片轮转那一栏四个进程的完成时间写成了一串杂乱无章的数字问他怎么来的说感觉应该是这个顺序。这种感觉式演算在调度题里几乎必然出错因为进程调度本质上是一个带约束的状态推进过程每一步的选择都由前一步的结果决定中间少考虑一个到达事件后面全盘皆错。想算对第一步不是急着画时间轴而是把题目里那几个关键字翻译成精确的数学定义。1.1 三个时间量把文字描述压成可计算的数字调度题里翻来覆去就是三个量到达时间、服务时间、完成时间。到达时间是进程进入就绪队列的时刻服务时间是它需要占用处理器的总时长完成时间是它最后一次释放处理器的时刻。这三个量本身没有歧义但由它们派生的两个指标经常被写反周转时间 完成时间 − 到达时间带权周转时间 周转时间 ÷ 服务时间等待时间 周转时间 − 服务时间周转时间的物理含义是从进程进入系统到离开系统一共花了多久注意它包含了进程实际在处理器上跑的时间和它排队等待的时间。带权周转时间则是把周转时间对服务时间做了归一化一个服务时间 1 个时间单位却等了 3 个时间单位才完成的进程带权周转时间是 3而一个服务时间 100 个时间单位、周转时间 105 的进程带权周转时间只有 1.05。带权周转时间衡量的是相对被耽误的程度不是绝对时长这一点是后面判优的核心依据。提示等待时间和周转时间的换算关系是 周转 − 服务不是 服务 − 周转我批改时大概每十份就有一份写反方向导致出现负数的等待时间自己都没察觉。1.2 周转时间与带权周转时间谁才是判优标准课本上评价调度算法优劣时给的指标通常是平均周转时间和平均带权周转时间两个很多同学默认后者只是前者的补充随便挑一个算完就交。实际上这两个指标的导向完全不同会给出相反的结论。设想两个进程 A 和 BA 服务时间 1、周转时间 10B 服务时间 50、周转时间 55。按绝对周转时间看A 拖了后腿10 对 1按带权周转时间看A 是 10B 只有 1.1A 才是真正的受害者。现实中我们更关心的是带权周转时间因为它直接反映了用户的主观感受——打开一个需要 0.1 秒响应的操作却卡了 3 秒比一个本来就要跑一分钟的任务多花 5 秒要难受得多。所以练习里如果没指定我一般两个都算并且在结论里以带权周转时间为主。1.3 抢占与非抢占一句约定改写全部结果抢占式和非抢占式的差别只在一个新进程到达时是否允许把它正在运行的进程踢下去这一句上但对结果的影响是决定性的。非抢占式调度里一旦某个进程拿到了处理器它会一直跑到结束或者主动让出中途来的进程再紧急也得排队抢占式调度则允许调度器在任意时刻重新做选择。最短剩余时间优先SRTF就是最短作业优先SJF的抢占版本两者面对同一张进程表平均周转时间往往能差出一个数量级。判定标准很简单新到达进程的剩余服务时间是否小于当前运行进程的剩余服务时间小于就抢不小于就等。这里的关键词是剩余不是原始很多同学拿新进程的服务时间去和当前进程的原始服务时间比这是最容易出错的一个点。优先级调度同理抢占版本要在每个到达事件发生时检查优先级高低非抢占版本只在进程结束时才重新选。2. 演算前的准备工作进程表、时间轴与约定准备工作做扎实后面能省一半时间。我习惯先把题目给的进程表原样抄一遍然后在下面另起一行手写出适用于这道题的三条约定写在纸上就不会中途忘记。这一步看起来多余实际上批改时答案出错的卷子有相当比例是因为自己定的规则和后面用的规则不一致——比如一开始说同一时刻新到达的先入队算到一半又按被抢占的先入队处理了。2.1 贯穿全篇的样例进程表为了让几种算法能横向对比后面所有推演都用这同一张表四个进程到达时间和服务时间各不相同覆盖了同时到达中途密集到达短作业与长作业混杂这几种典型情况。进程到达时间服务时间P107P224P341P454这张表的总服务时间是 7414 16 个时间单位也就是说无论用哪种算法最后一个进程的完成时间都不会早于 16。这个下界很有用算完之后可以拿它做个粗略校验——如果算出来的最大完成时间小于 16那一定是哪里少跑了时间比如漏掉了某个进程的执行段或者把两个进程的执行时间当成并行处理了。P3 的服务时间只有 1是整个表里最短的作业它会在 SJF 和 SRTF 里被优先照顾在 RR 里则要看运气。2.2 用甘特图代替公式推导我强烈建议手算时直接画时间轴不要一上来就套公式。做法是画一条横轴从 0 开始按时间单位刻度每确定一个进程的运行区间就在轴上画一段方块并标注进程号。以 FCFS 为例轴上的方块依次是 P1 占 0 到 7、P2 占 7 到 11、P3 占 11 到 12、P4 占 12 到 16一眼就能看出哪段处理器是空闲的、哪段被谁占用。画完轴之后每个进程的完成时间就是从它方块右端读出来的数字周转时间用完成时间减到达时间即可。这种方式比列一堆不等式快得多而且错不了——因为每个时间点只有一种状态方块之间的接缝天然保证了时间不会重叠也不会跳空。我后来带过的学生里凡是坚持画时间轴的错误率比直接写公式的低一大截。2.3 三条必须先写下来的约定结合上面那张表我会在草稿纸顶部固定写下这三条新到达的进程在到达当刻进入就绪队列即使此刻处理器正忙。时间片用完与新进程到达撞在同一时刻时新到达的进程先入队被剥夺的进程后入队尾。进程在时间片内提前完成立即触发一次调度不必等到时间片耗完。第 2 条是整篇里最关键的一条约定不同教材对它的处理并不一致有的把被剥夺的进程放在前面。这不代表谁对谁错而是说明做题前必须确认老师或者教材用的是哪一套。下面第 4 章我会用同一张表、仅仅把这条约定反过来演示结果会差多少。3. 先来先服务、短作业优先与最短剩余时间优先这三种算法放在一起讲是因为它们共享同一个决策逻辑——在某个时刻从就绪队列里挑一个进程区别只在于挑谁和什么时候挑。先把非抢占的两个算清楚再引入抢占机制理解起来会顺很多。3.1 FCFS顺序执行下的等待堆积先来先服务就是严格的队列谁先到谁先跑跑完再轮到下一个。按样例表走时刻 0 只有 P1 到达它跑满 7 个时间单位到时刻 7 结束时刻 7 时 P2、P3、P4 都已经到达按到达顺序排P2 先跑 7 到 11接着 P3 跑 11 到 12最后 P4 跑 12 到 16。进程完成时间周转时间带权周转时间P1771.000P21192.250P31288.000P416112.750平均周转时间 (79811) ÷ 4 8.75平均带权周转时间 (1.02.258.02.75) ÷ 4 3.5。注意 P3 的带权周转时间高达 8.0它只干 1 个单位的活却等了 8 个单位。这就是 FCFS 最典型的问题长作业在前面的时候后面所有作业都要陪着等服务时间短的作业受害最重。批改时我会特别看这一行几乎所有人的 P3 带权周转时间都算得出来但很多人不做任何评论其实这里正是引出 SJF 的最佳切入点。3.2 非抢占 SJF一次选择全局受影响短作业优先的规则是每次选择服务时间最短的进程。非抢占版本只在当前进程结束、需要重新选人时才做决定。时刻 0 只有 P1 可运行所以尽管 P1 是表里最长的作业之一也只能让它先跑——这一点很多同学第一次会困惑以为 SJF 应该跳过 P1实际上调度器没有预知未来的能力它只能在当前已经到达的进程里挑。P1 跑到时刻 7 结束此时就绪队列里有 P2还需 4、P3还需 1、P4还需 4。选最短的 P3跑 7 到 8 结束。时刻 8 就绪队列里剩 P2 和 P4服务时间都是 4这时候需要一个次级规则通常按到达时间早的先来P2 在时刻 2 到达、P4 在时刻 5 到达所以 P2 先跑 8 到 12P4 最后跑 12 到 16。进程完成时间周转时间带权周转时间P1771.000P212102.500P3844.000P416112.750平均周转时间 (710411) ÷ 4 8.0平均带权周转时间 (1.02.54.02.75) ÷ 4 2.5625。对比 FCFS平均周转时间降了 0.75平均带权周转时间从 3.5 降到 2.56改善相当明显主要功劳就是 P3 从等 8 个单位变成等 3 个单位完成。注意时刻 8 那个次级规则必须写出来。P2 和 P4 服务时间相同如果按进程号排序会得到同样的结果但如果题目里 P4 的到达时间更早结果就会变。规范的做法是明确注明服务时间相同时按到达时间先后或者干脆照抄题目给出的次序。3.3 SRTF抢占版本把平均周转压到最低最短剩余时间优先是 SJF 的抢占版每个到达事件发生时都要检查一遍。推演过程比前两个复杂但逻辑是一致的。时刻 0P1 开始运行剩余 7。时刻 2P2 到达服务时间 4而 P1 还剩 5从 0 跑到 2已经消耗 24 小于 5P2 抢占P1 被挂起。P2 从 2 跑到 4消耗 2还剩 2。时刻 4P3 到达服务时间 1小于 P2 剩余的 2P3 抢占。P3 从 4 跑到 5 结束周转时间 5−4 1带权 1.0。时刻 5P4 到达服务时间 4。此刻就绪队列里有 P1剩余 5、P2剩余 2、P4剩余 4。最小的是 P2 的 2P2 从 5 跑到 7 结束周转时间 7−2 5带权 5÷4 1.25。时刻 7比较 P1剩余 5和 P4剩余 4选 P4P4 从 7 跑到 11 结束周转 11−5 6带权 6÷4 1.5。最后 P1 从 11 跑到 16周转 16−0 16带权 16÷7 ≈ 2.286。进程完成时间周转时间带权周转时间P116162.286P2751.250P3511.000P41161.500平均周转时间 (16516) ÷ 4 7.0平均带权周转时间 (2.2861.251.01.5) ÷ 4 ≈ 1.509。这是四种算法里带权周转时间最低的代价是 P1 从原本 7 个时间单位完成被拖到了 16 个。SRTF 优化的从来不是单个进程的体验而是全体进程的平均值这一点在做题时要心里有数现实中的调度器也很少敢这么激进因为长作业被无限推迟会带来别的麻烦。3.4 三种结果摆在一起看把三组数据并排放在一张表里结论会清晰很多算法平均周转时间平均带权周转时间明显受益者明显受害者FCFS8.753.50P1P3非抢占 SJF8.002.56P3P1、P4SRTF7.001.51P2、P3P1能看出来一个规律带权周转时间对短作业特别敏感。P3 这种服务时间为 1 的进程只要让它多等 1 个时间单位带权周转时间就增加 1对整个平均值的影响远大于让 P1 多等 1 个单位。所以任何优先照顾短作业的算法在平均带权周转时间这个指标上都占便宜。理解这一点之后再看时间片轮转为什么表现平平就顺理成章了。4. 时间片轮转的推演细节与代码对照时间片轮转Round RobinRR是练习里丢分最集中的一块没有之一。FCFS 和 SJF 只要算得慢一点基本不会错RR 不一样它对就绪队列的维护顺序要求非常严格队列里少一个元素、多一个元素、顺序反一下最后四个进程的完成时间就全变了。4.1 就绪队列的维护是全部难点所在RR 的核心机制是把就绪进程排成一个循环队列调度器每次从队头取一个进程给它一个时间片 q 的处理器时间。如果它在 q 内跑完了直接离队如果没跑完它被剥夺处理器重新排到队尾等前面所有进程都轮一遍再回来。这里有几个必须在纸上写死的操作细节入队时机进程到达时进入队尾还是立刻抢占当前进程标准 RR 是非抢占的新到达的进程只入队不影响当前正在跑的进程当前进程的时间片用完了才切换。被剥夺进程的入队位置时间片用完的进程放队尾这一点没有争议。新到达进程与被剥夺进程的先后这两个动作如果发生在同一时刻顺序就需要明确约定前面第 2.3 节我选的是新到达的先入队。提前完成的处理进程在时间片内跑完立刻释放处理器从队头取下一个不需要等当前时间片走完。这四条里第三条是分歧最大的。我见过至少两种主流处理方式而且都能说得通关键在于前后一致。4.2 q2 的完整时间轴推演设时间片 q 2按第 2.3 节的约定新到达的先入队、被剥夺的后入队完整过程如下。时刻 0就绪队列只有 P1取 P1 运行。P1 从 0 跑到 2消耗 2剩余 5。此刻 P2 到达先入队P1 剩余 5后入队尾。队列变成 [P2, P1]。时刻 2取队头 P2 运行从 2 跑到 4消耗 2剩余 2。此刻 P3 在时刻 4 到达先入队P2 剩余 2后入队尾。队列从 [P1] 变成 [P1, P3, P2]。时刻 4取队头 P1 运行从 4 跑到 6消耗 2剩余 3。注意这里 P1 又被选中了因为它一直排在队列里而 P3 在它后面。此刻 P4 在时刻 5 到达需要入队队列先是 [P3, P2]加入 P4 后是 [P3, P2, P4]再把 P1 放队尾变成 [P3, P2, P4, P1]。时刻 6取队头 P3 运行服务时间只有 1从 6 跑到 7 就结束了完成时间 7周转时间 7−4 3带权 3.0。此刻没有新进程到达队列是 [P2, P4, P1]。时刻 7取队头 P2 运行剩余 2从 7 跑到 9 结束完成时间 9周转 9−2 7带权 7÷4 1.75。队列变成 [P4, P1]。时刻 9取 P4 运行从 9 跑到 11消耗 2剩余 2。队列变成 [P1, P4]。时刻 11取 P1 运行从 11 跑到 13剩余 1。队列变成 [P4, P1]。时刻 13取 P4 运行剩余 2从 13 跑到 15 结束完成时间 15周转 15−5 10带权 10÷4 2.5。队列只剩 [P1]。时刻 15取 P1 运行剩余 1从 15 跑到 16 结束完成时间 16周转 16带权 16÷7 ≈ 2.286。进程完成时间周转时间带权周转时间P116162.286P2971.750P3733.000P415102.500平均周转时间 (167310) ÷ 4 9.0平均带权周转时间 (2.2861.753.02.5) ÷ 4 ≈ 2.384。4.3 换一条入队规则答案立刻不同现在把第 2.3 节的第 2 条约定反过来被剥夺的进程先入队新到达的后入队。只改这一条时刻 4 的队列就从 [P1, P3, P2] 变成 [P1, P2, P3]等等这样 P2 反而跑得更早也不对。真正的分歧点在时刻 4 的新到达 P3 和刚用完时间片的 P2 谁先两种规则给出的队列分别是 [P1, P3, P2] 和 [P1, P2, P3]P1 因为在时刻 2 就排在队里所以始终在第一位。按第二种规则继续推队列顺序不同后面的完成时间会整体偏移最终 P3 的完成时间可能从 7 变成 12带权周转时间从 3 变成 8。四个进程的平均带权周转时间会从 2.384 变成 3.1 左右。这中间的差距足够让一道题的答案完全对不上参考答案。所以我的建议是在草稿纸最上方用一句话写清楚自己采用的是哪条规则然后全程不改。如果参考答案和自己算的不一样先别急着改答案回头对一下规则是否一致很多时候问题出在约定层面而不是计算层面。老师出题时如果没写清楚你可以在答题时注明本题按新到达进程先入队处理这本身就是一种学术严谨反而容易拿分。4.4 用二十行代码验证手算结果手算容易出错最可靠的校验方式是写个小模拟器跑一遍。下面这段 Python 用的就是 4.2 节那套规则输出可以直接跟手算结果逐行比对。from collections import deque def rr_schedule(procs, q): procs sorted(procs, keylambda p: (p[1], p[0])) n len(procs) idx, now 0, 0 queue deque() remain {p[0]: p[2] for p in procs} arrive {p[0]: p[1] for p in procs} burst {p[0]: p[2] for p in procs} finish {} def admit(t): nonlocal idx while idx n and procs[idx][1] t: queue.append(procs[idx][0]) idx 1 admit(now) while queue: pid queue.popleft() run min(q, remain[pid]) now run remain[pid] - run admit(now) # 新到达的先入队 if remain[pid] 0: queue.append(pid) # 被剥夺的后入队 else: finish[pid] now total_tat total_wtat 0 for pid in sorted(finish): tat finish[pid] - arrive[pid] wtat tat / burst[pid] total_tat tat total_wtat wtat print(f{pid} 完成{finish[pid]:3} 周转{tat:3} 带权{wtat:.3f}) print(f平均周转{total_tat/len(finish):.3f} 平均带权{total_wtat/len(finish):.3f}) rr_schedule([(P1, 0, 7), (P2, 2, 4), (P3, 4, 1), (P4, 5, 4)], 2)跑出来的结果是 P1 完成 16、P2 完成 9、P3 完成 7、P4 完成 15平均周转 9.000平均带权 2.384和 4.2 节的手算完全一致。把这段代码里的admit(now)和queue.append(pid)两行交换位置就能立刻得到 4.3 节说的另一种结果这也是我验证规则约定最常用的办法。4.5 时间片长度怎么选q 的取值对 RR 的影响是质变级别的不是量变。q 取得足够大比如大于所有进程的服务时间RR 就退化成 FCFSq 取得极小比如 1 个时间单位队列切换会变得极其频繁每个进程都被切得支离破碎。时间片 q平均周转时间本例现象1偏大切换次数多短作业反而反复排队29.0平衡长短作业都能轮上4接近 FCFS长作业一次跑完短作业等待明显8等同 FCFS没有进程会在时间片内被剥夺选 q 的经验法则是让绝大多数进程的一次 CPU 突发能在一个时间片内完成同时把切换开销控制在总时间的百分之几以内。现代通用系统的 q 通常在几十毫秒量级历史上有过 100 毫秒一类的取值。如果 q 小到几十微秒光是保存和恢复现场的开销就可能吃掉可观的处理能力。这一点在练习题里不会考但理解了它你才会明白为什么课本说 RR 的响应快和开销大是一体两面。5. 优先级调度、老化与多级反馈队列前面几种算法都只看到达时间或服务时间优先级调度引入了第三个维度谁更重要。这个概念一进来问题就从单纯的效率优化变成了效率与公平的拉扯。为了把这个话题讲清楚我另起一张小表因为优先级数值需要单独给。约定数值越小优先级越高。进程到达时间服务时间优先级P1043P2131P3254P43225.1 静态优先级的饥饿陷阱先看非抢占版本。时刻 0 只有 P1 到达运行 0 到 4。时刻 4 时 P2、P3、P4 都在队列里优先级分别是 1、4、2选最高的 P2运行 4 到 7。时刻 7 剩 P3优先级 4和 P4优先级 2选 P4运行 7 到 9。最后 P3 运行 9 到 14。给出各进程的周转时间P1 是 4、P2 是 6、P4 是 6、P3 是 12。平均周转时间 7.0带权分别是 1.0、2.0、3.0、2.4平均带权 2.1。抢占式版本会更有意思。时刻 0 P1 运行时刻 1 P2 到达优先级 1 高于 P1 的 3P2 抢占P1 剩余 3 挂起时刻 2 和 3P3、P4 陆续到达但它们的优先级分别是 4 和 2都低于正在运行的 P2 的 1所以谁也没抢动。P2 从 1 跑到 4 结束完成时间 4周转 3。时刻 4 比较 P1剩余 3优先级 3、P4优先级 2、P3优先级 4选 P4跑 4 到 6 结束。时刻 6 比较 P1 和 P3P1 优先级 3 更高跑 6 到 9 结束。最后 P3 跑 9 到 14。平均周转时间 (93123) ÷ 4 6.75比非抢占版本还低。但这个结果不能说明抢占一定更好因为在另一组数据下一个低优先级的长作业可能被源源不断到来的高优先级作业一直插队永远拿不到处理器。这就是饥饿静态优先级调度最需要警惕的问题。5.2 老化机制与响应比公式工程上解决饥饿最常用的办法是老化等待时间越长的进程优先级被逐步提高。具体做法可以每隔一段时间把就绪队列里所有进程的优先级数值减 1假设数值越小越高或者按公式动态计算。这样即使是最初优先级很低的进程等得够久之后也能升到足够高的位置。另一种折中思路是响应比高者优先HRRN不设优先级改用公式计算响应比 (等待时间 服务时间) ÷ 服务时间这个公式的巧妙之处在于它同时照顾了两个因素。等待时间长的进程响应比会升高防止饥饿服务时间短的进程响应比天生就高保持了对短作业的倾斜。它以非抢占方式运行每个进程结束时重新算一遍就绪队列里所有进程的响应比挑最大的。用样例表验证一下时刻 7 P1 结束时P2 等待 5 个时间单位、服务 4响应比 (54)÷4 2.25P3 等待 3、服务 1响应比 4.0P4 等待 2、服务 4响应比 1.5。选 P3和 SJF 给出的选择一致但等 P3 跑完之后P2 和 P4 的响应比会重新计算P2 的等待时间优势会继续扩大。5.3 多级反馈队列的降级规则多级反馈队列MLFQ把前面几种思路全部揉在一起是实际系统里用得最多的方案。它的结构是若干个优先级递减的就绪队列队列越往下优先级越低分配的时间片越长。典型规则有这么几条新创建的进程进入最高优先级队列的队尾。同一队列内部按时间片轮转。进程用完当前队列的时间片还没跑完就被降到下一级队列的队尾。只有高优先级队列为空时才调度低优先级队列。最低一级队列内部按时间片轮转不再降级。这套规则的设计意图很清楚短作业和新进程在最高优先级队列里待一小会儿就跑完了用户体验极好长作业会被逐渐降到低优先级队列用更长的时间片跑减少切换开销。它不需要预先知道进程的服务时间靠运行行为自动分类这是它比 SJF 实用的地方。不过纯 MLFQ 也会退化如果一个长作业刻意保持交互不断在时间片内主动让出处理器它就能一直待在高优先级队列里把真正需要响应的短作业挤到后面。现代实现里通常再加一条周期性地把所有进程提升回最高优先级队列用一个全局的优先级提升动作兜底。5.4 优先级反转是怎么发生的优先级调度还有一个现实中的坑叫优先级反转。场景是这样的一个低优先级进程持有一把共享锁此时一个高优先级进程需要这把锁被迫等待同时一个中等优先级的进程因为优先级高于低优先级进程把持锁进程抢占了。结果就是高优先级进程被中优先级进程间接拖住优先级被反转了。解决思路主要有两种优先级继承持锁的低优先级进程临时继承等待者的最高优先级这样它就不会被中优先级进程抢占优先级天花板给每把锁设定一个高于所有可能使用者最高优先级的数值任何进程拿到这把锁就自动提升到该数值。这部分内容在基础的调度练习里通常不考但理解了它你对优先级这个抽象概念在实际系统里的复杂性会有更具体的认识。6. 批改时最常见的六类错误我把这几百份作业里出现频率最高的问题归了归类基本能覆盖九成以上的失分点。每一条都配了具体的症状和修正办法对照着检查自己算完的答案比重新推一遍快得多。6.1 时间量定义混淆最典型的是把等待时间写成服务时间减周转时间出现负数还不自知。另一个变体是把周转时间和带权周转时间搞混最后求平均值时分母用了服务时间。修正办法很朴素算完之后立刻检查三件事——所有周转时间必须是正数、所有带权周转时间必须大于等于 1、等待时间永远小于周转时间。这三条只要有一条不满足回头查定义。6.2 队列入队顺序随手写时间片轮转里就绪队列的顺序在草稿纸上往往是画成一排箭头写到最后自己都看不清哪个在最前面。我的做法是用方括号明确写出队列内容每次变化都写一行比如[P1] - [P2, P1] - [P1, P3, P2]这样后面回头检查时一目了然。曾在批改时见过一份卷子队列中间少写了一个 P1导致后面所有完成时间整体前移了 3 个时间单位四个进程全部算错。6.3 抢占时刻漏判抢占式算法里新进程到达的每一个时刻都要检查一次不能只在进程结束的时候看。样例表里 SRTF 的抢占点有三次时刻 2、4、5漏掉任何一次后面的结果都不对。检查方法把所有不同的到达时刻列出来逐个打勾确认已经检查过形成清单。6.4 分母用错平均带权周转时间的分母是进程个数不是总服务时间也不是最后一个完成时间。这个错误比较低级但在时间紧张的时候确实有人犯。同理平均周转时间的分母也是进程个数。我见过把总和直接当成平均值交上去的整道题的分就没了。6.5 空转与处理器空闲有些进程表里第一个进程的到达时间不是 0或者中间存在一段没有任何进程到达的间隔。这段时间处理器是空闲的时间轴要如实空着不能把下一个进程的开始时间提前。批改时见过把空闲期挤掉的卷子导致所有后续完成时间都偏小。判断方法很简单任意时刻要么有进程在跑要么是明确标注的空闲不能出现无标注的空白。6.6 平均值只算一半有些题目要求同时给出平均周转时间和平均带权周转时间很多同学只算了一个。带权周转时间是判优的主要依据漏掉它等于放弃了一半的分数。我建议在草稿纸上固定画一张四列表格进程、完成时间、周转时间、带权周转时间最后一行填平均值形成习惯之后就不会漏。7. 从练习题到真实调度器还差什么把练习做对说明你掌握了调度算法在理想模型下的行为但真实的操作系统里还要考虑很多东西。了解这些差距对理解为什么实际系统不直接照搬课本算法很有帮助。7.1 练习题忽略的上下文切换开销练习里假设切换是零成本的进程 A 停止的那一刻进程 B 立刻开始跑。现实中保存和恢复寄存器、刷新地址转换缓存、切换内核栈都要花时间量级在几微秒到几十微秒。当时间片本身只有几十毫秒时这部分开销占比不大但如果时间片被设得很小切换开销就会变得不可忽略。这就是为什么 RR 的时间片不能在练习题里那样随便取 1。7.2 多核与缓存亲和性单处理器的调度模型里只有一个处理器谁拿到谁跑。多核环境下调度器还要决定把进程放到哪个核上。有一个经验性的优化是尽量让进程留在上次运行的那个核上因为那个核的缓存里可能还留着它的数据换核会带来冷启动开销。这个优化在多核系统上对性能的影响相当可观。7.3 把练习里的思路用在哪里最后说点实操层面的体会。我在做后端服务的时候任务队列的排序策略其实和调度算法是一回事有的场景按到达时间先进先出对应 FCFS有的场景把小任务优先处理对应 SJF有的场景给不同业务打上优先级标签对应优先级调度有的场景为了防止某个大任务被无限推迟加了按等待时长提升优先级的逻辑对应老化。课本上的这些算法名字只是个外壳真正有用的是它们背后那几种取舍——是追求平均指标最优还是保障最坏情况下的公平还是给重要任务开绿灯。这个取舍意识比记住 FCFS 全称是什么有用得多。我自己的习惯是遇到任何排队系统先问三个问题队列里排的是什么、谁决定下一个被处理的、有没有可能永远轮不到。这三个问题问完方案基本就成形了。 进程调度习题精讲：FCFS、SJF、SRTF、RR与优先级调度避坑指南
进程调度这道题我在操作系统课上做过一遍后来给下一届当助教批改又看了几百份最直观的感受是同一张进程表、同一套算法名称最后交上来的答案能有三四种。有人算出平均周转时间 8.75有人算出 9.0还有人算出 6.75而且每个人都能把自己的推导过程写得头头是道。问题往往不出在公式上而出在几条规定从来没被写下来——时间片用完的那一刻和新进程到达的那一刻撞在一起谁先进就绪队列抢占是发生在到达瞬间还是下一个时间片边界这些细节一旦含糊整道题的结果就全歪了。这篇就把课堂练习 3.3进程的调度这类练习从头到尾拆一遍。我会用一张固定的样例进程表把先来先服务、短作业优先、最短剩余时间优先、时间片轮转、优先级调度这几种算法的完整推演过程走一遍每一步的算式都摊开写中间那些教材上往往一笔带过的约定我会单独拎出来讲清楚。不管你是正在赶这份作业的学生还是想重新捡起操作系统基础的人只要跟着算一遍后面遇到同类题目基本就不会再翻车。1. 一道调度题为什么能算出四五种答案先厘清考核口径批改时我见过最离谱的一份卷子前面 FCFS 算得完全正确到时间片轮转那一栏四个进程的完成时间写成了一串杂乱无章的数字问他怎么来的说感觉应该是这个顺序。这种感觉式演算在调度题里几乎必然出错因为进程调度本质上是一个带约束的状态推进过程每一步的选择都由前一步的结果决定中间少考虑一个到达事件后面全盘皆错。想算对第一步不是急着画时间轴而是把题目里那几个关键字翻译成精确的数学定义。1.1 三个时间量把文字描述压成可计算的数字调度题里翻来覆去就是三个量到达时间、服务时间、完成时间。到达时间是进程进入就绪队列的时刻服务时间是它需要占用处理器的总时长完成时间是它最后一次释放处理器的时刻。这三个量本身没有歧义但由它们派生的两个指标经常被写反周转时间 完成时间 − 到达时间带权周转时间 周转时间 ÷ 服务时间等待时间 周转时间 − 服务时间周转时间的物理含义是从进程进入系统到离开系统一共花了多久注意它包含了进程实际在处理器上跑的时间和它排队等待的时间。带权周转时间则是把周转时间对服务时间做了归一化一个服务时间 1 个时间单位却等了 3 个时间单位才完成的进程带权周转时间是 3而一个服务时间 100 个时间单位、周转时间 105 的进程带权周转时间只有 1.05。带权周转时间衡量的是相对被耽误的程度不是绝对时长这一点是后面判优的核心依据。提示等待时间和周转时间的换算关系是 周转 − 服务不是 服务 − 周转我批改时大概每十份就有一份写反方向导致出现负数的等待时间自己都没察觉。1.2 周转时间与带权周转时间谁才是判优标准课本上评价调度算法优劣时给的指标通常是平均周转时间和平均带权周转时间两个很多同学默认后者只是前者的补充随便挑一个算完就交。实际上这两个指标的导向完全不同会给出相反的结论。设想两个进程 A 和 BA 服务时间 1、周转时间 10B 服务时间 50、周转时间 55。按绝对周转时间看A 拖了后腿10 对 1按带权周转时间看A 是 10B 只有 1.1A 才是真正的受害者。现实中我们更关心的是带权周转时间因为它直接反映了用户的主观感受——打开一个需要 0.1 秒响应的操作却卡了 3 秒比一个本来就要跑一分钟的任务多花 5 秒要难受得多。所以练习里如果没指定我一般两个都算并且在结论里以带权周转时间为主。1.3 抢占与非抢占一句约定改写全部结果抢占式和非抢占式的差别只在一个新进程到达时是否允许把它正在运行的进程踢下去这一句上但对结果的影响是决定性的。非抢占式调度里一旦某个进程拿到了处理器它会一直跑到结束或者主动让出中途来的进程再紧急也得排队抢占式调度则允许调度器在任意时刻重新做选择。最短剩余时间优先SRTF就是最短作业优先SJF的抢占版本两者面对同一张进程表平均周转时间往往能差出一个数量级。判定标准很简单新到达进程的剩余服务时间是否小于当前运行进程的剩余服务时间小于就抢不小于就等。这里的关键词是剩余不是原始很多同学拿新进程的服务时间去和当前进程的原始服务时间比这是最容易出错的一个点。优先级调度同理抢占版本要在每个到达事件发生时检查优先级高低非抢占版本只在进程结束时才重新选。2. 演算前的准备工作进程表、时间轴与约定准备工作做扎实后面能省一半时间。我习惯先把题目给的进程表原样抄一遍然后在下面另起一行手写出适用于这道题的三条约定写在纸上就不会中途忘记。这一步看起来多余实际上批改时答案出错的卷子有相当比例是因为自己定的规则和后面用的规则不一致——比如一开始说同一时刻新到达的先入队算到一半又按被抢占的先入队处理了。2.1 贯穿全篇的样例进程表为了让几种算法能横向对比后面所有推演都用这同一张表四个进程到达时间和服务时间各不相同覆盖了同时到达中途密集到达短作业与长作业混杂这几种典型情况。进程到达时间服务时间P107P224P341P454这张表的总服务时间是 7414 16 个时间单位也就是说无论用哪种算法最后一个进程的完成时间都不会早于 16。这个下界很有用算完之后可以拿它做个粗略校验——如果算出来的最大完成时间小于 16那一定是哪里少跑了时间比如漏掉了某个进程的执行段或者把两个进程的执行时间当成并行处理了。P3 的服务时间只有 1是整个表里最短的作业它会在 SJF 和 SRTF 里被优先照顾在 RR 里则要看运气。2.2 用甘特图代替公式推导我强烈建议手算时直接画时间轴不要一上来就套公式。做法是画一条横轴从 0 开始按时间单位刻度每确定一个进程的运行区间就在轴上画一段方块并标注进程号。以 FCFS 为例轴上的方块依次是 P1 占 0 到 7、P2 占 7 到 11、P3 占 11 到 12、P4 占 12 到 16一眼就能看出哪段处理器是空闲的、哪段被谁占用。画完轴之后每个进程的完成时间就是从它方块右端读出来的数字周转时间用完成时间减到达时间即可。这种方式比列一堆不等式快得多而且错不了——因为每个时间点只有一种状态方块之间的接缝天然保证了时间不会重叠也不会跳空。我后来带过的学生里凡是坚持画时间轴的错误率比直接写公式的低一大截。2.3 三条必须先写下来的约定结合上面那张表我会在草稿纸顶部固定写下这三条新到达的进程在到达当刻进入就绪队列即使此刻处理器正忙。时间片用完与新进程到达撞在同一时刻时新到达的进程先入队被剥夺的进程后入队尾。进程在时间片内提前完成立即触发一次调度不必等到时间片耗完。第 2 条是整篇里最关键的一条约定不同教材对它的处理并不一致有的把被剥夺的进程放在前面。这不代表谁对谁错而是说明做题前必须确认老师或者教材用的是哪一套。下面第 4 章我会用同一张表、仅仅把这条约定反过来演示结果会差多少。3. 先来先服务、短作业优先与最短剩余时间优先这三种算法放在一起讲是因为它们共享同一个决策逻辑——在某个时刻从就绪队列里挑一个进程区别只在于挑谁和什么时候挑。先把非抢占的两个算清楚再引入抢占机制理解起来会顺很多。3.1 FCFS顺序执行下的等待堆积先来先服务就是严格的队列谁先到谁先跑跑完再轮到下一个。按样例表走时刻 0 只有 P1 到达它跑满 7 个时间单位到时刻 7 结束时刻 7 时 P2、P3、P4 都已经到达按到达顺序排P2 先跑 7 到 11接着 P3 跑 11 到 12最后 P4 跑 12 到 16。进程完成时间周转时间带权周转时间P1771.000P21192.250P31288.000P416112.750平均周转时间 (79811) ÷ 4 8.75平均带权周转时间 (1.02.258.02.75) ÷ 4 3.5。注意 P3 的带权周转时间高达 8.0它只干 1 个单位的活却等了 8 个单位。这就是 FCFS 最典型的问题长作业在前面的时候后面所有作业都要陪着等服务时间短的作业受害最重。批改时我会特别看这一行几乎所有人的 P3 带权周转时间都算得出来但很多人不做任何评论其实这里正是引出 SJF 的最佳切入点。3.2 非抢占 SJF一次选择全局受影响短作业优先的规则是每次选择服务时间最短的进程。非抢占版本只在当前进程结束、需要重新选人时才做决定。时刻 0 只有 P1 可运行所以尽管 P1 是表里最长的作业之一也只能让它先跑——这一点很多同学第一次会困惑以为 SJF 应该跳过 P1实际上调度器没有预知未来的能力它只能在当前已经到达的进程里挑。P1 跑到时刻 7 结束此时就绪队列里有 P2还需 4、P3还需 1、P4还需 4。选最短的 P3跑 7 到 8 结束。时刻 8 就绪队列里剩 P2 和 P4服务时间都是 4这时候需要一个次级规则通常按到达时间早的先来P2 在时刻 2 到达、P4 在时刻 5 到达所以 P2 先跑 8 到 12P4 最后跑 12 到 16。进程完成时间周转时间带权周转时间P1771.000P212102.500P3844.000P416112.750平均周转时间 (710411) ÷ 4 8.0平均带权周转时间 (1.02.54.02.75) ÷ 4 2.5625。对比 FCFS平均周转时间降了 0.75平均带权周转时间从 3.5 降到 2.56改善相当明显主要功劳就是 P3 从等 8 个单位变成等 3 个单位完成。注意时刻 8 那个次级规则必须写出来。P2 和 P4 服务时间相同如果按进程号排序会得到同样的结果但如果题目里 P4 的到达时间更早结果就会变。规范的做法是明确注明服务时间相同时按到达时间先后或者干脆照抄题目给出的次序。3.3 SRTF抢占版本把平均周转压到最低最短剩余时间优先是 SJF 的抢占版每个到达事件发生时都要检查一遍。推演过程比前两个复杂但逻辑是一致的。时刻 0P1 开始运行剩余 7。时刻 2P2 到达服务时间 4而 P1 还剩 5从 0 跑到 2已经消耗 24 小于 5P2 抢占P1 被挂起。P2 从 2 跑到 4消耗 2还剩 2。时刻 4P3 到达服务时间 1小于 P2 剩余的 2P3 抢占。P3 从 4 跑到 5 结束周转时间 5−4 1带权 1.0。时刻 5P4 到达服务时间 4。此刻就绪队列里有 P1剩余 5、P2剩余 2、P4剩余 4。最小的是 P2 的 2P2 从 5 跑到 7 结束周转时间 7−2 5带权 5÷4 1.25。时刻 7比较 P1剩余 5和 P4剩余 4选 P4P4 从 7 跑到 11 结束周转 11−5 6带权 6÷4 1.5。最后 P1 从 11 跑到 16周转 16−0 16带权 16÷7 ≈ 2.286。进程完成时间周转时间带权周转时间P116162.286P2751.250P3511.000P41161.500平均周转时间 (16516) ÷ 4 7.0平均带权周转时间 (2.2861.251.01.5) ÷ 4 ≈ 1.509。这是四种算法里带权周转时间最低的代价是 P1 从原本 7 个时间单位完成被拖到了 16 个。SRTF 优化的从来不是单个进程的体验而是全体进程的平均值这一点在做题时要心里有数现实中的调度器也很少敢这么激进因为长作业被无限推迟会带来别的麻烦。3.4 三种结果摆在一起看把三组数据并排放在一张表里结论会清晰很多算法平均周转时间平均带权周转时间明显受益者明显受害者FCFS8.753.50P1P3非抢占 SJF8.002.56P3P1、P4SRTF7.001.51P2、P3P1能看出来一个规律带权周转时间对短作业特别敏感。P3 这种服务时间为 1 的进程只要让它多等 1 个时间单位带权周转时间就增加 1对整个平均值的影响远大于让 P1 多等 1 个单位。所以任何优先照顾短作业的算法在平均带权周转时间这个指标上都占便宜。理解这一点之后再看时间片轮转为什么表现平平就顺理成章了。4. 时间片轮转的推演细节与代码对照时间片轮转Round RobinRR是练习里丢分最集中的一块没有之一。FCFS 和 SJF 只要算得慢一点基本不会错RR 不一样它对就绪队列的维护顺序要求非常严格队列里少一个元素、多一个元素、顺序反一下最后四个进程的完成时间就全变了。4.1 就绪队列的维护是全部难点所在RR 的核心机制是把就绪进程排成一个循环队列调度器每次从队头取一个进程给它一个时间片 q 的处理器时间。如果它在 q 内跑完了直接离队如果没跑完它被剥夺处理器重新排到队尾等前面所有进程都轮一遍再回来。这里有几个必须在纸上写死的操作细节入队时机进程到达时进入队尾还是立刻抢占当前进程标准 RR 是非抢占的新到达的进程只入队不影响当前正在跑的进程当前进程的时间片用完了才切换。被剥夺进程的入队位置时间片用完的进程放队尾这一点没有争议。新到达进程与被剥夺进程的先后这两个动作如果发生在同一时刻顺序就需要明确约定前面第 2.3 节我选的是新到达的先入队。提前完成的处理进程在时间片内跑完立刻释放处理器从队头取下一个不需要等当前时间片走完。这四条里第三条是分歧最大的。我见过至少两种主流处理方式而且都能说得通关键在于前后一致。4.2 q2 的完整时间轴推演设时间片 q 2按第 2.3 节的约定新到达的先入队、被剥夺的后入队完整过程如下。时刻 0就绪队列只有 P1取 P1 运行。P1 从 0 跑到 2消耗 2剩余 5。此刻 P2 到达先入队P1 剩余 5后入队尾。队列变成 [P2, P1]。时刻 2取队头 P2 运行从 2 跑到 4消耗 2剩余 2。此刻 P3 在时刻 4 到达先入队P2 剩余 2后入队尾。队列从 [P1] 变成 [P1, P3, P2]。时刻 4取队头 P1 运行从 4 跑到 6消耗 2剩余 3。注意这里 P1 又被选中了因为它一直排在队列里而 P3 在它后面。此刻 P4 在时刻 5 到达需要入队队列先是 [P3, P2]加入 P4 后是 [P3, P2, P4]再把 P1 放队尾变成 [P3, P2, P4, P1]。时刻 6取队头 P3 运行服务时间只有 1从 6 跑到 7 就结束了完成时间 7周转时间 7−4 3带权 3.0。此刻没有新进程到达队列是 [P2, P4, P1]。时刻 7取队头 P2 运行剩余 2从 7 跑到 9 结束完成时间 9周转 9−2 7带权 7÷4 1.75。队列变成 [P4, P1]。时刻 9取 P4 运行从 9 跑到 11消耗 2剩余 2。队列变成 [P1, P4]。时刻 11取 P1 运行从 11 跑到 13剩余 1。队列变成 [P4, P1]。时刻 13取 P4 运行剩余 2从 13 跑到 15 结束完成时间 15周转 15−5 10带权 10÷4 2.5。队列只剩 [P1]。时刻 15取 P1 运行剩余 1从 15 跑到 16 结束完成时间 16周转 16带权 16÷7 ≈ 2.286。进程完成时间周转时间带权周转时间P116162.286P2971.750P3733.000P415102.500平均周转时间 (167310) ÷ 4 9.0平均带权周转时间 (2.2861.753.02.5) ÷ 4 ≈ 2.384。4.3 换一条入队规则答案立刻不同现在把第 2.3 节的第 2 条约定反过来被剥夺的进程先入队新到达的后入队。只改这一条时刻 4 的队列就从 [P1, P3, P2] 变成 [P1, P2, P3]等等这样 P2 反而跑得更早也不对。真正的分歧点在时刻 4 的新到达 P3 和刚用完时间片的 P2 谁先两种规则给出的队列分别是 [P1, P3, P2] 和 [P1, P2, P3]P1 因为在时刻 2 就排在队里所以始终在第一位。按第二种规则继续推队列顺序不同后面的完成时间会整体偏移最终 P3 的完成时间可能从 7 变成 12带权周转时间从 3 变成 8。四个进程的平均带权周转时间会从 2.384 变成 3.1 左右。这中间的差距足够让一道题的答案完全对不上参考答案。所以我的建议是在草稿纸最上方用一句话写清楚自己采用的是哪条规则然后全程不改。如果参考答案和自己算的不一样先别急着改答案回头对一下规则是否一致很多时候问题出在约定层面而不是计算层面。老师出题时如果没写清楚你可以在答题时注明本题按新到达进程先入队处理这本身就是一种学术严谨反而容易拿分。4.4 用二十行代码验证手算结果手算容易出错最可靠的校验方式是写个小模拟器跑一遍。下面这段 Python 用的就是 4.2 节那套规则输出可以直接跟手算结果逐行比对。from collections import deque def rr_schedule(procs, q): procs sorted(procs, keylambda p: (p[1], p[0])) n len(procs) idx, now 0, 0 queue deque() remain {p[0]: p[2] for p in procs} arrive {p[0]: p[1] for p in procs} burst {p[0]: p[2] for p in procs} finish {} def admit(t): nonlocal idx while idx n and procs[idx][1] t: queue.append(procs[idx][0]) idx 1 admit(now) while queue: pid queue.popleft() run min(q, remain[pid]) now run remain[pid] - run admit(now) # 新到达的先入队 if remain[pid] 0: queue.append(pid) # 被剥夺的后入队 else: finish[pid] now total_tat total_wtat 0 for pid in sorted(finish): tat finish[pid] - arrive[pid] wtat tat / burst[pid] total_tat tat total_wtat wtat print(f{pid} 完成{finish[pid]:3} 周转{tat:3} 带权{wtat:.3f}) print(f平均周转{total_tat/len(finish):.3f} 平均带权{total_wtat/len(finish):.3f}) rr_schedule([(P1, 0, 7), (P2, 2, 4), (P3, 4, 1), (P4, 5, 4)], 2)跑出来的结果是 P1 完成 16、P2 完成 9、P3 完成 7、P4 完成 15平均周转 9.000平均带权 2.384和 4.2 节的手算完全一致。把这段代码里的admit(now)和queue.append(pid)两行交换位置就能立刻得到 4.3 节说的另一种结果这也是我验证规则约定最常用的办法。4.5 时间片长度怎么选q 的取值对 RR 的影响是质变级别的不是量变。q 取得足够大比如大于所有进程的服务时间RR 就退化成 FCFSq 取得极小比如 1 个时间单位队列切换会变得极其频繁每个进程都被切得支离破碎。时间片 q平均周转时间本例现象1偏大切换次数多短作业反而反复排队29.0平衡长短作业都能轮上4接近 FCFS长作业一次跑完短作业等待明显8等同 FCFS没有进程会在时间片内被剥夺选 q 的经验法则是让绝大多数进程的一次 CPU 突发能在一个时间片内完成同时把切换开销控制在总时间的百分之几以内。现代通用系统的 q 通常在几十毫秒量级历史上有过 100 毫秒一类的取值。如果 q 小到几十微秒光是保存和恢复现场的开销就可能吃掉可观的处理能力。这一点在练习题里不会考但理解了它你才会明白为什么课本说 RR 的响应快和开销大是一体两面。5. 优先级调度、老化与多级反馈队列前面几种算法都只看到达时间或服务时间优先级调度引入了第三个维度谁更重要。这个概念一进来问题就从单纯的效率优化变成了效率与公平的拉扯。为了把这个话题讲清楚我另起一张小表因为优先级数值需要单独给。约定数值越小优先级越高。进程到达时间服务时间优先级P1043P2131P3254P43225.1 静态优先级的饥饿陷阱先看非抢占版本。时刻 0 只有 P1 到达运行 0 到 4。时刻 4 时 P2、P3、P4 都在队列里优先级分别是 1、4、2选最高的 P2运行 4 到 7。时刻 7 剩 P3优先级 4和 P4优先级 2选 P4运行 7 到 9。最后 P3 运行 9 到 14。给出各进程的周转时间P1 是 4、P2 是 6、P4 是 6、P3 是 12。平均周转时间 7.0带权分别是 1.0、2.0、3.0、2.4平均带权 2.1。抢占式版本会更有意思。时刻 0 P1 运行时刻 1 P2 到达优先级 1 高于 P1 的 3P2 抢占P1 剩余 3 挂起时刻 2 和 3P3、P4 陆续到达但它们的优先级分别是 4 和 2都低于正在运行的 P2 的 1所以谁也没抢动。P2 从 1 跑到 4 结束完成时间 4周转 3。时刻 4 比较 P1剩余 3优先级 3、P4优先级 2、P3优先级 4选 P4跑 4 到 6 结束。时刻 6 比较 P1 和 P3P1 优先级 3 更高跑 6 到 9 结束。最后 P3 跑 9 到 14。平均周转时间 (93123) ÷ 4 6.75比非抢占版本还低。但这个结果不能说明抢占一定更好因为在另一组数据下一个低优先级的长作业可能被源源不断到来的高优先级作业一直插队永远拿不到处理器。这就是饥饿静态优先级调度最需要警惕的问题。5.2 老化机制与响应比公式工程上解决饥饿最常用的办法是老化等待时间越长的进程优先级被逐步提高。具体做法可以每隔一段时间把就绪队列里所有进程的优先级数值减 1假设数值越小越高或者按公式动态计算。这样即使是最初优先级很低的进程等得够久之后也能升到足够高的位置。另一种折中思路是响应比高者优先HRRN不设优先级改用公式计算响应比 (等待时间 服务时间) ÷ 服务时间这个公式的巧妙之处在于它同时照顾了两个因素。等待时间长的进程响应比会升高防止饥饿服务时间短的进程响应比天生就高保持了对短作业的倾斜。它以非抢占方式运行每个进程结束时重新算一遍就绪队列里所有进程的响应比挑最大的。用样例表验证一下时刻 7 P1 结束时P2 等待 5 个时间单位、服务 4响应比 (54)÷4 2.25P3 等待 3、服务 1响应比 4.0P4 等待 2、服务 4响应比 1.5。选 P3和 SJF 给出的选择一致但等 P3 跑完之后P2 和 P4 的响应比会重新计算P2 的等待时间优势会继续扩大。5.3 多级反馈队列的降级规则多级反馈队列MLFQ把前面几种思路全部揉在一起是实际系统里用得最多的方案。它的结构是若干个优先级递减的就绪队列队列越往下优先级越低分配的时间片越长。典型规则有这么几条新创建的进程进入最高优先级队列的队尾。同一队列内部按时间片轮转。进程用完当前队列的时间片还没跑完就被降到下一级队列的队尾。只有高优先级队列为空时才调度低优先级队列。最低一级队列内部按时间片轮转不再降级。这套规则的设计意图很清楚短作业和新进程在最高优先级队列里待一小会儿就跑完了用户体验极好长作业会被逐渐降到低优先级队列用更长的时间片跑减少切换开销。它不需要预先知道进程的服务时间靠运行行为自动分类这是它比 SJF 实用的地方。不过纯 MLFQ 也会退化如果一个长作业刻意保持交互不断在时间片内主动让出处理器它就能一直待在高优先级队列里把真正需要响应的短作业挤到后面。现代实现里通常再加一条周期性地把所有进程提升回最高优先级队列用一个全局的优先级提升动作兜底。5.4 优先级反转是怎么发生的优先级调度还有一个现实中的坑叫优先级反转。场景是这样的一个低优先级进程持有一把共享锁此时一个高优先级进程需要这把锁被迫等待同时一个中等优先级的进程因为优先级高于低优先级进程把持锁进程抢占了。结果就是高优先级进程被中优先级进程间接拖住优先级被反转了。解决思路主要有两种优先级继承持锁的低优先级进程临时继承等待者的最高优先级这样它就不会被中优先级进程抢占优先级天花板给每把锁设定一个高于所有可能使用者最高优先级的数值任何进程拿到这把锁就自动提升到该数值。这部分内容在基础的调度练习里通常不考但理解了它你对优先级这个抽象概念在实际系统里的复杂性会有更具体的认识。6. 批改时最常见的六类错误我把这几百份作业里出现频率最高的问题归了归类基本能覆盖九成以上的失分点。每一条都配了具体的症状和修正办法对照着检查自己算完的答案比重新推一遍快得多。6.1 时间量定义混淆最典型的是把等待时间写成服务时间减周转时间出现负数还不自知。另一个变体是把周转时间和带权周转时间搞混最后求平均值时分母用了服务时间。修正办法很朴素算完之后立刻检查三件事——所有周转时间必须是正数、所有带权周转时间必须大于等于 1、等待时间永远小于周转时间。这三条只要有一条不满足回头查定义。6.2 队列入队顺序随手写时间片轮转里就绪队列的顺序在草稿纸上往往是画成一排箭头写到最后自己都看不清哪个在最前面。我的做法是用方括号明确写出队列内容每次变化都写一行比如[P1] - [P2, P1] - [P1, P3, P2]这样后面回头检查时一目了然。曾在批改时见过一份卷子队列中间少写了一个 P1导致后面所有完成时间整体前移了 3 个时间单位四个进程全部算错。6.3 抢占时刻漏判抢占式算法里新进程到达的每一个时刻都要检查一次不能只在进程结束的时候看。样例表里 SRTF 的抢占点有三次时刻 2、4、5漏掉任何一次后面的结果都不对。检查方法把所有不同的到达时刻列出来逐个打勾确认已经检查过形成清单。6.4 分母用错平均带权周转时间的分母是进程个数不是总服务时间也不是最后一个完成时间。这个错误比较低级但在时间紧张的时候确实有人犯。同理平均周转时间的分母也是进程个数。我见过把总和直接当成平均值交上去的整道题的分就没了。6.5 空转与处理器空闲有些进程表里第一个进程的到达时间不是 0或者中间存在一段没有任何进程到达的间隔。这段时间处理器是空闲的时间轴要如实空着不能把下一个进程的开始时间提前。批改时见过把空闲期挤掉的卷子导致所有后续完成时间都偏小。判断方法很简单任意时刻要么有进程在跑要么是明确标注的空闲不能出现无标注的空白。6.6 平均值只算一半有些题目要求同时给出平均周转时间和平均带权周转时间很多同学只算了一个。带权周转时间是判优的主要依据漏掉它等于放弃了一半的分数。我建议在草稿纸上固定画一张四列表格进程、完成时间、周转时间、带权周转时间最后一行填平均值形成习惯之后就不会漏。7. 从练习题到真实调度器还差什么把练习做对说明你掌握了调度算法在理想模型下的行为但真实的操作系统里还要考虑很多东西。了解这些差距对理解为什么实际系统不直接照搬课本算法很有帮助。7.1 练习题忽略的上下文切换开销练习里假设切换是零成本的进程 A 停止的那一刻进程 B 立刻开始跑。现实中保存和恢复寄存器、刷新地址转换缓存、切换内核栈都要花时间量级在几微秒到几十微秒。当时间片本身只有几十毫秒时这部分开销占比不大但如果时间片被设得很小切换开销就会变得不可忽略。这就是为什么 RR 的时间片不能在练习题里那样随便取 1。7.2 多核与缓存亲和性单处理器的调度模型里只有一个处理器谁拿到谁跑。多核环境下调度器还要决定把进程放到哪个核上。有一个经验性的优化是尽量让进程留在上次运行的那个核上因为那个核的缓存里可能还留着它的数据换核会带来冷启动开销。这个优化在多核系统上对性能的影响相当可观。7.3 把练习里的思路用在哪里最后说点实操层面的体会。我在做后端服务的时候任务队列的排序策略其实和调度算法是一回事有的场景按到达时间先进先出对应 FCFS有的场景把小任务优先处理对应 SJF有的场景给不同业务打上优先级标签对应优先级调度有的场景为了防止某个大任务被无限推迟加了按等待时长提升优先级的逻辑对应老化。课本上的这些算法名字只是个外壳真正有用的是它们背后那几种取舍——是追求平均指标最优还是保障最坏情况下的公平还是给重要任务开绿灯。这个取舍意识比记住 FCFS 全称是什么有用得多。我自己的习惯是遇到任何排队系统先问三个问题队列里排的是什么、谁决定下一个被处理的、有没有可能永远轮不到。这三个问题问完方案基本就成形了。