Lecture 14 - File Systems

文件系统概述与XV6对比

文件系统的重要性

文件系统是操作系统中除Shell之外最常见的用户接口。用户日常操作计算机时，文件系统是不可或缺的一部分。通过对文件系统的学习，了解其背后的原理和实现方法，有助于更深刻地理解操作系统的整体设计。

文件系统的核心特性

1. 用户友好的文件名与路径：
   • 文件系统允许使用层级路径名来组织文件，这使得用户能够以逻辑方式组织和管理文件。这种结构化路径不仅方便了文件的查找和管理，也使得在用户与进程之间共享文件变得更加容易。
2. 持久化存储：
   • 文件系统提供了持久化功能，这意味着文件在计算机重启后依然保留。这一点使得文件系统区别于其他资源管理子系统，如进程管理，它们在系统重启后需要重新初始化，而文件系统则能保证数据的持久性。

XV6文件系统与现代文件系统的异同

1. 文件大小与文件名限制：
   • XV6文件系统对支持的文件大小有较为严格的限制，相比之下，现代文件系统支持的文件尺寸更大。此外，XV6对文件名的长度也有限制，而现代文件系统通常支持更长、更灵活的文件名。
2. 缺少高级特性：
   • XV6文件系统缺少一些现代文件系统中的高级特性，例如copy-on-write（写时复制）技术，这种技术可以有效地减少数据写入时的资源消耗。
3. 基本结构的相似性：
   • 尽管在功能上有所不同，XV6文件系统与现代文件系统在基本结构上仍然相似。它们都采用了文件名、inode（索引节点）、目录等基本概念，并且文件目录的结构都是层级式的。
4. …

文件系统的内部机制与关键概念

在接下来的课程中，我们将深入探讨文件系统的内部工作原理。文件系统之所以有趣，主要有以下几个原因：

1. 文件系统对硬件的抽象

• 硬件抽象的实现：文件系统通过对硬件的抽象，使得用户和应用程序可以方便地与底层存储设备进行交互，而无需关心具体的硬件细节。理解这一抽象层的实现方式对于深入理解操作系统的设计有重要意义。

2. 崩溃安全性（Crash Safety）

• 崩溃恢复能力：文件系统在执行过程中，可能会遇到计算机崩溃的情况。在这种情况下，崩溃安全性能够确保文件系统在重启后仍然保持数据的完整性和一致性。如果文件系统在崩溃后无法恢复，用户的数据可能会丢失或损坏。因此，崩溃安全性是文件系统设计中的一个关键点，我们将在下节课中深入探讨这一主题。

3. 文件系统在磁盘上的布局

• 磁盘数据结构：文件系统的目录和文件在磁盘上需要以某种数据结构存在，这样才能在系统重启后恢复数据。XV6文件系统使用的磁盘数据结构较为简单，因为其目的是教学。然而，真实的文件系统通常会更为复杂，这些复杂的数据结构在磁盘上保存文件系统的结构和内容。今天的课程将重点探讨这些数据结构如何在磁盘上布局和组织。

4. 文件系统的性能优化

• 硬件速度差异与性能优化：存储设备的访问速度通常较慢，比如在SSD上写入数据的操作可能需要数毫秒，而在这段时间内，计算机可以执行大量的其他任务。因此，优化文件系统的性能非常重要。例如，文件系统通常使用缓冲缓存（buffer cache）或块缓存（block cache）来减少对磁盘的直接写入操作，从而提升整体性能。
• 并发处理：文件系统还需要处理多进程并发操作。例如，当一个进程正在查找路径名时，另一个进程可能在执行其他文件系统操作。如何有效管理这些并发操作是文件系统设计中的一个重要话题。

实验内容与文件系统的关联

接下来的实验内容将围绕文件系统展开：

• Lab任务：下一个实验（lab）将完全聚焦于文件系统的实现和优化。再下一个实验则会结合虚拟内存和文件系统进行综合练习。即使是本周的实验，也涉及到如何让缓冲缓存支持更多的并发操作。因此，深入理解文件系统不仅对理论学习有帮助，也直接影响到你们在实验中的实践表现。

文件系统相关系统调用与实现细节

在理解文件系统的功能和实现时，研究其提供的系统调用是至关重要的。通过这些系统调用的接口，我们可以推测出文件系统内部的一些设计细节。以下是与文件系统相关的一些关键系统调用及其背后机制的分析。

1. open 系统调用

代码示例：

int fd = open("x/y", O_CREATE | O_RDWR);

• 功能：在路径 x/y 下创建一个新文件，或打开已存在的文件，并返回一个文件描述符 fd。
• 分析：
  • 路径名的可读性：系统调用中的路径名是用户可读的字符串，而非硬件层面的数字地址，这意味着文件系统需要支持将用户输入的路径名解析为具体的存储位置。
  • 文件的偏移管理：open 仅返回文件描述符，而文件偏移量（offset）并未作为参数传入。文件系统必须内部维护文件的当前偏移量，以便后续的 write 操作可以在正确的位置进行写入。

2. write 系统调用

代码示例：

write(fd, "abc", 3);

• 功能：将字符串 "abc" 写入到文件 fd 指向的文件中。
• 分析：
  • 隐式文件偏移量：write 系统调用没有显式提供偏移量。文件系统会在内部记录文件的当前偏移量，并在每次写入后自动更新这个值。
  • 并发写入的管理：由于文件偏移量是在文件系统内部管理的，多线程或多进程的并发写入需要确保对偏移量的访问是线程安全的，避免数据竞争。

3. link 系统调用

代码示例：

link("x/y", "x/z");

• 功能：为已有文件 x/y 创建一个新的硬链接 x/z，即 x/y 和 x/z 两个路径名指向同一个文件。
• 分析：
  • 引用计数管理：文件系统需要跟踪同一个文件的多个文件名。这通常通过增加引用计数的方式来实现，每创建一个新的链接，引用计数加一。
  • inode的管理：link 操作直接在 inode 层面进行，而不是文件描述符层面。inode 是文件系统内部用来表示文件元数据的结构，每个文件对应一个唯一的 inode。

4. unlink 系统调用

代码示例：

unlink("x/y");

• 功能：删除路径名 x/y，使之不再指向任何文件。如果此文件的引用计数降为0，则文件将从磁盘中删除。
• 分析：
  • 命名空间与文件对象的分离：unlink 仅删除文件名与文件对象之间的映射关系，而不会影响已打开的文件描述符。即使路径名被删除，文件描述符依然可以继续操作该文件。这意味着文件系统需要在内部维护文件对象与文件名之间的独立性。

文件系统API与实现之间的关系

通过上述系统调用的API，我们可以推测出文件系统内部的一些设计和实现细节：

1. 路径名解析：文件系统需要实现从路径名到具体存储位置（如 inode）的解析过程。这涉及到文件系统的目录结构和路径查找算法。
2. 文件偏移管理：文件系统必须在内部维护每个打开文件的当前偏移量，以支持连续的读写操作。
3. 引用计数与inode管理：文件系统需要维护每个文件的引用计数，以便在文件的引用数归零时正确地释放资源。同时，文件系统还必须在 inode 层面管理文件链接操作。
4. 文件对象的抽象：文件系统内部必须将文件对象与其命名分离，以支持在文件名删除后仍然可以通过文件描述符访问文件。

文件系统的实现与其他存储系统的对比

值得注意的是，文件系统提供的API并不是唯一构建存储系统的方式。比如，数据库系统同样可以持久化存储数据，但其API与文件系统的API完全不同。早期数据库通常直接基于磁盘构建自己的文件系统，以提高性能并确保数据一致性（ACID属性）。然而，现代操作系统的文件系统已经足够强大，绝大多数现代数据库都建立在操作系统自带的文件系统之上。

硬链接与软链接：硬链接 (link) 直接操作 inode，而软链接（将在下一个实验中实现）是指向文件路径的符号链接。硬链接与文件对象直接关联，而软链接则是一个独立的文件，存储了目标文件的路径信息。

文件系统的结构与核心数据结构

为了实现前面介绍的各种文件系统API，文件系统内部必须维护一系列复杂的数据结构。接下来，我们将重点介绍这些结构是如何组织的，以及它们如何协同工作以支持文件系统的功能。

1. inode（索引节点）

• inode的作用：在文件系统中，inode 是一个代表文件的对象，它不依赖于文件名。每个 inode 都有一个唯一的编号（整数），文件系统内部通过这个编号来引用和管理文件，而不是通过路径名。
• link count：inode 还必须维护一个 link count，用于跟踪指向该 inode 的文件名的数量。只有当 link count 为0时，文件才能被删除。
• openfd count：此外，inode 还需要维护一个 openfd count，即当前打开的文件描述符的数量。只有当 link count 和 openfd count 都为0时，文件才会被从磁盘上删除。

+------------------------------+
|          inode               |
|  +------------------------+  |
|  | inode number (ID)      |  |  // Unique identifier for the file
|  +------------------------+  |
|  +------------------------+  |
|  | link count             |  |  // Tracks the number of links to this inode
|  +------------------------+  |
|  +------------------------+  |
|  | openfd count           |  |  // Tracks the number of open file descriptors
|  +------------------------+  |
+------------------------------+

2. 文件描述符（File Descriptor）

• offset管理：每个文件描述符（file descriptor）与用户进程交互，并隐式地维护了一个文件的偏移量（offset）。当进行 read 或 write 操作时，文件系统会自动更新这个偏移量，以确保数据被正确地写入或读取。
• 文件描述符与inode的关联：文件描述符本质上是用户访问文件的接口，而 inode 是文件在文件系统内部的表示形式。文件描述符通过 inode 访问文件的实际数据。

+------------------------------+
|      File Descriptor         |
|  +------------------------+  |
|  | File Descriptor ID     |  |  // Handle used by user process
|  +------------------------+  |
|  +------------------------+  |
|  | File Offset            |  |  // Maintains the current read/write position
|  +------------------------+  |
|  +------------------------+  |
|  | Pointer to inode       |  |  // Points to the inode for actual file data
|  +------------------------+  |
+------------------------------+

3. 文件系统的分层结构

文件系统的实现通常非常复杂，为了更好地理解这些复杂性，我们可以采用分层的方式来分析文件系统的结构。这种分层结构帮助我们从概念上理解文件系统的各个组件是如何协同工作的。

• 磁盘层：这是最底层，负责实际的数据存储。磁盘提供了持久化存储功能。
• 缓冲缓存（Buffer Cache）/块缓存（Block Cache）：位于磁盘之上，缓冲缓存用来减少对磁盘的直接访问，提升性能。数据从磁盘读取后，通常会被暂时保存在缓存中，以便快速访问。
• 日志记录层（Logging Layer）：在缓冲缓存之上，许多文件系统都会有日志记录机制，用于保证系统的持久性和一致性。通过日志记录，可以在系统崩溃后恢复未完成的文件操作。我们将在下节课深入讨论这个层次。
• inode缓存层：在XV6中，为了实现同步操作，系统维护了 inode 缓存。多个 inode 通常打包在一个磁盘块中，因此 inode 缓存帮助我们在操作单个 inode 时实现同步。
• inode层：这个层次直接负责文件的 read 和 write 操作，是文件系统的核心部分之一。
• 路径名和文件描述符层：最上层是路径名解析和文件描述符操作。路径名用于用户定位文件，文件描述符则是用户与文件系统交互的主要方式。

  +----------------------------------------+
  |  Pathname & File Descriptor Layer      |
  |  - Pathname resolution                 |
  |  - File Descriptor operations          |
  +----------------------------------------+
  |            inode Layer                 |
  |  - Handles read/write operations       |
  +----------------------------------------+
  |           inode Cache Layer            |
  |  - Synchronize & optimize inode access |
  +----------------------------------------+
  |          Logging Layer                 |
  |  - Ensure system durability            |
  +----------------------------------------+
  |         Buffer/Block Cache Layer       |
  |  - Reduce disk I/O                     |
  +----------------------------------------+
  |           Disk Layer                   |
  |  - Persistent storage devices          |
  |  - Data blocks, metadata blocks, etc.  |
  +----------------------------------------+

4. 文件系统实现的灵活性

• 不同文件系统的差异：尽管大多数文件系统都会有类似的结构和分层，但实现细节可能会有所不同。有些文件系统在某些层次上可能会合并，或者采用不同的优化策略。例如，在某些文件系统中，缓存机制或日志机制可能会更为复杂或定制化。
• 分层的意义：尽管分层在实际实现中并不总是严格的，但从概念上理解这些层次对于掌握文件系统的工作原理非常有帮助。无论文件系统如何实现，它们通常都会涉及到缓存、日志、inode 和路径名解析等核心组件。

存储设备概述

在文件系统的最底层，是各种类型的存储设备。虽然有许多不同类型的存储设备，但我们主要关注两种最常见的类型：SSD（固态硬盘）和HDD（机械硬盘）。这两种存储设备尽管在性能上有显著差异，但它们都以合理的成本提供了大量的存储空间。

1. SSD与HDD的性能对比

• SSD（Solid State Drive）：
  • 访问时间通常在 0.1到1毫秒 之间。
  • 通过闪存技术存储数据，速度快，但成本相对较高。
• HDD（Hard Disk Drive）：
  • 访问时间通常在 10毫秒 量级。
  • 使用磁性材料的旋转盘片存储数据，较慢但成本较低。

2. 术语解释：Sectors与Blocks

• Sector：
  • 是磁盘驱动器可以读写的最小单元，通常为 512字节。
• Block：
  • 是操作系统或文件系统视角的数据单元，大小由文件系统定义。在XV6中，一个block是1024字节，因此一个block通常对应两个sector。

有时候，磁盘上的sector也被称为block，这使得术语使用上可能不太精确。

3. 存储设备与计算机的连接

存储设备（如SSD和HDD）通过计算机的总线连接到CPU和内存。文件系统运行在CPU上，管理内存中的数据，同时通过读写block的形式与存储设备进行交互。存储设备的接口通常非常简单，主要包括 read 和 write 操作，通过block编号来指定读写位置。

4. 硬件抽象与驱动程序

尽管SSD和HDD在内部工作原理上有很大不同，但硬件抽象屏蔽了这些差异。磁盘驱动程序通常使用标准协议（如PCIe）与存储设备交互。从文件系统的角度看，不同的存储设备在编程接口上看起来几乎一样——你可以通过提供block编号、控制寄存器读写等方式来与设备进行通信。

无论存储设备的底层机制如何不同，文件系统通过统一的抽象层与这些设备进行交互，使得编程更加简便和一致。

同步/异步接口：磁盘驱动程序与之前讲的console的驱动类似，都是通过发送命令开始读写操作，并在操作完成后产生中断通知。然而，由于磁盘设备的复杂性，磁盘驱动程序的实现通常比console的驱动更复杂，但它们的代码结构仍然是相似的，包括底层的控制和中断处理部分。

文件系统视角下的磁盘结构

从文件系统的角度来看，磁盘可以被抽象为一个巨大的block数组，这个数组的索引从0开始，一直到磁盘的最后一个block。文件系统的工作就是将所有需要的文件数据和元数据以一种能够在系统重启后重新构建文件系统的方式存放在这个磁盘上。

1. 磁盘的block布局

• Block 0：通常是保留的，或者被用作 boot sector，用于启动操作系统。
• Block 1：称为 super block，描述文件系统的整体信息，比如文件系统包含多少个block等。XV6的super block中还包含了更多的元数据信息，可以通过它重建大部分的文件系统结构。
• Block 2-31：在XV6中，这些block用于 log（日志）。日志用于记录文件系统的操作，以保证崩溃恢复的完整性。日志的大小由super block定义，在XV6中通常是30个block。
• Block 32-45：这些block存储了文件系统的 inode。每个inode大小为64字节，多个inode被打包在一个block中。
• Block 46：存储 bitmap block，用于记录数据block的使用状态（空闲或已用）。
• Block 47及以后：这些是 数据block，用于存储文件的内容和目录的数据。

+-----------------------------------------------------------------------------------------+
|  Block 0   |  Block 1  |  Block 2-31   |  Block 32-44  |  Block 45    | Block 46+   ... |
| Boot Block | Superblock|  Log Blocks   |  inode Blocks | Bitmap Block | Data Blocks     |
+-----------------------------------------------------------------------------------------+

2. 元数据block

• Metadata Blocks：通常，bitmap block，inode blocks 和 log blocks 被统称为元数据block（metadata blocks）。这些block虽然不存储实际的文件数据，但它们保存了对文件系统进行管理和维护所需的重要信息。

3. inode在磁盘上的定位

由于每个inode大小为64字节，因此多个inode可以存储在一个block中。为了找到某个特定inode在磁盘上的位置，可以使用以下计算公式：

计算公式

• inode 所在的 block:block number = start block + (inode number * inode size) / block size

• inode 在 block 中的偏移量: offset = (inode number * inode size) % block size

给定条件

• inode 大小: 64 字节
• block 大小: 1024 字节
• inode 起始 block: 32

示例

读取 inode10 的位置：

1. 计算 inode10 所在的 block:
   • block number = 32 + (10 * 64) / 1024
   • block number = 32 + 640 / 1024
   • block number = 32 + 0 (因为 640 小于 1024)
   • inode10 在 block 32
2. 计算 inode10 在 block32 中的偏移量:
   • offset = (10 * 64) % 1024
   • offset = 640 % 1024
   • offset = 640
   • inode10 在 block 32 的偏移量为 640 字节

这个计算方法可以让我们准确定位磁盘上任何 inode 的存储位置，只要我们知道 inode 编号，就可以找到它在磁盘上的位置和偏移量。

+-------------------------------------------------------------+
| Block 32 (inodes 0-15) | Block 33 (inodes 16-31) | ...      |
+-------------------------------------------------------------+

4. XV6与QEMU的启动

• Boot Block：通常，boot block包含启动操作系统所需的初始代码。系统启动后，操作系统的进一步加载和初始化将从文件系统中完成。
• XV6在QEMU中的特殊处理：在QEMU中运行XV6时，使用了简化的启动过程。QEMU可以直接从命令行加载内核镜像文件，并将其加载到物理内存的 0x80000000 地址。这种方式跳过了从虚拟磁盘读取boot sector的步骤。

磁盘上存储的 inode 结构

在文件系统中，inode 是一个关键的数据结构，它描述了文件的元数据以及文件数据在磁盘上的存储位置。在 XV6 中，inode 是一个 64 字节的结构体，其具体组成如下：

inode 的组成部分

1. type 字段：

   • 指定 inode 是文件、目录还是其他类型。

2. nlink 字段：

   • 也称为链接计数器（link count），跟踪有多少文件名指向当前的 inode。当 nlink 变为 0 时，文件就可以被删除。

3. size 字段：

   • 表示文件的大小（以字节为单位）。

4. direct block numbers（直接块编号）：

   • XV6 的 inode 中包含 12 个直接块编号（block numbers），分别指向文件的前 12 个数据块。这些数据块包含了文件的实际内容。
   • 例如，如果文件只有 2 个字节，那么只会使用第一个直接块编号（block number 0），它指向磁盘上存储文件的 2 个字节的那个一个块。

5. indirect block number（间接块编号）：

   • 除了 12 个直接块编号之外，inode 还包含一个间接块编号。这是一个指向磁盘上另一个块的指针，该 block 内包含 256 个块编号，每个编号指向文件的一个数据块。这些数据块存储了文件的更多内容。

   inode 结构示意图：

     +---------------------------------+
     |        inode (64 bytes)         |
     +---------------------------------+
     | type       | 表示文件类型         |
     +---------------------------------+
     | nlink      | 链接计数器           |
     +---------------------------------+
     | size       | 文件大小（字节）      |
     +---------------------------------+
     | direct block number 0           |
     +---------------------------------+
     | direct block number 1           |
     +---------------------------------
     | ...                             |
     +---------------------------------+
     | direct block number 11          |
     +---------------------------------+
     | indirect block number           |
     +---------------------------------+
   

文件最大长度的计算

在 XV6 中，由于 inode 结构的限制，文件的最大长度可以通过以下公式计算：

最大文件长度 = (12 * block size) + (256 * block size)

• 12 个直接块：每个块大小为 1024 字节（1KB）。
• 256 个间接块：每个块包含 256 个块编号，每个块大小为 1024 字节。

最大文件长度 = (12 * 1024) + (256 * 1024) = 12 KB + 256 KB = 268 KB

这是 XV6 中文件的最大长度，为 268KB。尽管这个大小在现代文件系统中显得很小，但 XV6 的设计基于早期 Unix 系统，其文件大小限制与之类似。

扩展 inode 结构以支持更大的文件

为了支持更大的文件，可以扩展 inode 结构，增加双重或多重间接块。例如：

• 双重间接块：指向一个块，这个块包含 256 个间接块编号，每个间接块编号又指向一个包含 256 个直接块编号的块。这样，文件的最大长度可以达到 256 * 256 * 1KB = 64MB。

这种设计类似于多级页表，可以大幅度增加文件系统能够支持的文件大小。你将在接下来的实验中实现这一功能。

读取文件特定字节的步骤

假设需要读取文件的第 8000 个字节，我们可以通过以下步骤来确定如何从磁盘上读取该字节：

1. 确定文件的块编号：
   • 文件的每个块大小为 1024 字节（1KB）。
   • 计算块编号：8000 / 1024 = 7，所以第 8000 个字节在文件的第 7 个块中。
   • 由于 7 小于 12，因此该块是 inode 中的第 7 个直接块编号所指向的块。
2. 计算块内的字节偏移量：
   • 计算偏移量：8000 % 1024 = 832，所以第 8000 个字节在第 7 个块内的偏移量为 832 字节。

inode 与 read/write 系统调用

通过 inode 中的信息，文件系统可以准确地定位文件的数据块，从而实现 read 和 write 系统调用。至少在简单情况下，inode 提供的信息足以查找文件的相关磁盘块并执行读取或写入操作。

目录结构与路径名查找

在文件系统中，目录（directory）是实现层次化命名空间（hierarchical namespace）的关键元素。目录允许用户组织文件和子目录，并使用对用户友好的名称进行访问。大多数 Unix 文件系统中的目录本质上是一个文件，它包含了文件系统能够理解的结构。在 XV6 中，目录的结构非常简单。

1. 目录结构

在 XV6 中，每个目录包含若干个目录项（directory entries），每个目录项的格式固定，总共占用 16 个字节：

• 前 2 个字节：存储文件或子目录的 inode 编号。
• 接下来的 14 个字节：存储文件或子目录的名称。

目录项结构示意图：

+------------------------+-------------------------------+
| inode number (2 bytes) |        Name (14 bytes)        |
+------------------------+-------------------------------+

2. 路径名查找的实现

在文件系统中，路径名查找是将路径名解析为文件或目录的 inode 编号的过程。我们通过一个例子来说明路径名查找的具体步骤。假设我们要查找路径名 "/y/x"，路径名查找的过程如下：

1. 从根目录开始：
   • 路径名 "/y/x" 指示我们需要从根目录开始查找。根目录的 inode 编号通常是固定的，在 XV6 中，这个编号是 1。
   • 根据 inode 编号，文件系统可以确定根目录 inode 在磁盘上的位置。具体来说，inode 存储在从 block 32 开始的区域。inode 1 位于 block 32 中的 64 到 128 字节的位置。
2. 读取根目录的 inode 内容：
   • 读取根目录的 inode 后，文件系统会扫描根目录 inode 对应的所有数据块，以查找名称为 "y" 的目录项。
   • 文件系统需要读取根目录的所有直接块编号（direct block numbers）和间接块编号（indirect block numbers）来查找目录项。
3. 查找子目录 y：
   • 如果找到了 "y" 对应的目录项，那么它会包含子目录 y 的 inode 编号（假设为 251）。
   • 然后，文件系统将读取 inode 251 的内容，并扫描其对应的所有数据块，查找名称为 "x" 的目录项。
4. 返回查找结果：
   • 找到 "x" 对应的 inode 编号后，路径名查找结束，返回该 inode 编号。

3. 目录和文件的区分

在路径名查找过程中，文件系统需要区分 inode 是目录还是文件。这是通过 inode 中的 type 字段实现的。

• type 字段：inode 的 type 字段表明这是一个目录还是一个文件。
• 如果试图对一个文件类型的 inode 进行路径名查找，文件系统会返回错误，因为文件不能作为目录进行进一步查找。

目录查找的效率

在 XV6 中，目录项的查找是通过线性扫描完成的。这种方式虽然简单，但当目录中的文件和子目录数量增加时，查找效率会显著下降。现代文件系统通常使用更复杂的数据结构（如 B 树、哈希表）来加速路径名查找，从而提高查找效率。

然而，XV6 采用了这种简单的结构，目的是为了保持设计的简洁性，并便于解释和理解。尽管这种方法在性能上有所妥协，但它有效地展示了文件系统的基本工作原理。

XV6 文件系统的实际工作流程

在接下来的讨论中，我们将通过一个简单的实验，观察 XV6 文件系统是如何工作的。这对于你们即将进行的实验（lab）非常有帮助。

1. 启动 XV6 和文件系统的创建

当我们启动 XV6 时，会调用 makefs 指令来创建一个文件系统。这一步骤会生成一个新的磁盘镜像，包含在命令中指定的一些文件。

• 文件系统信息：启动时，XV6 会打印出文件系统的基本信息。我们可以看到这个文件系统由 46 个元数据块（meta blocks）和 954 个数据块组成，共 1000 个块。元数据块包括：
  • Boot Block
  • Super Block
  • 30 个 Log Block
  • 13 个 Inode Block
  • 1 个 Bitmap Block

+---------------------------+
| makefs (Create FS)        |
| |                         |
| |--> New Disk Image       |
|      |                    |
|      |--> Boot Block      |
|      |--> Super Block     |
|      |--> 30 Log Blocks   |
|      |--> 13 Inode Blocks |
|      |--> 1 Bitmap Block  |
|      |--> 954 Data Blocks |
+---------------------------+

+-----------------------------------------------------------------------------------------+
|  Block 0   |  Block 1  |  Block 2-31   |  Block 32-44  |  Block 45    | Block 46+   ... |
| Boot Block | Superblock|  Log Blocks   |  inode Blocks | Bitmap Block | Data Blocks     |
+-----------------------------------------------------------------------------------------+

2. 文件系统的写入操作

在演示实验中，对 XV6 进行了修改，使得在任何写入块时，系统都会打印出块的编号。通过观察控制台的输出，我们可以看到在 XV6 启动过程中，某些文件系统调用写入了块 。

3. 实验命令：创建文件并写入数据

我们运行 echo "hi" > x 命令来创建一个文件 x，并向其中写入字符串 "hi"。在此过程中，我们可以观察到以下几个阶段：

1. 创建文件：此阶段创建文件 x 并分配一个新的 inode。
2. 写入 “hi”：此阶段将字符串 "hi" 写入文件 x。
3. 写入换行符：最后，写入一个换行符 \n。

通过控制台输出，我们可以看到这些阶段分别对哪些块进行了写入操作。

4. echo 命令的代码实现

下面是 echo 命令的代码实现。代码基本按照我们观察到的三个阶段执行。

int
main(int argc, char *argv[])
{
  int i;

  for(i = 1; i < argc; i++){
    write(1, argv[i], strlen(argv[i]));  // 将参数写入文件描述符1
    if(i + 1 < argc){
      write(1, " ", 1);  // 写入空格，如果有多个参数
    } else {
      write(1, "\n", 1);  // 写入换行符
    }
  }
  exit(0);
}

• write(1, argv[i], strlen(argv[i]));：将每个参数写入到文件描述符 1（标准输出或重定向的文件）。
• write(1, " ", 1);：如果有多个参数，写入空格。
• write(1, "\n", 1);：在所有参数后面添加一个换行符。

echo 命令执行过程的逐步解析

通过执行 echo "hi" > x 命令，我们可以逐步分析文件系统的操作，特别是它在磁盘上的表现。这有助于我们深入理解文件系统如何分配、管理和更新文件的元数据和数据。

第一阶段：创建文件

在第一阶段，文件系统分配了一个新的 inode，并在根目录中为文件 x 创建了一个新的目录项。以下是每个写操作的详细解释：

1. 写入 Block 33：
   • 操作：系统两次写入了 block 33。
   • 第一次写入：标记新分配的 inode 不再是空闲状态。
     • 在 XV6 中，inode 的 type 字段用于标识 inode 是否空闲，并且表示 inode 是文件还是目录。
     • 第一次写入将 inode 的 type 字段从空闲状态更改为文件类型，并将这个信息写入磁盘。
   • 第二次写入：更新 inode 的元数据。
     • 这次写入将 inode 的其他信息（如 link count 设置为 1）写入磁盘。
2. 写入 Block 46：
   • 操作：向根目录的第一个 block 写入数据。
   • 原因：由于创建了一个新文件 x，需要在根目录中添加一个新的目录项。
   • 目录项内容：这个目录项包含了新文件的名称 x 以及其对应的 inode 编号。
3. 写入 Block 32：
   • 操作：更新根目录的 inode。
   • 原因：根目录的大小增加了 16 个字节（一个目录项的大小），所以需要更新根目录的 inode 信息。
   • 更新内容：更新了 inode 的 size 字段，以反映目录项的增加。
4. 再次写入 Block 33：
   • 操作：再次更新文件 x 的 inode。
   • 原因：尽管此时还没有写入实际数据，文件 x 的 inode 信息（例如 type 字段和 link count）已经发生了变化，需要写入磁盘。

总结：

• 第一阶段 的主要任务是创建文件 x，分配 inode 并在根目录中为其添加目录项。

第二阶段：写入 “hi” 到文件

第二阶段涉及将字符串 "hi" 写入文件 x，并更新相关的元数据。

1. 写入 Block 45：
   • 操作：更新 Bitmap。
   • 原因：文件系统需要在 Bitmap 中找到一个空闲的 data block 来存储数据。找到空闲块后，必须将对应的位设置为 1，表示该块已经被分配。
2. 写入 Block 595（两次）：
   • 操作：文件系统将字符串 "hi" 写入 Block 595。
   • 原因：Block 595 被选择为存储文件 x 的数据块。因为 "hi" 有两个字符，所以数据被写入该块的前两个字节，并两次触发写操作。
3. 再次写入 Block 33：
   • 操作：更新文件 x 的 inode。
   • 原因：需要更新 inode 中的 size 字段，因为文件 x 中有了两个字符。
   • 同时：还需要将 inode 中的第一个 direct block number 更新为 595，指向存储 "hi" 数据的块。

总结：

• 第二阶段 涉及实际数据的写入操作，包括数据块的分配、数据写入以及相关 inode 的更新。

第三阶段：写入换行符到文件

类似第二阶段。

解析 XV6 文件系统的代码实现

在之前的实验中，我们通过操作文件系统并观察磁盘上的变化，初步了解了文件系统的基本操作。现在，我们将深入 XV6 的代码，特别是涉及到 inode 分配的部分，进一步理解文件系统是如何在内核中实现的。这部分内容对理解文件系统的内部工作机制非常重要，也为接下来的实验打下基础。

1. sys_open 函数

sys_open 是处理文件打开和创建的系统调用函数。它位于 sysfile.c 中，负责处理与文件系统相关的操作。以下是 sys_open 函数的代码片段：

// kernel/sysfile.c

uint64
sys_open(void)
{
  char path[MAXPATH];
  int omode;
  struct inode *ip;

  // 获取路径名和打开模式
  argint(1, &omode);
  argstr(0, path, MAXPATH);

  begin_op();

  // 如果指定了 O_CREATE 标志，则创建文件
  if(omode & O_CREATE){
    ip = create(path, T_FILE, 0, 0);
    if(ip == 0){
      end_op();
      return -1;
    }
  } else {
    // 否则尝试打开现有文件
    if((ip = namei(path)) == 0){
      end_op();
      return -1;
    }
    ...
  }
  ...
}

• sys_open 功能：
  • 处理文件的打开请求，如果文件不存在且指定了 O_CREATE 标志，则创建新文件。
  • 如果 O_CREATE 标志存在，sys_open 会调用 create 函数来创建文件。

2. create 函数

create 函数负责处理文件的创建操作。它的实现位于 sysfile.c 中。

// 创建一个新的文件 inode，并在目录中添加相应的目录项
static struct inode*
create(char *path, short type, short major, short minor)
{
  struct inode *ip, *dp;
  char name[DIRSIZ];

  // 解析路径并找到最后一个目录
  dp = nameiparent(path, name);

  ilock(dp);

  // 检查文件是否已经存在
  if((ip = dirlookup(dp, name, 0)) != 0){
    iunlockput(dp);
    ilock(ip);
    // 如果文件已经存在且类型匹配，则返回该 inode
    if(type == T_FILE && (ip->type == T_FILE || ip->type == T_DEVICE))
      return ip;
    iunlockput(ip);
    return 0;
  }

  // 如果文件不存在，分配一个新的 inode
  ip = ialloc(dp->dev, type);
  ilock(ip);
  ip->major = major;
  ip->minor = minor;
  ip->nlink = 1;
  iupdate(ip);  // 更新 inode 到磁盘

  // 为新文件在目录中添加一个目录项
  if(dirlink(dp, name, ip->inum) < 0)
    goto fail;

  iunlockput(dp);
  return ip;

 fail:
  // 如果失败，释放分配的 inode
  ip->nlink = 0;
  iupdate(ip);
  iunlockput(ip);
  iunlockput(dp);
  return 0;
}

• create 功能：
  • 解析路径名并找到最后一个目录。
  • 检查文件是否已存在。如果存在且类型匹配，则返回该文件的 inode。
  • 如果文件不存在，则调用 ialloc 分配一个新的 inode。

3. ialloc 函数

ialloc 函数负责在设备上分配一个新的 inode。它的实现位于 fs.c 中。

// 在设备 dev 上分配一个新的 inode，并将其标记为已分配
struct inode*
ialloc(uint dev, short type)
{
  int inum;
  struct buf *bp;
  struct dinode *dip;

  // 遍历所有可能的 inode，寻找空闲的 inode
  for(inum = 1; inum < sb.ninodes; inum++){
    bp = bread(dev, IBLOCK(inum, sb));  // 读取包含该 inode 的块
    dip = (struct dinode*)bp->data + inum%IPB;
    if(dip->type == 0){  // 找到空闲的 inode
      memset(dip, 0, sizeof(*dip));  // 清空 inode 内容
      dip->type = type;  // 设置 inode 类型为文件
      log_write(bp);  // 将更改写入磁盘
      brelse(bp);
      return iget(dev, inum);  // 返回已分配的 inode
    }
    brelse(bp);
  }
  printf("ialloc: no inodes\n");
  return 0;
}

• ialloc 功能：
  • 遍历所有 inode 编号，找到一个空闲的 inode。
  • 如果找到空闲 inode，将其 type 字段设置为文件类型，标记为已分配。
  • 使用 log_write 将此修改写入磁盘，这是我们在控制台看到的第一个写操作。

4. 函数调用链总结

• sys_open：判断是否需要创建文件，如果需要，则调用 create 函数。
• create：处理文件创建逻辑，包括路径解析、目录项检查、inode 分配等。
• ialloc：实际分配 inode，将 inode 的 type 字段标记为文件，并将这个更改记录到磁盘。

5. 实际上的写入过程

当我们执行 echo "hi" > x 命令时，以下是文件系统创建文件的实际操作过程：

1. 第一个 write 33: 分配 inode 并标记为已使用

• 对应的代码：ialloc(dp->dev, type);
• 操作：在 ialloc 函数中，文件系统找到一个空闲的 inode，将其 type 字段设置为文件类型，并通过 log_write(bp); 将这个更改写入磁盘。
• 原因：此 write 操作标记了新的 inode 已被分配，并更新了 inode 的类型信息。

1. 第二个 write 33: 更新 inode 的元数据

• 对应的代码：iupdate(ip);
• 操作：更新该 inode 的其他元数据，如 nlink（链接计数）等字段，并将这些更改写入磁盘。
• 原因：此 write 操作确保新的 inode 的元数据已正确设置并存储在磁盘上。

1. 接下来的 write 46: 更新根目录的数据块，添加新目录项

• 对应的代码：dirlink(dp, name, ip->inum);

  • dirlink 函数中if(writei(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))

• 操作：将文件 x 的目录项写入根目录的第一个数据块（block 46）。这个目录项包含了文件名 x 和新分配的 inode 编号。

• 原因：此 write 操作更新了根目录的数据块，将新文件的目录项添加到根目录中。

  下面是 dirlink 函数]

  // 向目录 dp 中写入一个新的目录项 (name, inum)。
  // 如果成功返回 0，如果失败返回 -1（例如磁盘块不足）。
  int
  dirlink(struct inode *dp, char *name, uint inum)
  {
  int off;
  struct dirent de;
  struct inode *ip;
  
  // 检查目录中是否已经存在相同的文件名
  if((ip = dirlookup(dp, name, 0)) != 0){
   // 如果已经存在，释放 inode 并返回错误
   iput(ip);
   return -1;
  }
  
  // 查找目录中的空目录项（即 inum == 0 的目录项）
  for(off = 0; off < dp->size; off += sizeof(de)){
   // 读取目录中的一个目录项
   if(readi(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
     panic("dirlink read");  // 如果读取失败，触发 panic
  
   // 找到空的目录项
   if(de.inum == 0)
     break;
  }
  
  // 将新的文件名复制到目录项中
  strncpy(de.name, name, DIRSIZ);
  // 将新的 inode 编号存储到目录项中
  de.inum = inum;
  
  // 将修改后的目录项写回到目录 dp 中
  if(writei(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
   return -1;  // 如果写入失败，返回错误
  
  return 0;  // 成功返回 0
  }
  

  1. dirlookup(dp, name, 0):
     • 该函数检查目录 dp 中是否已经存在名为 name 的目录项。如果存在，返回相应的 inode。
     • 如果文件名已经存在，dirlink 会释放该 inode 并返回 -1，表示不能创建重复的目录项。
  2. 查找空目录项:
     • for(off = 0; off < dp->size; off += sizeof(de)):
       • 该循环遍历目录 dp 中的所有目录项，查找一个空的目录项位置（即 inum == 0 的位置）。
     • readi(dp, 0, (uint64)&de, off, sizeof(de)):
       • readi 函数从目录 dp 的数据块中读取一个目录项到 de 结构中。
     • if(de.inum == 0):
       • 当发现一个空的目录项（即 inum 为 0）时，循环终止。
  3. 创建新的目录项:
     • strncpy(de.name, name, DIRSIZ):
       • 将文件名 name 复制到目录项 de 的 name 字段中。
     • de.inum = inum:
       • 将文件的 inode 编号 inum 存储到目录项 de 的 inum 字段中。
  4. 写入目录项到目录中:
     • writei(dp, 0, (uint64)&de, off, sizeof(de)):
       • 使用 writei 函数将修改后的目录项写回到目录 dp 的数据块中。如果写入失败，返回 -1。
  5. 成功返回:
     • 如果 dirlink 成功完成所有操作，返回 0，表示目录项已成功添加到目录中。

  目录 inode 的更新

  dirlink 函数的作用是将新的目录项（文件名和 inode 编号的映射）写入目录 dp。在执行 writei(dp, ...) 操作时，如果目录的数据块发生变化，相关的元数据（如 size 字段）也会随之更新。然后，在 iunlockput(dp) 被调用时，inode 的这些元数据更新会被写入磁盘，确保文件系统的一致性。

1. 写入 Block 32：更新根目录的 inode

• 对应的代码：iunlockput(dp); 中的 iupdate(dp); 的间接调用

• 代码位置：iunlockput 函数

void
iunlockput(struct inode *ip)
{
  iunlock(ip);
  iput(ip);
}

• 操作：iunlockput(dp); 函数在释放根目录的 inode 锁时，间接调用了 iupdate(dp);，这会将更新后的 inode（包括 size 字段的变化）写入磁盘，更新 Block 32。

  // 如果文件不存在，分配一个新的 inode
  ip = ialloc(dp->dev, type);   // 第一个 `write 33`
  ilock(ip);
  ip->major = major;
  ip->minor = minor;
  ip->nlink = 1;
  iupdate(ip);  // 更新 inode 到磁盘，第二个 `write 33`

  // 为新文件在目录中添加一个目录项
  if(dirlink(dp, name, ip->inum) < 0)   // `write 46`
    goto fail;

  iunlockput(dp);  // `write 32`
  return ip;

并发创建文件时的关键问题

在多核系统中，多个进程可能会同时调用 create 函数以创建新文件。为了防止并发操作导致的数据不一致和竞态条件，XV6 文件系统使用了一系列锁机制来确保数据的一致性。下面我们详细分析一下这些锁机制是如何工作的，尤其是在 bread、bget 以及 brelse 函数中如何确保安全性。

假设有两个进程同时调用 create 函数来创建文件，它们都会执行以下操作：

1. 调用 ialloc 函数分配一个新的 inode。
2. ialloc 函数会读取 inode 所在的磁盘块，检查是否有空闲的 inode，然后更新并分配。

bread 函数：读取块数据

// Return a locked buf with the contents of the indicated block.
struct buf*
bread(uint dev, uint blockno)
{
  struct buf *b;

  b = bget(dev, blockno);  // 获取 block 的缓存，如果缓存中不存在，则创建一个新的缓存块
  if(!b->valid) {  // 如果缓存块无效，表示需要从磁盘中读取实际数据
    virtio_disk_rw(b, 0);  // 从磁盘读取数据到缓存块
    b->valid = 1;  // 标记缓存块为有效
  }
  return b;  // 返回锁定的缓存块
}

bread 函数首先调用 bget 来获取指定块的缓存。如果缓存中已经存在该块的数据，它将直接返回该缓存块；否则，它将从磁盘中读取块的数据。

bget 函数：获取或创建缓存块

// Look through buffer cache for block on device dev.
// If not found, allocate a buffer.
// In either case, return locked buffer.
static struct buf*
bget(uint dev, uint blockno)
{
  struct buf *b;

  acquire(&bcache.lock);  // 获取 bcache 的锁，确保只有一个进程能够操作缓存

  // 检查目标 block 是否已经缓存
  for(b = bcache.head.next; b != &bcache.head; b = b->next){
    if(b->dev == dev && b->blockno == blockno){
      b->refcnt++;  // 增加引用计数，表示该缓存块被使用
      release(&bcache.lock);  // 释放 bcache 的锁
      acquiresleep(&b->lock);  // 获取缓存块的 sleep lock
      return b;  // 返回锁定的缓存块
    }
  }

  // 如果缓存中没有找到 block，则需要创建一个新的缓存块，从链表尾部开始回收一个未使用的缓存块
  for(b = bcache.head.prev; b != &bcache.head; b = b->prev){
    if(b->refcnt == 0) {  // 找到一个未被使用的缓存块
      b->dev = dev;
      b->blockno = blockno;
      b->valid = 0;  // 标记缓存块无效，需要从磁盘读取数据
      b->refcnt = 1;  // 设置引用计数为 1，表示该缓存块被使用
      release(&bcache.lock);  // 释放 bcache 的锁
      acquiresleep(&b->lock);  // 获取缓存块的 sleep lock
      return b;  // 返回锁定的缓存块
    }
  }

  // 如果没有可用的缓存块，触发 panic
  panic("bget: no buffers");
}

• 锁机制：在访问或修改缓存块链表时，需要持有 bcache.lock。这是一种自旋锁，确保同一时刻只有一个进程可以操作缓存链表。
• 引用计数：当一个缓存块被找到并锁定时，会增加其引用计数 (refcnt)。这意味着缓存块正在被使用，并且不会被其他进程移除。
• 双重锁机制：首先获取 bcache.lock 来确保缓存的安全访问，然后获取 b 的 sleep lock 以确保缓存块的内容在操作时不被其他进程修改。
• for(b = bcache.head.prev; b != &bcache.head; b = b->prev)：
  • 这个循环从缓存链表的尾部（bcache.head.prev）开始遍历，逐步向前移动到链表头部。
  • 尾部的块是最久未被使用的块，因为在 brelse 函数中，最近释放的块会被移到链表头部。

并发访问时的情况

当两个进程同时调用 create 函数时，它们可能都会试图读取或修改同一个磁盘块（例如，block 33，包含 inode 的信息）。由于使用了上述锁机制，只有一个进程可以先获取到 bcache.lock 并检查缓存，然后增加 refcnt 并获取 sleep lock。此时，其他进程将被阻塞，直到当前进程释放 sleep lock。

这确保了即使多个进程尝试同时访问和修改同一个磁盘块，也只有一个进程可以进行修改，而其他进程会在其完成后才能继续。

brelse 函数：释放缓存块

// Release a locked buffer.
// Move to the head of the most-recently-used list.
void
brelse(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);  // 释放 block 缓存的 sleep lock

  acquire(&bcache.lock);  // 获取 bcache 的锁
  b->refcnt--;  // 引用计数减 1
  if (b->refcnt == 0) {  // 如果没有进程在使用这个缓存块
    // 将缓存块移动到最常用列表的头部
    b->next->prev = b->prev;
    b->prev->next = b->next;
    b->next = bcache.head.next;
    b->prev = &bcache.head;
    bcache.head.next->prev = b;
    bcache.head.next = b;
  }
  
  release(&bcache.lock);  // 释放 bcache 的锁
}

• 释放 sleep lock：释放当前缓存块的 sleep lock，使得其他等待该块的进程可以继续。
• 管理引用计数：如果引用计数为 0，表示没有进程在使用该块，它将被移动到最常用缓存列表的头部。

竞态条件的避免

• 防止缓存块的重复创建：通过 bcache.lock 确保一个磁盘块的缓存块只会被创建一次。即使多个进程几乎同时请求读取同一个块，也只有一个进程能够先创建并锁定缓存块。
• 保护缓存内容：通过 sleep lock 确保在缓存块内容的读取和修改过程中，不会有其他进程并发地修改同一块的内容。
• 缓存一致性：引用计数和 sleep lock 确保一个磁盘块在缓存中的唯一性，防止多个缓存块表示同一磁盘块的情况。

通过使用 bcache.lock 和 sleep lock 的双重锁机制，XV6 文件系统确保了多个进程可以安全并发地操作共享资源（如磁盘块和 inode），而不会引发数据不一致和竞态条件。这些机制对于确保文件系统的可靠性和数据完整性至关重要。

sleeplock 与 spinlock 的结合使用

在XV6文件系统中，sleeplock（睡眠锁）和spinlock（自旋锁）的结合使用，确保了多核系统中的数据一致性和系统性能。让我们详细分析这些机制及其实现，尤其是为何使用sleep lock来保护block cache，以及如何通过两层锁机制来确保系统的安全性和效率。

1. acquiresleep 函数：获取睡眠锁

void
acquiresleep(struct sleeplock *lk)
{
  acquire(&lk->lk);  // 获取与睡眠锁关联的spinlock
  while (lk->locked) {  // 如果睡眠锁已被持有，进入等待
    sleep(lk, &lk->lk);  // 进入睡眠状态，并将CPU调度给其他进程
  }
  lk->locked = 1;  // 标记睡眠锁为已锁定
  lk->pid = myproc()->pid;  // 记录当前持有锁的进程ID
  release(&lk->lk);  // 释放与睡眠锁关联的spinlock
}

// Long-term locks for processes
struct sleeplock {
  uint locked;       // Is the lock held?
  struct spinlock lk; // spinlock protecting this sleep lock
  
  // For debugging:
  char *name;        // Name of lock.
  int pid;           // Process holding lock
};

• 工作原理：
  • acquiresleep 首先获取一个关联的spinlock来保护locked标志位的访问。这样做可以避免多个进程同时操作locked标志位，从而造成竞态条件。
  • 如果锁已经被其他进程持有，调用进程会进入睡眠状态，放弃当前CPU的使用权，等待锁释放后再重新竞争锁。
  • sleeplock的一个显著优势是，在持有锁时不需要关闭中断，允许长时间持有锁，同时可以安全地进行I/O操作。

2. 为何使用 sleeplock 而非 spinlock？

• I/O操作的延迟：磁盘I/O操作可能需要较长时间。如果使用spinlock，CPU会在等待锁的过程中不停循环，浪费大量CPU资源。而sleeplock允许进程在等待期间进入睡眠状态，将CPU资源让给其他进程，显著提高系统的效率。

• 中断处理的灵活性：spinlock要求在持有锁的期间关闭中断，以避免中断处理程序打断正在持锁的进程。然而，对于一些长时间的操作（如磁盘I/O），这种策略会导致中断被抑制过久，影响系统响应时间。sleeplock避免了这个问题。

brelse 函数：释放块缓存

void
brelse(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);  // 释放块缓存的睡眠锁

  acquire(&bcache.lock);  // 获取buffer cache的全局锁
  b->refcnt--;  // 减少块缓存的引用计数
  if (b->refcnt == 0) {
    // 如果没有进程在使用该缓存块，将其移动到LRU链表的头部
    b->next->prev = b->prev;
    b->prev->next = b->next;
    b->next = bcache.head.next;
    b->prev = &bcache.head;
    bcache.head.next->prev = b;
    bcache.head.next = b;
  }
  
  release(&bcache.lock);  // 释放buffer cache的全局锁
}

brelse 的关键点：

• 释放 sleeplock：首先释放块缓存的sleeplock，以允许其他等待该块的进程继续操作。
• 引用计数和LRU策略：在释放buffer cache的全局锁之前，减少块缓存的引用计数。如果引用计数为零，表示该缓存块不再被任何进程使用，将其移动到LRU链表的头部。这样在下次需要回收缓存块时，最不常使用的块将会被优先替换。

LRU（Least Recently Used）策略

LRU 是一种常用的缓存替换策略，其基本思想是：最近最少使用的缓存块最有可能在未来较长时间内不会被访问，因此在需要回收缓存空间时，优先移除这些缓存块。

将引用计数为零的缓存块放到链表的头部

1. 标记为最近使用：
   • 在缓存链表中，链表头部的块表示最近被使用过的缓存块，链表尾部的块表示最久未被使用的缓存块。
   • 当一个缓存块的引用计数变为零时，它表示当前没有进程在使用这个缓存块。这时将它放在链表的头部，表示它是最近被访问过的。
2. 维持 LRU 策略：
   • 当一个缓存块被释放后，它的引用计数降为零，但这并不意味着它会立即被替换。相反，它被移到链表头部，表示它在不久前刚刚被使用过。
   • 在接下来的缓存替换过程中，系统会从链表的尾部开始查找未被使用的缓存块（即引用计数为零且位于链表尾部的块），这些块会被优先回收。
   • 这种机制确保了缓存块的回收顺序符合 LRU 策略——最近最少使用的块会最先被替换。
3. 减少未来的 I/O 操作：
   • 如果一个缓存块最近刚刚被使用过，那么根据时间局部性原理，它很可能在短时间内再次被访问。
   • 将它放在链表的头部，有助于在接下来的缓存访问中继续命中这个块，从而减少不必要的磁盘 I/O 操作，提升系统性能。

block cache 的重要特性

1. 每个块在内存中只有一份缓存：
   • 通过 bcache.lock 保护，确保在内存中每个磁盘块只有一份缓存。这样可以避免多个进程对同一个块的不同缓存副本进行操作，从而导致数据不一致。
2. sleep lock 允许持有锁的同时进行I/O操作：
   • sleep lock 的设计允许在进行I/O操作时持有锁，且无需关闭中断。这对于长时间的磁盘操作尤其重要。
3. LRU（Least Recently Used）缓存替换策略：
   • block cache 使用LRU策略来管理缓存块的回收。通过将最近使用的块移动到链表头部，系统可以优先保留那些可能会被再次访问的块，从而提高缓存命中率。
4. 双重锁机制：
   • bcache.lock 保护全局buffer cache的数据结构，防止多个进程同时修改缓存链表。
   • sleep lock 保护每个块缓存的具体内容，确保同一时间只有一个进程可以读写该块缓存的内容。

通过在block cache中使用sleep lock，XV6有效解决了多进程并发操作时可能出现的竞态条件和资源浪费问题。sleep lock允许在不关闭中断的情况下持有锁，特别适合处理可能需要较长时间的磁盘I/O操作。而通过结合使用spinlock，系统能够确保对共享资源的安全访问。LRU策略则进一步提升了缓存的利用效率，使得系统在高负载下仍能保持较高的性能和一致性。

提问：为什么在 brelse 函数中，先释放了 sleeplock，然后再对引用计数 refcnt 进行减一操作？

这是因为 refcnt 的变化仅仅反映了当前进程对该块缓存的兴趣。如果有其他进程正在等待锁，那么 refcnt 必然大于 1。释放 sleeplock 允许其他等待的进程获取锁，而 b->refcnt-- 只表明当前进程不再关心这个缓存块。如果有其他进程正在使用这个缓存块，那么 refcnt 不会降到 0，因此不会触发缓存块的回收操作。

总结

1. 文件系统的数据结构：
   • 文件系统是一个存储在磁盘上的数据结构。在本节课中，我们主要讨论了 XV6 文件系统的基本结构。这些结构相对简单，但为理解更复杂的文件系统打下了基础。
   • XV6 的文件系统数据结构包括 inode、数据块、目录项等。这些结构共同作用，支持文件的创建、读取、写入和删除操作。
2. Block Cache（块缓存）的实现：
   • Block Cache 是为了提升性能而设计的，因为直接从磁盘进行读写操作非常耗时，通常需要数百毫秒。
   • 通过使用缓存，系统可以避免重复从磁盘读取相同的数据块。当一个数据块被访问时，它会被存储在缓存中，以供后续访问使用。
   • 我们还讨论了 sleep lock 的使用，确保在处理 I/O 操作时系统能够有效地管理并发访问，而不会阻塞 CPU 资源。

下节课预告

Crash Safety（崩溃安全性）：

• 崩溃安全性是文件系统设计中的一个重要方面，涉及如何确保在系统崩溃后，文件系统的数据仍然保持一致性。
• 我们将深入探讨基于日志（log-based）的崩溃安全机制。下节课的重点将是通过日志记录的方式来保证文件系统在崩溃后的数据一致性。
• 在随后的课程中，我们还将研究 Linux 的 ext3 文件系统，它使用了一种更快的日志记录方法，进一步提高了系统的性能和可靠性。