OS-7/8 文件系统与 I/O 管理

这一部分为什么存在？

内存是易失的，程序和数据必须持久保存到磁盘。但磁盘是“以块为单位、机械寻道、毫秒级”的设备，与内存“按字节、纳秒级”的世界完全两套语言。于是产生两组问题：

文件系统（OS-7）：

1. 用户不想管“我的数据在第几磁道第几扇区”——需要把一堆磁盘块抽象成文件（有名字的字节序列）；
2. 几百万个文件怎么组织查找——需要目录；
3. 文件该占哪些磁盘块、空闲块谁来记——需要文件分配与空闲空间管理。

I/O 管理（OS-8）：

4. 设备千差万别（键盘/磁盘/网卡/打印机），程序不能每种都写一套——需要统一的 I/O 软件层次与设备独立性；
5. 独占设备（打印机）不能真共享——需要 SPOOLing 虚拟化；
6. 磁盘机械寻道极慢，访问顺序直接影响性能——需要磁盘调度算法。

没有这层抽象：每个程序都要自己算磁道扇区，文件无法共享和保护，磁盘访问乱序导致大量寻道浪费。

flowchart TD
    A["磁盘块世界 ↔ 用户字节世界"] --> B["文件 = 抽象的字节序列<br/>属性记在 FCB / inode"]
    B --> C["目录：文件名 → inode 号<br/>树形目录解决命名与查找"]
    B --> D["文件怎么占盘？<br/>连续 / 链接 / 索引 / 混合索引"]
    A --> E["空闲块怎么记？<br/>位图 / 空闲链表 / FAT"]
    A --> F["设备太多太杂<br/>→ I/O 软件分层 + 设备独立性"]
    F --> G["独占设备 → SPOOLing 虚拟成共享"]
    A --> H["寻道是磁盘性能瓶颈<br/>→ 磁盘调度：FCFS/SSTF/SCAN/C-SCAN"]

核心概念：

1. 三种文件分配方式与混合索引计算（必考模板）

混合索引最大文件长度模板（来源：复习资料 P3 §8.2）：每索引块可存 $n$ = 块大小/地址项大小 个块号，则

$L_{max} = (\text{直接项数} + \text{一级项}\times n + \text{二级项}\times n^2 + \text{三级项}\times n^3)\times \text{块大小}$

• 2010-30：4 直接 + 2 一级 + 1 二级，块 256B、地址项 4B（$n=64$）→ 1057KB。
• 2018-46：8 直接 + 一/二/三级各 1，簇 4KB（$n=1024$）→ 约 4TB+4GB+4MB+32KB；该题还考“获取 F1(6KB) 与 F2(40KB) 最后一个簇号的时间是否相同”——不同：F1 末块走一级间接（读 1 索引块），F2 走二级间接（读 2 索引块）。
• 2015-29：偏移 1234 在直接区（访 1 块）；偏移 307400 落在二级间接区（读 2 索引块 + 1 数据块 = 3 块）——“读哪一层索引”是定位访问次数的标准考法。
• 2012-46：4TB 盘、块 1KB → 块号至少 4B；FCB 512B 索引表区全做直接索引 → 128 项 → 单文件最大 128KB。

2. 位图空闲管理换算（必考模板）

$\text{位图块号} = \text{起始块} + \left\lfloor \frac{b}{\text{块大小}\times 8} \right\rfloor,\qquad \text{块内字节} = \frac{b \bmod (\text{块大小}\times 8)}{8}$

2015-31：释放块 409612，位图在 32~127 块、块 1024B（8192 bit）→ 块号 32+50 = 82、块内字节 1。2014-27：10GB、簇 4KB → 位图 $10\times2^{30}/2^{12}/8/2^{12} = 80$ 簇。

3. I/O 软件分层与一次 I/O 的旅程

用户软件（库函数）→ 设备独立软件（逻辑设备名映射、缓冲、块大小屏蔽）→ 设备驱动程序（把抽象命令翻译成具体控制器寄存器操作；簇号→柱面/磁道/扇区的换算就在这里，2019-44 第 3 问）→ 中断处理程序（I/O 完成后唤醒等待进程）→ 硬件。分层回答了“千差万别如何统一”：每层只对上一层暴露统一接口。

缓冲：单缓冲 10 块 = 1550μs、双缓冲 = 1100μs（2011-31：读入 100 + 传送 50 + 分析 50 的流水化分析，双缓冲让读入与分析重叠）。

4. 磁盘调度：寻道时间是瓶颈

磁盘一次访问 = 寻道 + 旋转延迟 + 传输，其中寻道占大头，调度算法重排请求队列以减少磁头总移动：

经典算例（磁头 50 向增，请求 98,183,37,122,14,124,65,67，来源：复习资料 P3 §9.1）：FCFS 643、SSTF 239、SCAN 302、C-SCAN 353。

真题：2009-29（105 向增 SCAN 序列 110,170,180,195,68,45,35,12）、2015-32（58 向内 SCAN 移动 325）、2024-32（C-SCAN 完成 200 后向减 → 移动 788）、2019-44（柱面/磁道/扇区换算 + SSTF 排序）、2010-45（C-SCAN + 位图 + SSD 综合大题：SSD 无机械寻道，FCFS 即可——这正是 X-4 连接点）。

文件逻辑结构 vs 物理结构（易混对）：为什么易混——都有“结构”二字且都与文件组织有关。本质区别——逻辑结构是用户看到的信息组织（流式/记录式），物理结构是磁盘上的块组织（连续/链接/索引）。判别线索：题目问“记录怎么排序”→ 逻辑；问“占哪些块、随机访问快不快”→ 物理。

磁盘调度 vs 进程调度（思想迁移）：SSTF ≈ SJF（最短优先、都饥饿），SCAN ≈ 带方向的公平轮询，FCFS 同名同义。考试借此考“饥饿”“黏着”概念迁移（2018-30）。

硬链接 vs 软链接：硬链接共享同一 inode（计数 +1，删原名文件仍在）；软链接存路径字符串（计数不变，原文件删则链接失效）（2009-31）。

形态一：混合索引计算：2010-30、2012-46、2015-29、2018-46、2022-45（索引结点 + 目录树 + 读文件需几个磁盘块）。触发词：“直接/一级/二级间接地址项”→ 立即算 $n$ = 块/地址项。

形态二：位图与簇计算：2014-27、2015-31、2017-26、2024-26。

形态三：磁盘调度序列与移动量：2009-29、2015-32、2018-30（磁臂黏着）、2019-44、2024-32、2010-45（含 SSD 之问）。

形态四：概念辨析：FCB/inode/目录（2009-30、2009-31、2020-31、2022-24/45）、空闲管理数据结构（2019-26：位图/空闲链/FAT 可以，索引结点不行）、SPOOLing（2016-31）、设备独立性（2009-32）、单双缓冲（2011-31）。

来源：真题markdown/2009-2024统考真题.md 对应题号；复习资料 P3 §八、§九。

• 向前依赖：OS-5/6（页面交换区在磁盘上，缺页最终落到文件/磁盘的读写；位图与页帧管理思想同源）；OS-1（I/O 阻塞与唤醒）。
• 向后引出 / 跨学科：
  • 磁盘构造（磁道/扇区/记录方式）→ CO 外存；簇号→物理地址由驱动程序完成（2019-44 第 3 问，X-4）；
  • I/O 数据搬运方式（程序查询/中断/DMA）→ CO-7 / X-3；文件读写的缓冲管理 ↔ Cache 思想（X-7）；
  • 索引分配 = 多级索引树，与多级页表、B+ 树同构（X-8；数据库索引的源头）；
  • SSD 无寻道 → 调度算法选择改变（2010-45 第 3 问）→ 新技术对旧机制的修正。

1. 为什么需要文件系统？（磁盘块世界 ↔ 用户字节世界的抽象）
2. 文件的属性记在哪？为什么要把文件名从 FCB 中拆出去？（inode；目录检索提速）
3. 树形目录解决了什么问题？硬链接和软链接差在哪？
4. 文件占盘有哪三种方式？各自能不能随机访问、好不好扩展？
5. 混合索引怎么算最大文件长度？读某偏移量要访问几个磁盘块？（先定 $n$，再看落在哪一层）
6. 空闲块怎么记？位图换算公式？（块号→位图块号/字节号）
7. 设备千差万别，程序怎么做到统一使用？（I/O 分层 + 逻辑设备名）
8. 独占的打印机怎么让多进程“同时”用？（SPOOLing：输入井/输出井）
9. 缓冲为什么能提速？单缓冲和双缓冲差在哪？（重叠 I/O 与 CPU）
10. 磁盘一次访问的时间构成？大头是什么？（寻道）
11. 四种磁盘调度算法各怎么排？谁会饥饿/黏着？SCAN 和 C-SCAN 差在哪？（折返 vs 跳回）
12. 换成 SSD 后调度策略该怎么变？为什么？（无机械寻道，FCFS 即可——接 X-4）