文件管理：逻辑结构、目录与文件系统
本篇对应王道第四章（原 14 文件管理基础 + 15 目录 + 16 文件系统合并）。两条主线：文件这种抽象数据类型长什么样（逻辑结构 + 物理结构），OS 怎么管理一堆文件（目录）+ 怎么管理磁盘空间（空闲块）。
一、文件与文件系统
文件的定义与图书馆类比
文件 = 存储在计算机上的信息集合。三个构成要素：一块存储空间中的数据、分类和索引信息、访问权限信息。
图书馆类比：文件 ≈ 书，OS 管理文件 ≈ 图书管理员管理书——书的内容 = 文件数据；分类上架编号登记 = 文件的分类查找（索书号 ≈ FCB）；绝版贵书只借 VIP = 访问权限。类比不完全等价，但关键属性的思想一致。
用户视角：文件系统提供二级存储的抽象，让用户不用关心文件怎么存在辅存上、存储介质什么特征、文件具体在哪个位置，就能方便地命名、分类、查找、保护文件。
FCB 与索引节点
文件控制块 FCB：存放控制文件所需各种信息的数据结构，实现按名存取。文件与 FCB 一一对应，FCB 的有序集合 = 文件目录，一个 FCB 就是一个目录项；目录本身也是文件（目录文件）。FCB 包含：基本信息（文件名、物理位置、逻辑/物理结构）、存取控制信息、使用信息（建立时间、修改时间）。
索引节点（i 节点，inode）：目录通常在磁盘上，文件很多时目录占大量盘块，检索目录时要反复读盘。但检索时只用文件名，找到匹配项才需要物理地址——其他描述信息根本用不上。
于是文件名与描述信息分离：描述信息单独形成索引节点，目录项只留文件名 + 索引节点号。
效果（必考计算）：FCB 64B、盘块 1KB → 每块 16 个 FCB，640 个 FCB 检索平均启动磁盘 20 次；UNIX 目录项只占 16B（14B 文件名 + 2B i 节点号）→ 每块 64 个目录项，启动磁盘次数降为 1/4。
索引节点分两种：磁盘索引节点（文件主标识、类型、存取权限、13 个地址项 iaddr(0)~(12)、长度、链接计数、存取时间）和内存索引节点（文件打开时复制进内存，增加索引节点号、上锁状态、访问计数、逻辑设备号、链表指针）。
文件操作与打开文件表
基本操作：创建（分配外存空间 + 建目录项）、删除（删目录项和 FCB + 回收空间）、读/写（查目录得地址 + 移动读写指针）。
打开（open）：多次读写总不能每次都检索目录。打开 = 把目录项从外存复制到内存的打开文件表，返回表目索引号——UNIX 叫文件描述符，Windows 叫文件句柄。之后所有操作（read/write/lseek/close）用描述符，不再用文件名。close = 删除进程表中表目。
两级打开文件表：整个系统表（进程无关信息：磁盘位置、文件大小、打开计数器）+ 每进程表（读写指针、访问权限、指向系统表的指针）。系统表按打开计数器管理：计数器为 0 才删表目。
打开文件的关联信息：文件指针（读写位置，每进程唯一）、打开计数、文件磁盘位置（缓存避免反复读盘）、访问权限。
文件保护
口令（存 FCB 里，开销小但不安全）、加密（保密强，编解码费时）、访问控制（控制访问方式，主流）。
访问控制列表 ACL：规定每个用户名及允许的访问类型——灵活但长度不可预计。精简版：把用户分三类——拥有者 / 组 / 其他，每类每操作一位，3×4 位矩阵搞定。访问时：是文件主按主权限，同组按组权限，否则按其他。
二、文件的逻辑结构（用户视角）
逻辑结构 = 用户看到的组织形式，与存储介质无关。
无结构文件（流式文件）
字符流构成，按字节计长，读写指针指出下一个字节。源程序、可执行文件、库函数都是。没有结构 → 检索只能穷举。
有结构文件（记录式文件）
由相似记录组成。按记录长度分定长记录（检索快，可随机访问：第 i 条地址 = i×L）和变长记录（只能顺序查找，慢）。按组织形式分三种：
| 结构 | 原理 | 适用 |
|---|---|---|
| 顺序文件 | 记录顺序排列（串结构按存入时间/顺序结构按关键字排序） | 批处理存取效率最高；磁带只能用它；但增删改查单条记录性能差 |
| 索引文件 | 为每个记录建索引项（指针+长度），索引表按关键字排序（定长记录的顺序文件） | 变长记录的快速随机检索；代价是索引表存储开销 |
| 索引顺序文件 | 记录分组，索引表为每组第一个记录建索引项；组内可无序、组间必须有序 | N 条记录：直接找平均 N/2 次；分组后找 √N/2 + √N/2 = √N 次——就是分块查找 |
还有散列文件（Hash）：键值经散列函数直接决定物理地址，存取快但会冲突。
三、文件的物理结构（外存视角）
物理结构 = 文件数据在磁盘上怎么分布和组织。对应两个问题：文件分配（非空闲块管理）和存储空间管理（空闲块管理，见第五节）。注意与逻辑结构区分（类比线性表 vs 顺序表 vs 链表的关系）。磁盘块通常与内存页面大小相同，磁盘 IO 以块为单位。
连续分配
文件占一组连续的块，目录项记起始块号 + 块数；访问第 i 块直接算 b+i-1。
优点：支持顺序和直接访问（随机）；磁头移动距离最小、速度快。缺点：外部碎片；必须事先知道文件长度，不支持动态增长（长了会覆盖相邻文件）；增删记录要物理移动。
链接分配
离散分配，消除外部碎片、便于动态增长、增删方便。
隐式链接：目录记首块和尾块指针，每个盘块里藏指向下一块的指针（对用户透明）。
缺点：只支持顺序访问（要第 i 块得从头数）；一个指针坏了整条链丢数据；指针占空间（可以按"簇"分配减少指针比例，代价是内部碎片）。
显式链接（FAT）：把链接指针抽出来集中放一张表——文件分配表 FAT，整个磁盘一张，表项与全部盘块一一对应，-1 表示文件末块、-2 表示空闲块。
文件目录只需记起始块号，后续沿 FAT 找。FAT 开机就读入内存，检索在内存进行——支持随机访问、显著减少访盘。缺点：FAT 占内存。FAT 还顺带管理了空闲块（-2 表项）。
索引分配
思路：打开文件时只需把该文件自己的块号表调入内存，没必要整张 FAT 都读——给每个文件配一个索引块，集中放它的所有盘块号。
优点：支持直接访问（索引块第 i 个条目 = 第 i 块）；无外部碎片。缺点：索引块额外开销；小文件也占一个索引块（利用率低），大文件要多个索引块。
多级索引：索引块太多时给索引块再建索引（主索引）——原理同内存管理的多级页表。盘块 4KB、块号 4B → 单级最大 1024×4KB=4MB；两级 1024×1024×4KB=4GB。缺点：访问一个盘块要多次启动磁盘，级数越多访盘越多，对小文件不利。
混合索引（UNIX 的做法）：i 节点设 13 个地址项 iaddr(0)~(12)，按文件大小各取所需：
| 地址项 | 用途 | 能表示的文件大小 |
|---|---|---|
| iaddr(0)~(9) | 直接地址（块号直接放 i 节点） | ≤ 40KB（10×4KB） |
| iaddr(10) | 一次间址（指向索引块） | + 4MB |
| iaddr(11) | 二次间址（指向主索引块） | + 4GB |
| iaddr(12) | 三次间址 | + 4TB |
小文件直接寻址（快），中型一次间址，大型二三次间址——全面照顾各类文件。
四、目录管理
目录提供文件名 → 文件的映射，要求：按名存取、检索快、支持共享、允许不同用户的文件重名（靠树形结构解决）。
四种目录结构
| 结构 | 原理 | 问题 |
|---|---|---|
| 单级 | 全系统一张目录表 | 查找慢、不允许重名、不便共享 |
| 两级 | 主文件目录 MFD（用户名→UFD 位置）+ 用户文件目录 UFD | 解决重名、有访问控制；缺乏灵活性，不能分类 |
| 树形 | 两级推广；绝对路径（从根）/ 相对路径（从当前目录） | 分类清晰、便于管理保护；但逐级查中间节点访盘次数多。UNIX/Linux/Windows 都用它 |
| 无环图 | 树形 + 指向同一节点的共享有向边 | 便于共享；管理复杂。删除共享节点用共享计数器：加共享链 +1，删除 -1，计数器为 0 才真删，否则只删共享链 |
路径细节：绝对路径如 Linux 的 /dev/hda；当前目录 /bin 下 ./ls 是相对路径。每个用户登录后有自己的当前目录，cd 命令改变它（UNIX 里默认当前目录记录在 /etc/passwd）。
目录操作：搜索、创建/删除文件（增删目录项）、创建/删除目录（两种策略：不删非空目录要递归删干净；或允许删非空目录连子树一起删）、移动、显示、修改。
目录的实现
就是为了查找：
- 线性列表：文件名 + 数据块指针的线性表。实现简单，查找费时；删除可用链表结构优化
- 哈希表：文件名 → 指向线性列表元素的指针。查找快、插删简单，但要处理冲突
目录查询要在磁盘上反复搜索、不断 IO——所以把当前使用的文件目录复制到内存，降低磁盘操作次数。
文件共享：软硬兼施
硬链接（基于索引节点的共享）
文件物理地址和属性放索引节点里，目录项只设文件名 + i 节点指针。i 节点里的链接计数 count = 指向它的目录项数。
关键：用户 A（文件主）不要这文件了，不能直接删——B 可能正在写。A 只能 count-1 并删自己的目录项；count = 0 才真正删除。多个指针指向一个索引节点，只要还有一个指针，索引节点就不能删。
软链接（符号链）
系统创建一个 LINK 类型的新文件 L 放进 B 的目录，L 里只写被链接文件 F 的路径名——类似 Windows 快捷方式。
B 访问 L 时，OS 看到是 LINK 类型，按路径名去找 F 再读写。文件主删除 F 后不会留下悬空指针——其他人通过符号链访问失败，把符号链删掉即可，无副作用。代价：每次访问都要按路径逐级查目录、多次读盘，符号链本身也是个文件、占空间。但符号链能实现网络文件共享（路径名里写上机器的网络地址即可）。
一句话：硬链接 = 多个指针指向一个 i 节点（快，count 保护）；软链接 = 保存路径名（慢，但主删共享者不悬空，还能跨网络）。硬链接查找比软链接快。
五、文件系统
层次结构（自下而上）
- I/O 控制层：设备驱动 + 中断处理，把命令翻译成底层硬件指令
- 基本文件系统：向驱动发读写物理块的通用命令；管理内存缓冲区和各类缓存
- 文件组织模块：逻辑块号 → 物理块号的转换 + 空闲空间管理器
- 逻辑文件系统：管理元数据（目录结构、FCB）、文件保护——按文件名找到文件组织模块所需信息
文件系统布局
在磁盘上：
- MBR（主引导记录）：0 号扇区，含分区表和活动分区标志；BIOS 读入并执行 MBR，MBR 找到活动分区读入其第一块
- 引导块（boot block）：每个分区统一从它开始（即使不含 OS，也为以后装系统留位置）；Windows 称分区引导扇区
- 超级块（super block）：文件系统的所有关键信息——块总数、块大小、空闲块数量和指针、空闲 FCB 数量和指针；启动时/首次使用时读入内存
- 之后是空闲块信息（位示图或指针链接）、i 节点区、根目录，其余放目录和文件
在内存中（安装时加载、操作时更新、卸载时丢弃）：安装表 mount table、目录缓存、整个系统的打开文件表（FCB 副本+打开计数）、每进程打开文件表（描述符+指向系统表的指针）。
外存空闲空间管理（四种方法）
一个分区 = 一个卷（可以是磁盘一部分、整盘或 RAID 集）；卷里文件区（数据）和目录区（FCB）分离。
| 方法 | 思想 | 优缺点 |
|---|---|---|
| 空闲表法 | 空闲区建表（起始块号+块数），连续分配，分配用首次/最佳适应，回收合并相邻区 | 分配快；适合小文件 |
| 空闲链表法 | 空闲盘块链（一盘块一节点，简单但链长、重复操作多）/ 空闲盘区链（盘区含多块+指针+块数，类似动态分区，效率高、链短但回收合并复杂） | — |
| 位示图法 | 每盘块对应一位：0 空闲 1 已分配。行 i 列 j ↔ 盘块号 b = n(i-1)+j（行列从 1 开始，题说从 0 就要调整公式） | 容易找连续空闲块；位示图小可放内存省启动开销；随磁盘容量增大而增大，常用于小型机 |
| 成组链接法（UNIX） | 空闲盘块分组（如 100 个/组），每组第一个盘块记录下一组的总数和块号，链起来；第一组信息放空闲盘块号栈 | 结合前两种、克服"表太长"；大文件系统适用 |
成组链接的分配：从栈顶依次分配；分到栈底那个盘块号时（它存着下一组的信息），先把它的内容读入栈，再把该盘块分配出去，栈中空闲数减 1。回收：盘块号压栈、计数加 1；栈满（100）时，把栈里 100 个块号写入新回收的盘块，让新盘块当新栈底，计数置 1。
位示图和空闲盘块号栈都放卷头，UNIX 里也归入超级块，操作前读入内存并保持一致。
虚拟文件系统 VFS
屏蔽不同文件系统的差异和操作细节，向上提供统一调用接口——用户 open 一个文件不用管它在什么文件系统、什么介质上。
面向对象思想：抽象出四个对象类型（每个含数据 + 函数指针，指向具体文件系统的实现）：
| 对象 | 对应 | 备注 |
|---|---|---|
| 超级块对象 | 一个已挂载的特定文件系统 | 存元信息，操作：分配/销毁/读/写 inode |
| 索引节点对象 | 一个特定文件（一对一） | 文件被访问时才在内存创建 |
| 目录项对象 | 路径的一个组成部分 | 磁盘上没有对应结构——VFS 遍历路径时逐个解析出来的 |
| 文件对象 | 一个与进程相关的已打开文件 | 文件对象与物理文件的关系 ≈ 进程与程序的关系 |
调用 write() 时：VFS 的 sys_write 找到具体文件系统的写方法 → 交给该文件系统 → 与物理介质交互。VFS 只存在于内存中，启动时建立、关闭时消亡——严格说它不是一种实际的文件系统。
文件系统挂载
文件系统在进程使用前必须先挂载（mounting）：把设备中的文件系统挂到某个目录（安装点），之后通过这个目录访问设备文件。同一设备可有多个安装点；同一安装点同时只能挂一个设备。
- Windows：驱动器字母（C 盘 D 盘）+ 卷的树形目录；新版也允许挂任意位置
- UNIX：启动时装根文件系统（内核映像所在），其他文件系统挂到根下的某目录；
mount -t ext2 /dev/fd0 /flp，卸载用umount
全篇两条主线
① 文件这种抽象数据类型：逻辑结构（怎么给用户看）+ 物理结构（怎么存）；② OS 怎么管理它们：目录（按名存取）+ 磁盘管理（空闲空间）。宏观把握是为了微观更准地掌控细节。
六、盲点总复习
- 目录项瘦身（i 节点分离）的动机是减少检索目录时的读盘次数——16B 目录项让磁盘启动次数降为 1/4
- open 之后所有操作用文件描述符/句柄，不再用文件名；系统表按打开计数器决定何时删表目
- 精简访问控制三类用户：拥有者/组/其他；判定顺序：文件主 → 同组 → 其他
- 索引顺序文件查找 √N 次 = 分块查找；定长顺序文件可折半查找
- FAT 是显式链接，开机读入内存，兼管空闲块；隐式链接的指针藏在盘块里
- UNIX 13 地址项：10 直接 + 一次 + 二次 + 三次间址；4KB 块 → 40KB / 4MB / 4GB / 4TB
- 无环图目录删除靠共享计数器；硬链接删除靠 count——同一个思想
- 位示图公式默认行列从 1 开始：b = n(i-1)+j；反算 i=(b-1)DIV n +1、j=(b-1)MOD n +1
- 成组链接：分到栈底块时先读内容进栈再分配；回收栈满时写栈入新块、新块当栈底、计数置 1
- VFS 四对象中目录项对象在磁盘上没有对应结构；VFS 只在内存中存在
- 硬链接不跨文件系统，软链接可以（路径名可以指向任何地方，包括网络）
- 超级块装"文件系统的所有关键信息"；引导块每个分区都有（哪怕不装系统）
文件躺在磁盘上，磁盘怎么调度怎么保养？下一章讲 IO 管理与磁盘 → 08-IO管理
💬 评论