题目

假设计算机系统采用 C-SCAN（循环扫描） 磁盘调度策略，使用 2 KB 的内存空间记录 16384 个磁盘块的空闲状态。

图（文字版）：磁盘从外到内编号 0~100 号磁道，磁头当前位于 100 号磁道、运动方向为"磁道号增大方向"（即向内）。某扇区在磁道上随机分布。

(1) 请说明在上述条件下如何进行磁盘块空闲状态的管理。

(2) 设某单面磁盘的旋转速度为 6000 rpm，每个磁道有 100 个扇区，相邻磁道间的平均移动时间为 1 ms。若在某时刻，磁头位于 100 号磁道处，并沿着磁道号增大的方向移动，磁道号的请求队列为 50, 90, 30, 120，对请求队列中的每个磁道需读取 1 个随机分布的扇区，则读完这个扇区共需要多少时间？需要给出计算过程。

(3) 如果将磁盘替换为随机访问的 Flash 半导体存储器（如 U 盘、SSD 等），是否有比 C-SCAN 更高效的磁盘调度策略？若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。

解析

（1）用位示图管理磁盘块空闲状态

磁盘块共有 16384 个，每块用 1 位记录"空闲（0）/ 占用（1）"，所需位数 = 16384 bit。换算到字节：

正好等于题面给的 2 KB 内存。所以用位示图法：拿一个 2 KB 的位图、每位对应一个磁盘块，分配 / 回收时只要找 / 改对应位即可。

编者注（数字凑得这么整不是巧合）：题目给"2 KB 内存 + 16384 块"显然就是在暗示位示图——2 KB = 16384 bit。考场上看到"内存大小 ÷ 块数 = 1/8 字节"立刻反应"位示图"。其它管理方法（空闲表、空闲链表、成组链接）所需空间都比位示图大、与本题数据对不上。

（2）C-SCAN 总耗时计算

Step 1：决定访问磁道顺序

C-SCAN 规则：单方向扫描（这里向内），到端点后直接跳回另一端（不服务返程上的请求），再单向扫描。

请求队列：50, 90, 30, 120。当前磁头在 100 号、向内（即向 120 号方向）。

阶段	当前位置 → 下一目标	服务的请求	移动距离（磁道数）
向内扫到底	100 → 120	120	20
跳回外端（瞬时跳转）	120 → 0	（只跳，不服务任何请求）	跳回不算寻道（约定）
重新向内扫	0 → 30	30	30
继续	30 → 50	50	20
继续	50 → 90	90	40
完毕	—	—	总移动 = 20 + 30 + 20 + 40 = 110 磁道

编者注（C-SCAN 算法的"跳回"）：408 标答里 C-SCAN 的"跳回"通常按0 距离 / 0 时间算（理想化），不计入寻道距离。也有教材把跳回计成"相当于跨整个磁盘"的额外时间——本题按教材主流写法不计。如果题目特别注明"跳回需要 X ms"再加上即可。

题目原标答给的顺序是 120 → 30 → 50 → 90，对应距离 20+90+20+40=170 —— 这把"跳回 120→0 的瞬时跳转"也算成 90 磁道的寻道。这是 408 标答的做法，按它来即给分。

我们这里沿用标答的写法：

服务顺序	移动磁道数
100 → 120	20
120 → 30（含跳回）	90
30 → 50	20
50 → 90	40
合计	170

Step 2：寻道时间

Step 3：旋转延迟

转速 6000 rpm = 100 转/秒 → 每转 10 ms。平均旋转延迟 = 半转 = 5 ms（扇区随机分布时按平均算）。

4 个请求各等一次：

Step 4：传输时间

每磁道 100 个扇区，读 1 个扇区 = 转过 1/100 圈 = 0.1 ms。

Step 5：总时间

编者注（易错点）：

• 三大块时间分清楚：寻道（磁臂物理移动）、旋转延迟（等扇区转到磁头下）、传输（磁头读完扇区）。少算任何一块都会扣分。
• "扇区随机分布"暗示用平均值：旋转延迟取半转（5 ms），不是最坏情况一整圈。
• 传输时间不要按磁道数算：本题每磁道只读 1 个扇区，所以是 4 × 0.1 ms，而不是 4 × 10 ms（满磁道）。

（3）SSD 上比 C-SCAN 更优的策略

有，可以用 FCFS（先来先服务）。

C-SCAN 的"按磁道排序减少寻道"是因为机械磁盘有磁臂物理移动开销（单位 ms 级）和旋转延迟（毫秒级）——把请求按磁道顺序排可以大幅减少磁臂往复移动的距离。

但 SSD / U 盘是电子寻址（无机械臂、无旋转），任意位置访问时间近似常数（微秒级），对 I/O 顺序完全不敏感。这种情况下：

• C-SCAN 这种"基于磁道排序"的策略不再有优势——排序本身要消耗 CPU 时间
• 直接按 FCFS 顺序服务，无需排序，调度开销最小、响应最快

编者注（趋势补充）：SSD 时代主流策略是 **NOOP（FCFS 改良版）**或 deadline / mq-deadline——核心思想都是"少排序、按到达顺序服务、保证最长延迟有上界"。教材常考的 SCAN / C-SCAN / SSTF 等磁臂调度算法，只对机械磁盘有意义，遇到 SSD 题型直接答 FCFS / NOOP 即可。