Appearance
调度模拟：规则定出次序，次序定出代价（专题总纲）
Intro
这一类题的题面长得很不一样：一边是四个进程的到达时刻和 CPU 运行时间，一边是一串磁道号和转速；一边问「首次调度发生在哪个时刻」，一边问「读完这 4 个扇区共需要多少时间」。
但拿到手上要做的事只有一件：
调度就是把「谁先谁后」定下来。规则决定次序，次序决定代价。
题面给的那一堆细则（谁抢谁、什么时候能抢、平局怎么办、扫到头往哪拐）全都只做一件事——在每个岔口告诉你下一个该轮到谁。把这些细则一步步执行下去，次序就出来了；次序出来了，题目问的那个数就是在这个次序上数出来的。
所以推演动作是可枚举的，一共五步——2010、2019、2026 这三道都走这五步（2016 那道反着走，下一节单说）：
- 画一条轴。 CPU 调度的轴是时间，磁盘调度的轴是磁头位置。
- 在轴的起点写下「此刻谁可选」——就绪队列，或者 I/O 请求队列。
- 按题面给的规则从可选集里挑一个，在轴上落一段，记一笔。
- 更新可选集（有人跑完了、有人新到了、有人被踢回来了），回到第 3 步。
- 全部挑完，把要的那个量按定义加起来——时间、次数、还是某个时刻。
第 3 步的「规则」是唯一随题变化的东西。它可以是优先级、可以是时间片、可以是离磁头最近，也可以是你自己设计出来的一个公式。
四道题在「规则 → 次序 → 代价」上的四个位置
这条箭头有三节，四道真题分别在不同的位置下手：
| 年份·题号 | 题面给你的规则 | 让你走到哪一步 |
|---|---|---|
| 2019·44(2) | SSTF | 停在次序——只问访问簇的先后次序，不问耗时 |
| 2010·45(2) | C-SCAN | 走完全程——次序排出来，代价是毫秒数 |
| 2026·45(1) | 优先级 + 时间片轮转，外加六条细则 | 走完全程——代价是中断次数、调度次数和四个时刻 |
| 2016·46 | 一条会饿死人的规则：priority = nice | 反着走——从次序的一个坏性质倒推回去改规则 |
先把「都」这个字拆开逐条对一遍，免得记成一句不成立的话：
- 2010、2019、2026 这三道要在轴上排出一个实际的次序；
- 2010、2026 这两道在次序之上还要把代价加出来；
- 2016 那道不产生任何次序，它问的是「什么样的规则会让某个进程永远排不到队首」，答的是怎么把规则改掉。
所以这个专题真正共有的东西是那条箭头本身，而不是「排次序」这一个动作。2016 那道和另外三道的关系，是同一条箭头的两个方向。
两种资源，同一条轴
CPU 调度和磁盘调度在教材里隔着好几章，卷面上却几乎同构：
| CPU 调度（2026·45） | 磁盘调度（2010·45、2019·44） | |
|---|---|---|
| 轴是什么 | 时间（ms） | 磁头位置（磁道号 / 柱面号） |
| 可选集 | 就绪队列 | I/O 请求队列 |
| 挑选的依据 | 优先级值、入队先后 | 与当前磁头的距离、当前移动方向 |
| 落一段的长度 | 这次占用 CPU 多久 | 这次移动几个磁道 |
| 最后加出来的代价 | 次数、时刻 | 磁道数 → 毫秒 |
两处结构上的差别值得先记住，它们各自对应一个失分点：
其一，请求什么时候进队不一样。 磁盘那两道的请求队列在题面里一次性给全（2010 是 50, 90, 30, 120，2019 是四个簇号），推演途中不会有新请求冒出来。CPU 那道则相反，P3 在 t=12、P4 在 t=14 是推演到一半才到达的，每到一个就要重算一次「此刻谁可选」。
其二，磁盘的代价里有一部分和次序无关。 2010 那道的旋转延迟 4 × 5 = 20 ms、传输时间 4 × 0.1 = 0.4 ms，无论四个请求怎么排都是这两个数——它们只跟「读了几个扇区」有关。次序影响的只有寻道那 170 ms 这一段。先把与次序无关的那两段单独算出来放在一边，再回头排次序，比混在一起算稳得多。
边界必错点
「到达」不等于「可以抢占」（2026 年那道）。 题面规定「仅当发生时钟中断时才触发抢占 CPU 的操作」，而时钟中断每 10 ms 一次。P3 在 t=12 到达、P4 在 t=14 到达，都不是中断时刻，所以它们只入就绪队列、不换 CPU，P2 继续跑到 t=20。把这条漏掉，整条时间轴从 t=12 起就整体偏掉，四个首次调度时刻会连着一起错。
两种「回到就绪队列」的后果不一样（2026 年那道）。 题面给了两条并列的细则：因时间片用完而返回，优先级值减 1；被更高优先级抢占而返回，优先级值保持不变。P2 在 t=20 被 P4 抢走，优先级仍是 4；P4 在 t=70 时间片用完，才从 5 降到 4。每次把一个进程踢回队列时，先问自己是哪一种回法。
平局要看谁先入队，而入队时刻是推演出来的（2026 年那道）。 题面只说「多个进程优先级相同时，先进入就绪队列的进程优先」。t=70 那次 P2 和 P4 都是优先级 4，P2 是 t=20 被抢占时入队的、P4 是 t=70 刚入队，所以选 P2；t=140 那次 P1 和 P3 都是优先级 2，P3 是 t=12 入队的、P1 是 t=140 刚降级入队，所以选 P3。这两个入队时刻题面没有直接给，要从前面的推演里翻出来。
三段时间少一段，总数就对不上（2010 年那道）。 寻道 170 ms、旋转延迟 20 ms、传输 0.4 ms，三段相加才是 190.4 ms。传输那一段是每磁道 100 个扇区里读 1 个，等于 1/100 转 = 0.1 ms，四次共 0.4 ms；按整条磁道算成 10 ms 一次会得到 40 ms。每一问先在草稿边上写「寻道 / 旋转 / 传输」三个字，再往后面填数。
旋转延迟按半转算，判断依据在题面里（2010 年那道）。 题面写着「需读取 1 个随机分布的扇区」，随机分布就取平均值，半转 = 5 ms，四个请求共 20 ms。按最坏情况一整转（10 ms × 4 = 40 ms）会多出 20 ms。
SSTF 比的是柱面距离，不是簇号之差（2019 年那道）。 题面说磁头在「85 号柱面」上，这一个柱面覆盖 85000～85999 整整一千个簇，题面并没有说磁头停在其中哪一个簇上。所以四个请求的簇号必须先各自除以「每柱面 1000 簇」落到柱面号（100、60、101、110），再拿柱面号去和 85 比距离。拿簇号直接做减法就没有起点可减。
符号方向决定分（2016 年那道）。 题面写的是「选择优先数最小的进程运行」，所以跑得越多要让优先数变大、等得越久要让优先数变小。cpuTime 前面是加号、waitTime 前面是减号。方向写反，公式的作用就跟着反过来。
一道题的答卷长什么样
2010 年那道的第 (2) 问
这一问 5 分，卷面就是四小段，每段一行结论。中间量全部摆出来——分是按段给的。
① 先把与次序无关的两段算掉
转速 6000 rpm = 100 转/秒 → 每转 10 ms
平均旋转延迟 = 半转 = 5 ms ← 题面说扇区随机分布，取平均
读 1 个扇区 = 1/100 转 = 0.1 ms ← 每磁道 100 个扇区
旋转延迟合计 = 4 × 5 = 20 ms
传输时间合计 = 4 × 0.1 = 0.4 ms② 按 C-SCAN 排出服务次序
磁头在 100 号、沿磁道号增大方向；请求队列 50, 90, 30, 120。
服务次序：100 → 120 → 30 → 50 → 90③ 累加寻道位移
| 段 | 位移（磁道） |
|---|---|
| 100 → 120 | 20 |
| 120 → 30（跳回段，按端点差计） | 90 |
| 30 → 50 | 20 |
| 50 → 90 | 40 |
| 合计 | 170 |
⚠️ 跳回那一段在本题标答里是计距离的，四段合计 170 磁道。把它当成免费的传送门，总数就下来了。
④ 三段相加
寻道时间 = 170 × 1 ms = 170 ms
总时间 = 170 + 20 + 0.4 = 190.4 ms写到 190.4 ms 为止，这一问就完了。190 ms 和 190.4 ms 是两个答案，那 0.4 就是传输段。
2026 年那道的第 (1) 问
这一问的卷面主体是一张推演表。逐行写，每一行只回答「这个时刻谁上 CPU、为什么」，写完表答案就在表里。
t=10 P1(prio 3)、P2(prio 4) 到达，CPU 空闲 → 调度 P2 [调度①]
t=12 P3(prio 2) 到达 —— 非中断时刻，只入队，P2 继续跑
t=14 P4(prio 5) 到达 —— 非中断时刻，只入队，P2 继续跑
t=20 中断：P4 优先级 5 最高 → 抢占 P2 → 调度 P4 [调度②]
P2 是「被抢占」回队，优先级仍为 4，还剩 10 ms
t=70 中断：P4 连跑 50 ms，时间片用完，5→4
就绪队列里 P2、P4 同为 4，P2 于 t=20 入队更早 → 调度 P2 [调度③]
t=80 中断：P2 跑满 10+10=20 ms，完成
就绪队列剩 P1(3)、P3(2)、P4(4) → 调度 P4 [调度④]
t=90 中断：P4 跑满 50+10=60 ms，完成
就绪队列剩 P1(3)、P3(2) → 调度 P1 [调度⑤]
t=140 中断：P1 连跑 50 ms，时间片用完，3→2
P1、P3 同为 2，P3 于 t=12 入队更早 → 调度 P3 [调度⑥]
t=180 中断：P3 跑满 40 ms，完成 → 调度 P1 [调度⑦]
t=225 P1 跑完剩下的 45 ms，全部结束三个答案直接从表里读：
时钟中断次数 = 10、20、…、220，共 22 次 ← 末次中断在 220，P1 于 225 结束
CPU 调度次数 = 10、20、70、80、90、140、180，共 7 次
首次调度时刻 = P1: 90 P2: 10 P3: 140 P4: 20⚠️ 首次调度时刻和到达时刻是两件事。 P3 在 t=12 就进了就绪队列，第一次拿到 CPU 却是 t=140，中间隔了 128 ms。这四个数写的是「第一次占上 CPU 的时刻」。
反着走的那道题，卷面长什么样
2016 年那道不产生任何次序，它给你一个坏结果、让你改规则。全题 6 分，是本专题 唯一一道要写文字论述的，分是按「公式里的每一项」分开给的。
(1) 为什么会饥饿（2 分）——要说清机制，不能只答「会」：
priority = nice 时优先数是静态的、执行期间永不变化
只要系统里持续有 nice 更小的进程到达，nice 大的那个就永远排不到 CPU⚠️ 饥饿不是死锁：死锁是互相等对方的资源、谁也走不了；饥饿是这个进程一直没轮上， 系统其余部分照常推进。混着答会被扣。
(2) 设计动态优先数（4 分）——公式要含三项，每项 1 分，符号方向错就不给：
priority = nice + k₁ · cpuTime − k₂ · waitTime (k₁, k₂ > 0)
nice 保留静态基准，题面要求用上它
cpuTime 跑得越多优先数越大 → 越不优先（所以是加号）
waitTime 等得越久优先数越小 → 越优先（所以是减号）还要单独答一句 waitTime 的作用（1 分）：它补偿长期等待的进程，等得越久越优先， 这样任何进程等下去总会被调度到，饥饿就被消掉了。这一句是题面点名要的，别以为写完公式就完了。
真题的两种形态
第一组 · 在时间轴上推演（2016-46、2026-45）。 可选集是就绪队列，途中会有新进程到达。2026 那道是完整的推演题，题面把六条细则写得很细，照着一条条执行就行；2016 那道是这一组的反面——题面给的规则会让低优先级进程永远排不上号，让你把规则改成动态的（保留 nice 作基准、+k₁·cpuTime 惩罚长跑、−k₂·waitTime 补偿久等），并说明 waitTime 起什么作用。这道题的分是按公式里的三项分别给的，三项都要写出来，还要单独说一句 waitTime 的作用。
第二组 · 在磁头位置轴上推演（2010-45、2019-44）。 可选集在题面里一次性给全。2010 那道给 C-SCAN 让你排次序并把三段时间加出来，第 (3) 问再换一种硬件——Flash 没有磁臂移动、没有旋转等待，按磁道排序这件事本身就失去了意义，所以答 FCFS（或 NOOP）这种不排序的策略。2019 那道只让你排出 SSTF 的访问次序，不问耗时。
哪几问是外挂
这 4 道题合计 27 分，其中 6 分不在本专题的动作范围内——它们是别的章节挂在同一道题的骨架上，各自独立给分：
| 外挂的小问 | 手上做的动作 | 分值 | 归属 |
|---|---|---|---|
| 2019·44 (1) 磁盘容量是多少 | 柱面数 × 磁道数 × 扇区数 × 扇区大小，一次乘法 | 2 | 磁盘几何参数 |
| 2019·44 (3) 第 100530 簇的物理地址、由什么程序完成 | 逐层带余除法取商与余数；外加一问 I/O 软件分层 | 3 | 文件系统与磁盘布局 / I/O 软件层次 |
| 2010·45 (1) 如何管理磁盘块空闲状态 | 由「2 KB 内存对 16384 个块」反推出每块 1 位 | 1 | 文件系统的空闲空间管理 |
就看「手上做什么」：把簇号 100530 拆成柱面 100、磁道 5、扇区 60，做的是除法取商余，和「决定谁先谁后」没有关系；它和文件系统那边把字节偏移拆成逻辑块号是同一个动作。这几问不该硬收进调度，把它们算在本专题里只会让统一还原变得什么都能装。
反过来说，2019·44 (2) 那一问用的几何参数（每柱面 1000 簇 = 10 × 200 ÷ 2）直接来自题干前言，并不需要先做出 (1)——这恰恰是 (1) 能独立摘出去的最好证据；但下笔的动作不同，复习时该分开练。
交卷前扫一眼
先画轴、再列可选集 · 与次序无关的代价（旋转、传输）先单独算掉 · 「到达」不等于「能抢占」 · 时间片用完才降优先级、被抢占不降 · 平局看谁先入队 · 磁盘比的是柱面距离
配套内容
- 调度的基本概念与目标｜上下文切换机制｜调度算法对比模拟器使用指南
- FCFS 先来先服务调度｜SJF 短作业优先调度｜高响应比优先调度｜时间片轮转调度
- 优先级调度｜多级队列调度｜多级反馈队列调度｜公平调度算法｜多处理机调度
- 磁盘结构与调度｜机械硬盘模拟器使用指南｜固态硬盘｜I/O软件层次结构
考纲要求、但这 4 道真题没有正面考过的（专题的巩固栏里配了题）：
- 平均周转时间、平均等待时间、带权周转时间这三个指标——大纲列了「调度的目标」，而这 4 道真题一次都没让算过它们。2026 那道要的是中断次数、调度次数和四个时刻；2016 那道题面里确实出现了
waitTime，但那是喂给优先数公式的一个计数器，不是让你算出来的指标 - FCFS、SJF、高响应比优先这三种 CPU 调度算法——4 道真题里正面出现过的挑选规则只有优先级加时间片轮转（2026）、C-SCAN（2010）、SSTF（2019）。2010 那道第 (3) 问的答案里出现过 FCFS，但那是「在 SSD 上不必排序」的意思，没有让你按 FCFS 排一次次序再算代价
- 抢占式与非抢占式的直接对照——大纲把「调度的时机与调度方式（抢占式/非抢占式）」写在了「调度的实现」下面。2026 那道全程是抢占式的，没有让同一组参数换成非抢占再推一遍、比一比差多少
- 调度的三个层级，以及调度程序在什么时机被调用——2026 那道把时机限定成「仅当发生时钟中断时」，省掉了判断这一步；至于还有哪些事件会触发调度、哪些时刻反而不能调度（比如正在内核临界区里），真题没问过
- SCAN 与 LOOK——磁盘那两道正面用到的算法只有 C-SCAN 和 SSTF。SCAN 走不走到端点、LOOK 与 SCAN 差在哪一段空跑，没考过
- 扇区的交替编号（交叉因子）——大纲「磁盘」条目下写着「格式化」。一条磁道上的扇区为什么不按 0、1、2 顺序编号、交叉因子该取多少才配得上控制器的传送时间，没考过
- 同一条磁道上记录的间隔排布——读一条、处理一条时，记录紧贴着放会导致每读完一条就错过下一条的开头、要空转近一整圈；怎么摆才能不空转，没考过
- 固态硬盘的读写性能特性与磨损均衡——大纲单列了「固态硬盘」。2010 那道第 (3) 问只让你答 SSD 上该换什么调度策略，读写不对称、擦除以块为单位、磨损均衡这些没问过（暂无配套巩固题）
- 多处理机调度——大纲明列的一条，4 道真题里一次都没出现（暂无配套巩固题）
- 上下文及其切换机制——2026 那道第 (2) 问只让判断「中断间隔从 10 ms 缩到 1 ms，系统开销增大」，至于一次切换到底要保存和恢复哪些东西、这个开销由什么构成，没问过（暂无配套巩固题）
逐题精讲（建设中）——真题作答与 AI 判分入口见站内大题专题。