当前位置：首页 > web >正文

26考研——文件管理_文件系统（4）

web 2025/7/15 8:41:02

408答疑

文章目录

三、文件系统
- 1、文件系统架构
- - 1.1、文件系统的基本概念
  - 1.2、文件系统结构
  - 1.3、文件系统布局
  - - 1.3.1、文件系统在磁盘中的结构
    - 1.3.2、文件系统在内存中的结构
  - 1.4、虚拟文件系统
- 2、磁盘空间管理
- - - 2.1、空闲表法
    - 2.2、空闲链表法
    - 2.3、位示图法
    - 2.4、成组链接法
五、参考资料
- 鲍鱼科技课件
- 26王道考研书
- 小林coding

三、文件系统

1、文件系统架构

1.1、文件系统的基本概念

什么是文件系统？
- 文件（File）：相关信息的集合。
- 目录（Directory）：组织和管理文件的形式。
- 文件系统（File System, FS）：操作系统中驻留于持久化存储设备（如硬盘）上的重要子系统，实现数据的存储、定位和检索，为磁盘提供高效访问。
文件系统的作用：
- 对用户而言：
  - 实现文件的基本操作（创建、存储、查找、共享、保护等）。
  - 提供结构化的文件组织方式。
- 对操作系统而言：
  - 管理磁盘信息与结构。
  - 控制文件的存放和调度。
  - 提高系统性能与可靠性。
文件系统的构成：
1. 与文件管理相关的软件
2. 被管理的文件数据本身
3. 用于支持管理的数据结构（如文件控制块 FCB）
常见文件系统类型：
- Windows：NTFS、FAT
- Linux：ext2、ext3、ext4
- macOS：AFS 等
文件系统的实现重点：
- 逻辑文件系统使用 FCB（File Control Block） 管理文件结构。
- 实现用户对文件的访问、修改、保存等操作。
文件系统要完成的核心功能：
1. 对用户：提供直观的文件操作界面和功能。
2. 对系统：高效组织文件在磁盘上的存储结构、管理磁盘交换与调度等。
文件系统的设计涉及两个不同的问题：
1. 定义文件系统的用户接口，它涉及定义文件及其属性、所允许的文件操作、如何组织文件的目录结构。
2. 创建算法和数据结构，以便映射逻辑文件系统到物理外存设备。

1.2、文件系统结构

现代操作系统有多种文件系统类型，因此文件系统的层次结构也不尽相同。下图是一个合理的文件系统层次结构。
I/O 控制层：
- 包括设备驱动程序和中断处理程序，在内存和磁盘系统之间传输信息。
- 设备驱动程序将输入的命令翻译成底层硬件的特定指令，硬件控制器利用这些指令使 I/O 设备与系统交互。
- 设备驱动程序告诉 I/O 控制器对设备的什么位置采取什么动作。
基本文件系统：
- 向对应的设备驱动程序发送通用命令，以读取和写入磁盘的物理块。每个物理块由磁盘地址标识。
- 该层也管理内存缓冲区，并保存各种文件系统、目录和数据块的缓存。
- 在进行磁盘块传输前，分配合适的缓冲区，并对缓冲区进行管理。
- 管理它们对于系统性能的优化至关重要。
文件组织模块：
- 组织文件及其逻辑块和物理块。
- 文件组织模块可以将文件的逻辑块地址转换为物理块地址，每个文件的逻辑块从 0 到 N 编号，它与数据的物理块不匹配，因此需要通过转换来定位。
- 文件组织模块还包括空闲空间管理器，以跟踪未分配的块，根据需求提供给文件组织模块。
逻辑文件系统：
- 用于管理文件系统中的元数据信息。
- 元数据包括文件系统的所有结构，而不包括实际数据（或文件内容）。
- 逻辑文件系统管理目录结构，以便根据给定文件名为文件组织模块提供所需要的信息。它通过文件控制块来维护文件结构。
- 逻辑文件系统还负责文件保护。

1.3、文件系统布局

1.3.1、文件系统在磁盘中的结构

文件系统存放在磁盘上，多数磁盘划分为一个或多个分区，每个分区中有一个独立的文件系统。
文件系统可能包括如下信息：启动存储在那里的操作系统的方式、总的块数、空闲块的数量和位置、目录结构以及各个具体文件等。
下图所示为一个可能的文件系统布局。
除了从引导块开始，磁盘分区的布局是随着文件系统的不同而变化的。文件系统经常包含有如上图所列的一些项目。
1. 主引导记录（Master Boot Record, MBR）：
  - 位于磁盘的 0 号扇区，用来引导计算机。
  - MBR 的后面是分区表，该表给出每个分区的起始和结束地址。
  - 表中的一个分区被标记为活动分区。
  - 当计算机启动时，BIOS 读入并执行 MBR。
  - MBR 做的第一件事是确定活动分区，读入它的第一块，即引导块。
2. 引导块（boot block）：
  - MBR 执行引导块中的程序后，该程序负责启动该分区中的操作系统。
  - 每个分区都是统一从一个引导块开始，即使它不含有可启动的操作系统，也不排斥以后会在该分区安装一个操作系统。
  - Windows 系统称之为分区引导扇区。
3. 超级块（super block）：
  - 包含文件系统的所有关键信息，在计算机启动时，或者在该文件系统首次使用时，超级块会被读入内存。
  - 超级块中的典型信息包括分区的块的数量、块的大小、空闲块的数量和指针、空闲的 FCB 数量和 FCB 指针等。
4. 文件系统中空闲块的信息：可以用位示图或指针链接的形式给出。
注意：
- 除了以上四点，后面也许跟的是一组 i 节点，每个文件对应一个节点，i 节点说明了文件的方方面面。
- 接着可能是根目录，它存放文件系统目录树的根部。
- 最后，磁盘的其他部分存放了其他所有的目录和文件。

1.3.2、文件系统在内存中的结构

内存中的信息用于管理文件系统并通过缓存来提高性能。这些数据在安装文件系统时被加载，在文件系统操作期间被更新，在卸载时被丢弃。
这些结构的类型可能包括：
1. 安装表（mount table），包含每个已安装文件系统分区的有关信息。
2. 目录结构的缓存，包含最近访问目录的信息。
3. 整个系统的打开文件表，包含每个打开文件的 FCB 副本、打开计数及其他信息。
4. 每个进程的打开文件表，包含进程打开文件的文件描述符（Windows 称之为文件句柄）和指向整个系统的打开文件表中对应表项的指针。

1.4、虚拟文件系统

概述：
- 虚拟文件系统（VFS）屏蔽了不同文件系统的差异和操作细节，向上为用户提供了文件操作的统一调用接口，如下图所示。
- 当用户程序访问文件时，通过 VFS 提供的统一调用函数（如 open() 等）来操作不同文件系统的文件，而无须考虑具体的文件系统和实际的存储介质。
设计思想：
- 虚拟文件系统采用了面向对象的思想，它抽象出一个通用的文件系统模型，定义了通用文件系统都支持的接口。
- 新的文件系统只要支持并实现这些接口，即可安装和使用。
- 为了实现虚拟文件系统，系统抽象了四种对象类型。每个对象都包含数据和函数指针，这些函数指针指向操作这些数据的文件系统的实现函数。
- 这四种对象类型如下。
  1. 超级块对象：
    - 表示一个已安装（或称挂载）的特定文件系统。
    - 超级块对象对应于磁盘上特定扇区的文件系统超级块，用于存储已安装文件系统的元信息。
    - 其操作方法包含一系列可在超级块对象上调用的操作函数，主要有分配 inode、销毁 inode、读 inode、写 inode 等。
  2. 索引节点对象：
    - 表示一个特定的文件。
    - 索引节点和文件是一对一的关系。
    - 只有当文件被访问时，才在内存中创建索引节点对象，每个索引节点对象都会复制磁盘索引节点包含的一些数据。
    - 索引节点对象还提供许多操作函数，如创建新索引节点、创建硬链接、创建新目录等。
  3. 目录项对象：
    - 表示一个特定的目录项。
    - 目录项对象是一个路径的组成部分，它包含指向关联索引节点的指针，还包含指向父目录和指向子目录的指针。
    - 不同于前面两个对象，目录项对象在磁盘上没有对应的数据结构，而是 VFS 在遍历路径的过程中，将它们逐个解析成目录项对象的。
  4. 文件对象：
    - 表示一个与进程相关的已打开文件。
    - 可以通过调用 open() 打开一个文件，通过调用 close() 关闭一个文件。
    - 文件对象仅是进程视图上代表已打开的文件，它反过来指向其索引节点。
    - 文件对象包含与该文件相关联的目录项对象，包含该文件的文件系统、文件指针等，还包含在该文件对象上的一系列操作函数。
- 对用户来说，不需要关心不同文件系统的具体实现细节，只需要对一个虚拟的文件操作界面进行操作。
- VFS 对每个文件系统的所有细节进行抽象，使得不同的文件系统在系统中运行的进程看来都是相同的。
- 严格来说，VFS 并不是一种实际的文件系统，它只存在于内存中，不存在于任何外存空间中。
- VFS 在系统启动时建立，在系统关闭时消亡。
示例分析：
- 当进程发起一个面向文件的系统调用时，内核调用 VFS 中的一个函数，该函数调用目标文件系统中的相应函数，将文件系统请求转换到面向设备的指令。
- 以在用户空间调用 write() 为例，它在 VFS 中通过 sys_write() 函数处理，sys_write() 找到具体文件系统提供的写方法，将控制权交给该文件系统，最后由该文件系统与物理介质交互并写入数据，如下图所示。

2、磁盘空间管理

卷的定义和组成：
- 一个存储设备可以按整体用于文件系统，也可以细分。例如，一个磁盘可以划分为 2 个分区，每个分区都可以有单独的文件系统。
- 包含文件系统的分区通常称为卷（volume）。
  - 卷可以是磁盘的一部分，也可以是整个磁盘，还可以是多个磁盘组成 RAID 集，如下图所示。
  - 卷的结构：
    - 在一个卷中，存放文件数据的空间（文件区）和 FCB 的空间（目录区）是分离的。
    - 因为存在很多种类的文件表示和存放格式，所以现代操作系统中一般都有很多不同的文件管理模块，通过它们可以访问不同格式的卷中的文件。
    - 卷在提供文件服务前，必须由对应的文件程序进行初始化，划分好目录区和文件区，建立空闲空间管理表格及存放卷信息的超级块。
文件存储设备的管理：文件存储设备分成许多大小相同的物理块，并以块为单位交换信息，因此，文件存储设备的管理实质上是对空闲块的组织和管理，它包括空闲块的组织、分配与回收等问题。

存储分配策略：连续 vs 非连续

2.1、空闲表法

空闲表法的概述：
- 空闲表法属于连续分配方式，它与内存的动态分区分配类似，为每个文件分配一块连续的存储空间。
- 系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应一个空闲表项，其中包括表项序号、该空闲区的第一个空闲盘块号、该空闲区的空闲盘块数等信息。
- 再将所有空闲区按其起始盘块号递增的次序排列，如下图所示。
盘块的分配：
- 空闲盘区的分配与内存的动态分配类似，也是采用首次适应算法、最佳适应算法等。
- 例如，在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲盘块表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户，同时修改空闲盘块表。
盘块的回收：在对用户所释放的存储空间进行回收时，也采用类似于内存回收的方法，即要考虑回收区是否与空闲盘块表中插入点的前区和后区相邻接，对相邻接者应予以合并。
空闲表法的优点：具有较高的分配速度，可减少访问磁盘的 I/O 频率。
对于较小的文件（ $\sim 5$ 个盘块），可以采用连续分配方式为文件分配几个相邻的盘块。

2.2、空闲链表法

空闲链表法是指将所有空闲盘区拉成一条空闲链，可分为以下两种。

空闲盘块链：
- 空闲盘块链是指将磁盘上的所有空闲空间以盘块为单位拉成一条链。每个盘块都有指向下一个空闲盘块的指针，如下图所示。
- 盘块的分配：当用户请求分配存储空间时，从链首开始，依次摘下适当数量的空闲盘块分配给用户。
- 盘块的回收：当用户释放存储空间时，将回收的盘块依次插入空闲盘块链的末尾。
- 空闲盘块链的优点：分配和回收一个盘块的过程非常简单。
- 空闲盘块链的缺点：在为一个文件分配盘块时可能要重复操作多次，效率较低；又因为它是以盘块为单位的，空闲盘块链会很长。
空闲盘区链：
- 空闲盘区链是指将磁盘上的所有空闲盘区拉成一条链，每个盘区包含若干相邻的盘块。每个盘区含有指向下一个空闲盘区的指针和本盘区的盘块数。
- 分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。
- 回收盘区时，同样也要将回收区与相邻接的空闲盘区合并。
- 空闲盘区链的优缺点正好与空闲盘块链的相反。
  - 空闲盘区链的优点：分配与回收的效率较高，且空闲盘区链较短。
  - 空闲盘区链的缺点：分配与回收的过程比较复杂。

2.3、位示图法

位示图法的概述：
- 位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上的所有盘块都有一个二进制位与之对应。
  - 当其值为 “0” 时，表示对应的盘块空闲；
  - 为 “1” 时，表示已分配。
- 这样，一个 $\times n$ 位组成的位示图就可用表示 $\times n$ 个盘块的使用情况，如下图所示。
盘块的分配：
1. 顺序扫描位示图，从中找出一个或一组其值为 “0” 的二进制位。
2. 将找到的一个或一组二进制位转换成与之对应的盘块号。假设找到值为 “0” 的二进制位处在位示图的第 $i$ 行、第 $j$ 列，则其对应的盘块号应按下式计算（ $n$ 为每行位数）：
  $b = n (i - 1) + j$
3. 修改位示图，令 $ma p [i, j] = 1$ 。
盘块的回收：
1. 将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：
  $\, \text{DIV} \, n + 1 \\ j = (b - 1) \, \text{MOD} \, n + 1$
2. 修改位示图，令 $ma p [i, j] = 0$ 。

如无特别提示，本书所用位示图的行和列都从 1 开始编号。特别注意，若题中指明从 0 开始编号，则上述计算方法要进行相应的调整。

位示图法的优点：
- 很容易在位示图中找到一个或一组相邻接的空闲盘块。
- 由于位示图很小，占用空间少，因此可将它保存在内存中，从而节省许多磁盘启动的开销。
位示图法的缺点：位示图大小会随着磁盘容量的增加而增大，因此常用于小型计算机。

2.4、成组链接法

成组链接法的概述：
- 成组链接法适用于大型文件系统，它结合了空闲表法和空闲链表法的思想，以克服“表太长”的缺点。
- UNIX系统中采用的就是成组链接法。
示例分析：
- 如下图所示。
- 将空闲盘块分成若干组，如每 100 个盘块作为一组，每组的第一个盘块记录下一组的空闲盘块总数和空闲盘块号。这样，由各组的第一个盘块可以链接成一条链。
- 第一组的空闲盘块总数和空闲盘块号保存在内存的专用栈中，称为空闲盘块号栈。
- 假设系统空闲区为第 $201\sim7999$ 号盘块，则第一组的盘块号为 $201\sim300……$ 次末组的盘块号 $7801 ～ 7900$ ，最末一组的盘块号为 $7901 ～ 7999$ 。最末一组只有 99 个盘块，它们的块号记录在前一组的 7900 号盘块中，该块中存放的第一个盘块号是 “0”，以作为空闲盘块链的结束标志。
- 简而言之，每组（除了最后一组）的第一块作为索引块，然后将这些索引块链接起来。
盘块的分配：
- 根据空闲盘块号栈的指针，将与之对应的盘块分配给用户，同时移动指针，并将栈中的空闲盘块数减 1。
- 若该指针指向的是栈底的盘块号，则在该盘块号对应的盘块中保存的是下一组空闲盘块号，因此要将该盘块的内容读入栈，作为新的空闲盘块号栈的内容，并将原栈底盘块号对应的盘块分配出去（其中有用的数据已读入栈）。
- 例如，在分配盘块时，先依次分配 $201\sim299$ 号盘块，当需要分配 300 号盘块时，首先将 300 号盘块的内容读入空闲盘块号栈，然后再分配 300 号盘块。
盘块的回收：
- 将回收的盘块号存入空闲盘块号栈的顶部，同时移动指针，并将栈中的空闲盘块数加 1。
- 当栈中的空闲盘块数已达 100 时，表示栈已满，将现有栈中的 100 个空闲盘块号存入新回收的盘块，并将该新回收的盘块号作为新栈底，再将栈中的空闲盘块数置为 1。