Appearance
磁盘调度算法
概念
磁盘调度（disk scheduling）指当有多个 I/O 请求在磁盘队列里排队时，操作系统决定"先服务哪一个"的策略。
一句话说清它是什么：磁盘调度就是给等待中的读盘请求排队——而排队只有一个目标：让磁头少跑路。
为什么只优化"跑路"：上一章算过账——读一个 4 KB 块的总时间是 12.2318 ms，其中寻道 8.0 ms、旋转 4.1667 ms、传输只有 0.0651 ms。
传输时间只占 0.53%，寻道占了 65%——所以调度算法优化的只是寻道那一段。
⚠️ 三个"不能再少"的事实：
- 磁盘调度管的是"寻道顺序"，管不了"旋转"——旋转延迟靠"交替编号/错位命名"这类物理手段（见
os/31-disk.md），调度只能把请求排得让磁头少走冤枉路。- 调度不会减少请求数，只会改变服务顺序——"优化"的全部空间就是"总移动磁道数"。
- 总移动磁道数完全由"请求集合 + 起始位置 + 移动方向"决定——题目给了这三个量，答案就唯一了。
原理
一、FCFS：先来先服务
text
请求队列: 98 183 37 122 14 124 65 67 磁头起始: 53
就按到达顺序一个个来:
53 ──45──> 98 ──85──> 183 ──146──> 37 ──85──> 122 ──108──> 14
──110──> 124 ──59──> 65 ──2──> 67- 公平：每个请求的等待时间都是"前面所有请求走完"，不存在饥饿。
- 但磁头来回乱窜，本题总寻道 640 个磁道，是理论最优的 2.7 倍。
二、SSTF：最短寻道时间优先
text
每步都选"离当前磁头最近"的那个请求:
53 ──12──> 65 ──2──> 67 ──30──> 37 ──23──> 14 ──84──> 98
──24──> 122 ──2──> 124 ──59──> 183SSTF 是"贪心算法"：每一步都局部最优（总跑 236 个磁道，比 FCFS 少了 63%）。
⚠️ SSTF 的致命缺陷 = 饥饿（starvation）： 假如磁头 53 附近不断有新请求到达（如 60、61、58……），那么 183 这种"远端请求"就永远轮不上——因为每次比较时它总是"最远的"。 "局部最优 ≠ 全局最优" + "新请求可以不断插队" = 饥饿。SSTF 是本章唯一会产生饥饿的算法。
三、SCAN：电梯算法
SCAN（扫描算法）规定磁头只沿一个方向走，"走到头"才折返，回程路上照样服务——它的行为跟电梯一模一样（电梯一路向上，到顶再向下，中间不停反向），所以别名 电梯算法（elevator algorithm）。
text
方向: 向大号(53 -> 199) 磁道范围 0 ~ 199
53 ─12─> 65 ─2─> 67 ─31─> 98 ─24─> 122 ─2─> 124 ─59─> 183 ─16─> 199
│
37 <─162─┘ │
│ │
14 <────────────────23──────────────┘ (到达端点 199 才折返)总寻道 = 331 个磁道，其中 16（走到端点）和 162（从端点折返到 37）是"调度强加的代价"。
四、C-SCAN：循环扫描
C-SCAN（circular SCAN）只在一个方向服务，回程直接"空跑"回起点，不服务任何请求：
text
53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199
──────────── 空跑回 0 (不服务) ────────────> 0
0 -> 14 -> 37 (到达 0 后才重新单向服务)
总寻道 = 382⚠️ C-SCAN 为什么反而更贵（本题 382 > SCAN 的 331）： 因为它多付了一次"从 199 空跑到 0"的 199 个磁道，而换来的好处是"各磁道被服务的等待时间更均匀"。C-SCAN 的设计目标不是"总寻道最短"，而是"公平"——这跟
os/11-scheduling.md里"响应比/轮转 vs 短作业优先"的取舍是同一个逻辑。
五、LOOK 与 C-LOOK：不到端点就折返
LOOK 和 C-LOOK 是 SCAN/C-SCAN 的实用版：磁头走到"最边上的那个请求"就折返，不必真跑到物理端点。
text
SCAN vs LOOK 的差别: "是否走到 199 / 0"
SCAN : 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> [199] -> 37 -> 14 总 331
LOOK : 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 ---------> 37 -> 14 总 299
省掉 183->199->183 这一趟 32 个磁道
C-SCAN vs C-LOOK 的差别: "回程时是否空跑到 0"
C-SCAN : ... -> 183 -> [199] -> [0] -> 14 -> 37 总 382
C-LOOK : ... -> 183 ------------ -> 14 -> 37 总 322
省掉 199->0 这一趟 199 个磁道六种算法的演进关系（一张图记住）：
text
FCFS ──加"就近优先"──> SSTF ──加"不反向"约束──> SCAN 族
│
┌────────────────────────────┴───────────────────┐
│ │
"折返点在哪" "回程服不服务"
│ │
SCAN(到端点) LOOK(到最远请求) SCAN/LOOK(服务) C-SCAN/C-LOOK(不服务)⚠️ 四句话把六个算法钉死：
- FCFS：按到达顺序（最公平、最慢）。
- SSTF：就近优先（最快但有饥饿）。
- SCAN/LOOK：单向走到底再折返，回程也服务（无饥饿，最常用）。
- C-SCAN/C-LOOK：单向走到底，回程不服务（更均匀，但多付空跑代价）。
"LOOK 比 SCAN 少跑一趟、C-LOOK 比 C-SCAN 少跑一整圈"——记住这两句就不会把名字搞反。
六、公平性：谁会被饿死
把"每个请求排在第几个被服务"列出来，饥饿问题就一目了然（请求序列 98 183 37 122 14 124 65 67，起点 53，向大号方向）：
| 算法 | 98 | 183 | 37 | 122 | 14 | 124 | 65 | 67 |
|---|---|---|---|---|---|---|---|---|
| FCFS | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| SSTF | 5 | 8 | 3 | 6 | 4 | 7 | 1 | 2 |
| SCAN | 3 | 6 | 7 | 4 | 8 | 5 | 1 | 2 |
| LOOK | 3 | 6 | 7 | 4 | 8 | 5 | 1 | 2 |
FCFS 的序号就是到达顺序（1~8 单调），没有任何请求被跳过；SSTF 下 183 被推到第 8 位——如果此时新请求持续在 53 附近到达，183 会被无限期推后；SCAN/LOOK 下每个请求的序号是"有界的"（最多等"磁头走完一圈"），所以不会饥饿。
⚠️ "无饥饿"的严格理由：SCAN/LOOK 保证磁头"扫完整个方向"——任何在磁头前进方向上的请求，最长等待时间 = "扫一遍的时间"，是个常数上界。 这个性质叫"有界等待"（bounded waiting），与
os/16-deadlock.md里"用老化解决饥饿"是同一类思路。
示例
例 1：C 实现——六种调度算法的寻道轨迹
参数：请求序列
98 183 37 122 14 124 65 67；磁头起始 53；磁道范围 0 ~ 199；SCAN/C-SCAN/LOOK/C-LOOK 一律先向大号方向。
#include <stdio.h>
#define NREQ 8
#define MAXC 199
static int req[NREQ] = {98, 183, 37, 122, 14, 124, 65, 67};
static void emit(const char *name, int *seq, int n, int total) {
int i;
printf("%-6s 总寻道 %3d, 平均 %7.4f\n", name, total, total / (double)NREQ);
printf(" ");
for (i = 0; i < n; i++) printf("%s%d", i ? " -> " : "", seq[i]);
printf("\n");
}
/* 先来先服务 */
static int fcfs(int head, int *seq) {
int i, total = 0;
seq[0] = head;
for (i = 0; i < NREQ; i++) {
total += head > req[i] ? head - req[i] : req[i] - head;
head = req[i];
seq[i + 1] = head;
}
return total;
}
/* 最短寻道时间优先(距离相同时取柱面号小的) */
static int sstf(int head, int *seq) {
int done[NREQ] = {0}, i, k, total = 0, best, bd, d;
seq[0] = head;
for (k = 1; k <= NREQ; k++) {
best = -1; bd = 1 << 30;
for (i = 0; i < NREQ; i++) {
if (done[i]) continue;
d = head > req[i] ? head - req[i] : req[i] - head;
if (d < bd) { bd = d; best = i; }
}
total += bd; head = req[best]; done[best] = 1; seq[k] = head;
}
return total;
}
static void sortreq(int *s) {
int i, j, t;
for (i = 0; i < NREQ; i++) s[i] = req[i];
for (i = 0; i < NREQ; i++)
for (j = i + 1; j < NREQ; j++)
if (s[j] < s[i]) { t = s[i]; s[i] = s[j]; s[j] = t; }
}
/* SCAN: 走到端点 MAXC 才折返, 回程服务 */
static int scan(int head, int *seq, int up) {
int s[NREQ], i, k = 1, total = 0, cur = head;
sortreq(s);
seq[0] = head;
if (up) {
for (i = 0; i < NREQ; i++)
if (s[i] >= head) { total += s[i] - cur; cur = s[i]; seq[k++] = cur; }
total += MAXC - cur; cur = MAXC; seq[k++] = cur;
for (i = NREQ - 1; i >= 0; i--)
if (s[i] < head) { total += cur - s[i]; cur = s[i]; seq[k++] = cur; }
} else {
for (i = NREQ - 1; i >= 0; i--)
if (s[i] <= head) { total += cur - s[i]; cur = s[i]; seq[k++] = cur; }
total += cur - 0; cur = 0; seq[k++] = cur;
for (i = 0; i < NREQ; i++)
if (s[i] > head) { total += s[i] - cur; cur = s[i]; seq[k++] = cur; }
}
return total;
}
/* C-SCAN: 向大号服务到底, 空跑回 0, 再向大号服务 */
static int cscan(int head, int *seq) {
int s[NREQ], i, k = 1, total = 0, cur = head;
sortreq(s);
seq[0] = head;
for (i = 0; i < NREQ; i++)
if (s[i] >= head) { total += s[i] - cur; cur = s[i]; seq[k++] = cur; }
total += MAXC - cur; cur = MAXC; seq[k++] = cur;
total += cur - 0; cur = 0; seq[k++] = cur;
for (i = 0; i < NREQ; i++)
if (s[i] < head) { total += s[i] - cur; cur = s[i]; seq[k++] = cur; }
return total;
}
/* LOOK: 到最远请求就折返, 回程服务 */
static int look(int head, int *seq, int up) {
int s[NREQ], i, k = 1, total = 0, cur = head;
sortreq(s);
seq[0] = head;
if (up) {
for (i = 0; i < NREQ; i++)
if (s[i] >= head) { total += s[i] - cur; cur = s[i]; seq[k++] = cur; }
for (i = NREQ - 1; i >= 0; i--)
if (s[i] < head) { total += cur - s[i]; cur = s[i]; seq[k++] = cur; }
} else {
for (i = NREQ - 1; i >= 0; i--)
if (s[i] <= head) { total += cur - s[i]; cur = s[i]; seq[k++] = cur; }
for (i = 0; i < NREQ; i++)
if (s[i] > head) { total += s[i] - cur; cur = s[i]; seq[k++] = cur; }
}
return total;
}
/* C-LOOK: 向大号服务到最远请求, 跳到最小请求, 再向大号服务 */
static int clook(int head, int *seq) {
int s[NREQ], i, k = 1, total = 0, cur = head;
sortreq(s);
seq[0] = head;
for (i = 0; i < NREQ; i++)
if (s[i] >= head) { total += s[i] - cur; cur = s[i]; seq[k++] = cur; }
for (i = 0; i < NREQ; i++)
if (s[i] < head) { total += cur - s[i]; cur = s[i]; seq[k++] = cur; }
return total;
}
int main(void) {
int seq[16], i;
printf("磁头起始 %d, 磁道范围 0 ~ %d\n", 53, MAXC);
printf("请求序列:");
for (i = 0; i < NREQ; i++) printf(" %d", req[i]);
printf("\n\n");
emit("FCFS", seq, NREQ + 1, fcfs(53, seq));
emit("SSTF", seq, NREQ + 1, sstf(53, seq));
emit("SCAN", seq, NREQ + 2, scan(53, seq, 1));
emit("C-SCAN", seq, NREQ + 3, cscan(53, seq));
emit("LOOK", seq, NREQ + 1, look(53, seq, 1));
emit("C-LOOK", seq, NREQ + 1, clook(53, seq));
printf("\nSCAN 方向对照 (磁头 53):\n");
for (i = 1; i >= 0; i--) {
int n = NREQ + 2, t = scan(53, seq, i), k;
printf(" 向%s号: 总寻道 %3d, 序列 ", i ? "大" : "小", t);
for (k = 0; k < n; k++) printf("%s%d", k ? " -> " : "", seq[k]);
printf("\n");
}
printf("LOOK 方向对照 (磁头 53):\n");
for (i = 1; i >= 0; i--) {
int n = NREQ + 1, t = look(53, seq, i), k;
printf(" 向%s号: 总寻道 %3d, 序列 ", i ? "大" : "小", t);
for (k = 0; k < n; k++) printf("%s%d", k ? " -> " : "", seq[k]);
printf("\n");
}
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
预期输出：
磁头起始 53, 磁道范围 0 ~ 199
请求序列: 98 183 37 122 14 124 65 67
FCFS 总寻道 640, 平均 80.0000
53 -> 98 -> 183 -> 37 -> 122 -> 14 -> 124 -> 65 -> 67
SSTF 总寻道 236, 平均 29.5000
53 -> 65 -> 67 -> 37 -> 14 -> 98 -> 122 -> 124 -> 183
SCAN 总寻道 331, 平均 41.3750
53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 -> 37 -> 14
C-SCAN 总寻道 382, 平均 47.7500
53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 -> 0 -> 14 -> 37
LOOK 总寻道 299, 平均 37.3750
53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 37 -> 14
C-LOOK 总寻道 322, 平均 40.2500
53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 14 -> 37
SCAN 方向对照 (磁头 53):
向大号: 总寻道 331, 序列 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 -> 37 -> 14
向小号: 总寻道 236, 序列 53 -> 37 -> 14 -> 0 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183
LOOK 方向对照 (磁头 53):
向大号: 总寻道 299, 序列 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 37 -> 14
向小号: 总寻道 208, 序列 53 -> 37 -> 14 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183⚠️ 三点说明：
sstf用d < bd而不是d <= bd——这样"距离相同时"保留的是数组里靠前的那个；本题没有等距的请求，所以结果与 Python 的min(..., key=(距离, 柱面号))一致（有等距时两种写法会给出不同答案，题目若没规定就都写一句"等距时取柱面号小的"）。emit的第四个参数是序列长度，六个算法各不相同：FCFS/SSTF/LOOK/C-LOOK 是NREQ+1 = 9个点；SCAN 多一个端点 199 是 10 个；C-SCAN 多两个端点 199 和 0 是 11 个——写统一成NREQ+1会把端点和请求一起漏掉。- 本机无 C 编译器：此段代码逐行人工审查，并用等价的 Python 实现实跑核对，输出 22 行逐字一致。
例 2：Python——服务序号（饥饿分析）、方向对照与服务时间换算
REQ = [98, 183, 37, 122, 14, 124, 65, 67]
START, MAXC = 53, 199
def fcfs():
seq, tot = [START], 0
for r in REQ:
tot += abs(r - seq[-1]); seq.append(r)
return seq, tot
def sstf():
rem, seq, tot = list(REQ), [START], 0
while rem:
nx = min(rem, key=lambda x: (abs(x - seq[-1]), x))
tot += abs(nx - seq[-1]); rem.remove(nx); seq.append(nx)
return seq, tot
def scan(up=True):
s = sorted(REQ); seq, tot, cur = [START], 0, START
hi = [r for r in s if r >= START]; lo = [r for r in s if r < START]
order = (hi + [MAXC] + sorted(lo, reverse=True)) if up \
else (sorted(lo, reverse=True) + [0] + hi)
for r in order:
tot += abs(r - cur); cur = r; seq.append(r)
return seq, tot
def cscan():
s = sorted(REQ); seq, tot, cur = [START], 0, START
hi = [r for r in s if r >= START]; lo = [r for r in s if r < START]
for r in hi + [MAXC, 0] + lo:
tot += abs(r - cur); cur = r; seq.append(r)
return seq, tot
def look(up=True):
s = sorted(REQ); seq, tot, cur = [START], 0, START
hi = [r for r in s if r >= START]; lo = [r for r in s if r < START]
order = (hi + sorted(lo, reverse=True)) if up else (sorted(lo, reverse=True) + hi)
for r in order:
tot += abs(r - cur); cur = r; seq.append(r)
return seq, tot
def clook():
s = sorted(REQ); seq, tot, cur = [START], 0, START
hi = [r for r in s if r >= START]; lo = [r for r in s if r < START]
for r in hi + lo:
tot += abs(r - cur); cur = r; seq.append(r)
return seq, tot
ALGOS = [('FCFS', fcfs()), ('SSTF', sstf()), ('SCAN', scan(True)),
('C-SCAN', cscan()), ('LOOK', look(True)), ('C-LOOK', clook())]
print('=== ① 总寻道长度与平均寻道长度 ===')
print(' 算法 移动次数 总寻道 平均寻道')
for nm, (seq, tot) in ALGOS:
print(' %-8s %5d %5d %8.4f' % (nm, len(seq) - 1, tot, tot / float(len(REQ))))
print(' FCFS 最差 640; SSTF 最好 236; 两者相差 %.2f 倍' % (640 / 236.0))
print()
print('=== ② 服务序号表: 看谁可能被饿死 ===')
print(' 算法 ' + ' '.join('%5d' % r for r in REQ))
for nm, (seq, tot) in ALGOS:
order, j = {}, 0
for v in seq[1:]:
if v in REQ and v not in order:
j += 1
order[v] = j
print(' %-8s ' % nm + ' '.join('%5s' % order.get(r, '-') for r in REQ))
print(' ★ FCFS 序号就是到达序(1~8), 谁都不会饿;')
print(' SSTF 把最远的 183 推到第 8 位 -> 新请求不断插队时它会无限期等待 = 饥饿;')
print(' SCAN/LOOK 的等待有上界(最长等"扫一遍"), 不会饥饿')
print()
print('=== ③ 起始方向对结果的影响 ===')
for nm, f in [('SCAN', scan), ('LOOK', look)]:
for up in (True, False):
seq, tot = f(up)
print(' %-5s 向%s号: 总寻道 %3d' % (nm, '大' if up else '小', tot))
print(' ★ 同一组请求, 换个方向 331 <-> 236 (SCAN)、299 <-> 208 (LOOK)')
print(' -> 方向由"上一个请求在哪"决定, 题目没给就两个方向都算一遍')
print()
print('=== ④ 寻道只占总服务时间的一部分 ===')
ROT, TRANS = 4.1667, 0.0651 # 7200 rpm + 4 KB 块(沿用 os/31 的锚点)
fixed = (ROT + TRANS) * len(REQ)
print(' 每请求固定付出 旋转 %.4f + 传输 %.4f = %.4f ms' % (ROT, TRANS, ROT + TRANS))
print(' %d 个请求的固定部分 = %.4f ms (与调度算法无关)' % (len(REQ), fixed))
print(' 算法 移动次数 移动磁道 寻道ms 总时间ms')
for nm, (seq, tot) in ALGOS:
moves = len(seq) - 1
se = moves * 2.0 + tot * 0.01 # 2 ms 启动 + 0.01 ms/磁道
print(' %-8s %5d %9d %9.4f %10.4f' % (nm, moves, tot, se, se + fixed))
print(' ★ 注意 C-SCAN 总时间反而略大于 FCFS: 它多付了 199->0 的空跑一趟')
print(' -> "总寻道最短"和"总时间最短"不是一回事, 还要看移动次数')
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
输出对照（真实运行结果）：
=== ① 总寻道长度与平均寻道长度 ===
算法 移动次数 总寻道 平均寻道
FCFS 8 640 80.0000
SSTF 8 236 29.5000
SCAN 9 331 41.3750
C-SCAN 10 382 47.7500
LOOK 8 299 37.3750
C-LOOK 8 322 40.2500
FCFS 最差 640; SSTF 最好 236; 两者相差 2.71 倍
=== ② 服务序号表: 看谁可能被饿死 ===
算法 98 183 37 122 14 124 65 67
FCFS 1 2 3 4 5 6 7 8
SSTF 5 8 3 6 4 7 1 2
SCAN 3 6 7 4 8 5 1 2
C-SCAN 3 6 8 4 7 5 1 2
LOOK 3 6 7 4 8 5 1 2
C-LOOK 3 6 8 4 7 5 1 2
★ FCFS 序号就是到达序(1~8), 谁都不会饿;
SSTF 把最远的 183 推到第 8 位 -> 新请求不断插队时它会无限期等待 = 饥饿;
SCAN/LOOK 的等待有上界(最长等"扫一遍"), 不会饥饿
=== ③ 起始方向对结果的影响 ===
SCAN 向大号: 总寻道 331
SCAN 向小号: 总寻道 236
LOOK 向大号: 总寻道 299
LOOK 向小号: 总寻道 208
★ 同一组请求, 换个方向 331 <-> 236 (SCAN)、299 <-> 208 (LOOK)
-> 方向由"上一个请求在哪"决定, 题目没给就两个方向都算一遍
=== ④ 寻道只占总服务时间的一部分 ===
每请求固定付出 旋转 4.1667 + 传输 0.0651 = 4.2318 ms
8 个请求的固定部分 = 33.8544 ms (与调度算法无关)
算法 移动次数 移动磁道 寻道ms 总时间ms
FCFS 8 640 22.4000 56.2544
SSTF 8 236 18.3600 52.2144
SCAN 9 331 21.3100 55.1644
C-SCAN 10 382 23.8200 57.6744
LOOK 8 299 18.9900 52.8444
C-LOOK 8 322 19.2200 53.0744
★ 注意 C-SCAN 总时间反而略大于 FCFS: 它多付了 199->0 的空跑一趟
-> "总寻道最短"和"总时间最短"不是一回事, 还要看移动次数四条结论：
- 总寻道长度排序：SSTF 236 < LOOK 299 < C-LOOK 322 < SCAN 331 < C-SCAN 382 < FCFS 640；FCFS 与 SSTF 相差 2.71 倍——这就是"调度"的全部价值。
- 服务序号把"公平性"量化了：FCFS 的序号是 1~8 递增（完全按到达序）；SSTF 把 183 推到第 8 位；SCAN/LOOK 族把 65/67 提到第 1/2 位、把 14 放到第 8 位——"谁被推后"就是"谁可能要饿"。注意 SCAN 与 LOOK 的序号表完全相同（差别只在"是否走到端点"，那只影响总寻道，不影响被服务顺序）。
- 方向一变，答案就变：SCAN 向大号 331 / 向小号 236；LOOK 向大号 299 / 向小号 208——本题恰好"向小号更省"（因为 14、37 在低端，先往下走顺路）。所以题目没给方向时，两个方向都要算，别默认。
- "总寻道最短"不等于"总时间最短"：C-SCAN 的 382 个磁道里含"199→0 空跑 199 个磁道"，而且移动次数多达 10 次（每次要付 2 ms 启动开销），于是它的总时间 57.6744 ms 反而比 FCFS 的 56.2544 ms 还大一点——这说明"评价调度算法"至少要看两个量：总移动距离 + 移动次数。
考点
考点
1. 必背结论
- 磁盘调度只优化"寻道时间"——寻道占访问时间约 65%，传输只占 0.53%。
- 六种算法一句话：
- FCFS：按到达顺序（最公平、最慢）。
- SSTF：就近优先（贪心、最快之一、会饥饿）。
- SCAN（电梯算法）：单向走到物理端点才折返，回程也服务。
- C-SCAN：单向服务，回程直接空跑回起点、不服务。
- LOOK：走到最远的请求就折返，回程也服务。
- C-LOOK：单向服务，回头时直接跳到最小请求、不服务。
- "SCAN 到端点、LOOK 到最远请求"——这是两者唯一的区别；"C- 前缀 = 回程不服务"。
- 只有 SSTF 会饥饿（"就近优先 + 新请求可插队"导致远端请求无限期等待）。
- SCAN/LOOK 族"无饥饿"，因为等待有界（最多等"扫一遍"）。
- 锚点（请求
98 183 37 122 14 124 65 67、起点 53、范围 0~199、先向大号）： FCFS 640 / SSTF 236 / SCAN 331 / C-SCAN 382 / LOOK 299 / C-LOOK 322； 平均寻道 80.0000 / 29.5000 / 41.3750 / 47.7500 / 37.3750 / 40.2500； 移动次数 8 / 8 / 9 / 10 / 8 / 8。 - 锚点（方向对照）：SCAN 向小号 236、LOOK 向小号 208（本题"向小号"更省）。
- 锚点（总时间）：每请求固定 旋转 4.1667 + 传输 0.0651 = 4.2318 ms；8 个请求固定 33.8544 ms；按"2 ms 启动 + 0.01 ms/磁道"算，总时间 FCFS 56.2544 / SSTF 52.2144 / SCAN 55.1644 / C-SCAN 57.6744 / LOOK 52.8444 / C-LOOK 53.0744 ms。
- "总寻道最短 ≠ 总时间最短"（C-SCAN 的 382 磁道 = 含 199 个空跑磁道，且移动次数 10 次最多）。
2. 高频陷阱
- 把"SCAN"与"LOOK"混为一谈：SCAN 走到物理端点（0/199）才折返；LOOK 走到最远请求就折返——本题差 32 个磁道（331 vs 299）。
- 把"C-SCAN"与"SCAN"混为一谈：C-SCAN 回程不服务——所以它必须"空跑回起点"，多付 199 个磁道。
- 认为"SSTF 一定最优"：错。它只是"当前这一步最优"（贪心），且有饥饿问题；本题 SSTF 236 确实最短，但换成请求分布不同的题目就不一定了。
- 认为"SCAN 比 SSTF 好，因为它没有饥饿"：不准确。SCAN 的代价是总寻道更长（本题 331 vs 236）——"公平"和"吞吐"本就是权衡。
- 算 SCAN 的总寻道时忘了"端点那一段"：SCAN 必须走到端点（题型默认"走到磁道 0 或 199"），所以序列里要有 199 或 0；漏掉它总寻道会少 16 个磁道（本题）。
- 把 C-SCAN 的"回程空跑"算成"回程服务"：错。C-SCAN 回程不服务任何请求——序列里应写
... -> 199 -> 0 -> 14 -> 37（0 之后才继续服务）。 - 题目没给方向时默认"向大号"：错。这是题目最常见的隐藏条件缺失点——应先说明"默认向大号"，或两个方向都算，本题 331 与 236 差别很大。
- 算"平均寻道长度"时除以"移动次数"：错。平均寻道长度 = 总寻道长度 ÷ 请求个数（本题除以 8，所以 SSTF 是 236/8 = 29.5000）。
- 认为"磁头起始位置不影响结果"：错。起始位置 + 方向共同决定了"先服务哪些请求"——起始 53 与起始 100 会给出完全不同的序列。
- 把"磁盘调度"与"页面置换"混为一谈：错。页面置换是"内存装不下时换谁出局"（
os/23-virtual.md）；磁盘调度是"多个读盘请求谁先来"。 一个是空间问题、一个是顺序问题。 - 说"C-SCAN 比 SCAN 更好"：不准确。C-SCAN 的优点是"等待时间更均匀"，代价是"总寻道更长"（本题 382 > 331）——它用吞吐换公平。
- 把"移动次数"漏掉只看磁道数：不准确。每次移动都有固定启动开销（本题设 2 ms）——C-SCAN 移动 10 次、FCFS 只 8 次，这个差在总时间上正好翻盘。
3. 解题模板（"磁盘调度题"）
① 抄下三个已知量: 请求序列 / 磁头起始位置 / 磁道范围(含端点 0 与 MAX)
② 逐个算法手推序列, 每步只写"当前磁头 -> 下一个目标"
FCFS : 按题目给的顺序, 一个不落
SSTF : 每步选距当前最近的; 等距时取柱面号小的(要声明)
SCAN : 先向<题目指定方向>服务沿途请求 -> 走到端点(0 或 MAX) -> 折返服务剩余
C-SCAN: 同 SCAN 的单向部分 -> 走到端点 -> 空跑到另一端 -> 再单向服务剩余
LOOK : 同 SCAN 但"走到最远请求"就折返(不写端点)
C-LOOK: 同 C-SCAN 但来回都不写端点
③ 总寻道 = 相邻两点距离之和; 平均寻道 = 总寻道 / 请求个数
④ 若问"哪个会饥饿": 答 SSTF; 理由 = 就近优先 + 新请求可插队 -> 远端请求无限期等待
⑤ 若问"哪个最好": 不能只看总寻道
还要看"移动次数"与"等待是否均匀"; 一般答"SCAN/LOOK 族综合最好"
⑥ 方向没给 -> 两个方向都算, 并把两个答案都写上4. 与相邻章节的接口
os/31-disk.md（磁盘组织与空闲空间管理）：本章的"寻道 8 ms、旋转 4.1667 ms、传输 0.0651 ms"全部来自那一章的锚点；"交替编号 / 错位命名"治旋转，本章治寻道——两章合起来才是"把磁盘 I/O 时间压下去"的完整手段。os/32-io.md（I/O 管理）："磁盘 I/O 请求队列"就是本章排队的那条队列；通道方式一次能接过多个请求，正是本章算法要处理的对象。os/11-scheduling.md（处理机调度）："SSTF 对应短作业优先（有饥饿）、FCFS 对应先来先服务、SCAN 对应轮转（公平但有开销）"——两章的算法谱系一一对应，是同一套权衡在不同资源上的复现。os/16-deadlock.md（死锁与饥饿）："饥饿"的定义与"用老化解决饥饿"在那章；本章的 SSTF 是"饥饿"在 I/O 场景里的实例。ds/22-mst.md与ds/23-shortest.md（图算法）："每步选最近的"就是 Dijkstra/Prim 的贪心骨架——SSTF 与它们是同一种"局部最优"思路，也共享同一类"贪心不保证全局最优"的局限。arch/41-io.md（I/O 系统）：那章讲"DMAC 怎么搬"，本章讲"磁头先去哪"——一个管传输、一个管顺序。
小结
- 磁盘调度只管"寻道顺序"——因为寻道占访问时间约 65%、传输只占 0.53%。
- 六种算法一句话：FCFS（按到达序）/ SSTF（就近，会饥饿）/ SCAN（到端点折返，回程服务）/ C-SCAN（回程不服务）/ LOOK（到最远请求折返）/ C-LOOK（回头不服务）。
- 两个关键字："SCAN vs LOOK" 差在"是否走到物理端点"；"加 C-" 差在"回程是否服务"。
- 只有 SSTF 会饥饿；SCAN/LOOK 族的等待有界。
- 锚点（起点 53、请求
98 183 37 122 14 124 65 67、范围 0~199、向大号）：FCFS 640 / SSTF 236 / SCAN 331 / C-SCAN 382 / LOOK 299 / C-LOOK 322；移动次数 8/8/9/10/8/8。 - 方向是隐藏条件：SCAN 向小号 236、LOOK 向小号 208——本题"向小号"更省。
- 评价算法至少看两个量：总移动磁道数 + 移动次数；C-SCAN 的 382 磁道 + 10 次移动使它总时间反而比 FCFS 略高。
- "文件与设备"支线到此闭环：文件怎么组织（30）→ 磁盘空间怎么管（31）→ I/O 怎么送到设备（32）→ 磁头怎么排顺序（33）。 408 的操作系统部分全部结束，往下进入计网。
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。