10 File System Implementation

10.1 File-System Structure

文件系统是操作系统中用于以文件形式管理计算机软件资源的软件，它由被管理的文件以及目录、索引表等数据结构组成，是对存储设备上数据和元数据进行组织与管理的机制。

磁盘提供大量的外存空间来维持文件系统，磁盘的两个特点，使其成为存储多个文件的方便媒介

• 可以原地重写；可以从磁盘上读一块，修改该块，并将它写回到原来的位置
• 可以直接访问磁盘上的任意一块信息。（随机或顺序方式）

分层设计的文件系统

下面列举一些常见的文件系统

• FAT32（VFAT）
• ext2、ext3、ext4（linux文件系统、Android）
• HFS+ (Mac OS ，iOS文件系统)
• ...

10.2 File-System Implementation

文件系统的实现涉及在磁盘（外存）和内存中维护两套相互关联但用途不同的数据结构。

在磁盘上，文件系统需要存储一系列关键的静态信息，以确保其自身能够被正确识别、启动和使用。这些信息包括：

• 用于启动操作系统的引导控制块（Boot control block）
• 描述整个卷（Volume）属性的卷控制块（Volume control block）
• 组织所有文件的目录结构
• 为每个文件单独维护的文件控制块（FCB），其中包含了该文件的详细元数据（如权限、大小、位置等）

在内存中缓存并维护一套动态的数据结构。这套内存结构主要包括：

• 一个分区表，用于记录所有已挂载卷的信息；
• 一个目录结构缓存，用于加速对最近访问过的目录项的查找；
• 一个系统级的打开文件表，它包含了所有当前被打开文件的FCB副本以及全局的访问状态（如文件指针、打开计数等）；
• 每个进程独有的打开文件表，用于管理该进程对各个打开文件的私有信息（如各自的读写位置和访问权限）。

图（a）描述了open(file_name)操作：当用户程序调用打开文件时，操作系统在内核内存中查找目录结构以定位文件，并在二级存储（如磁盘）中找到对应的文件控制块（file-control block），建立文件的元数据映射。

图（b）描述了read(index)操作：在文件已打开后，用户程序通过索引读取数据，此时系统利用进程私有的打开文件表（per-process open-file table）和全局打开文件表（system-wide open-file table）来定位文件控制块，并最终访问二级存储中的数据块。

现代操作系统普遍采用虚拟文件系统（VFS）作为核心抽象层。VFS提供了一种面向对象的方法，它定义了一套统一的接口（API），使得上层应用程序和系统调用无需关心底层具体是哪种物理文件系统（如ext4、NTFS、FAT32等）。

10.3 Directory Implementation

Linear list（线性检索法）：最为简单的目录实现方法是使用存储文件名和数据块指针的线性列表（数组、链表等），容易实现，但运行费时。许多操作系统采用软件缓存来存储最近访问过的目录信息，如：Linux的目录项对象

哈希表（Hash Table）是一种常用方法，它将目录组织为带有哈希数据结构的线性列表，通过计算文件名的哈希值来快速定位文件，显著减少了搜索时间；其主要挑战在于哈希冲突（即不同文件名映射到同一位置）以及哈希表大小固定和对哈希函数的依赖性。

索引也是一种常见的方法。ext系列文件系统（如ext2、ext3、ext4）会使用索引机制来管理大量目录项。XFS是一种高性能的日志式文件系统，常用于Linux系统中的高性能计算和大型数据库等场景，它利用B+树索引来组织目录结构，以支持高效的随机访问和大容量数据管理。

10.4 Allocation Methods

文件的物理结构由其磁盘块分配方法决定，主要分为三种：

• 连续分配（Contiguous allocation）将一个文件的所有磁盘块连续存放，便于顺序访问但易产生外部碎片；
• 链接分配（Linked allocation）通过指针将分散的磁盘块连接起来，解决了碎片问题但不支持高效随机访问；
• 索引分配（Indexed allocation）使用一个索引块来存储所有数据块的地址，既支持随机访问又避免了外部碎片。

Unix和Linux系统采用直接、间接和多重间接混合的分配方式，结合了多种方法的优点，以实现高效灵活的文件存储管理。

Contiguous Allocation

每个文件占据磁盘上的一组连续的物理块，在目录中只需要记录文件的起始位置（块号）及长度。此时访问文件很容易，所需的寻道时间也最少。

但是这个方法的问题在于为新文件找空间比较困难（类似于内存分配中的连续内存分配方式），文件也很难增长。

Example

针对上述缺点，进行一定的改进，提出一种 Extent-Based Systems （基于长度系统）的文件系统。该方法开始分配一块连续空间，当空间不够时，另一块被称为扩展的连续空间会添加到原来的分配中。

那么此时记录文件快的位置就为开始地址、块数、加上一个指向下一扩展的指针。

Example

Linked allocation

每个文件是磁盘块的链表；磁盘块分布在磁盘的任何地方。实现起来也比较容易，同时记录时只需要起始位置与最终位置，文件创建起来和增长起来比较容易。

缺点就是不能随机访问，必须要遍历，同时块与块之间的链接指针需要占用空间。

分配簇(Cluster，若干个扇区)比分配块(block，一般是指一个扇区)更节省指针占用的空间，减少访问时间。如：Windows

一个典型的应用是 FAT 文件系统家族。

---

FAT（文件分配表）文件系统是一种被MS-DOS和OS/2所使用的磁盘空间管理机制，其核心是通过一个名为FAT的表格来追踪磁盘上每个簇（Cluster）的使用状态和链接关系。

在MS-DOS中，一个卷的结构通常包含引导记录、两个FAT表（用于冗余备份）、根目录区和数据区（存放文件和子目录）

FAT32引导区记录被扩展为包括重要数据结构的备份，根目录也被改为了一个普通的簇链（不同于上图），其目录项可以放在文件区任何地方。

主引导区记录MBR 是主引导区的第一个扇区，它由两部分组成

• 第一部分主引导代码，占据扇区的前446个字节，磁盘标识符（FD 4E F2 14）位于这段代码的未尾。
• 第二部分是分区表，分区表中每个条目有16字节长，分区表最多有4个条目，第一个分区条目从扇区的偏移量位置是0x01BE。

PC 启动过程

计算机系统启动时，首先执行的是BIOS引导程序，完成自检，并加载主引导代码和分区表，然后执行主引导程序，由它加载激活分区（安装操作系统的分区）引导记录，再执行分区引导记录程序，加载操作系统，最后执行操作系统，配置系统。

Indexed allocation

将所有的数据块指针集中到索引块中

• 索引块中的第 \(i\) 个条目指向文件的第 \(i\) 块。
• 目录条目包括索引块的地址

索引分配支持直接访问，且没有外部碎片问题

索引块本身可能会浪费空间

• 链接方案：一个索引块通常为一个磁盘块。对于大文件，可以将多个索引块链接起来。
• 多层索引：类似于内存的间接寻址方式（一级、二级间接…）
• 组合方案：如Unix的inode

对于链接方案下的索引怎么从虚拟地址找到物理块在哪里

每一个物理块 512 个字节，每一个索引块有 511 个索引（最后一个指向下一个索引块）

对于二级索引来说，怎么从虚拟地址找到相应的物理块呢？

注意这里与前者的区分

在 UNIX、Linux 采用直接间接混合分配方法

在 Linux 的 ext2/ext3/ext4 文件系统中，每个文件都有一个对应的 inode（索引结点），它是一个数据结构，用来存储该文件的元信息和数据块的位置信息。

由于80％以上文件是小文件，为了解决能高速存取小文件和管理大文件的矛盾，UNIX将直接寻址、一级索引、二级索引和三级索引结合起来，形成混合寻址方式，如上图所示。

在Linux ext2的索引结点中设有15个地址项，它们把所存的地址项分成两类，其中最后三个地址项分别是一级索引、二级索引和三级索引的指针，而前面12个为直接寻址的地址项，即存放文件逻辑块第0－11块的盘块号。

如每个盘块大小为4KB时，当文件不大于48KB时，便可直接从索引结点中读出该文件全部盘块号，这样读小文件时速度快；如文件大于 48KB时，系统再逐步增加一级索引、二级索引和三级索引，这样最大管理的文件为48KB＋4MB＋4GB＋4TB，达到管理大文件的目标。

10.5 Free-Space Management

为了记录空闲磁盘空间，系统需要维护一个空闲空间链表，它记录了所有空闲磁盘空间，即未分配给文件或目录的空间。（不一定以链表的方式实现）

常用的方法有以下几种

• 位示图法（Bitmap）
• 空闲链表法
• 空闲表法，计数
• 分组

位图：bit[i] = 0 说明 block[i]空闲；bit[i] = 1 说明 block[i]被占用。位图的使用需要额外的空间（用于记录每一块是否空闲）这个方法被 Windows、Liunx、Mac OS 所使用。

链表(空闲链表)：将所有空闲磁盘块用链表连接起来，并将指向第一空闲块的指针保存在磁盘的特殊位置，同时也缓存在内存中。

• 不易得到连续空间
• 没有空间浪费

分组：将n个空闲块的地址存在第一个空闲块中，而最后一块包含另外n个空闲块的地址，如此继续。（意思就是第一个空闲块存储（n-1）个空闲块的地址，然后最后一个存储下一个这样存储其他空闲块的空闲块）

计数（空闲表法）：通常，有多个连续块需要同时分配或释放。因此，可以记录第一块的地址和紧跟第一块的连续的空闲块的数量n。

评论区

对你有帮助的话请给我个赞和 star =>
欢迎跟我探讨！！！