跳转至

408 高频考点精讲:磁盘调度算法

模块归属:操作系统 · I/O管理
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生


一、 考情档案

  • 近十年考查频次:3 次(2018 年第 30 题、2021 年第 26 题、2024 年第 32 题)
  • 历年总考查频次:6 次(2011 年第 28 题、2014 年第 26 题、2015 年第 28 题、2018 年第 30 题、2021 年第 26 题、2024 年第 32 题)
  • 出题形式:单项选择题(分值均为 2 分)。该考点亦具备与文件系统物理结构分配、磁盘访问时间延迟构成相结合命制综合分析大题的考查潜力。
  • 命题特点:
  • 轨迹推演及寻道距离量化计算:历年真题以给定初始磁头位置、移动方向以及待访问磁道请求序列为前提,要求学生精确推导最短寻道时间优先(SSTF)、扫描算法(SCAN)、循环扫描算法(C-SCAN)的磁头调度轨迹,并准确计算磁头移动总道数与平均寻道长度。
  • 物理边界及折返规则判定:命题重点考察 SCAN/C-SCAN 与 LOOK/C-LOOK 在边界处理上的本质区别。SCAN/C-SCAN 严格要求移动到磁盘的物理极端边界(0 号或最大磁道号),而 LOOK/C-LOOK 仅移动至当前方向的极值请求即可转向或回绕。此外,C-SCAN 在端点间的回绕距离是否计入总位移量是高频陷阱点。
  • 算法本质缺陷与异常状态考查:深入考查不同调度算法的公平性、饥饿现象(Starvation)以及由高并发局部密集访问引发的“磁臂粘着”(Arm Stickiness)病态现象,考查学生对算法工程特性的深层理解。

近十年考查年份分布表格(2016~2025)

+----------+------------+------------------------------------------------------+
|  年份    |    题号    |                       考查主题                       |
+----------+------------+------------------------------------------------------+
| 2016 年  |     -      | 未考查                                               |
| 2017 年  |     -      | 未考查                                               |
| 2018 年  | 第 30 题   | 磁盘调度算法特性剖析及磁臂粘着现象防范               |
| 2019 年  |     -      | 未考查                                               |
| 2020 年  |     -      | 未考查                                               |
| 2021 年  | 第 26 题   | 最短寻道时间优先算法 (SSTF) 磁头移动轨迹与距离计算   |
| 2022 年  |     -      | 未考查                                               |
| 2023 年  |     -      | 未考查                                               |
| 2024 年  | 第 32 题   | 循环扫描算法 (C-SCAN) 边界回绕处理与总寻道距离计算   |
| 2025 年  |     -      | 未考查                                               |
+----------+------------+------------------------------------------------------+

二、 具体考察内容

(一) 磁盘物理构造与访问延迟模型

机械磁盘(Hard Disk Drive, HDD)属于典型的块设备与直接存取存储设备。其物理结构与读写时间延迟构成如下:

                    ┌─────────────────────────┐
                    │      主轴 (Spindle)      │
                    └────────────┬────────────┘
                                 │
           ┌─────────────────────┼─────────────────────┐
           │ 盘面 (Platter) 0     │ [ 磁道 / 扇区 ]      │ <── 磁头 0 (Head)
           ├─────────────────────┼─────────────────────┤
           │ 盘面 (Platter) 1     │ [ 磁道 / 扇区 ]      │ <── 磁头 1 (Head)
           ├─────────────────────┼─────────────────────┤
           │ 盘面 (Platter) 2     │ [ 磁道 / 扇区 ]      │ <── 磁头 2 (Head)
           └─────────────────────┴─────────────────────┘
                                 ▲
                                 │ 由传动臂 (Actuator Arm) 同步驱动
                                 │ 径向移动(寻道)

1. 物理结构基本概念

  • 盘面(Platter Surface):磁盘由若干个叠放在主轴上的双面盘片构成,每个有效表面称为一个盘面,对应一个独立的读写磁头(Head)。
  • 磁道(Track):盘面上划分出的若干同心圆轨迹。磁道由外向内依序编号(通常 \(0 \sim N-1\))。
  • 柱面(Cylinder):所有盘面上半径相同、位置重合的磁道集合。磁道数等于柱面数,柱面号与磁道号在数值上等价。
  • 扇区(Sector):磁道被划分为若干固定弧段,称为扇区(通常为 512B 或 4KB)。扇区是磁盘 I/O 的最小物理寻址与传输单元。

2. 磁盘读写总时间数学模型

从发起磁盘读写请求到数据传输完成,总耗时 \(T_{\text{total}}\) 由三个核心部分构成: $\(T_{\text{total}} = T_s + T_r + T_t\)$

  • 寻道时间(Seek Time, \(T_s\)):磁头臂启动并将磁头沿径向物理移动到目标磁道所耗费的时间。 $\(T_s = s + m \times \Delta n\)$ 其中 \(s\)$ \text{为磁臂启动延迟(Startup Time),} $\(m\)$ \text{为磁头每跨越一个磁道所需的硬件常数,} $\(\Delta n\)$ \text{为移动跨越的磁道道数。寻道时间通常在} $\(3 \sim 15\text{ ms}\)$ \text{量级,是机械磁盘读写过程中耗时最大、波动最剧烈的瓶颈阶段。磁盘调度算法的核心目标正是通过优化磁道服务次序,最小化总寻道移动道数} $\(\sum \Delta n\),从而降低平均寻道时间。
  • 旋转延迟(Rotational Latency, \(T_r\)$ \text{):磁头定位于目标磁道后,等待目标扇区随主轴旋转至磁头正下方所需的时间。若盘片转速为} $\(r\)$ \text{(单位:转/秒,} $\(\text{rps}\)),则平均旋转延迟取盘片旋转半周的时间: $\(T_r = \frac{1}{2r}\)$ 例如,对于 \(7200\text{ rpm}\)$ \text{的硬盘,转速} $\(r = 120\text{ rps}\)$ \text{,平均旋转延迟为} $\(T_r = \frac{1}{2 \times 120} \approx 4.17\text{ ms}\)。
  • 传输时间(Transfer Time, \(T_t\)$ \text{):磁头扫描目标扇区并将数据读出或写入的时间。设待读写数据量为} $\(b\)$ \text{字节,每个磁道容量为} $\(N\) 字节,则: $\(T_t = \frac{b}{r \times N}\)$

(二) 核心磁盘调度算法原理与执行机制

设磁盘请求队列为 \(Q = \{R_1, R_2, \dots, R_k\}\)$ \text{,磁头当前位于磁道} $\(P_{\text{cur}}\)$ \text{,移动方向为} $\(Dir \in \{\text{递增}, \text{递减}\}\)。

1. 先来先服务算法(FCFS, First-Come, First-Served)

  • 核心机制:严格按照 I/O 请求到达就绪队列的先后物理时序依次调度磁头。
  • 执行流程:队列先进先出,不改变任何请求的相对次序。
  • 算法评价:
  • 优点:算法简单,绝对公平,各请求的响应时间方差小,绝无饥饿现象,绝不产生磁臂粘着。
  • 缺点:未考虑磁头移动路径,若请求序列在内外磁道间随机离散跳变,磁头将频繁往返剧烈抖动,平均寻道长度(ASL)极大,系统吞吐量极低。

2. 最短寻道时间优先算法(SSTF, Shortest Seek Time First)

  • 核心机制:基于局部贪心策略,每次在待处理请求集合中选择与当前磁头所在磁道距离最近(即 \(|P_i - P_{\text{cur}}|\) 最小)的请求进行服务。
  • 数学决策模型: $\(R^* = \arg\min_{R_i \in Q} |P_i - P_{\text{cur}}|\)$ 若存在多个距离相等的候选磁道,通常根据先来次序或沿当前移动方向决断。
  • 算法评价:
  • 优点:大幅降低平均寻道时间,吞吐量显著高于 FCFS。
  • 缺点:属于局部最优策略,无法保证全局寻道总距离最小;存在严重的饥饿现象(Starvation)。当磁头在某一局部磁道区域密集服务时,远处磁道的请求可能长时间得不到响应。在极端情况下,若该局部磁道持续产生新请求,将诱发磁臂粘着。

3. 扫描算法(SCAN, 电梯算法)

  • 核心机制:模拟电梯运行逻辑。磁头沿预定的单调方向(如向外向大磁道号方向)移动,沿途依次服务所有碰到的待处理请求。只有当磁头到达磁盘的物理最外端(物理最大磁道号)或最内端(0 号磁道)后,才强制改变移动方向向反向扫描。
  • 执行约束:必须行进至磁盘的物理边界(端点),无论端点处是否存在读写请求。
  • 算法评价:
  • 优点:寻道性能良好,有效避免了长距离来回跳跃,彻底消除了由于距离过远引发的严重饥饿。
  • 缺点:
    1. 边界偏倚不均:磁头刚在某一端掉头时,该端附近的磁道刚刚被服务完毕,请求密度极低;而另一远端在磁头移动过程中积累了大量新请求。这导致两端磁道请求的平均等待时间显著长于中间磁道。
    2. 物理端点无效开销:当最外端或最内端没有请求时,磁头仍盲目行进至物理极限才折返,产生不必要的空程延迟。

4. 循环扫描算法(C-SCAN, Circular SCAN)

  • 核心机制:规定磁头仅在单向移动过程中提供读写服务(例如仅在磁道号自小到大递增移动时服务请求)。当磁头到达磁盘的一个物理端点(如最大磁道号)后,不提供任何服务,直接以最快速度立即回绕至磁盘的另一物理端点(0 号磁道),随后重新开始沿相同的单调方向扫描服务。
  • 执行约束:端点回绕阶段不响应任何 I/O 请求,但回绕跨越的物理磁道数计入磁头移动总位移。
  • 算法评价:
  • 优点:消除了 SCAN 算法两端与中间磁道等待时间不均的缺陷,使所有柱面位置的请求享有基本恒定的平均等待时间。
  • 缺点:回绕跨越了整个磁盘的物理全长(如 \(0 \to N-1\)),在未采用快速跳回机构的设备上会带来额外的物理寻道位移。

5. LOOK 算法与 C-LOOK 算法(边界优化改进)

  • LOOK 算法:对 SCAN 的边界优化。磁头在指定方向扫描时,仅移动到该方向上最远的待处理请求磁道即可立即掉头,无需继续行进至磁盘的物理极限端点(0 或 \(N-1\))。
  • C-LOOK 算法:对 C-SCAN 的边界优化。磁头在单向扫描时,仅移动到该方向上最远的待处理请求磁道,随后直接回绕跳转至另一端最远的待处理请求磁道,回绕过程不响应请求,随后重新沿原方向服务。
  • 算法精要:LOOK 族算法消除了磁头在“最边缘请求”与“物理端点”之间的空转浪费,在实际生产操作系统中应用最为普遍。
【算法寻道路径与边界折返行为对比】

1. SCAN 算法 (到达物理端点 199 掉头):
当前 (100) ──> 请求 (150) ──> 请求 (180) ──> [物理端点 199]
                                                    │ 掉头反向
当前 (50)  <── 请求 (80)  <─────────────────────────┘

2. LOOK 算法 (到达最外侧请求 180 立即掉头):
当前 (100) ──> 请求 (150) ──> [最外请求 180] 
                                    │ 掉头反向
当前 (50)  <── 请求 (80)  <─────────┘

3. C-SCAN 算法 (到达物理端点 199,空程回绕至物理端点 0):
当前 (100) ──> 请求 (150) ──> [物理端点 199]
                                    │
    ┌───────────────────────────────┘ (快速回绕,不服务)
    ▼
[物理端点 0] ──> 请求 (30) ──> 请求 (80) ──> ...

4. C-LOOK 算法 (到达最外侧请求 180,回绕至最内侧请求 30):
当前 (100) ──> 请求 (150) ──> [最外请求 180]
                                    │
    ┌───────────────────────────────┘ (回绕至最小请求,不服务)
    ▼
[最小请求 30] ──> 请求 (80) ──> ...

(三) 核心计算模型与磁臂粘着分析

1. 寻道移动距离与平均寻道长度计算模型

设调度算法生成的磁道服务序列为 \(P_0, P_1, P_2, \dots, P_k\)$ \text{(其中} $\(P_0\)$ \text{为初始磁头位置,} $\(k\) 为服务请求总数)。 - 总寻道距离(Total Head Movement, \(D\)): $\(D = \sum_{i=1}^m |X_i - X_{i-1}|\)$ 其中 \(X_0, X_1, \dots, X_m\) 为磁头实际经历的全部关键转折点(包括物理端点、回绕跳跃点与所有服务请求点)。 - 平均寻道长度(Average Seek Length, ASL): $\(ASL = \frac{D}{k}\)$ 注意:分母 \(k\) 为服务的有效请求总数,中间空载经过的端点与回绕折返点不计入请求数。

2. 磁臂粘着(Arm Stickiness)病态机制与根治策略

  • 现象定义:系统在高并发环境下,磁头长期停留在某一磁道或其邻近极小范围内反复响应新产生的请求,致使其他磁道的 I/O 阻塞停滞,这种硬件磁臂被“锁死”在局部的病态现象称为磁臂粘着。
  • 诱发成因:
  • SSTF 算法依据距离优先,若某进程持续对当前磁道发出 I/O 请求,新请求的寻道距离为 \(0\),调度器将无休止地选择当前磁道,造成全局饥饿与磁臂粘着。
  • SCAN/C-SCAN 在行进至某一磁道时,若该磁道突发大量连续的高频请求,由于其正处于磁头当前物理位置,扫描机制可能会优先将其吞并处理,同样诱发局部驻留粘着。
  • 免疫算法:
  • FCFS 算法:严格按入队时间串行服务,新产生的请求无论位于何磁道均被排在队列尾部,磁头必须先清空既有队列,因而绝不会导致磁臂粘着。
  • 工业级工程防御演进:
  • N 步扫描算法(N-Step-SCAN):将磁盘请求队列按照到达顺序切分为若干长度固定为 \(N\)$ \text{的子队列。磁盘调度以子队列为单位,在单个子队列内部采用常规 SCAN 调度;子队列处理期间新到达的请求必须压入下一个子队列排队。当} $\(N=1\)$ \text{时退化为 FCFS(杜绝粘着);当} $\(N \to \infty\) 时即为 SCAN。
  • 双队列扫描算法(FSCAN):将请求队列显式隔离为两个队列:当前扫描队列 \(Q_{\text{active}}\)$ \text{与新到达请求队列} $\(Q_{\text{wait}}\)$ \text{。所有服务仅在} $\(Q_{\text{active}}\)$ \text{中按 SCAN 执行,扫描过程中产生的所有新请求强制沉淀入} $\(Q_{\text{wait}}\)$ \text{,待} $\(Q_{\text{active}}\) 彻底清空后两队列角色对调。此机制从根源上斩断了同磁道连续请求对磁臂的吸附。

(四) 六大磁盘调度算法核心维度横向对比

算法名称 调度决策依据 寻道效率 (ASL) 公平性 饥饿现象 磁臂粘着风险 边界处理特征
FCFS 到达时间戳先后 最差(随机波动大) 极高(绝对公平) 无 无(完全免疫) 无转向要求,完全随请求跳变
SSTF 局部最小寻道距离 \(\min \|P - P_{\text{cur}}\|\) 较优(局部最优) 差(边缘请求推迟) 有(严重) 极高(连续访问同一道即粘着) 无固定方向,受就近分布驱动
SCAN 单向移动优先顺路处理,到端折返 良好 较好 无 可能存在(高频突发请求同道滞留) 必须触及磁盘物理两极(\(0\)$ \text{与} $\(N-1\))
C-SCAN 单向移动服务,到端快速回绕 良好(响应更均匀) 优良(分布一致) 无 可能存在(高频突发请求同道滞留) 必须触及物理端点,且单向服务全幅回绕
LOOK SCAN 的请求极值改进版 优于 SCAN 较好 无 可能存在 仅移动至该方向最远请求即掉头
C-LOOK C-SCAN 的请求极值改进版 优于 C-SCAN 优良 无 可能存在 仅在最小与最大请求之间单向服务与回绕

三、 近十年真题精讲(2016~2025)

【真题 1】2018 年 408 第 30 题 · 磁盘调度算法特性剖析及磁臂粘着现象

题目
系统总是访问磁盘的某个磁道而不响应对其他磁道的访问请求,这种现象称为磁臂粘着。下列磁盘调度算法中,不会导致磁臂粘着的是( )。
A. 先来先服务 (FCFS)
B. 最短寻道时间优先 (SSTF)
C. 扫描算法 (SCAN)
D. 循环扫描算法 (CSCAN)

【解析】

  1. 知识定位:本题考查磁盘 I/O 管理中的调度策略病态特征——磁臂粘着(Arm Stickiness)的成因与算法防御特性。
  2. 机理分析:
  3. 磁臂粘着本质上是一种极端形式的局部饥饿现象。当系统中某进程(或一组进程)持续高频地对当前磁头所在的特定磁道提交读写请求时:
    • SSTF 算法:每次调度均在队列中选择距离磁头最近的请求。新到达的该磁道请求与磁头距离为 \(0\),因此该请求始终具有最高优先级,调度器被死锁在当前磁道,无法响应其他远端请求,诱发严重的磁臂粘着。
    • SCAN 与 CSCAN 算法:磁头在移动至某磁道执行服务期间,若该磁道持续流入新请求,由于磁头当前恰好对准该磁道,算法将顺带连续处理该磁道的新请求,导致磁臂驻留停滞,同样可能引发磁臂粘着(为此操作系统引入了 FSCAN 与 N-Step-SCAN 进行物理队列阻断隔离)。
    • FCFS 算法:严格遵守队列的 FIFO(先进先出)排队法则。所有 I/O 请求按物理到达时序压入队列尾部,调度器仅处理队头请求。即使当前磁道持续产生后续请求,也只能排在队列末尾等待前面所有异道请求被依次满足。因此,FCFS 具有绝对的时间顺序公平性,绝不会产生磁臂粘着。
  4. 选项辨析与排除:
  5. A 选项正确:FCFS 严格按请求到达次序排队执行,彻底杜绝了局部优先级霸占,不会发生磁臂粘着。
  6. B 选项错误:SSTF 贪心选择距离最近的磁道,距离为 \(0\) 的新请求持续插队,属于最典型的磁臂粘着诱因。
  7. C、D 选项错误:SCAN 与 CSCAN 在未引入多级队列约束的前提下,磁头在当前磁道会持续响应同道新请求,无法天然杜绝磁臂粘着。

正确答案:A


【真题 2】2021 年 408 第 26 题 · 最短寻道时间优先算法 (SSTF) 移动距离精确计算

题目
某系统中磁盘的磁道数为 200 (0~199),磁头当前在 184 号磁道上。用户进程提出的磁盘访问请求对应的磁道号依次为 184, 187, 176, 182, 199。若采用最短寻道时间优先调度算法 (SSTF) 完成磁盘访问,则磁头移动的距离(磁道数)是( )。
A. 37
B. 38
C. 41
D. 42

【解析】

  1. 知识定位:本题考查最短寻道时间优先算法(SSTF)的状态转移与寻道距离计算。
  2. 核心推导步骤:
  3. 初始状态:磁头初始位置 \(P_{\text{cur}} = 184\)。
  4. 待服务请求集合:\(Q = \{184, 187, 176, 182, 199\}\)。
  5. 步骤 1:计算 \(P_{\text{cur}} = 184\) 到各候选请求的距离: $$|184

  6. 184| = 0,\quad |187

  7. 184| = 3,\quad |182

  8. 184| = 2,\quad |176

  9. 184| = 8,\quad |199

  10. 184| = 15$$ 最小距离为 \(0\),调度请求 184。 移动距离 \(\Delta d_1 = |184 - 184| = 0\)$ \text{。当前磁头位于} $\(184\)$ \text{。剩余集合} $\(Q_1 = \{187, 176, 182, 199\}\)。

  11. 步骤 2:从 \(P_{\text{cur}} = 184\)$ \text{出发,计算到} $\(Q_1\) 中各请求的距离: $$|182

  12. 184| = 2,\quad |187

  13. 184| = 3,\quad |176

  14. 184| = 8,\quad |199

  15. 184| = 15$$ 最小距离为 \(2\),调度请求 182。 移动距离 \(\Delta d_2 = |182 - 184| = 2\)$ \text{。当前磁头位于} $\(182\)$ \text{。剩余集合} $\(Q_2 = \{187, 176, 199\}\)。

  16. 步骤 3:从 \(P_{\text{cur}} = 182\)$ \text{出发,计算到} $\(Q_2\) 中各请求的距离: $$|187

  17. 182| = 5,\quad |176

  18. 182| = 6,\quad |199

  19. 182| = 17$$ 最小距离为 \(5\),调度请求 187。 移动距离 \(\Delta d_3 = |187 - 182| = 5\)$ \text{。当前磁头位于} $\(187\)$ \text{。剩余集合} $\(Q_3 = \{176, 199\}\)。

  20. 步骤 4:从 \(P_{\text{cur}} = 187\)$ \text{出发,计算到} $\(Q_3\) 中各请求的距离: $\(|176 - 187| = 11,\quad |199 - 187| = 12\)$ 最小距离为 \(11\)$ \text{(注意:} $\(11 < 12\)),调度请求 176。 移动距离 \(\Delta d_4 = |176 - 187| = 11\)$ \text{。当前磁头位于} $\(176\)$ \text{。剩余集合} $\(Q_4 = \{199\}\)。
  21. 步骤 5:从 \(P_{\text{cur}} = 176\) 出发,响应最后一个请求 199: 移动距离 \(\Delta d_5 = |199 - 176| = 23\)$ \text{。当前磁头位于} $\(199\)。所有请求完成。
  22. 汇总求和: 磁头移动访问序列为:\(184 \to 184 \to 182 \to 187 \to 176 \to 199\)。 总移动距离 \(D = 0 + 2 + 5 + 11 + 23 = 41\)。
  23. 选项辨析:
  24. A 选项(37):若误判步骤 4 转向,错误选择先访问 199(\(|199-187|=12\)$ \text{),序列变为} $\(187 \to 199 \to 176\)$ \text{,距离为} $\(0 + 2 + 5 + 12 + 23 = 42\),与 37 不符;37 往往源于数值计算粗心遗漏小位移。
  25. B 选项(38):常见计算失误干扰项。
  26. C 选项(41):推导无误,完全吻合。
  27. D 选项(42):若步骤 4 中主观臆断顺着方向向大磁道号走,选了 199 再折返 176,则距离为 \(2+5+12+23 = 42\),落入典型贪心误区。

正确答案:C


【真题 3】2024 年 408 第 32 题 · 循环扫描算法 (C-SCAN) 寻道路径与边界回绕距离计算

题目
某磁盘的磁道数为 400(磁道号为 0~399),采用循环扫描算法 (CSCAN) 进行磁盘调度,完成对 200 号磁道的请求后,磁头向磁道号减小的方向移动,若还有 7 个请求,对应的磁道号分别为 300, 120, 110, 0, 160, 210, 399,则完成上述磁盘请求后磁头移动的距离是( )。
A. 599
B. 619
C. 788
D. 799

【解析】

  1. 知识定位:本题考查循环扫描算法(C-SCAN)的移动规约、物理端点触碰机制与回绕距离计算。
  2. 核心推导步骤:
  3. 初始条件梳理:
    • 磁盘全量物理磁道范围:\(0 \sim 399\)$ \text{(磁道总数 400,内侧物理边界为} $\(0\)$ \text{,外侧物理边界为} $\(399\))。
    • 磁头当前所处位置:刚完成 \(200\)$ \text{号磁道,即起点} $\(P_{\text{cur}} = 200\)。
    • 初始移动方向:向磁道号减小的方向移动。
    • 待服务请求集合:\(\{300, 120, 110, 0, 160, 210, 399\}\),共 7 个请求。
  4. 阶段一:沿递减方向单向扫描服务:
    • 磁头自 \(200\)$ \text{号磁道向减小方向移动,待处理请求中} $\(\le 200\)$ \text{的请求集合为} $\(\{160, 120, 110, 0\}\)。
    • 磁头依次经过并服务的序列为:\(160 \to 120 \to 110 \to 0\)。
    • 由于采用的是 C-SCAN(循环扫描算法) 而非 C-LOOK,磁头必须移动至磁盘的物理边界端点。本题中最小物理边界为 \(0\)$ \text{号磁道,而请求中恰好存在} $\(0\)$ \text{号磁道,磁头在到达端点} $\(0\) 的同时服务该请求。
    • 阶段一移动位移: $\(D_1 = |200 - 0| = 200\)$
  5. 阶段二:物理端点回绕阶段(空程快速复位):
    • 到达最小端点 \(0\)$ \text{号后,按照 C-SCAN 规则,磁头不服务任何请求,立即以最快速度直接回绕复位到磁盘的另一端物理极限端点(即最大磁道号} $\(399\))。
    • 注意:虽然请求集合中恰好包含 \(399\)$ \text{号磁道,但在规范的 C-SCAN 定义下,磁头必须复位到物理最外侧边界} $\(399\)。
    • 回绕阶段跨越的物理磁道数: $\(D_{\text{wrap}} = |399 - 0| = 399\)$
  6. 阶段三:从最大端点继续沿递减方向扫描服务:
    • 磁头位于 \(399\)$ \text{号磁道。此时首先服务位于} $\(399\) 处的请求(位移增量为 0)。
    • 剩余待服务请求集合为 \(\{300, 210\}\)。
    • 磁头继续沿递减方向前行,依次访问:\(300 \to 210\)。
    • 服务完最后一个请求 \(210\) 号磁道后调度终止。
    • 阶段三移动位移: $\(D_2 = |399 - 210| = 189\)$
  7. 计算总移动距离: $\(D = D_1 + D_{\text{wrap}} + D_2 = 200 + 399 + 189 = 788\)$
  8. 分步逐段核验法:
  9. 路径轨迹:$$ 200 \to 160 \to 120 \to 110 \to 0 \to \text{[回绕至 399]} \to 300 \to 210 $$。
  10. \(\Delta d(200 \to 160) = 40\)
  11. \(\Delta d(160 \to 120) = 40\)
  12. \(\Delta d(120 \to 110) = 10\)
  13. \(\Delta d(110 \to 0) = 110\)
  14. \(\Delta d(0 \to 399) = 399\)(回绕距离)
  15. \(\Delta d(399 \to 300) = 99\)
  16. \(\Delta d(300 \to 210) = 90\)
  17. 总和 \(D = 40 + 40 + 10 + 110 + 399 + 99 + 90 = 788\)。
  18. 干扰项成因剖析:
  19. A 选项(599):若错误地将回绕视为“瞬时逻辑传送”,没有将 \(0 \to 399\)$ \text{的回绕距离(} $\(399\)$ \text{)计入总位移,得出} $\(200 + 189 = 389\)$ \text{,或者误按单向 SCAN 纯单程} $\(200 + 399 = 599\) 计算。
  20. B 选项(619):混淆了回绕终点,若错误按照 C-LOOK 计算(从 0 跳回未服务的最大请求 399,再到 210,若起始端未算至端点易发生各类偏移错漏)。
  21. C 选项(788):严格遵守 C-SCAN 物理端点回绕规约,计算准确。
  22. D 选项(799):在阶段三中误以为磁头必须再次跑满至物理端点 \(0\)$ \text{(即多算了} $\(210 \to 0\)$ \text{的距离:} $\(788 + 210 = 998\)$ \text{),或者在端点计算中产生了} $\(+1\)$ \text{的栅栏数计数错误(如} $\(399 - 0 + 1 = 400\))。

正确答案:C


四、 综合考法拓展

虽然磁盘调度算法在近十年中主要以单项选择题呈现,但其机制与整个 I/O 子系统、文件系统底层布局高度耦合,在综合应用大题中极具命题潜力。以下提炼三大高频综合考查维度:

(一) 文件物理块映射及磁盘调度综合题型

  • 考法机制:题干给定某种文件分配方式(如连续分配、隐式链接分配、单级/多级索引分配)及目录项(FCB/Inode)。用户进程执行文件读写操作时,需先将文件的逻辑块号(LBN)转换为磁盘的物理块号(PBN)。
  • 解题链路:
  • 跨层地址解析:根据磁盘几何物理参数(每个柱面的磁道数、每个磁道的扇区数),将物理块号转换为三维物理地址 (柱面号/磁道号, 磁头号/盘面号, 扇区号)。 $$ \text{柱面号} = \lfloor \text{物理块号} / (\text{盘面数} \times \text{每道扇区数}) \rfloor $$
  • 提取磁道请求序列:提取出所有待读取文件数据块对应的目标柱面(磁道)序列。
  • 应用调度算法:针对提取出的磁道序列,结合初始磁头位置,利用 SSTF 或 SCAN 计算磁臂移动总距离。

(二) 磁盘 I/O 端到端读写延迟综合估算

  • 考法机制:考查多个离散数据块读写时系统的吞吐效率与总耗时对比。
  • 解题模板: 对每个磁道请求执行流水分解: $\(T_{\text{block}} = T_{\text{seek}} + T_{\text{rotation}} + T_{\text{transfer}}\)$
  • 寻道时间:依据磁盘调度算法推算各请求间的寻道间距 \(\Delta n\)$ \text{,代入} $\(T_s = s + m \times \Delta n\)$ \text{计算具体时间。若相邻两次请求位于同一柱面,则寻道时间为} $\(0\)。
  • 旋转延迟:若无特殊说明,平均取 \(\frac{1}{2r}\);若题目指明了各块在磁道上的具体扇区物理编号,则需结合盘片转动角速度精确推导磁头旋转到目标扇区起始位置的角度位移与耗时。
  • 数据传输:根据扇区弧长或字节大小按转速比例折算。

(三) 扇区交替编号、错位命名及柱面调度的协同优化

  • 背景矛盾:磁盘连续读取多个扇区时,磁头读完一个扇区后需要极短的时间进行缓冲区处理(例如将数据送入控制器缓冲区),而主轴高速旋转,导致磁头掠过紧随其后的物理扇区,不得不额外空转一整圈才能对准下一逻辑扇区。
  • 优化技术:
  • 扇区交替编号(Interleaving):在同一磁道内,逻辑上连续的扇区在物理上间隔若干扇区排列(如编号 \(0, 2, 4, 1, 3, 5\)),使数据处理时间恰好等于掠过间隔扇区的时间。
  • 错位命名(Cylinder Skewing):相邻柱面的同号扇区在物理角度上发生相对扭转偏移,抵消磁头跨越磁道寻道时的微小延迟,确保磁头移至新磁道时恰好对准下一逻辑扇区。
  • 大题综合点:要求考生在给定扇区交替比、磁臂寻道参数及转速条件下,计算顺序读取跨柱面大文件的精确总耗时。

五、 考点速记清单

1. 核心要点速记

  • FCFS:公平性最好,性能最差,唯一完全杜绝磁臂粘着的经典算法。
  • SSTF:贪心选择当前距离最近者,吞吐量高,但会导致严重饥饿与磁臂粘着。
  • SCAN:电梯算法,双向单调扫描,必须碰触磁盘物理端点(0 和 \(N-1\)) 才掉头。
  • LOOK:SCAN 的边界优化,仅到达最边缘待处理请求即掉头,不触碰空闲物理端点。
  • C-SCAN:单向服务,到达物理端点后全幅快速回绕至另一物理端点,回绕距离计入总位移,服务响应方差最小。
  • C-LOOK:C-SCAN 的请求极值优化,仅在最小请求与最大请求之间回绕,不跑端点空程。

2. 核心计算公式汇总

  • 寻道总距离:\(D = \sum_{i=1}^m |X_i - X_{i-1}|\)(包含所有转折点与回绕跳跃点)。
  • 平均寻道长度 (ASL):\(ASL = \frac{D}{k}\)(\(k\) 为服务的实际用户请求总数,端点与折返点不算请求)。
  • 磁盘读写延迟:\(T_{\text{total}} = T_s + T_r + T_t = (s + m \times \Delta n) + \frac{1}{2r} + \frac{b}{rN}\)。

3. 高频避坑指南

  • 陷阱 1:SCAN/C-SCAN 与 LOOK/C-LOOK 边界混淆
    审题务必看清题干标注的是“SCAN/CSCAN”还是“LOOK/CLOOK”。若是 SCAN/CSCAN,必须画到磁盘物理极限(0 或最大道号);若是 LOOK/CLOOK,只画到当前方向的最外/内侧请求。
  • 陷阱 2:C-SCAN 回绕距离漏算
    计算 C-SCAN 的移动距离时,回绕跨度必须计入总道数。若从 \(0\)$ \text{回绕到} $\(399\)$ \text{,该步位移贡献} $\(+399\) 磁道。
  • 陷阱 3:初始点原位请求位移记为 0
    若磁头初始位置恰好包含一个待处理请求,该请求响应的移动距离为 \(0\),直接在原位标记完成,切忌重复计步。
  • 陷阱 4:SSTF 动态距离实时重算
    SSTF 每服务完一个磁道,必须以新停留的磁道作为参考原点,重新计算剩余请求的绝对差值,不可凭直觉一次性按固定区间处理。

4. 极速解题口诀

电梯调度看端点,SCAN 到头 LOOK 止;
单向循环加 C 字,回绕跨度算位移;
贪心就近是 SSTF,饥饿粘着伴其身;
先来先服务最公道,粘着饥饿全除根。