401 文件管理

文件

基本概念

定义

• 文件：
  • 是以硬盘为载体的存储在计算机上的信息集合，可以是文本文档、图片、程序等
  • 用户进行的输入、输出操作中，以文件为基本单位
• 文件的结构【自底向上进行定义】：
  • 数据项：文件系统中最低级的数据组织方式，分为：
    • 基本数据项：描述一个对象的某种属性的一个值，是数据中的最小逻辑单位
    • 组合数据项：由多个基本数据项组成
  • 记录：一组相关的数据项的集合，用于描述一个对象在某方面的属性
  • 文件：由创建者所定义的、具有文件名的一组相关元素的集合，分为：
    • 有结构文件：文件由若干个相似的记录组成【如数据库表】
    • 无结构文件：文件被视为一个字节流【如二进制文件或字符文件】

属性

• 文件名：由创建文件的用户决定，为了方便用户找到文件，同一目录下不允许有重名文件
• 类型：被支持不同类型的文件系统所使用
• 创建者：文件创建者的 ID
• 所有者：文件当前所有者的 ID
• 位置：指向设备和设备上文件的指针
• 大小：文件当前大小（用字节、字或块表示），也可包含文件允许的最大值
• 保护：对文件进行保护的访问控制信息
• 创建时间、最后一次修改时间、最后一次存取时间：用于保护和跟踪文件

文件的数据结构

文件控制块 FCB

• 文件控制块：用来存放控制文件需要的各种信息的数据结构，以实现按名存取
• 文件目录：FCB 的有序集合【文件与 FCB 一一对应，一个 FCB 就是一个文件目录项】
• 目录文件：一个文件目录也被视为一个文件
• 每当创建一个新文件，系统就要为其建立一个 FCB，用来记录文件的各种属性
• FCB 主要包含以下信息：
  • 基本信息：文件名、文件的物理位置、文件的逻辑结构、文件的物理结构
  • 存取控制信息：文件主的存取权限、核准用户的存取权限以及一般用户的存取权限
  • 使用信息：文件的建立时间、上次修改时间等

索引节点

• 索引节点：包含了除文件名之外的所有信息，每个文件对应一个索引节点
• 文件目录的目录项中仅由文件名和相应的索引节点号（或索引节点指针）构成
• 优点：使用索引节点，目录项长度减小，因此每个磁盘块可以存放更多个目录项，减少了索引文件时磁盘 I/O 的次数
• 分类：
  • 磁盘索引节点：
    • 指存放在磁盘上的索引节点【外存中】
    • 每个文件有一个唯一的磁盘索引节点
    • 包含：文件主标识符、文件类型、文件存取权限、文件物理地址、文件长度、文件链接计数、文件存取时间
  • 内存索引节点：
    • 指存放在内存中的索引节点
    • 文件被打开时，将磁盘索引节点复制到内存的索引节点，便于以后使用
    • 新增：索引节点号、状态、访问计数、逻辑设备号、链接指针

文件的操作

创建文件（create 系统调用）

• 需要提供的主要参数：
  • 所需的外存空间大小（如：一个盘块，即 1 KB）
  • 文件存放路径（“D:/Demo”）
  • 文件名（这个地方默认为“新建文本文档.txt”）
• OS 的处理过程：
  • 在外存中找到文件所需的空间
  • 根据文件存放路径的信息找到该目录对应的目录文件（此处就是 D:/Demo 目录），在目录中创建该文件对应的目录项

删除文件（delete 系统调用）

• 需要提供的主要参数：
  • 文件存放路径（“D:/Demo”）
  • 文件名（“test.txt”）
• OS 的处理过程：
  • 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项
  • 根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块
  • 从目录表中删除文件对应的目录项

打开文件（open 系统调用）

• 需要提供的主要参数：
  • 文件存放路径（“D:/Demo”）
  • 文件名（“test. Txt”）
  • 要对文件的操作类型（如：r 只读；rw 读写等）
• OS 的处理过程：
  • 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的的目录项，并检查该用户是否有指定的操作权限
  • 将目录项从外存复制到内存中的“打开文件表” 的一个表目中，并将该表目的索引号（也称文件描述符）返回给用户
• 注意：
  • 只要完成了 open 系统调用，之后对文件的操作（read，write，Lseek，close 等）均使用文件描述符，这样可以加快文件的访问速度
  • 打开文件表整个系统只有一张
  • 对于访问打开文件表的索引号，UNIX 称之为文件描述符，Windows 称之为文件句柄
• 打开文件所具有的关联信息：
  • 文件指针：
    • 系统跟踪上次的读写位置作为当前文件位置的指针
    • 这种指针对打开文件的某个进程来说是唯一的，因此必须与磁盘文件属性分开保存
  • 文件打开计数：
    • 计数器跟踪当前文件打开和关闭的数量
    • 因为多个进程可能打开同一个文件，所以系统在删除打开文件条目之前，必须等待最后一个进程关闭文件
  • 文件磁盘位置：
    • 大多数文件操作要求系统修改文件数据
    • 查找磁盘上的文件所需的信息保存在内存中，以便系统不必为每个操作都从磁盘上读取该信息
  • 访问权限：
    • 每个进程打开文件都需要有一个访问模式（创建、只读、读写、添加等）
    • 该信息保存在进程的打开文件表中，以便操作系统能够允许或拒绝后续的 I/O 请求

关闭文件（close 系统调用）

• OS 的处理过程：
  • 将进程的打开文件表相应表项删除
  • 回收分配给该文件的内存空间等资源
  • 系统打开文件表的打开计数器 count 减 1，若 count =0，则删除对应表项
• 内存中文件的系统结构：
  • 在多个不同进程可以同时打开文件的操作系统中，通常采用两级表：
    • 整个系统的打开文件表：包含与进程无关的信息，如文件在磁盘上的位置、访问日期和文件大小
    • 每个进程的打开文件表：保存的是进程对文件的使用信息，如文件的当前读写指针、文件访问权限，并包含指向系统表中适应条目的指针
  • 一旦有进程打开了一个文件，系统表就包含该文件的条目
  • 当另一个进程执行调用 open 时，只不过是在其文件打开表中增加一个条目，并指向系统表的相应条目
  • 通常，系统打开文件表为每个文件关联一个打开计数器（Open Count）, 以记录多少进程打开了该文件
  • 每个关闭操作 close 使 count 递减，当打开计数器为 0 时，表示该文件不再被使用，并且可从系统打开文件表中删除相应条目

读文件（read 系统调用）

• 根据文件名查找目录【open 之后通过文件描述符】，找到指定文件的目录项后，再利用目录项中的读指针进行读操作
• 从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域
• 外存 -⇒ 内存

写文件（write 系统调用）

• 根据文件名查找目录【open 之后通过文件描述符】，找到指定文件的目录项后，再利用目录项中的写指针进行写操作
• 从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存
• 内存 -⇒ 外存

文件保护

基本概念

• 保护的目的：解决对文件的读、写、执行的许可问题
• 一个文件的访问常由用户访问权限和文件属性（包括保存在 FCB 中对文件访问的控制信息）共同设置

非访问控制方法

• 都是防止用户文件被他人存取或窃取，并没有控制用户对文件的访问类型

口令保护

• 定义：用户建立一个文件时需要提供口令【附在 FCB 上】，用户请求访问时必须提供相应口令
• 优点：时间和空间开销不多
• 缺点：口令直接存在系统内部，不安全

加密保护

• 定义：对文件进行加密，被访问时需要使用秘钥
• 优点：保密性强，节省了存储空间
• 缺点：编码和译码需要时间

访问控制方法

• 访问类型：读、写、执行、添加、删除、列表清单
• 方法：
  • 根据用户身份进行访问控制
  • 为每个文件和目录增加一个访问控制表 ACL，以规定每个用户名及其所允许的访问类型
  • 优点：可以使用复杂的访问方法
  • 缺点：长度无法预计并且可能导致复杂的空间管理
• 注意：
  • 上述的文件保护可以只在低层提供
  • 对文件的重命名、复制、粘贴等控制方式【高层功能】，可通过系统程序调用低层系统调用实现
• 精简的访问控制列表：
  • 解决 ACL 的问题，包含三种用户类型：
    • 拥有者：创建文件的用户
    • 组：一组需要共享文件且具有类似访问的用户
    • 其他：系统内的所有其他用户
  • 每项占用一个二进制位，只需 3 * 4 位的矩阵即可描述三类用户的权限
  • 创建文件时，系统将文件拥有者的名字、所属组名记录在该文件的 FCB 中

文件的逻辑结构

• 指从用户角度出发所看到的文件的组织形式

无结构文件

• 基本概念：
  • 最简单的文件组织形式
  • 文件内部的数据就是一系列二进制流或字符流，又称流式文件
  • 其长度以字节为单位
  • 如：系统中运行的大量源程序、可执行文件、库函数等
• 访问方式：
  • 通过读/写指针来指出下一个要访问的字节
  • 没有结构，因此对记录的访问只能通过穷举搜索的方式

有结构文件

• 基本概念：
  • 指由一个以上的记录构成的文件，又称记录式文件
  • 各记录由相同或不相同的数据项组成
• 根据各记录的长度是否相等，可分为：
  • 定长记录：
    • 文件中所有记录的长度相同
    • 各数据项都在记录中的相同位置，具有相同的长度
    • 特点：检索记录的速度快，方便用户对文件进行处理，广泛用于数据处理中
  • 变长记录：
    • 文件中各记录的长度不一定相同
    • 记录中所包含的数据项数目可能不同，数据项本身的长度可能不同
    • 特点：检索记录只能顺序查找，速度慢
• 根据记录的组织形式，可分为：

顺序文件

• 文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的
• 各个记录在物理上有两种存储方式：
  • 顺序存储：
    • 逻辑上相邻的记录物理上也相邻
    • 可变长记录：无法实现随机存取，每次只能从第一个记录开始依次往后查找
    • 定长记录：
      • 可以实现随机存取
      • 若采用串结构，无法快速找到某关键字对应的记录
      • 若采用顺序结构，可以快速找到某关键字对应的记录（如折半查找）
  • 链式存储：
    • 逻辑上相邻的记录物理上不一定相邻（类似于链表）
    • 无论是定长/可变长记录，都无法实现随机存取
• 顺序文件中记录的排列有两种结构：
  • 串结构：各记录之间的顺序与关键字无关
  • 顺序结构：记录之间的顺序按关键字顺序排列
• 注意：
  • 对记录进行批量操作，即每次要读或写一大批记录时，顺序文件的效率是所有逻辑文件中最高的
  • 对于顺序存储设备（如磁盘），只有顺序文件才能被存储并能有效地工作
  • 在需要经常增删改查单个记录的场合，性能较差

索引文件

• 建立一张索引表，为主文件的每个记录在索引表中分别设置一个索引表项，其中包含指向记录的指针和记录长度
• 索引表按关键字排序，其本身也是一个定长记录的顺序文件
• 将对变长记录顺序文件的检索转变成对记录索引文件的随机检索，从而加快了记录的检索速度
• 主要用于对信息处理的及时性要求比较高的场合

索引顺序文件

• 是索引文件和顺序文件思想的结合
• 先将变长记录顺序文件中的所有记录分为若干组，然后为文件建立一张索引表
• 为每组中的第一个记录建立一个索引项，包含该记录的关键字和指向该记录的指针
• 同一组内的关键字可以无序，组与组之间的关键字必须有序
• 检索效率分析：

直接文件或散列文件（Hash File）

• 给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址
• 这种映射结构不同于顺序文件或索引文件，没有顺序的特性
• 散列文件有很高的存取速度，但是会引起冲突，即不同关键字的散列函数值相同

文件的物理结构

• 用户通过逻辑地址来操作自己的文件，操作系统如何实现从逻辑地址到物理地址的映射？
• （逻辑块号，块内地址）-⇒（物理块号，块内地址）【只需转换块号就行，块内地址保 持不变】

连续分配

• 文件的目录项记录起始块号和所占用的块数
• 要求每个文件在磁盘上占有一组连续的块
• 磁盘地址定义了磁盘上的一个线性排序，使作业访问磁盘时需要的寻道数和寻到时间最小
• 优点：
  • 支持顺序访问和直接访问（即随机访问）
  • 连续分配的文件在顺序访问时速度最快
• 缺点：
  • 文件长度不宜动态增加
  • 存储空间利用率低，反复增删文件后会产生外部碎片
  • 很难确定一个文件需要的空间大小，因此只适用于长度固定的文件

链接分配

隐式链接

• 目录项中记录了文件存放的起始块号和结束块号
• 每个文件对应一个磁盘块的链表，磁盘块分布在磁盘的任何地方
• 除最后一个盘块外，每个盘块都含有指向文件下一个盘块的指针，这些指针对用户是透明的
• 优点：
  • 方便文件拓展，不会有碎片问题，外存利用率高
• 缺点：
  • 只适合顺序访问，不支持随机访问，查找效率低
  • 稳定性问题，文件盘块中的任何一个指针出问题，都会导致文件数据的丢失
  • 指向下一个盘块的指针也要耗费一定的存储空间
• 为了提高查找速度和减小指针所占空间，可以将几个盘块组成一个簇，按簇分配，可以大幅减少查找时间，但增加了内部碎片

显式链接

• 指把用于链接文件各物理块的指针，从每个物理块的末尾中提取出来，显式地存放在内存的一张链接表
• 该表在整个磁盘中仅设置一张，称为文件分配表 FAT
• 开机时文件分配表放入内存，并常驻内存
• 文件目录中只需记录文件的起始块号，后续块号可通过查 FAT
• 优点：
  • 很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问
  • 相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高
• 缺点：
  • 文件分配表的需要占用一定的存储空间

索引分配

单级索引分配

• 将每个文件所有的盘块号集中地放在一起，当访问到某个文件时，将该文件对应的盘块号一起调入内存
• 为每个文件分配一个索引块（表），存放分配给该文件的所有盘块号
• 假如盘块大小为 4 KB，每个盘块号占 4 B，则一个索引块中可放 1024 个盘块号，支持最大文件为 1024 * 4 KB = 4 MB
• 优点：
  • 支持直接访问
  • 不会产生外部碎片
• 缺点：
  • 索引块增加了额外的存储空间开销
  • 当文件很小时，比如只有数个盘块，此时索引块的利用率很低
  • 当文件很大时，若其盘块号占用若干索引块，可通过链指针将各索引块按序链接起来，但是很查找效率低下

多级索引分配

• 文件太大而索引块太多时，为这些索引块再建立一级索引，称为主索引
• 采用 K 层索引结构，且顶级索引表未调入内存，则访问一个数据块需要 K+1 次读磁盘操作
• 假如盘块大小为 4 KB，每个盘块号占 4 B，则一个索引块中可放 1024 个盘块号，支持最大文件为 1024 * 1024 * 4 KB = 4 GB
• 优点：极大加快了对大型文件的查找速度
• 缺点：当访问一个盘块时，其所要启动磁盘的次数随着索引级数的增加而增多

混合索引分配

• 全面照顾到小型、中星、大型和特大型文件
• 直接地址：
  • 地址项 0~9 存放直接地址，即文件数据块的盘块号
  • 假如每个盘块大小为 4 KB，适用于不大于 40 KB 的文件
  • 提高了对小文件的检索速度
• 一次间接地址：
  • 地址项 10 提供，即采用一级索引分配
  • 一次间接地址中记录了文件的一次间址块号，一次间址块就是索引块，记录了文件数据块的盘块号
  • 一次间址块中可存放 1024 个盘块号，允许最大文件长度 4 MB + 40 KB
• 多次间接地址：
  • 地址项 11 提供二次间接地址，即采用两级索引分配
  • 允许最大文件长度 4 GB + 4 MB + 40 KB

目录

文件目录的实现

• 一个文件对应一个 FCB，一个 FCB 就是一个目录项，多个 FCB 组成文件目录
• 对目录的操作：搜索、创建文件、删除文件、显示文件、修改文件
• 目录管理的基本要求：
  • 从用户角度，实现“按名存取”
  • 提高对目录的检索速度
  • 多用户系统中，提供用于控制访问文件的信息，允许文件共享
  • 允许不同用户对不同文件采用相同的名字

目录结构

单级目录结构

• 定义：
  • 整个文件系统只建立一张目录表
  • 每个文件占一个目录项
• 优点：实现了 “按名存取”
• 缺点：
  • 查找速度慢、文件不允许重名、不便于文件共享
  • 对于多用户的操作系统不适用

两级目录结构

• 定义：
  • 文件目录分为主文件目录 MDF 和用户文件目录 UFD
  • MDF 记录用户名及相应 UFD 所在的存储位置
  • UFD 记录用户所有文件的 FCB
• 优点：
  • 解决了多用户之间的文件重名问题
  • 文件系统可以在目录上实现访问限制
• 缺点：
  • 缺乏灵活性，不能对文件分类

树形目录结构

• 定义：
  • 当用户要访问某个文件时，用文件的路径名标识文件，文件路径名是个字符串，由从根目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成
  • 从根目录出发的路径称为绝对路径
  • 当层次较多时，每次从根目录查询会浪费时间，于是加入了当前目录（又称工作目录），进程对各文件的访问都是相对于当前目录进行的
  • 当用户要访问某个文件时，使用相对路径标识文件
  • 不同的用户的文件，文件名可相同可不同
  • 大多 OS 采用这种目录结构
• 优点：
  • 可以很方便的对文件进行分类
  • 能够有效地进行文件的管理和保护
• 缺点：
  • 不便于实现文件共享
  • 查找文件增加了磁盘访问次数，会影响查询速度
• 下图是 Linux 操作系统的目录结构，“/dev/hda” 就是一个绝对路径
• 若当前目录为 “/bin”，则 “./Is” 就是一个相对路径，其中符号 ”.” 表示当前工作目录

无环图目录结构

• 定义：
  • 在树形目录结构上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图
  • 可以用不同的文件名指向同一个文件，甚至可以指向同一个目录【共享同一目录下的所有内容】
  • 需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点
  • 用户提出删除结点的请求时，只是删除该用户的 FCB、并使共享计数器减 1，并不会直接删除共享结点
  • 只有共享计数器减为 0 时，才删除结点
• 优点：实现了文件共享
• 缺点：使得系统管理变得更加复杂

索引节点

• 除了文件名之外的所有信息都放到索引节点中，每个文件对应一个索引节点
• 目录项中只包含文件名、索引节点指针，因此每个目录项的长度大幅减小
• 每个磁盘块可以存放更多个目录项，因此线索文件时磁盘 I/O 的次数就少了很多

文件共享

• 文件共享使多个用户共享同一个文件，系统只需保留该文件的一个副本

基于索引节点的共享方式（硬链接）

• 定义：
  • 硬链接就是多个指针指向一个索引节点
  • 文件的物理地址和其他文件属性信息放在索引节点中
  • 索引节点中需要有链接计数 count
  • 某用户想删除文件时，只是删除该用户的目录项，count—
  • 只有 count == 0 时才能真正删除文件数据和索引节点，否则会导致指针悬空
• 特点：
  • 不可用于跨文件系统
  • 查找速度比软链接快

基于符号链的共享方式（软链接）

• 定义：
  • 在一个 Link 型的文件中记录共享文件的存放路径（类似于 Windows 系统中的快捷方式）
  • OS 根据路径一层层查找目录，最终找到共享文件
  • 只有文件主才拥有指向索引节点的指针
  • 共享文件的其他用户只有该文件的路径名，并不拥有指向其索引节点的指针
• 特点：
  • 访问共享文件时可能多次地读磁盘，增加了访问文件的开销
  • 实现网络文件共享时，只需提供该文件所在机器的网络地址及文件路径名

文件系统

文件系统的基本概念

• 概念：
  • 文件系统是 OS 中负责管理持久数据的子系统
  • 文件系统 = 与文件管理有关的软件 + 被管理的文件 + 试试文件管理所需的数据结构
  • 文件系统需先挂在到某个目录才可正常使用
  • 文件的基本操作单位就是数据块
• 目标：
  • 用户角度：实现对文件的基本操作，如按名存储和查找文件 + 组织成合适的结构 + 文件共享 + 文件保护
  • OS 角度：
    • 管理与磁盘的信息交换 + 完成逻辑结构和物理结构的变换
    • 组织文件在磁盘上的存放 + 采取好的文件排放顺序和磁盘调度方法
• 分类：
  • 磁盘的文件系统：
    • 它是直接把数据存储在磁盘中，比如 Ext 2/3/4、XFS 等都是这类文件系统
  • 内存的文件系统：
    • 这类文件系统的数据不是存储在硬盘的，而是占用内存空间
    • 我们经常用到的 /proc 和 /sys 文件系统都属于这一类
    • 读写这类文件，实际上是读写内核中相关的数据
  • 网络的文件系统：
    • 用来访问其他计算机主机数据的文件系统，比如 NFS、SMB 等等

文件系统结构

王道 ppt 版

• 假设某用户请求删除文件 “D:/工作目录/学生信息.xlsx” 的最后 100 条记录：
• 用户接口：用户需要通过操作系统提供的接口发出上述请求
• 文件目录系统：由于用户提供的是文件的存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录项
• 存取控制模块（存取控制验证层）：不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限
• 逻辑文件系统与文件信息缓冲区：验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址
• 物理文件系统：知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址
• 设备管理程序模块： 要删除这条记录，必定要对磁盘设备发出请求
• 辅助分配模块：删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收

王道书版

• I/O 控制：
  • 设备驱动程序：将输入的命令翻译成底层硬件的特定指令
  • 中断处理程序：利用指令使 IO 设备与系统交互
• 基本文件系统：
  • 向对应的设备驱动程序发送通用命令，以读取和写入磁盘的物理块
  • 管理内存缓冲区，保存各种文件系统，目录和数据块的缓冲
• 文件组织模块：
  • 组织文件及其逻辑块和物理块
  • 可以将逻辑地址转换为物理地址
  • 有空闲空间管理器，以跟踪未分配的块，根据需要提供给文件组织模块
• 逻辑文件系统：
  • 用于管理元数据信息（包括文件系统的所有结构，不包括文件内容）
  • 管理目录结构
  • 通过 FCB 维护文件结构
  • 负责文件保护

文件系统布局

文件系统在磁盘中的结构

• 文件系统存放在磁盘上，多数磁盘划分为一个或多个分区
• 每个分区中有一个独立的文件系统
• 文件系统可能包含如下信息：
• 主引导记录（MBR）：
  • 位于磁盘的 0 号区，用来引导计算机
  • MBR 后面是分区表，给出每个分区的起始和结束地址
  • 表中的第一个分区被标记为活动分区，当计算机启动时，计算机读入并执行 MBR
  • MBR 做的第一件事就是确定 1 活动分区，读入它的第一块，即引导块
• 引导块：
  • Windows 系统称之为分区引导扇区
  • MBR 执行引导块中的程序后，该程序负责启动该分区中的操作系统
  • 每个分区都从一个引导块开始，即使它不含有一个可启动的操作系统
  • 除了从引导块开始，磁盘分区的布局是随着文件系统的不同而变化的
• 超级块：
  • 包含文件系统的所有关键信息
  • 比如：分区的块的数量、块的大小、空闲块的数量和指针、空闲的 FCB 数量和 FCB 指针等
  • 在计算机启动时，或者在该文件系统首次使用时，超级块会被读入内存
• 文件系统中空闲块的信息：使用位示图或指针链接的形式给出
• i 节点：每个文件对应一个 i 节点，说明了文件的方方面面
• 根目录：存放文件系统目录树的根部
• 最后，磁盘的其他部分存放了其他所有的目录和文件

文件系统在内存中的结构

• 内存中的信息用于管理文件系统并通过缓存来提高信息
• 这些数据在安装文件系统时被加载，在文件系统操作期间被更新，在卸载时被丢弃
• 这些结构的类型可能包括：
  • 内存中的安装表：包含每个已安装文件系统分区的有关信息
  • 内存中的目录结构的缓存：包含最近访问目录的信息
  • 整个系统的打开文件表
  • 每个进程的打开文件表

外存空闲空间管理

• 一个磁盘可以划分为多个分区，每个分区够可以有单独的文件系统
• 卷：
  • 包含文件系统的分区【可以是磁盘的一部分/整个磁盘/多个磁盘组成的 RAID 集】
  • 文件区：存放文件数据的空间
  • 目录区：FCB 的空间
  • 卷在提供文件服务前，必须由对应的文件程序进行初始化，划分好目录区和文件区，建立空闲空间管理表格及存放卷信息的超级块
• 文件存储设备分成许多大小相同的物理块，并以块为单位交换信息
• 文件存储设备的管理实质上是对空闲块的组织和管理，它包括空闲块的组织、分配与回收等问题

空闲表法

• 属于连续分配方式，为每个分区文件分配一块连续的存储空间
• 在外存上为所有空闲区建立一张空闲表
• 每个空闲区对应一个空闲表项，包括：
  • 表项序号
  • 该空闲区的第一个空闲盘块号
  • 该空闲区的空闲盘块数
• 按起始盘块号递增的次序对空闲区排列
• 如何分配磁盘块：
  • 与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间
  • 同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间
• 如何回收磁盘块：
  • 与内存管理中的动态分区分配很类似，有四种情况
  • 回收时需要注意表项的合并问题

空闲链表法

空闲盘块链

• 将磁盘上的所有空闲空间以盘块为单位拉成一条链
• 每个盘块都有指向下一个空闲盘块的指针
• 当用户请求分配存储空间时：系统从链首开始，依次摘下适当数目的空闲盘块分配给用户
• 当用户释放存储空间时：系统将回收的盘块依次插入空闲盘块链的末尾
• 优点：
  • 分配和回收一个盘块的过程非常简单
  • 适用于离散分配的物理结构
• 缺点：
  • 在为一个文件分配盘块时可能要重复操作多次，效率较低
  • 以盘块为单位，链会很长

空闲盘区链

• 指将磁盘上的所有空闲盘区拉成一条链，每个盘区包含若干相邻的盘块
• 每个盘区含有下一个空闲盘区的指针和本盘区的盘块数
• 分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法
• 回收盘区时，同样也要将回收区与相邻接的空闲盘区合并
• 优点：是分配与回收的效率较高，且空闲盘区链较短
• 缺点：是分配与回收的过程比较复杂

位示图法

• 利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上所有的盘块都有一个二进制位与之对应【0 代表盘块空闲，1 代表盘块已分配】
• 盘块的分配：
  1. 顺序扫描位示图，从中找出一个或一组其值为 “0” 的二进制位
  2. 将找到的一个或一组二进制位，转换成与之对应的盘块号 b = n (i - 1) + j
  3. 修改位示图 0 ⇒ 1
• 盘块的回收：
  • 将回收盘块的盘块号转换成位示图中的行号和列号：
    • i = (b - 1) DIV n + 1
    • j = (b - 1) MOD n + 1
  • 修改位示图 1 ⇒ 0
• 优点：
  • 很容易在位示图中找到一个或一组相邻接的空闲盘块
  • 占用空间少，可将其保存在内存中，节省磁盘启动的开销
• 缺点：
  • 位示图大小会随着磁盘容量的增加而增大，故常用于小型计算机

成组链接法

• 基本思想：
  • 将空闲盘块分成若干个组，每组的第一个盘块记录下一组的空闲盘块总数和空闲盘块号
  • 由各组的第一个盘块可以链接成一条链
  • 第一组的空闲盘块总数和空闲盘块号保存在内存的专用栈中，称为空闲盘块号栈
• 盘块的分配：
  • 根据空闲盘块号栈的指针，将与之对应的盘块分配给用户，同时移动指针
  • 若该指针指向的是栈底的盘块号，则由于该盘块号对应的盘块中保存的是下一组空闲盘块号，因此要将该盘块的内容读入栈中，作为新的空闲盘块号栈的内容，并将原栈底盘块号对应的盘块分配出去 ( 其中有用的数据已读入栈中)
  • 最后，将栈中的空闲盘块数减 1
• 盘块的回收：
  • 将回收的盘块号存入空闲盘块号栈的顶部，同时移动指针，并将栈中的空闲盘块数加 1
  • 当栈中的空闲盘块数已达 100 时，表示栈已满，将现有栈中的 100 个空闲盘块号存入新回收的盘块，并将新回收的盘块号作为新栈底，再将栈中的空闲盘块数置为 1

虚拟文件系统

• 虚拟文件系统（VFS）：屏蔽了不同文件系统的差异和操作细节，向上为用户提供了文件操作的同一调用接口
• 特点：
  • 向上层用户进程提供统一标准的系统调用接口，屏蔽底层具体文件系统的实现差异
  • VFS 要求下层的文件系统必须实现某些规定的函数功能（open/read/write）
  • 一个新的文件系统想要在某 OS 上被使用，则必须满足 VFS 的要求
  • 每打开一个文件，VFS 就在主存中新建一个 vnode，用统一的数据结构表示文件，无论该文件存储在哪个文件系统【vnode 的功能指针指向具体文件系统的函数功能】

文件系统挂载

• 文件系统挂载（mounting）：文件系统在进程使用之前必须先挂载到某个目录，此后便可通过这个目录来访问设备上的文件
• 注意：这里的设备是逻辑上的设备，如一个磁盘上的不同分区都可视为不同的设备
• 挂载过程：
  1. 在 VFS 中注册新挂载的文件系统，内存中的挂载表包含每个文件系统的相关信息，包括文件系统类型、容量大小等
  2. 新挂载的文件系统，要向 VFS 提供一个函数地址列表
  3. 将新文件系统加到挂载点，也就是将新文件系统挂载到某个父目录下