408真题解析-2009-29-操作系统-磁盘电梯调度算法

一 真题2009-29

29题. 假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为：35,45,12,68,110,180,170,195，采用SCAN调度（电梯调度）算法得到的磁道访问序列是（）。

A. 110,170,180,195,68,45,35,12

B. 110,68,45,35,12,170,180,195

A. 110,170,180,195,12,35,45,68

A. 12,35,45,68,110,170,180,195

二 题目要素解析

初始状态： 磁头位于 105 道。

移动方向： 向磁道序号增加的方向（↑）移动。

请求序列： 35, 45, 12, 68, 110, 180, 170, 195。

算法：****SCAN（电梯调度算法）。

• 核心逻辑： 像电梯一样，“要么不回头，回头必到底”。即沿着当前方向一直扫描，处理所有在该方向上的请求，直到没有更远的请求为止；然后立即反转方向，处理另一侧的所有请求。

三 哔哔详解

步骤 1：将请求分为两组

• 当前方向（↑，≥105）：110, 180, 170, 195
• 反方向（↓，<105）：35, 45, 12, 68

步骤 2：对每组排序

• ↑ 组（升序）：110, 170, 180, 195

  （注意：170 < 180 < 195）

• ↓ 组（降序）：68, 45, 35, 12

  （反向扫描时，从高到低访问）

步骤 3：按 SCAN 规则拼接

✅ 最终访问序列：

110, 170, 180, 195, 68, 45, 35, 12

四 参考答案

参考答案A

五 考点精析

5.1 四种磁盘调度算法对比

5.2 饥饿问题

• FCFS、SCAN、C-SCAN：✅ 无饥饿（所有请求最终会被服务）
• SSTF：❌ 可能饥饿（远离磁头的请求长期得不到服务）

5.3 是否需要磁盘边界信息

• 若题目给出磁盘范围（如 0～199），SCAN/C-SCAN 需走到边界
• 若未给出 → 默认走到当前方向最远请求即转向（考研惯例）

5.4 SCAN 与 C-SCAN 的区别

SCAN (电梯调度)：

• 规则： 走到头 → 掉头 → 走回来。
• 特点： 两端的请求只需要移动一次距离。
• 比喻： 真正的电梯，从 1 楼到 10 楼，再从 10 楼回 1 楼。

C-SCAN (循环扫描 / 单向扫描)：

• 规则： 走到头 → 直接瞬移回起点（不处理沿途请求） → 重新开始。
• 特点： 处理请求更公平，两端的磁道移动距离是整个磁盘的长度。
• 比喻： 游乐园的过山车，从起点冲到终点，然后通过地下隧道（不载客）直接回到起点

5.5 LOOK 与 C-LOOK (进阶考点)

LOOK： SCAN 的变种。磁头不是走到磁盘的物理尽头，而是走到最远的请求就停止并掉头。（减少了不必要的空跑）。

C-LOOK： C-SCAN 的变种。磁头走到最远的请求就停止，然后直接跳到最近的请求（通常是另一端的最小请求），开始新的扫描。

考点： 如果题目没说 “到尽头”，而是说 “到最远请求”，那就是 LOOK/C-LOOK。

六 考点跟踪

暂无

说明：本文内容基于公开资料整理，参考了包括但不限于《数据结构》（严蔚敏）、《计算机操作系统》（汤小丹）、《计算机网络》（谢希仁）、《计算机组成原理》（唐朔飞）等国内高校经典教材，以及其他国际权威著作。同时，借鉴了王道、天勤、启航等机构出版的计算机专业考研辅导系列丛书中的知识体系框架与典型题型分析思路。文中所有观点、例题解析及文字表述均为作者结合自身理解进行的归纳与重述，未直接复制任何出版物原文。内容仅用于学习交流，若有引用不当或疏漏之处，敬请指正。