Lecture 8：知识 - 文件

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

文件管理用 FCB/inode 保存元数据，用逻辑结构组织记录，用物理结构把逻辑块映射到磁盘块。核心链路是：文件名查目录 → FCB/inode 定位 → open 返回 fd → read/write 按 fd 操作。

8.1 文件元数据、FCB 与 inode

文件属性与 FCB

属性	含义
文件名	用户为便于查找而命名；同一目录内不允许重名。
标识符	系统内部唯一、对用户通常不可读的名称。
类型	指示文件类型。
位置	路径供用户使用；外存地址供 OS 使用，对用户透明。
创建者/所有者、时间	记录来源及建立、修改等使用信息。
保护信息	不同用户或组的读、写、执行等访问权限。

**文件控制块（FCB）**是记录控制文件所需信息的数据结构，实现按名存取。一个文件对应一个 FCB；FCB 的有序集合是文件目录，目录中的一个 FCB 是一个目录项。创建文件时必须创建其 FCB；目录文件本身也是一种文件。

inode 对目录检索的优化

目录文件通常在磁盘上。若目录很大，顺序查目录时需要将目录数据块逐块调入内存；在匹配文件名以前，目录项中的大部分描述信息并不需要。

UNIX 将文件名与描述信息分离：目录项只保留“文件名 + inode 号（或指针）”，其余信息放在该文件唯一的 inode 中。匹配文件名后才调入 inode，并由 inode 中的外存地址定位数据。

例：FCB 为 64 B、块大小为 1 KB，故每块仅含 $1024/64=16$ 个 FCB。若目录有 640 个 FCB，共占 40 块；UNIX 目录项仅 16 B（文件名 14 B、inode 号 2 B）时，每块有 64 项，共占 10 块。按教材“查一半块”的近似口径，平均磁盘启动次数约从 20 次降到 5 次，即约为原来的 $1/4$。若假定目标均匀分布且从首块开始冷缓存顺序查找，严格期望分别是 $(1+40)/2=20.5$ 次和 $(1+10)/2=5.5$ 次；因此 20、5 与 $1/4$ 均为近似值。

类型	保存位置与附加状态
磁盘 inode	外存中的持久控制信息，例如文件类型、权限、所有者、链接计数、大小和块地址。
内存 inode	磁盘 inode 被调入后的运行时对象；还要记录修改标志、设备号、锁、当前访问者/引用等内存管理信息。

文件总数受 inode 总数约束：一个文件对应一个 inode，故 inode 号位数/索引节点总数决定可创建的最大文件数，与单个文件长度无关。单个文件长度则受块大小、地址项数和间接索引层数制约。

8.2 文件描述符与打开文件表

文件名完成 FCB/inode 定位后不再是已打开文件表的必要内容。open() 后，后续 read()、write()、lseek()、close() 都使用文件描述符 fd；UNIX 称为文件描述符（file descriptor），Windows 常称为文件句柄（file handle）。

打开文件需要保存的运行时信息：

信息	为什么不能只存于磁盘 FCB/inode
当前文件位置/读写指针	每个打开该文件的进程都可能不同。
打开计数	多进程可同时打开同一文件，最后一个关闭前不能删除系统表项。
文件磁盘位置、大小、访问日期等	放在内存中可避免每次操作都重新读磁盘。
本次打开的访问方式	如创建、只读、读写、追加；用于允许或拒绝后续 I/O。

系统通常采用两级打开文件表：

进程 A 的 fd 表项 ──> 打开文件描述 A（偏移、状态标志、引用计数）──> 内存 inode/vnode
进程 B 的 fd 表项 ──> 打开文件描述 B（独立 open 时偏移可不同）──> 同一内存 inode/vnode
dup/fork 得到的 fd ──> 与原 fd 共享打开文件描述及其偏移

系统级结构保存内存 inode/vnode 等文件对象，以及一次打开所形成的打开文件描述；后者通常含当前文件偏移、状态标志和引用计数。
进程打开文件表每进程一张，以 fd 指向打开文件描述，并可保存 close-on-exec 等描述符级标志。独立 open 通常得到独立的打开文件描述；dup 或 fork 继承的描述符可以共享同一偏移。

`open`、`close`、`read`、`write`

调用	参数/主要过程	要点
`create`	外存空间大小、文件路径、文件名；分配外存，在目标目录建立目录项。	目录项含文件名及定位文件所需信息。
`delete`	文件路径、文件名；查目录并删除相应目录项。	删除目录项后递减硬链接计数；只有硬链接计数为 0 且不再有打开引用时，inode/FCB 与数据块才可最终回收。删除不等于关闭。
`read(fd, buf, n)`	从读指针处向用户缓冲区 `buf` 读入 $n$ 字节。	若所需文件块不在内存，进程等待磁盘 I/O，随后转为就绪态；读/写按 fd，不再按文件名。
`write(fd, buf, n)`	把用户缓冲区的 $n$ 字节写向写指针处。	多进程可同时以读/写方式打开同一文件，OS 不自动保证写互斥；需通过加锁处理读者-写者式互斥。
`open(path, name, mode)`	按路径查目录并取得/缓存 inode 等文件对象，再为这次打开建立打开文件描述和进程 fd 表项；不同的独立 `open` 通常有独立偏移。	内存 inode/vnode 可以复用，但不能据此断定不同 `open` 必然共享同一打开状态；打开文件也不等于把文件数据全部读入内存。
`close(fd)`	删除进程 fd 表项，递减其指向的打开文件描述引用计数；引用计数为 0 时释放该打开描述，并相应释放内存文件对象引用。	关闭不递减外存 inode 的硬链接计数，也不直接释放仍有目录链接的文件数据；已取消链接的文件可在最后一个打开引用关闭后回收。

2024 题的要点：带“按文件名查找文件”功能的是 open()；read、write、close 使用 open 返回的 fd。

8.3 文件访问速度与保护

提升访问速度

预读：读当前块时把后续若干块一并读入缓存。
连续分配簇：顺序读取时无需查找下一数据块的位置。
延迟写：先写入缓冲区并设置延迟写标志，稍后批量写回，减少不必要的磁盘操作。在课件所述的经典空闲缓冲区链表算法中，带延迟写标志的缓冲区被再次申请是写回时机之一；一般系统还可能因后台周期回写、内存压力或缓存回收，以及 sync、fsync 等显式同步请求而写回，不能理解为“只有再次申请时才写盘”。
磁盘高速缓存：命中缓存时避免外存访问。

访问控制、口令与加密

方法	实现与特点
ACL	在 FCB/inode 中维护“用户名 → 允许操作”的访问控制列表。表达灵活，但表长难预测、空间管理复杂。
精简 ACL	把用户划为拥有者、组、其他三类；为每类用位描述读、写、执行等权限。创建时在 FCB 保存拥有者与组名，访问时按“拥有者 → 同组 → 其他”顺序判定。
口令保护	在 FCB/inode 存口令，访问时比对。空间与时间开销小，但正确口令存于系统内，安全性较弱。
加密保护	数据按密钥加密，正确密钥才能解密；保密性强且不必在系统中明存口令，但编/解码耗时。

课程列出的常见访问类型是：读、写、执行、添加、删除、列清单。访问控制信息属于文件而非某个用户，实质是“用户类别 × 访问类型”的权限矩阵。例：4 类用户、5 类权限需 $4\times5=20$ 位。

8.4 文件的逻辑结构

无结构与有结构文件

无结构文件（流式文件）：内部是连续的二进制流或字符流，如文本文件。
有结构文件（记录式文件）：由一组相似记录组成，每条记录由若干数据项组成；记录可以定长或可变长。

顺序文件

记录在逻辑上一个接一个排列；物理上可顺序存储或链接存储。逻辑排列又分：

结构	记录顺序	查找/更新特性
串结构	与关键字无关，通常按录入时间。	不可按关键字快速检索；除尾部插入外，插入删除困难。
顺序结构	按关键字有序。	若定长且物理连续，可通过 $i\times L$ 直接定位第 $i$ 条记录，并可按关键字快速查找。

随机存取条件要同时判断：

链式存储：定长、可变长都不能随机存取；必须从首记录顺序找。
连续存储但记录可变长：不能随机存取。
连续存储且记录定长：可随机存取，第 $i$ 条记录相对地址为 $iL$。

考试中“顺序文件”一般默认指物理连续存储的顺序文件。

索引文件与索引顺序文件

结构	索引粒度	关键性质
索引文件	每条记录一个索引项。	索引表连续存储、数据记录可离散；索引项可按关键字有序以支持折半查找。检索快，适合及时性要求高的场合，但索引表可能很大。
索引顺序文件	一组记录一个索引项。	组间关键字有序，组内可不有序；索引项减少，插入更方便。先找组，再在组内顺序找。
多级索引顺序文件	对索引表继续分组建上级索引。	进一步缩短大文件的查找路径。

例：10,000 条记录的串结构顺序查找平均约 5,000 次。若分为 100 组、每组 100 条，先顺序查 100 项索引表平均 50 次，再在组内平均查 50 次，共约 100 次。对 $10^6$ 条记录，每 100 条建低级索引，则低级索引约 10,000 项；再每 100 项建顶级索引，顶级约 100 项。

8.5 文件的物理结构

外存按等大的物理块（磁盘块）划分，文件逻辑空间也按文件块划分。逻辑地址为 (逻辑块号, 块内地址)，物理地址为 (物理块号, 块内地址)；文件系统以块为单位分配空间。块内地址位数取决于块大小。

连续分配

一个文件占一组连续物理块，目录项记录起始块号和长度。访问逻辑块 $i$ 时：

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

并要检查 $i<\text{长度}$。

优点：支持顺序和随机访问，地址转换简单，顺序读写最快。缺点：扩展困难，易有外部碎片，必要时紧凑需要大代价。

插入题：文件 F 有 200 条记录（从 1 编号）、一块一条记录，现插入为第 30 条且首尾均有空闲块。可把前 29 块整体前移一块，为每移动一块执行读入、释放原块、写入新块；29 块需 $29\times2=58$ 次块访问，再写入新第 30 块，共最少 59 次。FCB 的起始块号（前移后改变）和长度（200 变 201）需要更新。

隐式链接分配

文件可离散存储，除末块外每块保存下一块指针；目录项保存首块、尾块指针。未特别说明的“链接分配”通常指这种隐式链接。

优点：易扩展、无外部碎片、外存利用率高。
缺点：只支持顺序访问，查找第 $i$ 块需沿链访问；每块指针占空间且指针损坏会断链。

同一插入题中，若从首块沿链定位，需读取第 1～29 块以找到第 30 条的前驱；将新记录写入一个空闲块，再把第 29 块的后继指针改为新块并写回，共 $29+1+1=\mathbf{31}$ 次块访问（按原题不计分配空闲块等元数据 I/O，且第 29 块读出后可在内存中修改，无须重复读取）。新块的后继指针须指向原第 30 块。与连续分配相比不需搬移后续记录，但定位链中间位置慢。若块大小 1 KiB、指针 4 B，则每块数据容量为 1020 B；按题目理想化假设，4 B 块号可表示 $2^{32}$ 个块，最大文件数据长度为：

$$2^{32}\times1020\text{ B}=4{,}380{,}866{,}641{,}920\text{ B}=4080\text{ GiB}$$

此长度不计每块链接指针自身占用，且假设全部 $2^{32}$ 个块号都可用；若部分编码保留作空指针/结束标记，还须扣除。原 PDF 将这里的二进制单位写作 4080 GB，严格说应为 4080 GiB（约 4380.87 GB）。

FAT（显式链接）分配

FAT 将“下一块指针”显式集中存于文件分配表；一个磁盘一张 FAT，开机时读入内存并常驻。FAT 表项物理连续、等长，物理块号可由表项位置隐含。

优点：易扩展、无外部碎片；按教材口径支持随机访问，因为沿 FAT 查找后继块时无需逐块读磁盘，较隐式链接快。但定位第 $i$ 个逻辑块仍须从起始块沿内存 FAT 逐项追踪，不能像连续分配或索引分配那样由 $i$ 直接算出物理块号。
缺点：FAT 本身占存储空间。
区分：FAT 是每磁盘一张的全局表；下述索引分配的索引表是每文件一张。

索引分配

每个文件有一张索引表，索引表所在块称索引块，文件数据所在块称数据块；目录项记录索引块号。访问逻辑块 $i$：从目录项得索引表位置 → 把索引表读入内存 → 查第 $i$ 项得物理块号。

优点：支持随机访问，扩展时分配新数据块并新增索引项即可；缺点是索引块有额外开销。逻辑块号可隐含在索引项顺序中。

大文件三种索引方案：

方案	做法	优缺点
链接方案	一个索引块放不下时，以指针串接多个索引块。	若每索引块 256 项，要到第 $i$ 个索引块必须依次读此前索引块；大文件 I/O 多。
多层索引	顶级索引块指向下一层索引块，可继续扩展层级。	顶级索引表未在内存时，$K$ 层索引访问一个数据块需 $K+1$ 次磁盘读；小文件也承受该开销。每层索引表不能超过一个块。
混合索引	顶级表同时含直接、一级间接、二级间接等地址项。	小文件先走直接项，I/O 少；大文件再使用间接项。

混合索引图中，顶级索引表未在内存，有 8 个直接项、1 个一级间接项和 1 个二级间接项，每个索引块有 256 项：

逻辑块范围	需读磁盘次数
0--7（直接）	2：顶级索引块 + 数据块
8--263（一级间接）	3
264--65799（二级间接）	4

该结构可支持的数据块数为 $8+256+256^2=65{,}800$；若块大小为 1 KB，最大文件数据长度为 65,800 KB。

8.6 物理分配对比与图示复核

分配方式	目录中保存	随机访问	扩展与碎片	主要额外开销
连续分配	起始块号、长度	支持，直接相加	扩展难，有外部碎片	无额外索引/链接块
隐式链接	首块、尾块	不支持	易扩展，无外部碎片	每数据块的下一块指针
FAT 显式链接	起始块号，后继在 FAT	支持（查内存 FAT）	易扩展，无外部碎片	一张全局 FAT
索引分配	索引块号	支持	易扩展，无外部碎片	每文件索引块；大文件可能多级

FCB 与 UNIX 目录图明确：传统目录项可含完整控制信息，而 UNIX 目录项缩为“文件名 + inode 号”。
打开文件表图明确：用户空间的 read(fd) 经进程打开文件表、系统打开文件表，最后定位辅存中的 FCB/inode 和数据块。
逻辑地址图明确：文件逻辑块号和块内地址由 OS 转成物理块号和块内地址；分配最小单位是块。
三类物理结构图明确：连续分配按起始块加逻辑块号，隐式链接在数据块内串指针，FAT 将指针外置到内存常驻的表中，索引分配以单文件索引表映射所有逻辑块。

8.7 本节复盘

文件名只用于查目录；打开后用 fd。open 进行按名查找，read/write/close 不再重新查目录。
目录项解决按名查找，inode 保存文件元数据；系统级打开文件描述保存本次打开的偏移和状态，进程 fd 表保存描述符映射及其标志。独立 open 的偏移通常不同，dup/fork 共享同一打开文件描述时则共享偏移，不能一概称为“进程私有偏移”。
定长记录可先由 $iL$ 计算文件内逻辑字节偏移，再由文件系统把逻辑块映射到物理块；物理块不必连续。变长记录若无索引，通常需从前向后解析记录边界；顺序访问也不等于可按关键字快速检索。
物理分配计算题先明确块大小、指针大小、是否将索引块计入文件长度、索引块是否已在内存，以及题目中的“链接分配”是否特指 FAT。