📂 操作系统 - Operating System / Chapter IV 持久性 / Section 2 文件 / 2-1 文件系统

文件系统实现

2026-06-07
#OS

  • 关于文件系统

    • 在设计文件系统时，我们需要考虑文件系统的数据结构(data structure) 和访问方法(access method)
      • 在磁盘上通过什么结构来组织数据
      • 进程发出的调用如何映射到结构上，这些访问的执行效率如何
    • 接下来会介绍简单文件系统(VSFS, Very Simple File System) ，是典型Unix文件系统的简化版本

  • 整体组织

    • 首先开发VSFS在磁盘上的数据结构的整体组织，我们需要做的第一件事是给磁盘分块(block)，简单的文件系统只需要一种块大小，这里取4KB
    • 假设我们的磁盘中有64个4KB的块，这些块的地址为0~63

    • 数据区域

      • 磁盘中应当存储的最多的是用户数据，所以将磁盘的块8~63用于存放用户数据，这一片磁盘区域被称为数据区域(data region)

    • inode

      • 文件系统必须存储每个文件的信息，这些信息是元数据(metadata) 的关键部分，记录了如文件包含哪些块、文件大小、所有者、访问权限情况、修改时间等的信息，这些信息被存储在一个名为inode的结构中
      • 磁盘上需要留出一些空间来存放inode，这部分区域被称为inode表(inode table)，在这里用块3~7存储
      • 假设一个inode单元的大小为256字节，这里的inode表就包含80个inode

    • 分配结构

      • 我们还需要一部分空间用于存储inode或数据块是空闲还是已被分配，因此我们需要一个分配结构(allocation structure)。这里我们使用位图(bitmap) 作为分配结构。
      • 位图是一个简单的结构，每个位用于指示相应的对象/块是空闲（0）还是正在使用（1）
      • 我们需要一个inode位图和一个数据位图，分别使用块1和块2

    • 超级块

      • 我们将剩下的块0保留给超级块(superblck)
      • 超级块存储了该文件系统的信息，例如文件系统中有多少个inode和数据块、inode表的开始位置、文件系统类型等

  • 文件组织：inode

    • 文件系统中最重要的磁盘结构之一是inode，即索引节点(index node) 的缩写。这些节点最初存放在一个数组中，在访问特定inode时会用到该数组的索引
    • inode是用于描述保存给定文件元数据的结构，元数据中包括长度、权限、组成块的位置等
    • 每个inode都由一个数字inumber（即低级名称） 隐式引用。inumber是目标inode在inode表中的索引，配合inode表的地址与inode大小即可找到对应inode。
    • 每个inode中都存储了对应文件的所有信息，统称为元数据（实际上，除了用户数据之外的所有数据都被称作元数据）：
      • 文件类型：常规、目录
      • 大小
      • 分配给它的块数
      • 保护信息（访问权限等）
      • 事件信息（创建日期、修改日期等）
      • 数据块驻留在磁盘位置相关的信息

    • 设计inode

      • 设计inode时需要考虑inode如何引用数据块的位置。最简单的方法是维护一个或多个指针，每个指针都指向属于该文件的一个磁盘块，但这意味着需要的指针数量可能很大

      • 多级索引

        • 为了支持更大的文件，文件设计者需要在inode块中引入不同的结构
        • 一个常见的思路是引入一个被称为间接指针(indirect pointer) 的特殊指针
          • 间接指针并不指向包含用户数据的块，而是指向包含更多指针的块，那些指针是指向用户数据的
          • 如果一个文件变得足够大，那么系统就会从数据块区域为它分配一个间接块，并让inode的间接指针指向间接块
          • 如果还希望支持更大的文件，那么只需要一个双重间接指针(double indirect pointer)，指向一个包含间接块指针的块，每个间接块中都有很多指向数据块的指针。如果还要更大的，那就弄三重间接指针……
        • 这种不平衡树被称为指向文件块的多级索引(multi-level index) 方法
        • 是否使用间接指针以及使用几重间接指针是需要为每个文件分别考虑的，毕竟大多数文件用不上间接指针

      • 链接

        • 设计inode还可以使用链表(linked list)。这样，inode中只需要存储一个指向文件的第一个块的指针即可，然后在数据块的末尾添加指向下一个数据块的指针，直到最后一个数据块
        • 链接式文件分配对于某些工作负载表现不佳，例如读取文件的最后一个块或者随机访问时，可能需要遍历一大段链表
        • 为了使链接式分配更优秀地工作，有些系统在内存中保存链接信息表，而不是将下一个指针与数据块本身一起存储。这样就可以先相对高速地遍历内存中的表，然后再访问磁盘中的目标数据块
        • 这种系统采用的是文件分配表(FAT, File Allocation Table)，本身没有inode

  • 目录组织

    • 对于许多的文件系统，目录的组织很简单。一个目录只包含一个二元组（条目名称、inode号）的列表。这意味着对于给定目录中的每个文件和目录，目录的数据块中都有一个字符串和一个数字，看还会有一个长度数据（如果名称可变）
    • 除此之外，每个目录中还会有两个额外的条目：.（点目录） 和 ..（点点目录）
      • 点目录就是当前目录
      • 点点目录是当前目录的上一级目录（父目录）
    • 一个文件被删除时会在目录中间留下一段空白空间，新的条目就可以尝试重复使用这段空间
    • 由于操作系统将目录视为特殊的文件，所以一个目录自己也有一个inode，只不过该inode给目录标记为“目录” 而非文件
    • 线性目录并不是存储这些信息的唯一办法，还可以使用B树(B-tree)，使文件创建操作快于简单列表

  • 空闲空间管理

    • 文件系统必须记录哪些inode和数据块是空闲的、哪些不是，这就是空闲空间管理(free space management)。OS会使用两个位图来完成这一目的
    • 当我们创建一个文件时，我们必须为该文件分配一个inode。文件系统会通过位图搜索一个空闲的内容，并将其分配给该文件。然后文件系统会将该inode标记为已使用，并用正确的信息更新磁盘上的位图。分配数据块时也会发生类似的活动。
    • 一些系统会偏向于寻找一组连续的空闲块来分配给一个文件（即使这个文件可能用不了这么多块），保证文件的一部分在存储上是连续的，从而提高性能。这种预分配(pre-allocation)策略是为数据块分配空间时的常用启发式方法

  • 访问路径：读取和写入

    • 从磁盘读取文件

      1. 当用户发出一个open()调用，提供目标文件的路径，现在文件系统遍历(traverse) 路径名，找到所需的inode
      2. 先通过根目录的inumber（在大多数UNIX文件系统中为2），找到根目录的inode块
      3. 在inode中查找指向数据块的指针，找到下一级目录的inumber以及下一级目录的inode块
      4. 重复（递归）这一过程，直到找到目标文件的inode
      5. 通过inode，获得目标文件的位置，将目标文件读入内存
      • 读取文件是不会访问分配结构的

    • 写入磁盘

      • 写入磁盘过程与从磁盘读取类似
      • 写入有时会需要通过分配结构来获得新的块