考研笔记

文件的物理结构

这一节回答第 4 章最核心的一个问题：一个文件的第 0 块、第 1 块、第 1000 块，到底放在磁盘的什么地方，操作系统怎么找到它们。

本节是全章计算题的来源，也是与第 3 章内存分页结构最像的一节——“逻辑块号 → 物理块号”的映射思路完全一致，只是把内存页框换成了磁盘块。看清这一层对应关系，后面的三种分配方式就不再是三套孤立的规则。

机制

文件也有”逻辑地址”

磁盘按块（或簇，即若干连续磁盘块的组）为单位读写，文件也因此被划分成等长的逻辑块，从 0 开始编号。用户给出的字节偏移量会先被拆成两部分：

逻辑块号字节偏移量块大小块内偏移字节偏移量块大小

这和内存分页的地址拆分是同一个公式，原因也相同：块（页）是等长的，所以除法与取余能直接完成拆分。

块内偏移在整个转换过程中原样不动，需要”翻译”的只有逻辑块号 → 物理块号。三种分配方式的差别，全部集中在这一步怎么翻译。

连续分配

连续分配要求每个文件在磁盘上占有一组连续的块。 目录项只需记录起始块号和长度，翻译过程是一次加法：物理块号起始块号逻辑块号优点是访问速度最快，而且顺序访问和随机访问都快。 顺序访问快，是因为相邻逻辑块在磁盘上物理相邻，磁头几乎不需要移动；随机访问快，是因为一次加法就能算出位置。这是三种方式中唯一真正 定位的。

缺点有两条，且都很致命。 其一是文件难以增长：后面紧邻的块可能已被别人占用，此时要么整体搬家，要么无法扩展。其二是产生外部碎片：反复创建删除后，磁盘上散落着许多不够大的空闲片段，可以用紧凑来解决，但代价极高。

链接分配之一：隐式链接

隐式链接把”下一块的块号”存放在每个数据块的内部，像一条单向链表。目录项只记录首块号（有的系统还记末块号）。

优点是彻底消除了外部碎片，且文件扩展极其方便——找一个空闲块，改一下链尾的指针即可。

缺点是无法直接访问。 要读第 块，必须从首块开始逐块读出，因为下一块的地址就藏在上一块里，不读出来就不知道。访问第 块需要 次磁盘 I/O。此外，每个块要拿出几个字节存指针，块的有效容量不再是 2 的整数次幂；一旦某个块的指针损坏，其后整条链全部丢失。

链接分配之二：显式链接与 FAT

疑问点：FAT 的具体结构与工作方式

FAT 是什么，具体如何组织与使用。

显式链接的思路只有一句：把散落在各个数据块内部的指针，全部集中到一张表里。 这张表就是文件分配表（FAT, File Allocation Table），一个磁盘（分区）只有一张。

FAT 的结构极其简单：整个分区有多少个簇，FAT 就有多少个表项，第 号表项对应第 号簇。 表项里存的内容只有四种可能：

表项内容含义
一个簇号本簇的下一簇是它
EOF本簇是文件的最后一簇
FREE（通常为 0）本簇空闲
BAD本簇是坏簇，不可使用

假设某文件的目录项记录”起始簇 = 7”，而 FAT 中 FAT[7] = 13、FAT[13] = 4、FAT[4] = EOF，那么这个文件占用的簇依次是 7 → 13 → 4，共三簇。

FAT 的关键在于它被整体读入内存。 系统启动时把 FAT 装进内存，此后追链的动作全部在内存中完成，一次磁盘 I/O 都不需要。这一点是它区别于隐式链接的全部价值所在。

FAT12 / FAT16 / FAT32 中的数字指的是 FAT 表项的位数，即能表示多少个簇号：FAT16 的表项 16 位，最多编号 个簇；FAT32 的表项 32 位（实际使用 28 位）。它不是指”单个文件最大 32GB”，也不是指”每个文件 32 位”，而是决定了这个文件系统能管理多大的分区。

FAT 还兼任空闲块管理：表项为 FREE 的簇就是空闲簇，不需要另设位示图。这一点在 4.3.3 中还会作为一个考点出现。

索引分配

索引分配为每个文件单独建立一张索引表，表中第 项直接记录该文件第 个逻辑块的物理块号。 存放这张表的磁盘块称为索引块，目录项中记录索引块的地址。

翻译过程变成：读索引块 → 取第 项 → 得到物理块号。这是真正的随机访问，与逻辑块号 的大小无关，不需要走任何链。

问题在于一个索引块可能装不下。 若块大小 4KB、每个地址项 4B，一个索引块只能放 1024 个地址，即最多支持 4MB 的文件。三种解决办法：

① 链接方案——把多个索引块用链表串起来，最后一项指向下一个索引块。缺点是查后面的索引块又退化成顺序查找。

② 多层索引——让第一级索引块的每一项指向一个第二级索引块，如同多级页表。 级索引可支持 层数 个数据块，但小文件也要走满层数，访问代价固定偏高。

③ 混合索引——把前两者结合，也是 UNIX 的做法，见下。

UNIX 的混合索引

疑问点：UNIX 混合索引结构的具体组织

UNIX 混合索引结构是怎样组织的。

混合索引的核心思想是：小文件不该为大文件的能力付出代价。

UNIX 的 inode 中含有 13 个地址项 iaddr(0) ~ iaddr(12)，分工如下：

  • iaddr(0) ~ iaddr(9)：10 个直接地址项，直接指向数据块。
  • iaddr(10)：一级间接地址项，指向一个索引块，该索引块的每一项再指向数据块。
  • iaddr(11)：二级间接地址项，指向一个索引块，其每一项指向一个一级索引块。
  • iaddr(12)：三级间接地址项，再多一层。

设块大小 、每个地址项占 字节，则一个索引块可存 个地址。设直接地址项有 个，可寻址的数据块总数为最大文件大小为代入 UNIX 的典型参数（，，故 ；）：

层级可寻址块数覆盖的文件大小
直接（10 项）
一级间接
二级间接
三级间接

这张表就是混合索引全部设计意图的证明：小于 40KB 的文件（绝大多数）完全不用间接索引，一次就能拿到数据块地址；而一旦需要，规模能一路撑到 TB 级。用极少数大文件的额外开销，换取绝大多数小文件的零开销。

判断偏移量落在哪一级

这是计算题的固定套路，分三步：

① 求逻辑块号 ，块内偏移 。

② 判断 落在哪个区间：

直接地址一级间接二级间接三级间接

③ 算索引块内的下标。 一级间接下标为 。二级间接令 ，则第一层下标为 、第二层下标为 。三级间接令 ，三层下标依次为 、、。

访问磁盘次数（假定 inode 已在内存）：直接地址 1 次，一级间接 2 次，二级间接 3 次，三级间接 4 次。规律是每多一级间接就多读一个索引块。若 inode 不在内存，每一项都要再加 1。

边界

显式链接为什么支持随机访问

疑问点：显式链接支持直接访问的原因

显式链接为什么支持直接访问。

因为链在内存里，走链不花磁盘 I/O。

隐式链接和显式链接在逻辑上做的是同一件事——顺着链走 步。差别只在于走这 步的代价：

  • 隐式链接：指针在数据块内部，走一步就得读一次磁盘。走 步 = 次磁盘 I/O。
  • 显式链接：指针在内存的 FAT 里，走一步只是一次内存访问。走 步 = 次内存访问 + 最后读目标块的 1 次磁盘 I/O。

磁盘访问比内存访问慢约十万倍，所以这 步的开销在显式链接下可以忽略不计。 “支持随机访问”这个说法正是在这个意义上成立的。

但必须守住一条边界：显式链接的随机访问不是索引分配那种真正的直接定位。 FAT 仍然要在内存中走 步，是 ；索引分配是取索引表的第 项，是 。只是因为内存太快， 在实践中不构成瓶颈。

显式链接与索引分配的区别

疑问点：显式链接与索引分配的差异

显式链接和索引分配的区别是什么。

两者都把地址信息从数据块里搬了出来，区别在于搬到哪里、按什么组织：

① 表的数量和归属不同。 FAT 全盘只有一张，为整个分区的所有文件服务；索引块是一个文件一张（甚至多张），只服务于这一个文件。

② 表项的语义不同。 FAT 第 项的含义是”第 号簇的下一簇是谁”，索引是按物理簇号索引的；索引表第 项的含义是”本文件第 个逻辑块在哪”，索引是按逻辑块号索引的。这是最本质的一条。

③ 定位方式不同。 FAT 要追链（），索引表是下标直取（）。

④ 空间开销的分布不同。 FAT 的大小只与分区大小有关，与文件多少、大小无关——哪怕分区上只有一个文件，FAT 也是满的；索引块的开销与文件数量和大小成正比，小文件多时索引块的浪费很明显。

⑤ 能否兼管空闲块。 FAT 天然可以（表项为 FREE 即空闲）；索引分配不行，必须另设位示图或空闲链表。

文件中间插入一块，哪种方式 I/O 最多

疑问点：在文件中增加一块时磁盘 I/O 次数最多的分配方式

某 500 个盘块的文件的目录项已调入内存（索引分配，索引块也在内存中），若需要在文件中增加一块，下列分配方式中磁盘 I/O 次数最多的是（　）。 A. 连续分配　B. 隐式链接分配　C. 显式链接分配　D. 索引分配

答案 A。

题干的关键词是”在文件中增加一块”，即中间插入，而不是末尾追加。

连续分配下，插入位置之后的所有盘块必须整体向后移动一块才能腾出位置。500 个盘块的文件，最坏情况下要读出并写回数百个块，磁盘 I/O 数以百计。

其余三种都不需要搬动任何数据块：隐式链接改前后两个块内的指针，显式链接改两个 FAT 表项（在内存中），索引分配改索引表中的若干项（索引块也已在内存）。它们的开销都是常数级的。

这道题必须与”末尾追加”严格区分开。 若改为在文件末尾追加一块，结论会变：连续分配若后面正好有空闲块则只需 1 次写，反而是隐式链接最慢——只知道首块号时，必须顺链读完 500 块才能找到链尾。

所以看到”增加一块”，第一件事是找题干里说的是”中间”还是”末尾”。

FAT 的三道计算题

以下三问同源，条件相同：磁盘块 4KB，一簇 = 2 个磁盘块，以簇为分配单位，最大文件长度 512MB，FAT 表项仅存放簇号。

① 系统支持的最大文件块数。

问的是磁盘块数，直接用最大长度除以磁盘块大小：也可以先算簇：一簇 ， 簇，再 得 131072 块。

② FAT 表项至少多少位。

最大文件占 个簇，要能表示这些簇号，表项至少 16 位 = 2B。

③ FAT 表占多少空间。这三问最容易错的地方是单位。 题干同时出现了”磁盘块”和”簇”，而分配以簇为单位、FAT 按簇建表，但问”文件块数”时问的却是磁盘块。动笔前先把块、簇、字节、位四个单位的换算关系写在草稿纸最上面，是这类题唯一可靠的做法。

另外要分清**“表项位数”和”FAT 总大小”：16 位是每一个表项的宽度，128KB 是整张表**的大小，两者相差一个”表项个数”的因子。

单个文件的最大长度与 inode 总数无关

这一条在 4.1.2 已经论证过，这里给出计算侧的说法：最大文件长度 ，这个式子里出现的全是”一个 inode 内部”的参数——地址项个数 、索引级数、每块能放的地址数 （由块大小 和地址项宽度 决定）。inode 的总数从未出现在式子里。

文件控制信息里存什么物理地址信息

同一个”文件的物理位置”字段，在不同分配方式下装的东西完全不同，这是判断题的常见落点：

连续分配记起始块号 + 长度；隐式链接记首块号；显式链接记起始簇号（后续靠 FAT）；索引分配记索引块地址；混合索引把直接地址与各级间接地址项一起放在 inode 里。

不要以为”inode 里总是列出了文件的全部数据块地址”——只有小文件才如此，大文件的 inode 里存的是索引块的地址，真正的数据块地址在索引块中。

对照速查

连续分配隐式链接显式链接（FAT）索引分配
地址信息在哪目录项数据块内部内存中的 FAT索引块
随机访问最快， 加法不支持支持（内存追链 ）支持， 下标
外部碎片有无无无
文件扩展困难容易容易容易
能否管空闲块—否能否
主要缺点碎片、难增长必须顺链，指针坏则后续全丢FAT 占内存，大小随分区增长小文件索引块浪费
FAT 表项取值含义
簇号下一簇
EOF文件末簇
FREE空闲簇（可用于空闲块管理）
BAD坏簇
混合索引（）块数覆盖大小访问磁盘次数
直接1040KB1
一级间接10244MB2
二级间接4GB3
三级间接4TB4
题眼结论
”在文件中间增加一块”连续分配 I/O 最多
”在文件末尾追加一块”隐式链接可能最慢（要顺链找尾）
“FAT 表项仅存簇号”先算最大簇数 → 定表项位数
”最大文件块数”用最大长度 ÷ 磁盘块大小（不是簇）
“与单个文件长度无关”inode 总数

考点

  • 逻辑块号 → 物理块号的翻译方式，是三种分配方式的唯一区别
  • 连续分配是唯一 定位的，但有外部碎片、难增长
  • 隐式链接不支持随机访问；指针在数据块内部
  • 显式链接支持随机访问的原因是 FAT 在内存，但仍是追链而非直取
  • FAT 全盘一张、按物理簇号索引、可兼管空闲块；索引块一文件一张、按逻辑块号索引
  • FAT12/16/32 的数字是表项位数，决定能管多大分区
  • 混合索引的意图：小文件零间接开销，大文件仍能到 TB 级
  • 最大文件大小 ；访问次数每多一级加 1
  • “中间插入”选连续分配；“末尾追加”结论相反
  • FAT 计算题先统一单位；表项位数 ≠ FAT 总大小

链接

反向链接