Lecture 13：知识 - 磁盘管理

This note is currently available in Chinese. The original wording, formulas and diagrams are preserved to avoid an unverified technical translation.

磁盘访问时间由寻道、旋转延迟和传输时间组成。调度算法主要减少磁臂移动距离；地址与格式化题要分清柱面、盘面和扇区的层次。

13.1 结构与地址

盘面划分为磁道，磁道划分为物理扇区；扇区是磁盘硬件的基本读写/寻址单位。文件系统逻辑块是软件分配单位，一个逻辑块可以由一个或多个物理扇区组成，二者不能无条件等同。
同一半径、不同盘面的磁道构成柱面；所有磁头装在同一磁臂上，活动头磁盘的磁头共进退。
按磁头是否能径向移动，可分为活动头磁盘与固定头磁盘；后者每磁道可配独立磁头。按盘片能否拆换，还可分为可换盘片磁盘与固定盘片磁盘。这两种分类维度不同。
磁盘地址通常为：

$$ (\text{柱面号/磁道号},\ \text{盘面号/磁头号},\ \text{扇区号}) $$

位数计算：若字段有 $N$ 种可能取值，需要 $\lceil\log_2N\rceil$ 位；盘片数与盘面数需正确换算（每盘片通常双面）。

13.2 访问时间与调度

$$ T_{access}=T_{seek}+T_{rotation}+T_{transfer} $$

算法	选择规则	特点
FCFS	按到达顺序	公平简单，平均寻道可能大
SSTF	最近磁道优先	平均移动小，远端请求可能饥饿
SCAN	磁臂单向扫描到端点再反向	电梯算法，服务较均匀
LOOK	扫到本方向最后请求即反向	不必走到物理端点
C-SCAN/C-LOOK	单方向服务，回到起点再服务	等待时间更均匀

计算移动磁道数时按实际服务顺序逐段求绝对差；不要把回程是否计入与算法规则混淆。
交替编号能降低连续逻辑扇区读取时的旋转等待；优化块布局、预读和延迟写也能改善 I/O 性能。
原 PDF 的 2012 年题还列出三类改善措施：重排 I/O 请求次序、预读取与滞后写、优化文件物理块分布。仅增加磁盘分区数量不会直接缩短磁头寻道或旋转等待，不能当作独立的 I/O 性能优化方法。

13.3 初始化、引导与坏块

物理格式化：划分磁道和扇区、设置校验等。
分区：每分区由若干柱面组成。
逻辑格式化：创建文件系统、根目录和空闲空间管理结构。

ROM 中的自举装入程序定位磁盘启动块，将完整引导程序读入内存，再装入内核。
坏块是硬件故障，OS 不能修复数据面；可通过坏块表、扇区备用/重映射等避免继续分配。简单系统可在文件系统层标记，现代磁盘常由控制器重映射。
SSD 无机械寻道和旋转延迟，随机访问性能好；擦写次数有限，需要磨损均衡。

13.4 图示复核、公式与典型题

访问时间的分解

磁盘一次访问的平均时间由寻道、旋转延迟和传输三部分组成：

$$ T_a=T_s+T_r+T_t $$

设启动磁头臂的固定时间为 $s$，磁头匀速跨过一个磁道需 $m$，本次跨越 $n$ 个磁道；磁盘转速为 $r$ 转/秒（或先换算为转/秒），本磁道有 $N$ 字节，本次传输 $b$ 字节，则：

$$ T_s=s+mn,\qquad T_r=\frac{1}{2r},\qquad T_t=\frac{1}{r}\cdot\frac{b}{N}=\frac{b}{rN} $$

调度算法直接影响的是 $T_s$；在其他条件不变时，$T_r$ 与 $T_t$ 都与转速 $r$ 近似成反比，通常不能由操作系统的磁臂调度消除。

CHS 地址题（2022）

磁盘地址的三个字段是柱面号（磁道号）、磁头号（盘面号）、扇区号。例：4 个双面盘片、每盘面 20,000 条磁道、每磁道 500 个扇区时：

字段	可取值数	至少位数
柱面号	20,000	15 bit
磁头号	$4\times2=8$ 个盘面	3 bit
扇区号	500	9 bit

FCFS 与 SSTF 手算

FCFS 按到达顺序服务。若初始磁头在 100，请求序列为 $55,58,39,18,90,160,150,38,184$，则服务顺序不变，总移动量为：

$$45+3+19+21+72+70+10+112+146=498$$

平均寻道长度为 $498/9\approx55.3$ 个磁道。

SSTF 每次选与当前磁头距离最近的请求，是局部贪心，并不保证总寻道距离全局最小。2021 题中，磁道范围 0--199、初始 184、请求为 $184,187,176,182,199$；初始位置的同号请求不产生移动，之后顺序为：

$$184\to182\to187\to176\to199$$

总移动量为 $2+5+11+23=41$。SSTF 平均寻道时间较短，但持续到达的邻近请求可能使远端请求饥饿。

SCAN 与 C-SCAN 手算

SCAN 沿当前方向服务，到物理端点后才反向（电梯算法）。2009 题中，初始 105 且向磁道号增加方向移动，请求为 $35,45,12,68,110,180,170,195$，服务序列为：

$$110\to170\to180\to195\to68\to45\to35\to12$$

未给最大磁道号时，题目通常只要求给出请求服务顺序；若计算距离且给出了端点，则必须把前往端点的移动也计入。
2015 题中，共 200 个磁道（0--199），初始 58，方向为从外向内，即磁道号增加方向；请求为 $130,42,180,15,199$。SCAN 的轨迹为：

$$58\xrightarrow{72}130\xrightarrow{50}180\xrightarrow{19}199\xrightarrow{157}42\xrightarrow{27}15$$

总移动量为 $325$。这里 199 是物理内侧端点，故到达它后才允许反向。
C-SCAN 只在一个方向服务，到端点后快速返回另一端，返回过程的移动距离也要计入。2024 题中，磁道号 0--399，已完成 200 号请求且向减小方向移动，待请求为 $300,120,110,0,160,210,399$：

$$200\to160\to120\to110\to0\quad(200)$$

$$0\to399\quad(399),\qquad399\to300\to210\quad(189)$$

故总移动量为 $200+399+189=788$。

LOOK、C-LOOK 与饥饿辨析

算法	与对应扫描算法的差异	主要取舍
LOOK	当前方向已无请求时即反向，不必到物理端点。	比 SCAN 少无效寻道。
C-LOOK	当前方向无请求时，直接回到另一端最远的待服务请求，不必到物理端点。	比 C-SCAN 少无效寻道，且仍维持单方向服务的等待均匀性。
FCFS	按到达顺序。	公平、简单；不产生磁臂粘着，但请求分散时寻道距离大。
SSTF	最近请求优先。	平均寻道短，但可能饥饿/磁臂粘着。
SCAN、C-SCAN	按固定方向扫描，到规定端点再反向或回卷。	在每次请求服务有限、扫描方向不被新请求重置的标准定义下，近邻请求不会使磁臂无限停在原处；但不同磁道的等待时间可能不均，负载过高时仍会排队很久。

标准术语必须区分：SCAN/C-SCAN 会继续到规定的扫描端点，LOOK/C-LOOK 只走到当前方向最远的待服务请求。部分教材或题解会把二者简化混称；遇到这类题应以题干给出的移动规则为准，并在答案中写明采用的口径，不能默认互换。

WARNING · 原稿表述边界原 PDF 第 5 页把 SCAN/C-SCAN 与 SSTF 一起列为可能发生“磁臂粘着”，并用不断出现当前方向请求来解释。对于上表所述的标准 SCAN/C-SCAN，新请求不会让磁臂反复改向或取消既定端点，因此不能据此推出无限停留；如果实现改用 LOOK 式动态端点、服务队列持续超载或题目另定规则，才应按具体调度过程重新分析。SSTF 的近邻请求饥饿风险则是明确的。

图示补充

多盘面图中，同半径位置的磁道构成一个柱面；所有磁头装在同一磁臂上，因而只能共进退。一次访问依次经历寻道、选盘面、等待目标扇区旋转到磁头下方。
交替编号让逻辑相邻扇区在物理上留出间隔，以补偿处理完前一扇区后的控制器处理时间，减少连续读的旋转等待。
磁盘初始化顺序为：低级格式化（划分带校验的扇区）→ 分区（若干柱面组成一分区）→ 逻辑格式化（建文件系统、根目录和位图等空闲空间结构）。
ROM 中只保存很小的自举装入程序；它定位固定位置的引导块，把完整自举程序读入内存。简单磁盘可在 FAT 等文件系统结构中标记坏块；复杂磁盘由控制器维护坏块表并以备用扇区重映射，后者对 OS 透明。

13.5 本节复盘

物理扇区是磁盘硬件的基本读写单位，文件系统逻辑块可包含多个扇区；柱面由同半径磁道组成，活动磁头共进退。
磁盘调度主要优化寻道，手算按实际服务次序累计移动距离。
初始化顺序是物理格式化→分区→逻辑格式化；启动块/ROM 与坏块管理是常考补充。