文件块与磁盘块

文件的逻辑地址空间会被划分为一个个文件块。外存也被划分为一个个磁盘块或物理块。文件系统要把：

$$
(\text{逻辑块号},\ \text{块内地址})
$$

转换为：

$$
(\text{物理块号},\ \text{块内地址})
$$

块内地址不变，真正需要转换的是块号。

Note

内存与外存之间的数据交换通常以块为单位。一个文件只有 10 B，也可能占用一个完整磁盘块。

![1000](/assets/file-allocation-methods.svg)

连续分配

连续分配要求每个文件在磁盘上占有一组连续的块。目录项中通常记录：

起始块号。
文件长度，或占用块数。

若文件起始块号为 $s$，要访问逻辑块号 $i$，则：

$$
\text{物理块号}=s+i
$$

优点：

支持顺序访问。
支持直接访问，也就是随机访问。
顺序读写速度最快，因为逻辑相邻的块在物理上也相邻。

缺点：

文件扩展不方便。若文件后方没有连续空闲块，可能需要整体迁移。
容易产生外部碎片。
可以通过紧凑处理碎片，但紧凑代价很高。

链接分配

链接分配允许文件离散地分配在多个磁盘块中，分为隐式链接和显式链接。

隐式链接

除最后一个盘块外，每个盘块中保存指向下一个盘块的指针。目录项通常记录：

起始块号。
结束块号。

要访问逻辑块号 $i$，必须从起始块开始顺着指针找。若目标是第 $i$ 个逻辑块，通常需要读入前面的块才能找到目标块的位置，因此访问效率低。

优点：

文件扩展方便。
不产生外部碎片。
外存利用率高。

缺点：

只适合顺序访问，不支持高效随机访问。
块内指针占用少量存储空间。
若题目只说“链接分配”而不说明，一般按隐式链接理解。

显式链接与 FAT

显式链接把用于链接各物理块的指针集中存放在一张表中，称为 FAT，即文件分配表。

FAT 的特点：

一个磁盘通常只有一张 FAT。
开机时 FAT 读入内存并常驻内存。
FAT 表项在物理上连续存放，物理块号可以由表项位置隐含。
目录项只需要记录文件起始块号。

访问逻辑块号 $i$ 时，操作系统从起始块号出发，在内存中的 FAT 中追踪 $i$ 次即可得到物理块号。块号转换不需要额外磁盘 I/O，因此比隐式链接快。

显式链接支持顺序访问和随机访问，也方便扩展文件，但 FAT 本身需要占用一定内存和外存空间。

FAT 表空间计算

FAT 表的每个表项对应一个磁盘块。表项内容保存“下一个块的块号”，也可能保存空闲、坏块、文件结束等特殊标记。

若已知：

系统支持的最大文件长度为 $L_{\max}$。
磁盘块大小为 $B$。

则最大文件至少需要的块数为：

$$
N=\left\lceil \frac{L_{\max}}{B} \right\rceil
$$

为了能在 FAT 表项中表示这些块号，每个表项至少需要：

$$
\left\lceil \log_2 N \right\rceil
$$

位。

若要求把空闲块、坏块、文件结束等特殊状态也计入编码范围，则应把这些状态数一并加到可表示状态中，再取对数上取整。
若只要求“支持最大文件长度”所需的最小 FAT 空间，可按：$$\text{FAT大小}=N \times \left\lceil \log_2 N \right\rceil
$$

位计算。

若题目给的是整个磁盘或分区的块数 $N_{\text{disk}}$，则 FAT 表项数应按磁盘块数算：

$$
\text{FAT大小}=N_{\text{disk}} \times \left\lceil \log_2 N_{\text{disk}} \right\rceil
$$

位。

索引分配

索引分配为每个文件建立一张索引表。索引表记录：

$$
\text{逻辑块号}\rightarrow \text{物理块号}
$$

索引表存放的磁盘块称为索引块；文件数据存放的磁盘块称为数据块。目录项通常记录文件的索引块号。

索引分配的特点：

支持随机访问。
文件扩展方便，只需分配新数据块并增加索引表项。
不产生外部碎片。
索引表需要占用存储空间。
访问数据前可能需要先读入索引块。

索引表过大时

若一个索引块装不下整张索引表，可采用三种方案。

方案	做法	主要问题
链接方案	多个索引块链接起来	查找后面的索引块可能需要顺序读很多索引块
多层索引	一级索引指向二级索引，必要时继续分层	即使小文件也可能需要多次读索引块
混合索引	直接地址、一级间接、二级间接等结合	结构更复杂，但兼顾小文件与大文件

若磁盘块大小为 1 KB，一个索引项为 4 B，则一个索引块可放：

$$
\frac{1024}{4}=256
$$

个索引项。

两层索引可表示的最大文件大小为：

$$
256\times256\times1\text{ KB}=64\text{ MB}
$$

若采用 $K$ 层索引，并且顶级索引表尚未调入内存，则访问一个数据块通常需要 $K+1$ 次读磁盘：读各级索引块，再读目标数据块。

混合索引

混合索引在顶级索引表中同时放入：

直接地址：直接指向数据块。
一级间接地址：指向一层索引表。
二级间接地址：指向两层索引表。
更高层间接地址。

小文件可以通过直接地址访问，磁盘 I/O 次数少；大文件则通过间接索引扩展容量。

分配方式对比

分配方式	目录项内容	优点	缺点
连续分配	起始块号、文件长度	顺序读写快，支持随机访问	产生外部碎片，不利于扩展
隐式链接	起始块号、结束块号	无外部碎片，扩展方便	只能顺序访问，块内指针占空间
显式链接	起始块号，FAT 常驻内存	支持随机访问，扩展方便	FAT 占空间
索引分配	索引块号或顶级索引块号	支持随机访问，扩展方便	索引表占空间，访问前可能需读索引块

文件存储空间管理

外存空闲空间管理要回答三个问题：

用什么结构记录空闲块。
如何分配磁盘块。
如何回收磁盘块。

1000

文件卷通常分为目录区和文件区。目录区保存目录信息、FCB、空闲空间管理信息等；文件区保存文件数据。

空闲表法

空闲表法用表记录每个连续空闲区：

字段	含义
第一个空闲盘块号	空闲区起始位置
空闲盘块数	空闲区长度

它适合连续分配。分配时可以像动态分区分配一样采用首次适应、最佳适应、最坏适应等算法。回收时要考虑回收区与前后空闲区是否相邻，并进行表项合并。

空闲链表法

空闲链表法分为两类。

空闲盘块链

每个空闲盘块中保存下一个空闲盘块的指针。操作系统保存链头、链尾指针。

分配：从链头依次摘下所需盘块。
回收：把回收盘块挂到链尾。

它适合离散分配，但一次分配多个块时可能要重复多次操作。

空闲盘区链

连续的空闲盘块组成一个空闲盘区。每个空闲盘区的第一个块记录：

盘区长度。
下一个空闲盘区指针。

分配时可按首次适应、最佳适应等算法找空闲盘区。回收时若回收区与空闲盘区相邻，需要合并。

空闲盘区链既可用于连续分配，也可用于离散分配；为一个文件分配多个盘块时效率更高。

位示图法

位示图用一个二进制位表示一个盘块。例如：

0 表示空闲。
1 表示已分配。

若字长为 $n$，盘块号、字号、位号都从 0 开始，则：

$$
b=ni+j
$$

$$
i=\lfloor b/n\rfloor,\quad j=b\bmod n
$$

其中 $b$ 是盘块号，$i$ 是字号，$j$ 是位号。

分配时扫描位示图，找到足够的 0 位，计算对应盘块号并把这些位改为 1。回收时根据盘块号计算对应字号、位号，把相应位改为 0。

编号从 0 还是从 1

位示图题目必须先看清楚盘块号、字号、位号从 0 开始还是从 1 开始。起点不同，换算公式会有偏移。

# 成组链接法

空闲表和空闲链表在大型文件系统中可能过大。UNIX 采用成组链接法管理空闲块。

成组链接法的核心：

文件卷目录区中有一个超级块。
系统启动时把超级块读入内存。
超级块保存第一组空闲块数量和空闲块号。
某些空闲块中保存下一组空闲块的信息。

分配时先检查超级块中的第一组空闲块是否足够。若分配到保存下一组信息的块，需要把该块中的下一组信息复制到超级块。

回收时若当前第一组未满，把回收块号加入超级块记录的第一组。若第一组已满，则把超级块中的信息复制到新回收的块中，再让这个新回收块成为新的第一组入口。

文件共享

文件共享意味着系统中只有一份文件数据，多个目录项或用户可以访问同一份文件。共享不同于复制；共享文件被一个用户修改后，其他用户看到的也是修改后的内容。

硬链接

基于 inode 的共享方式也称硬链接。多个目录项指向同一个 inode。inode 中设置链接计数 count，表示有多少目录项链接到它。

删除某个硬链接时：

删除该用户目录中的目录项。
inode 的 count 减 1。
只有 count=0 时，才真正删除文件数据和 inode。

硬链接不会因为某个目录项删除而立即造成数据丢失，但通常要求共享者位于同一文件系统内。

不能给目录文件创建硬链接。若目录可以任意硬链接，目录树可能出现环，路径遍历、递归删除、备份和引用计数回收都会变得复杂，甚至可能无限循环。

目录中的 . 和 .. 是由文件系统维护的特殊目录项，不是普通用户随意创建的目录硬链接。

软链接

软链接也称符号链接。它本身是一个特殊文件，文件内容记录目标文件路径。

访问软链接时，操作系统先发现它是 Link 类型文件，再根据其中保存的路径继续查目录，最终找到目标文件。

软链接类似快捷方式。若目标文件被删除，软链接本身仍可能存在，但再通过该路径就找不到目标文件。

文件保护

文件保护用于保证不同用户对文件有不同操作权限。常见方式包括：

方式	做法	特点
口令保护	文件设置口令，访问前核对口令	开销小，但口令存放在系统中，不够安全
加密保护	文件内容加密，访问时用密码解密	保密性强，但加密/解密需要时间
访问控制	为不同用户或用户组设置读、写、执行等权限	管理灵活，是常见文件保护方式

访问控制

访问控制通常在文件的 FCB 或 inode 中保存访问控制列表。访问控制列表记录不同用户或用户组对该文件能执行哪些操作。

如果系统中用户很多，逐个记录每个用户的权限会让访问控制列表过大。常用做法是使用一个 $m \times n$ 的矩阵来表示访问控制列表 ACL：把用户划分为 $m$ 类，再为每类用户的 $n$ 类访问权限分别进行设置。因此描述一个 ACL 至少需要 $mn$ 位。

例如：

用户类型	读取	写入	删除	执行
拥有者	1	1	1	1
组	1	0	0	0
其他	0	0	0	0

其中 1 表示允许，0 表示不允许。当用户请求访问文件时，系统先判断该用户属于哪一类，再检查该类用户对目标操作是否有权限。