操作系统(4)：文件管理

这是《操作系统》课程的课程笔记系列。本文整理部分为“第4章：文件管理”。

4.1 文件管理

4.1.1 文件管理概览

• 文件的定义：一组有意义的信息的集合
• 文件的属性：文件名、标识符、类型、位置、大小、保护信息等
• 文件的逻辑结构：文件内部应该如何被组织起来
• 目录结构：文件之间应该如何被组织起来
• 操作系统向上提供的功能：create、delete、open、close、read、write 系统调用
• 文件的物理结构：文件应如何存放在外存中
• 存储空间的管理：操作系统如何管外存中的空闲块
• 操作系统需提供的其他文件管理功能：文件共享、文件保护

4.1.2 文件的逻辑结构

• 无结构文件：由二进制流或字符流组成，无明显的逻辑结构
• 有结构文件：
  • 由记录组成，分为定长记录、可变长记录
  • 顺序文件：默认各记录在物理上顺序存储
    • 串结构：记录顺序与关键字无关
    • 顺序结构：记录按关键字顺序排列
    • 随机存取：可变长记录的顺序文件无法实现随机存取，定长记录可以
    • 快速检索：定长记录、顺序结构的顺序文件可以快速检索（根据关键字快速找到记录）
    • 缺点：不方便增加或删除记录
  • 索引文件：建立一张索引表，每个记录对应一个表项
    • 支持随机存取：索引表本身就是定长记录的顺序文件，一个索引表项就是一条定长记录
    • 快速检索：若索引表按关键字顺序排列，则可支持快速检索
    • 优点：解决了顺序文件不方便增删记录的问题；让不定长记录的文件实现了随机存取
    • 缺点：索引表可能占用很多空间
  • 索引顺序文件：将记录分组，每组对应一个索引表项
    • 检索记录时先顺序查索引表，找到分组，再顺序查找分组
    • 当记录过多时，可建立多级索引表

4.1.3 文件目录

• 文件控制块（FCB）：一个文件对应一个 FCB，一个 FCB 就是一个目录项，多个 FCB 组成文件目录
  • 文件的基本信息：文件名、物理地址、逻辑结构、物理结构等
  • 存取控制信息：是否可读/可写、禁止访问的用户名单等
  • 使用信息：文件的建立时间、修改时间等
• 目录操作：搜索、创建文件、删除文件、显示文件、修改文件
• 目录结构：
  • 单级目录结构：一个系统只有一张目录表，不允许文件重名
  • 两级目录结构：不同用户的文件可以重名，但不能对文件进行分类
  • 多级（树形）目录结构：
    • 不同目录下的文件可以重名，可以对文件进行分类，不方便文件共享
    • 系统根据“文件路径”找到目标文件
      • 绝对路径：从根目录出发的路径
      • 相对路径：从“当前目录”出发的路径，可以减少磁盘 I/O 次数
  • 无环图目录结构：在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图
    • 为共享结点设置一个共享计数器，计数器为 0 时才真正删除该结点
• 索引结点：除了文件名之外的所有信息都放到索引结点中，每个文件对应一个索引结点
  • 目录项中只包含文件名、索引结点指针，因此每个目录项的长度大幅减小
  • 由于目录项长度减小，每个磁盘块可以存放更多个目录项，减少了检索文件时的磁盘 I/O 次数

4.1.4 文件的物理结构

• 连续分配：要求每个文件在磁盘上占有一组连续的块
  • 文件目录中记录存放的起始块号和长度（总共占用几个块）
  • 优点：
    • 支持顺序访问和直接访问（即随机访问）
    • 连续分配的文件在顺序访问时速度最快
  • 缺点：
    • 不方便文件拓展
    • 存储空间利用率低，会产生磁盘碎片
• 链接分配：采取离散分配的方式，可以文件分配离散的磁盘块
  • 隐式链接：除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针
    • 文件目录中记录文件存放的起始块号和结束块号
    • 优点：
      • 很方便文件拓展
      • 不会有碎片问题，外存利用率高
    • 缺点：
      • 只支持顺序访问，不支持随机访问，查找效率低
      • 指向下一个盘块的指针也需要耗费少量的存储空间
  • 显式链接：把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表（FAT）
    • 一个磁盘只会建立一张文件分配表；开机时文件分配表放入内存，并常驻内存
    • 文件目录中只需记录文件的起始块号
    • 优点：
      • 很方便文件拓展
      • 不会有碎片问题，外存利用率高
      • 支持随机访问，地址转换时不需要访问磁盘，文件的访问效率更高
    • 缺点：文件分配表的需要占用一定的存储空间
• 索引分配：允许文件离散地分配在各个磁盘块中，系统为每个文件建立一张索引表
  • 索引表中记录了文件的各个逻辑块对应的物理块
  • 索引表存放的磁盘块称为索引块，文件数据存放的磁盘块称为数据块
  • 链接方案：将多个索引块链接起来存放
    • 缺点：若索引表很长，会导致磁盘 I/O 次数过多，查找效率低下
  • 多层索引：建立多层索引，使第一层索引块指向第二层的索引块
    • 还可根据文件大小的要求再建立第三层、第四层索引块
    • 采用 K 层索引结构，且顶级索引表未调入内存，则访问一个数据块只需 K+1 次读磁盘操作
    • 缺点：即使是小文件，访问一个数据块依然需要 K+1 次读磁盘
  • 混合索引：多种索引分配方式的结合
    • 如一个文件的顶级索引表中，既包含直接地址索引，又包含一级间接索引、两级间接索引
    • 优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少

1. 会根据多层索引、混合索引的结构计算出文件的最大长度
   • 关键点：各级索引表最大不能超过一个块
2. 会分析访问某个数据块所需要的读磁盘次数
   • 关键点：FCB 中会存有指向顶级索引块的指针，因此可以根据FCB读入顶级索引块；每次读入下一级的索引块都需要一次读磁盘操作；另外，要注意题目条件：顶级索引块是否已调入内存

分配方式	如何分配	目录项内容	优点	缺点
顺序分配	为文件分配的必须是连续的磁盘块	起始块号、文件长度	顺序存取速度快，支持随机访问	会产生碎片，不利于文件拓展
隐式链接	除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针	起始块号、结束块号	可解决碎片问题，外存利用率高，文件拓展实现方便	只能顺序访问，不能随机访问
显式链接	建立一张文件分配表（FAT），显式记录盘块的先后关系（开机后 FAT 常驻内存）	起始块号	除了拥有隐式链接的优点外，还可通过查询内存中的 FAT 实现随机访问	FAT 需要占用一定的存储空间
索引分配	为文件数据块建立索引表；若文件太大，可采用链接方案、多层索引、混合索引	链接方案记录的是第一个索引块的块号，多层/混合索引记录的是顶级索引块的块号	支持随机访问，易于实现文件的拓展	索引表需占用一定的存储空间；访问数据块前需要先读入索引块，若采用链接方案，查找索引块时可能需要很多次读磁盘操作

4.1.5 文件存储空间管理

• 存储空间的划分：将物理磁盘划分为一个个文件卷（逻辑卷、逻辑盘）
  • 有的系统支持超大型文件，可支持由多个物理磁盘组成一个文件卷
• 存储空间的初始化：将各个文件卷划分为目录区、文件区
  • 目录区：包含文件目录（FCB）、空闲表、位示图、超级块等用于文件管理的数据
  • 文件区：用于存放文件数据
• 空闲表法：空闲表中记录每个连续空闲区的起始盘块号、盘块数
  • 分配：可采用首次适应、最佳适应等策略
  • 回收：注意表项的合并问题
• 空闲链表法：
  • 操作系统保存着链头、链尾指针
  • 空闲盘块链：以盘块为单位组成一条空闲链
    • 分配：从链头依次取出空闲块
    • 回收：将空闲块挂到链尾
  • 空闲盘区法：以盘区为单位组成一条空闲链
    • 分配：可采用首次适应、最佳适应等策略
    • 回收：注意相邻空闲盘区合并的问题
• 位示图法：一个二进制位对应一个盘块，（字号，位号）或（行号，列号）与盘块号一一对应
  • 重点：要能推出盘块号 -->（字号，位号）之间的相互转换公式
  • 注意：
    • 二进制位 0/1 到底哪个代表空闲，哪个代表不空闲
    • 字号、位号、盘块号是从 0 开始还是从 1 开始
• 成组链接法：UNIX 采用的策略，适合大型文件系统
  • 文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存
  • 将空闲盘块分组，每组（除了最后一组）的第一块作为索引块，然后将这些索引块链接起来

4.1.6 文件的基本操作

• 创建文件：分配外存空间，创建目录项
• 删除文件：回收外存空间，删除目录项
• 打开文件：
  • 将目录项中的信息复制到内存中的打开文件表中，并将打开文件表的索引号返回给用户
    • 打开文件时并不会把文件数据直接读入内存
    • “索引号”也称“文件描述符”
  • 打开文件之后，对文件的操作不再需要每次都查询目录，可以根据内存中的打开文件表进行操作
  • 打开文件表：每个进程有自己的打开文件表，系统中有一张总的打开文件表
  • 进程打开文件表中特有的属性：读写指针、访问权限
  • 系统打开文件表中特有的属性：打开计数器（有多少个进程打开了该文件）
• 关闭文件：
  • 将进程打开文件表中的相应表项删除
  • 系统打开文件表的打开计数器减 1，若打开计数器为 0，则删除系统表的表项
• 读文件：根据读指针、读入数据量、内存位置，将文件数据从外存读入内存
  • 读/写文件用“文件描述符”即可指明文件，不再需要用到“文件名”
• 写文件：根据写指针、写出数据量、内存位置，将文件数据从内存写出外存

4.1.7 文件共享

• 硬链接（基于索引结点的共享方式）：
  • 各个用户的目录项指向同一个索引结点
  • 索引结点中需要有链接计数 count
  • 某用户想删除文件时，只是删除该用户的目录项，且 count--
  • 只有 count == 0 时才能真正删除文件数据和索引结点，否则会导致指针悬空
• 软链接（基于符号链的共享方式）：
  • 在一个 Link 型的文件中记录共享文件的存放路径（如 Windows 快捷方式）
  • 操作系统根据路径一层层查找目录，最终找到共享文件
  • 即使软链接指向的共享文件已被删除，Link 型文件依然存在，只是通过 Link 型文件中的路径去查找共享文件会失败
  • 由于用软链接的方式访问共享文件时要查询多级目录，因此会有多次磁盘 I/O，查找速度慢

4.1.8 文件保护

• 口令保护：为文件设置一个“口令”，用户请求访问文件时必须提供口令
  • 口令一般存放在文件对应的 FCB 或索引结点中，由系统验证口令是否正确
  • 优点：保存口令的空间开销小，验证口令的时间开销也很小
  • 缺点：正确的“口令”存放在系统内部，不够安全
• 密码保护：用一个“密码”对文件加密，用户想要访问文件时，需要提供相同的密码才能正确的解密
  • 优点：保密性强，不需要在系统中存储“密码”
  • 缺点：编码/译码（加密/解密）要耗费一定时间
• 访问控制：用一个访问控制表（ACL）记录各个用户（或各组用户）对文件的访问权限
  • 对文件的访问类型可以分为 读 / 写 / 执行 / 删除 等
  • 优点：实现灵活，可以实现复杂的文件保护功能

4.2 文件系统

4.2.1 文件系统的层次结构

• 用户接口：对应“4.1.6 文件的基本操作”
  • 向上层的用户提供一些简单易用的功能接口，处理用户发出的系统调用请求
• 文件目录系统：对应“4.1.3 文件目录”
  • 根据用户给出的文件路径找到相应的 FCB 或索引结点
  • 所有和目录、目录项相关的管理工作都在本层完成
• 存取控制模块：对应“4.1.8 文件保护”
  • 验证用户是否有访问权限
• 逻辑文件系统与文件信息缓冲区：对应“4.1.2 文件的逻辑结构”
  • 将记录号转换为对应的逻辑地址
• 物理文件系统：对应“4.1.4 文件的物理结构”
  • 把上一层提供的文件逻辑地址转换为实际的物理地址
• 辅助分配模块：对应“4.1.5 文件存储空间管理”
  • 负责文件存储空间的管理（分配和回收）
• 设备管理模块：对应下一章中磁盘管理
  • 直接与硬件交互，负责和硬件直接相关的管理工作

graph TD
F(用户/应用程序) --> A[用户接口];
A --> F
A --> B[文件系统目录];
B --> A;
B --> C[存取控制模块];
C --> B;
C --> D[逻辑文件系统与<br>文件信息缓冲区];
D --> C;
D --> E[物理文件系统];
E --> D;
E --> G[辅助分配模块];
G --> E;
E --> H[设备管理模块];
H --> E;
H --> I(设备);
I --> H;

4.2.2 文件系统布局

• 物理格式化：即低级格式化，划分扇区，检测坏扇区，并用备用扇区替换坏扇区
• 逻辑格式化：磁盘分区（分卷），完成各分区的文件系统初始化
• 文件系统在磁盘中的结构：
  • 主引导记录（MBR）：包含磁盘引导程序和分区表
  • 引导块：负责开机时初始化操作系统
  • 超级块、空闲空间管理（如位示图）
  • i 结点区、根目录、其他目录和文件
• 文件系统在内存中的结构：
  • 目录结构的缓存：包含最近访问目录的信息
  • 系统打开文件表：包含每个打开文件的 FCB 副本、打开计数等
  • 进程打开文件表：包含每个打开文件的文件描述符、系统打开文件表索引等

4.2.3 虚拟文件系统

• 虚拟文件系统（VFS）的特征：
  • 向上层用户进程提供统一标准的系统调用接口
  • 要求下层的文件系统必须实现某些规定的函数功能
  • 每打开一个文件，就在主存中新建一个 vnode，用统一的数据结构表示文件
    • 将文件信息复制到 vnode 中，vnode 的功能指针指向具体文件系统的函数功能
• 文件系统挂载：即文件系统安装 / 装载，将一个文件系统挂载到操作系统中需要：
  • 在 VFS 中注册新挂载的文件系统
    • 挂载表：位于内存中，包含每个文件系统的相关信息，包括文件系统类型、容量大小等
  • 新挂载的文件系统，要向 VFS 提供一个函数地址列表
  • 将新文件系统加到挂载点，即挂载在某个父目录下