File

文件定义

文件是一组有意义的信息或数据集合。用户通常通过文件名、路径和应用程序来使用文件；操作系统则需要进一步记录文件的属性、外存位置、访问权限和打开状态。

常见文件属性：

属性	含义
文件名	由用户创建，便于用户查找；同一目录下通常不允许重名
标识符	系统内部唯一标识，对用户不要求可读
类型	指明文件类型，如文本、图片、目录、链接文件等
位置	用户看到的是路径；操作系统还要记录文件在外存中的位置
大小	文件当前占用的数据量
时间	创建时间、上次修改时间等
所有者	文件所属用户或用户组
保护信息	访问权限、口令、加密信息等

文件元数据与索引节点

FCB

FCB 是文件控制块。每一个文件对应一个 FCB 。

FCB 通常包含：

内容	作用
文件名	实现了文件名到文件实体的映射，因此实现按名查找
类型	区分普通文件、目录、链接文件等
存取权限	用于文件保护
物理位置	指向文件数据或索引结构在外存中的位置
逻辑结构、物理结构	决定如何解释和定位文件内容
时间、所有者等信息	文件管理和保护所需的元数据

inode

查找目录时，最常用的信息是文件名。若 FCB 中保存了所有文件属性，目录项会很大，目录检索需要读入更多磁盘块。

inode 的思想是把目录项文件名与其他信息分离：

结构	保存内容
目录项	文件名 + inode 号
inode	除文件名之外的属性、权限、外存位置等信息

这样只有文件名匹配后，才需要读入 inode。

假设一个 FCB 为 64 B，磁盘块大小为 1 KB，则每块只能放 16 个 FCB。若某目录有 640 个目录项，平均检索 320 项，约需读 20 个目录块。

若目录项缩小为 16 B，则每块可放 64 个目录项，平均检索同样的 320 项只需读约 5 个目录块。目录项瘦身能明显减少目录检索 I/O。

inode 可分为：

磁盘 inode 通常保存：

• 文件类型和访问权限；
• 所有者 UID、所属组 GID；
• 文件大小；
• 访问、修改和 inode 状态改变时间；
• 硬链接计数；
• 数据块地址、区段或各级索引指针；
• 与扩展属性、访问控制表等附加元数据有关的索引。

文件名不在 inode 中，而在目录项中。同一个磁盘 inode 因此可以被多个硬链接目录项引用。

类型	含义
磁盘 inode	存放在外存中的 inode
内存 inode	调入主存后的 inode，通常还会增加是否被修改、打开计数等运行时信息

文件的基本操作

文件操作看起来是在操作整个文件的内容，但操作系统实际处理的是三类对象：

• 目录项、FCB 或 inode：记录文件名、属性、权限、外存位置等元数据。
• 打开文件表：记录本次打开的状态，例如读写指针、访问模式、打开计数。
• 文件数据块：真正保存文件内容的外存块。

因此，open 和 close 不是把整个文件搬入或搬出内存。它们主要建立或撤销访问文件所需的内存数据结构。真正把文件内容读入内存的是 read、缺页调入，或其他 I/O 过程。

创建文件

创建文件时，用户通常给出文件路径、文件名和初始属性。操作系统需要：

1. 根据路径找到目标目录。
2. 检查同一目录下是否已有同名文件。
3. 在目录中建立目录项、FCB 或 inode。
4. 记录文件名、类型、权限、时间、所有者等属性。
5. 必要时为文件分配初始外存块；若创建的是空文件，也可以暂不分配数据块。

创建文件的核心是建立文件名到文件控制信息的映射。它不一定立即写入大量文件数据。

删除文件

删除文件时，用户通常给出路径和文件名。操作系统需要：

1. 根据路径找到目标目录文件。
2. 找到文件名对应的目录项。
3. 检查删除权限。
4. 根据目录项、FCB 或 inode 记录的物理位置回收文件占用的磁盘块。
5. 删除目录项，并更新空闲空间管理结构。

删除文件通常表示文件系统不再把这些磁盘块视为该文件所有；它不等于立刻把磁盘上的每个字节清零。

打开文件

系统要求读写前先 open。打开文件时，操作系统会按名查找，查找目录项、检查权限，并把文件相关信息复制到内存中的打开文件表。

打开后，系统返回一个编号，也就是文件描述符。之后 read 和 write 用文件描述符指明文件，不必每次重新用路径查目录。

Important

打开文件并不是把文件数据全部读入内存。open 主要把目录项、FCB 或 inode 中的必要信息调入内存，并建立进程打开文件表和系统打开文件表。

一次 open 通常会形成两级记录：

结构	保存内容
进程文件描述符表	文件描述符、描述符标志、指向打开文件描述的指针
系统打开文件表	当前读写偏移、文件状态标志、引用计数、指向目录项和内存 inode 的指针

每次独立调用 open 通常建立新的打开文件描述，因此即使打开同一文件，读写偏移也相互独立。dup 复制的文件描述符以及 fork 继承的文件描述符可以指向同一打开文件描述，从而共享读写偏移。

读文件

read 通常需要指明：

• 文件描述符。
• 要读入的数据量。
• 数据放入内存的目标地址。

操作系统根据文件描述符找到进程打开文件表，再找到系统打开文件表和文件物理结构。随后根据当前读写指针计算逻辑块号，再把逻辑块号转换成物理块号，从外存读入用户指定的内存区域。

读完后，读写指针通常向后移动。若读到文件末尾，实际读入的数据量可能小于请求的数据量。

写文件

write 通常需要指明：

• 文件描述符。
• 要写出的数据量。
• 数据在内存中的来源地址。

操作系统从用户指定的内存区域取数据，写到当前读写指针对应的文件位置。若写入超过文件原有长度，文件可能需要扩展；这时文件系统还要分配新的磁盘块，并更新 FCB、inode、索引表、FAT 或其他分配结构。

写操作还会影响一致性问题。若数据先进入缓冲区，磁盘上的文件内容可能稍后才真正更新。

mmap

read 和 write 是显式文件 I/O。mmap 则把文件区间映射到进程虚拟地址空间，程序用普通内存访问触发文件页调入或写回。它仍然依赖文件描述符建立映射，但映射建立后，访问路径进入虚拟存储和缺页处理流程。

关闭文件

进程使用完文件后执行 close。操作系统会：

1. 删除该进程打开文件表中的对应表项。
2. 回收与本次打开相关的内存资源。
3. 将系统打开文件表中的打开计数减 1。
4. 若打开计数变为 0，释放系统打开文件表中的对应表项。

close 关闭的是本进程的这次打开关系。若其他进程仍打开同一个文件，文件不会因为当前进程执行 close 而不可用。

`close` 没有将文件从内存写回外存

普通 open 本来就不会把整个文件读入内存，所以 close 也谈不上把整个文件搬回磁盘。

那真正的写回时机是什么时候？

取决于文件系统、页缓存、缓冲区和同步策略。

时机	含义
后台回写	操作系统周期性把脏页或脏缓冲区写回外存
缓存压力	内存紧张或缓存需要回收时，脏页必须先写回才能释放
显式同步	程序调用 fsync(fd)、fdatasync(fd) 或 sync()，要求同步数据或元数据
解除映射	对 mmap 的共享映射，msync()、后台回写、munmap() 或进程退出都可能与脏页写回有关
卸载文件系统	卸载前需要把尚未落盘的脏数据和元数据处理完

Note

写回不只包括文件内容。文件大小、时间戳、目录项、inode、位示图、FAT、索引结构等元数据也可能被缓存并延迟写回。

文件共享

通过链接的方式实现文件共享。文件共享意味着系统中只有一份文件数据，多个目录项或用户可以访问同一份文件。共享文件被一个用户修改后，其他用户看到的也是修改后的内容。

由Readers-Writers-Problem类比可知，允许多个用户同时对共享文件进行读操作，但不允许多个用户同时对共享文件进行写操作，也不允许读者和写者同时使用共享文件。

文件保护

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

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

访问控制

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

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

例如：

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

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

文件的逻辑结构

逻辑结构是用户视角下文件内部数据如何组织，用户可以决定，与底层存储介质无关。物理结构是操作系统视角下文件数据实际如何存放到外存块中，对用户透明。

同一个逻辑结构可以用不同物理结构实现。比如顺序文件在用户看来是一组有先后关系的记录，但这些记录对应的文件块在外存中可以连续分配、链接分配，也可以索引分配。

随机访问的两层含义

文件逻辑结构支持随机访问，是指可以根据记录号直接算出记录的逻辑地址。文件物理结构支持随机访问，是指操作系统可以较快把逻辑块号转换为物理块号。这两件事不是同一层问题。

根据逻辑结构文件可分为两类：

类型	含义	支持查找方式	例子
无结构文件	文件内部是一串二进制流或字符流，也称流式文件。	可顺序扫描；支持定位时也可按字节偏移直接访问，但内容查找由应用程序完成	文本文件
有结构文件	文件由一组相似记录组成，也称记录式文件	可按记录顺序查找；还可根据记录组织方式按记录号、关键字、索引或散列查找	数据库表文件

有结构文件

有结构文件也叫记录式文件。由三个关键部分组成：

• 数据项：文件系统中最基本的数据单位。
• 记录：一组相关数据项的集合。
• 关键字：记录中可用于识别不同记录的数据项。

有结构文件按记录长度又可分为：

类型	特点
定长记录	每条记录长度相同，各字段位置固定
可变长记录	记录长度不固定，通常需要额外记录长度或分隔信息

有结构文件按记录组织形式分类：顺序文件、索引文件、索引顺序文件。

顺序文件

顺序文件中的记录在逻辑上一个接一个排列。记录可以定长，也可以可变长；物理上可以顺序存储，也可以链式存储。

定长记录并且物理顺序存储时，可以直接计算第 $i$ 条记录的位置：

$$\text{address}(i)=\text{start}+i\times L$$

其中 $L$ 是每条记录长度。这种情况下可以快速定位第 $i$ 条记录。

顺序文件的特点：

情况	访问特点
定长记录 + 顺序存储	支持随机访问；若按关键字有序，还可快速检索
可变长记录	通常需要从头扫描前面的记录才能定位目标记录
链式存储	逻辑上有序，物理上不一定相邻

顺序文件增加或删除记录通常不方便。若记录在物理上顺序存储，插入或删除可能需要移动大量记录。

索引文件

对于可变长记录，若要快速找到第 $i$ 条记录，可以为文件建立索引表。索引表由用户或文件内容组织方式决定，映射“关键字或记录号 -> 记录逻辑地址”。索引表的每个索引项记录某条记录的长度、指针或关键字等信息。

索引文件的特点：

• 索引表本身通常是定长记录的顺序文件。
• 可以快速找到第 $i$ 个索引项，再通过索引项找到目标记录。
• 若索引项按关键字排序，还可以支持按关键字折半查找。
• 可以按不同数据项建立多个索引表。

两种“索引表”不要混淆

索引分配中的索引表由操作系统维护，映射“逻辑块号 -> 物理块号”。

索引文件的问题是索引表可能很大。若每条记录都对应一个索引项，而记录本身很小，索引表甚至可能比数据本身更占空间。

索引顺序文件

索引顺序文件结合了索引文件和顺序文件。与索引文件的区别是，它是一组顺序记录对应一个索引项。示例：数据结构的 分块查找。

检索过程：

1. 先查索引表，找到目标关键字可能所在的分组。
2. 再在该分组中顺序查找目标记录。

若文件有 $N$ 条记录，分成 $m$ 组，每组 $\frac{N}{m}$ 条记录，则平均查找次数约为：

$$\frac{m}{2}+\frac{N}{2m}\geqslant \sqrt{N}$$

当仅当 $m = \sqrt{ N }$ 时取等号

显然，引入多级索引顺序文件还可以进一步降低查找次数。

文件的物理结构

关于文件分配的基本单位的约定

虽然 I/O 的基本单位是一个磁盘块，但文件系统会把一个或多个磁盘块组成分配单位。UNIX 类文件系统通常称其为文件系统块，FAT 等文件系统通常称其为簇。
在没有明确提及”文件系统块”、”簇”或指明采用 FAT 表的情况下，默认分配的基本单位仍为一个磁盘块。
否则，则按照当前语境确定分配单位是”文件系统块”还是”簇”。
即使文件很小，通常也至少占用一个分配单位。

文件的逻辑地址空间也按分配单位划分。存入外存时，文件系统要把：

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

转换为：

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

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

文件分配方式直接决定文件的物理结构。常见有连续分配、链接分配、索引分配三种方式。

连续分配

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

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

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

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

优点：

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

缺点：

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

链接分配

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

隐式链接

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

• 起始块号。
• 结束块号。

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

优点：

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

缺点：

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

显式链接

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

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

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

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

FAT 的特点：

• 每个 FAT 文件卷都有自己的 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{volume}}$，则 FAT 表项数应按簇数算：$\text{FAT大小}=N_{\text{volume}} \times \left\lceil \log_2 N_{\text{volume}} \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 占空间
索引分配	索引块号或顶级索引块号	支持随机访问，扩展方便	索引表占空间，访问前可能需读索引块