Lecture 15 - Crash Recovery

崩溃安全性（Crash Safety）

本节中，我们讨论文件系统中的崩溃安全性（Crash Safety）。这个主题专注于解决特定类型的问题，即在发生崩溃或电力故障时，如何防止文件系统进入不一致或不正确的状态。这种不一致可能导致严重的问题，例如：

• 数据块重复使用：一个数据块可能会被错误地分配给两个不同的文件。
• inode 复用：一个 inode 可能会被错误地分配给两个文件。

为什么崩溃会导致文件系统不一致？

文件系统操作通常涉及多个步骤，尤其是复杂操作如文件创建、删除、或修改时。这些步骤可能包括：

1. 更新 inode：为新文件分配一个 inode 并记录文件的元数据。
2. 分配数据块：将数据块分配给文件，并在 inode 中记录这些块。
3. 更新目录结构：在目录中添加或移除与文件关联的目录项。

如果在这些步骤中的某个时刻发生崩溃（如电力故障或内核 panic），可能会出现以下问题：

• 部分写入：某些步骤已完成，但其他步骤尚未完成，导致文件系统处于部分更新的状态。这会导致数据块或 inode 处于不一致的状态。
• 元数据不一致：例如，数据块已被分配并写入，但 inode 尚未更新；或者目录项已经创建，但关联的 inode 尚未分配。

现实场景中的崩溃

考虑以下场景：

• 你在运行 make 指令编译代码，这个过程会频繁地与文件系统交互，创建临时文件、写入数据、删除文件等。
• 突然发生电力故障或系统崩溃，你的笔记本电脑电池耗尽，或者系统出现了内核 panic。

当你重启系统时，你期望文件系统仍然是可用的，数据没有丢失，且文件系统结构没有被破坏。然而，由于文件系统操作可能在多个步骤中间断（部分写入），文件系统可能进入一个不一致的状态。

我们关注的问题

在本节内容中，我们关注的主要问题是：如何确保在文件系统操作过程中，如果发生崩溃或电力故障，系统能够在重启后保持文件系统的一致性。

这与其他类型的问题（如硬件故障导致的数据丢失）不同。我们不讨论如何应对磁盘物理损坏或彻底的数据丢失（这些问题需要备份和恢复方案），而是讨论如何通过设计文件系统，使其能够在发生崩溃后保持一致性。

解决方案

接下来我们将讨论如何通过 logging（日志记录）技术来解决文件系统在发生崩溃或电力故障时的不一致性问题。Logging 技术最初来自于数据库领域，后来被广泛应用于文件系统中，用来确保数据一致性。我们将深入探讨 XV6 文件系统中的 logging 实现，并理解其基本原理、优缺点，以及如何在更复杂的系统中实现高性能的 logging。

Logging 的基本原理

Logging 是一种确保文件系统在发生崩溃后仍然保持一致性的方法。其核心思想是：在对文件系统进行修改之前，先将这些修改操作的步骤记录到一个日志中。如果系统在执行过程中发生崩溃，则可以通过重做或回滚这些日志记录，确保文件系统回到一致的状态。

为什么 Logging 重要？

文件系统操作通常涉及多个步骤。例如，在创建文件时，可能需要以下步骤：

1. 分配 inode：为新文件分配一个 inode，并在磁盘上将 inode 标记为已分配。
2. 更新目录数据块：将新文件的目录项添加到包含目录的数据块中。

如果在这些步骤之间发生崩溃，文件系统可能会变得不一致。例如，inode 已经被分配，但目录项尚未更新，此时系统崩溃可能导致以下问题：

• 数据丢失或损坏：崩溃后，重新启动系统时，文件系统可能尝试访问已经分配但未正确记录的 inode 或数据块，导致数据丢失或读取错误的数据。
• 文件系统崩溃：系统可能在访问这些不一致的结构时再次崩溃，导致进一步的损坏。

XV6 中的 Logging 实现

在 XV6 中，logging 的实现非常简单，主要为了演示核心思想。尽管如此，它仍然揭示了一些微妙的问题，这些问题也是文件系统设计中非常值得学习的内容。

Logging 的工作流程

1. 预写日志：在实际修改文件系统之前，首先将所有的修改步骤记录到日志中。这些日志记录包括需要修改的 inode、数据块等。
2. 写入日志：将日志写入磁盘，确保所有修改步骤都安全地存储在磁盘上。
3. 执行修改：一旦日志记录完成，开始执行文件系统的实际修改操作。
4. 提交日志：在所有修改操作成功完成后，将提交日志到磁盘，标记这些操作已完成。
5. 日志清理：清理已提交的日志记录，释放空间供未来的日志使用。

崩溃恢复

如果在修改操作中途发生崩溃，由于日志已经记录了所有的操作步骤，系统可以在重启时通过重新执行这些日志记录的操作（重做日志）来恢复文件系统的状态。这确保了即使在崩溃情况下，文件系统也能保持一致性。

Logging 的局限性

虽然 XV6 的 logging 实现展示了基本原理，但它也存在一些性能问题。例如，XV6 的 logging 实现并没有充分优化日志写入和提交的效率，导致在某些情况下性能不佳。为了解决这个问题，现代文件系统（如 Linux 的 ext3）采用了更复杂的 logging 技术，如事务性日志，以提高性能和可靠性。

另外，这是我们最后一节有关XV6的课程，在本节课结束后，我们将转向更高级的操作系统概念，通过阅读相关论文来深入理解现代操作系统的设计和实现。下节课，我们将学习 Linux ext3 文件系统中如何通过优化日志记录机制来提高文件系统的性能。

示例 crash 风险分析

下面通过示例分析文件系统操作中的崩溃或电力故障可能导致严重的不一致性问题。即使尝试调整写磁盘的顺序，也难以完全避免问题的发生。

上节课中创建文件时的操作系统与磁盘 block 的交互过程：

$ echo "hi">x
write: 33   allocate inode for x
write: 33   init inode x
write: 46   record x in / directory's data block
write: 32   update root inode
write: 33   update inode x

创建文件 x 时，涉及到多个写磁盘操作：

1. 分配 inode：write: 33，分配并标记一个 inode 为已使用。
2. 初始化 inode：write: 33，对 inode 进行初始化。
3. 更新目录数据块：write: 46，将文件 x 的 inode 编号写入到目录的 data block 中。
4. 更新根目录 inode：write: 32，更新根目录的 inode（如更新目录大小）。
5. 更新文件 inode：write: 33，再次更新文件 x 的 inode（如更新文件大小）。

情景一：假设在 write: 33 之后发生崩溃

在此假设下，崩溃发生在第二次 write: 33（初始化 inode）之后，但在更新目录数据块之前

$ echo "hi">x
write: 33   allocate inode for x
write: 33   init inode x
 // < --- crash here
write: 46   record x in / directory's data block
write: 32   update root inode
write: 33   update inode x

• 操作进度：我们已经分配了 inode 并标记它为已使用，但尚未将其记录到目录中。
• 崩溃后果：
  • 分配的 inode 丢失：
    • 在磁盘上，inode 已经被标记为分配状态，但它并未被添加到任何目录中，因为目录的数据块还没有更新。
    • 由于 inode 并未出现在任何目录中，系统重启后，用户无法通过正常的文件系统操作访问或删除这个 inode。这个 inode 会变成一个“丢失的 inode”。
  • 资源泄漏：
    • 这个未被引用的 inode 造成了系统资源的浪费，因为它已经被标记为已使用，但实际上没有任何有效的文件指向它。随着时间推移，越来越多的这种“丢失的 inode”会导致文件系统资源耗尽。
  • 不一致状态：
    • 文件系统存在着一块已分配的 inode，但它没有被任何文件引用。这使得文件系统处于一种不一致状态，因为从逻辑上看，这种状态是不应存在的。
  • 除了 inode 丢失，另一个潜在的严重问题是，如果这个崩溃发生得更早，系统可能在没有正确初始化 inode 的情况下，崩溃后重新启动，这可能导致系统尝试访问或操作一个未正确初始化的 inode。这会进一步导致数据损坏或系统崩溃。

情景二：调整写磁盘顺序后，在 write: 32 之后发生崩溃

尝试通过调整磁盘写入的顺序来避免 inode 丢失问题。具体做法是先更新目录内容，然后更新目录大小，最后才标记 inode 为已分配。乍一看，这似乎可以避免 inode 丢失的问题，因为目录中的条目会在 inode 被标记为已分配之前写入。但这种调整实际上引入了新的问题。

write: 46   更新目录内容
write: 32   更新目录的size字段
write: 33   标记为已被分配
...

如果在 write: 32 和 write: 33 之间发生崩溃：

write: 46   更新目录内容
write: 32   更新目录的size字段
 // < --- crash here
write: 33   标记为已被分配
...

在这种情况下，目录已经被更新并写入磁盘，指向了一个 inode（尽管此时 inode 并未被正式标记为已分配）。然而，由于崩溃发生在 inode 被标记之前，系统重启后会发生以下问题：

1. 目录中的无效条目：
   • 目录的数据块已经包含了新文件的 inode 编号，但这个 inode 实际上还没有被分配或者初始化。因此，系统重启后，如果尝试访问这个文件，系统会读取一个未被正确初始化的 inode。
2. inode 共享风险：
   • 由于 inode 尚未被正式标记为已分配，系统在重启后可能会将这个 inode 分配给另一个新创建的文件。因此，两个文件可能会意外地共享同一个 inode。
   • 如果这两个文件属于不同的用户，这会导致严重的安全问题，其中一个用户可能无意中获得对另一个用户数据的访问权限。
3. 文件系统不一致：
   • 系统处于一种不一致的状态：目录项指向了一个实际上未被分配或初始化的 inode，而这个 inode 可能会被重复分配给其他文件。

在这个例子中，尽管通过调整顺序可以避免某些特定问题（如 inode 丢失），但这并不能解决所有可能的故障情况。调整顺序只是将问题从一种形式转换为另一种形式，并未彻底解决数据一致性问题。

示例分析：向文件 x 写入 "hi" 的过程

--- write "hi" to file x
write: 45   set alloc bit in bitmap block
write: 595  write h to allocated data block
write: 595  write i to allocated data block
write: 33   (size update, bn0)

通过上节课的另一个例子，我们来进一步理解了文件系统在处理磁盘写入操作时的复杂性和脆弱性。尽管调整操作顺序可能在某些情况下减少特定类型的错误，但它并不能解决所有的问题。真正的问题在于，多个相关的写磁盘操作之间存在依赖关系，而这些操作需要以一种原子的方式执行，否则就会导致数据不一致、资源泄漏或安全漏洞。

步骤回顾

1. 分配数据块：
   • write: 45：设置 bitmap block 的分配位，表示 data block 595 已被分配。
2. 写入数据：
   • write: 595：将字符 "h" 写入已分配的 data block 595。
   • write: 595：将字符 "i" 写入 data block 595。
3. 更新 inode：
   • write: 33：更新文件 x 的 inode，记录其 size 字段以及指向的 data block 595。

情景一：在 write: 45 后崩溃

--- write "hi" to file x
write: 45   set alloc bit in bitmap block
 // < --- crash here
write: 595  write h to allocated data block
write: 595  write i to allocated data block
write: 33   (size update, bn0)

如果在 bitmap block 被更新之后、但在数据块 595 被写入和 inode 被更新之前发生崩溃：

• 结果：
  • Data block 595 被标记为已分配，但实际上并没有被写入任何有效数据，也没有被任何文件的 inode 引用。
  • 这将导致 data block 595 的泄漏，它变得无法访问且无法被重新使用。

情景二：调整顺序后在 write: 33 和 write: 45 之间崩溃

write: 33   (size update, bn0)
 // < --- crash here
write: 45   set alloc bit in bitmap block

假设我们调整了操作顺序，先更新 inode 再更新 bitmap，又发生write: 33 和 write: 45 之间的崩溃：

• 结果：
  • Inode 认为 data block 595 属于文件 x，但实际在磁盘上这个 data block 仍然标记为未分配。
  • 后续操作可能会将同一个 data block 595 分配给另一个文件，导致多个文件共享同一个数据块。
  • 这可能导致严重的安全问题，例如两个用户的文件意外共享同一个数据块，导致数据泄露。

文件系统一致性问题的复杂性

通过这两个情景可以看到，简单地调整磁盘写入的顺序并不能彻底解决文件系统的一致性问题：

1. 丢失的 inode：当 inode 已被分配但未写入目录时，如果发生崩溃，该 inode 会永久丢失，造成系统资源泄漏。
2. 未分配 inode 的文件记录：当目录记录已经写入但 inode 尚未分配时，如果发生崩溃，系统可能会读取到未初始化或被错误使用的 inode，导致文件系统的严重不一致性。

这些问题揭示了文件系统操作的复杂性，尤其是在涉及多个步骤时。即使是非常小的失误，也可能在崩溃时导致数据丢失或文件系统损坏。

真正的问题在于这些操作需要被原子地执行，即要么所有操作都成功完成，要么没有任何操作被应用到磁盘。这种原子性在顺序调整中无法实现，因此调整顺序不能彻底解决问题。

Logging 提供了一个系统化的方法来确保文件系统操作的原子性。通过记录所有操作步骤并在执行前将这些步骤写入日志，系统可以在崩溃后重启时使用这些日志来恢复文件系统，确保其一致性。

Logging 的解决方案

为了解决上述问题，Logging 提供了一个强大的解决方案：

1. 原子性操作：Logging 通过将文件系统的多个写操作组合为一个事务，确保要么所有操作都成功完成，要么系统能够在崩溃后回滚到事务开始之前的状态。
2. 恢复机制：如果系统在事务完成之前崩溃，日志记录允许系统在重启时重新执行未完成的操作，确保文件系统恢复到一致状态。
3. 顺序写入的安全性：通过在磁盘写入之前将所有操作记录到日志中，Logging 确保了即使崩溃发生在写入过程的任意时刻，文件系统都能通过回滚或重做日志中的操作来恢复。

通过将一系列相关的写操作记录在一个日志中，系统可以确保在崩溃发生后，可以通过重做日志中的操作来恢复文件系统的一致性：

1. 记录日志：在执行任何修改操作之前，首先将所有即将执行的操作记录到日志中。
2. 提交事务：只有在日志成功写入磁盘后，系统才会真正执行这些修改操作。
3. 崩溃恢复：如果在执行过程中发生崩溃，系统可以通过检查日志来恢复到一致的状态。

Logging

在这节课中我们讨论通过 logging 来解决文件系统崩溃后的数据一致性问题。Logging 是一种源自数据库的技术，它具有以下优点：

Logging 的优势

1. 确保系统调用的原子性：
   • Logging 确保文件系统的操作（如 create 或 write）要么完全执行成功，要么完全不执行。这种原子性避免了部分写操作导致的文件系统不一致问题。
2. 支持快速恢复（Fast Recovery）：
   • 在系统崩溃或重启后，logging 允许文件系统通过检查日志快速恢复到一致状态。相比传统的恢复方法（如文件系统检查工具 fsck），logging 仅需要处理日志中的内容，而不需要遍历整个文件系统的数据结构（如 inode 和数据块）。
3. 原则上可以实现高效：
   • 尽管在 XV6 中的实现可能不太高效，logging 技术在设计上能够实现非常高的性能，特别是在并发操作和崩溃恢复方面。

Logging 的基本工作原理

logging 的核心思想是将文件系统的修改操作记录到日志中，确保即使在崩溃后也能恢复一致性。这一过程可以分为以下几个步骤：

1. 日志写入（Log Write）

• 当需要更新文件系统的某个部分（如 bitmap block 或 inode block）时，不是直接写入这些数据块，而是先将这些更新操作记录到日志区域中。
• 比如，更新 bitmap block（block 45）的操作将被写入日志，而不是直接更新 block 45。本质上，所有的文件系统写操作都被重定向到日志中，而不是直接写入到文件系统的数据区域。

2. 提交操作（Commit Operation）

• 当一个文件系统操作（如创建文件或写入数据）结束时，日志中记录了所有的写操作。此时，系统会在日志中标记这些操作已经完成，并记录这些操作的数量。
• 这一步确保日志中记录的写操作是完整的，并且可以用于恢复。

3. 安装日志（Install Log）

• 在日志中记录了所有写操作后，系统会将这些操作从日志区域“回放”到实际的文件系统区域。
• 具体来说，日志中记录的第一个操作对应更新 block 45，那么系统就会将日志中的数据写入到实际的 block 45。接着是 block 33，依次类推，直到所有记录的操作都被应用到文件系统中。

4. 清除日志（Clean Log）

• 一旦所有的日志记录都被应用到文件系统中，日志区域就可以被清空，释放空间用于后续的操作。
• 清除日志的实际操作通常是将日志中的操作计数设置为 0，这样在下一次需要记录日志时，新的操作可以从日志的起始位置开始记录。

Logging 的工作流程

+--------------------------------------+
|          Write Operation             |
| (Modify Data in Block Cache & Log)   |
+--------------------------------------+
                   v
+--------------------------------------+
|          Log Write (to Disk)         |
| (Write Data Blocks to Log)           |
+--------------------------------------+
                   v
+--------------------------------------+
|            Commit Operation          |
| (Update Commit Record in Log Header) |
+--------------------------------------+
                   v
+--------------------------------------+
|            Install Log               |
| (Apply Log Data to Filesystem Blocks)|
+--------------------------------------+
                   v
+--------------------------------------+
|           Clean Log                  |
| (Clear Log for Future Operations)    |
+--------------------------------------+

1. Log Write：所有写操作都先写入日志，而不是直接写入目标 block。
2. Commit Operation：在日志中记录该操作已完成，并记录操作的数量。
3. Install Log：将日志中的数据写入实际的文件系统 block 中。
4. Clean Log：清空日志，准备好记录新的操作。

通过上述流程，logging 系统确保了文件系统操作的原子性和一致性，即使在系统崩溃的情况下，logging 也能通过重放日志来恢复文件系统。

为什么 logging 是有效的

通过使用 logging 机制，文件系统可以确保在发生崩溃后仍然保持数据的一致性和完整性。让我们更深入地理解为什么这种工作方式是有效的，并探讨在崩溃和重启过程中可能发生的情况。

1. 确保原子性

logging 的一个主要优势是它可以确保文件系统的操作是原子的。即：

• 要么操作完全成功：所有的更改都被正确写入文件系统。
• 要么操作完全失败：在崩溃后系统恢复时，这些更改不会部分存在。

2. 快速恢复

在系统重启时，文件系统只需检查日志中的 commit 记录值：

• 如果 commit 记录为 0：表示没有未完成的事务，无需采取任何恢复措施。
• 如果 commit 记录大于 0：表示有一个完整的事务已被记录在日志中，但可能尚未完全应用于文件系统。因此，系统会重新应用日志中的更改（即 reinstall log），以确保这些操作被正确应用。

确保数据一致性的原因

考虑以下几种可能的崩溃场景，来说明为什么 logging 能够保证数据的一致性：

情况 1：在日志写入（Log Write）和提交（Commit）之间发生崩溃

• 影响：在这段时间内，日志已经部分或全部写入，但没有执行 commit 操作。
• 恢复：重启时，系统会发现日志的 commit 记录为 0，因此不执行任何恢复操作。换句话说，这就像操作从未发生过一样。文件系统保持在崩溃前的状态。

情况 2：在提交（Commit）和日志安装（Install Log）之间发生崩溃

• 影响：日志已经完整地写入，并且 commit 操作已经完成，但日志内容尚未应用于文件系统的数据块。
• 恢复：重启时，系统会检查日志的 commit 记录，发现其大于 0，因此重新应用日志中的更改。这确保所有操作都正确应用，保证文件系统的一致性。

情况 3：在日志安装（Install Log）过程中发生崩溃

• 影响：日志内容正在被应用于文件系统的数据块中，但在完成之前系统崩溃了。
• 恢复：重启时，系统会重新应用日志中的所有更改，即使某些更改已经在上次崩溃前被应用。这是因为日志安装（Install Log）操作是幂等的，即无论执行多少次，最终效果都是一致的。

提问 1：关于 append 操作的安全性

append 操作本质上是在文件的末尾添加数据，这可以看作是文件系统中的一个操作。logging 机制可以扩展到 append 操作中，确保它的原子性。append 操作可以被分解为底层的 read/write 操作，logging 系统可以确保这些操作的原子性。

append 操作是指向文件的末尾添加数据的操作。与覆盖文件中已有内容的 write 操作不同，append 是在文件的末尾增加新数据，而不会影响文件中已经存在的数据。当你执行 append 操作时，新的数据会被追加到文件的现有内容之后。文件的大小会增加，以包含新追加的数据。常用于日志文件的记录、连续的数据写入等场景。例如，当一个程序生成日志时，每次都会将新日志条目追加到日志文件的末尾，而不会覆盖原有的日志内容。

提问 2：在 commit 操作时崩溃会发生什么？

在执行 commit 操作时，所有的写操作都已经被记录在日志中。commit 只会在所有日志记录都写入后进行。因此，commit 本身是一个相对简单的操作，通常涉及写入一个单一的日志头（header）块。

• 单块写入的原子性：文件系统通常假定单个块（sector）的写入是原子的，要么整个块被写入，要么不写入。如果 commit 操作成功写入日志头，系统在重启时会看到完整的日志并重新应用。如果 commit 失败，日志头不会更新，系统会认为此次事务未发生。

Logging 的基本结构

在 XV6 中，logging 结构分为两部分：内存中的日志结构 和 磁盘上的日志结构。我们来看一下这两部分的详细内容。

1. 磁盘上的日志结构

在磁盘上，日志区域由以下部分组成：

• Header Block（日志头块）：
  • 这个块包含了 commit record，其中有两个关键字段：
    • n：表示有效的日志块（log block）的数量。
    • block numbers：一个数组，记录了这些日志块对应的文件系统中的实际块编号。
  • 这个 header block 是用来指示哪些块在日志中已经被记录，并将在 install log 操作时写回到文件系统的主数据区域。
• Log Data Blocks（日志数据块）：
  • header block 之后是实际的日志数据块。这些块保存了文件系统中实际要被修改的块数据。这些数据在日志安装（install log）时将应用到文件系统的主数据区域。
  • 数据块按照它们在文件系统中的顺序存储，例如，bn0 对应日志中第一个数据块，bn1 对应第二个数据块，依此类推。

2. 内存中的日志结构

在内存中，文件系统维护了一份日志的副本，用于管理当前正在处理的文件系统操作。这些操作在提交（commit）之前仅存在于内存中。

• Header Block 的内存副本：

  • 在内存中有一份与磁盘上 header block 对应的副本，它包含与磁盘上相同的信息：有效日志块的数量 n 以及这些日志块对应的实际块编号数组。
  • 在文件系统操作过程中，所有要修改的块信息首先存储在内存中的日志结构中。
  • 内存中的 header block 用于跟踪文件系统当前的修改操作，这些操作在提交（commit）前存储在日志中。

  +------------------------------------+
  |        Disk Log Structure          |
  +------------------------------------+
  | +-------------------------------+  |
  | | Header Block                  |  |
  | |  - n = 2                      |  |
  | |  - Block Numbers: 33, 45, ... |  |
  | +-------------------------------+  |
  | +-------------------------------+  |
  | | Log Data Block 1 (for bn0)    |  |  <- Contains data for Block 33
  | +-------------------------------+  |
  | | Log Data Block 2 (for bn1)    |  |  <- Contains data for Block 45
  | +-------------------------------+  |
  | |   ...                         |  |
  | +-------------------------------+  |
  +------------------------------------+
    
  

• Block Cache：

  • 内存中的 Block Cache 保存了所有正在被修改的数据块。这些数据块首先被缓存并记录在内存中的日志结构中，然后再写入磁盘。

  +------------------------------------+
  |      In-Memory Log Structure       |
  +------------------------------------+
  | +-------------------------------+  |
  | | Header Block (In-Memory Copy) |  |
  | |  - n = 2                      |  |
  | |  - Block Numbers: 33, 45, ... |  |
  | +-------------------------------+  |
  | +-------------------------------+  |
  | | Block Cache for Block 33      |  |  <- Modified data for Block 33
  | +-------------------------------+  |
  | | Block Cache for Block 45      |  |  <- Modified data for Block 45
  | +-------------------------------+  |
  | |   ...                         |  | 
  | +-------------------------------+  |
  +------------------------------------+
  

Logging 的操作流程

当文件系统进行修改时，操作流程如下：

写入日志：

• 当文件系统需要修改数据时，这些数据首先被写入到 内存中的 Block Cache 和 内存中的日志结构。这意味着在提交（commit）之前，所有修改操作都仅存在于内存中。
• 一旦这些操作准备好被提交，它们会被写入 磁盘上的日志数据块，而不直接修改文件系统的数据块。

提交日志：

• 当所有修改操作都成功写入日志数据块后，文件系统会更新 日志头块（Header Block），写入 commit record，表明这些操作已被记录并提交。
• 这一过程遵循 write-ahead logging（WAL）规则，即必须在写入提交记录之前，确保所有日志数据块已成功写入磁盘。

安装日志：

• 在适当的时机，日志数据块中的内容会被应用到文件系统的主数据区域，执行 install log 操作。
• 当所有日志操作成功应用后，日志区域被清空（clean log），释放空间供未来的操作使用。

Logging 的优势

这种 logging 实现方式之所以有效，主要有以下几个原因：

1. 保证原子性：所有的修改操作要么完全成功，要么完全失败，确保文件系统的一致性。
2. 支持快速恢复：在崩溃后，只需要检查并重新应用日志中的操作，文件系统即可恢复到一致的状态。
3. 幂等性：日志的 install log 操作是幂等的，无论执行多少次，结果都不会改变。这保证了即使在日志安装过程中发生崩溃，文件系统仍然能够恢复。

XV6 中 Logging 和文件系统操作流程

下面通过代码分析如何在 XV6 文件系统中使用 Logging 机制来确保文件系统操作的原子性和一致性。

1. 事务的开始与结束

在 XV6 中，每个文件系统操作都被封装在一个事务（Transaction）中，以确保操作的原子性。一个典型的文件系统操作，如 sys_open，会以 begin_op 和 end_op 包围实际的操作过程。

begin_op();  // 开始事务
...
// 文件系统操作，修改数据结构
ip = create(path, T_FILE, 0, 0);
...
end_op();  // 结束事务，提交日志

• begin_op(): 表示事务的开始。系统会确保在事务完成之前，所有的写操作都不会永久写入到文件系统的主数据区域。
• end_op(): 表示事务的结束。所有在事务中进行的写操作将在 end_op 中通过日志提交（commit）机制原子性地写入磁盘。

2. ialloc 函数与 log_write 的关系

ialloc 函数负责分配一个新的 inode，并标记其已分配状态。不同于直接写入磁盘块，XV6 使用 log_write 来记录写操作。

struct inode* ialloc(uint dev, short type)
{
  ...
  bp = bread(dev, IBLOCK(inum, sb));  // 读取 inode block
  dip = (struct dinode*)bp->data + inum%IPB;
  if (dip->type == 0) {  // 发现一个空闲 inode
    memset(dip, 0, sizeof(*dip));  // 清空 inode
    dip->type = type;  // 标记为已分配
    log_write(bp);  // 记录写操作
    brelse(bp);  // 释放 buffer
    return iget(dev, inum);
  }
  ...
}

• log_write(bp): 代替 bwrite，它不直接写入磁盘，而是将写操作记录在日志中。
• log_write 的核心逻辑: 将修改后的块（如 inode block）加入到待提交的日志中，以确保在整个事务完成前不会实际更新磁盘上的数据。

3. log_write 函数分析

log_write 是处理文件系统写操作的重要函数。它确保所有的写操作在事务提交之前都被正确地记录在日志中，并在事务结束时通过日志提交机制进行统一处理。

void log_write(struct buf *b)
{
  acquire(&log.lock);  // 获取日志的锁

  // 检查日志是否已满或日志是否在事务之外
  if (log.lh.n >= LOGSIZE || log.lh.n >= log.size - 1)
    panic("too big a transaction");
  if (log.outstanding < 1)
    panic("log_write outside of trans");

  // 检查这个块是否已经在日志中记录
  for (int i = 0; i < log.lh.n; i++) {
    if (log.lh.block[i] == b->blockno)  // log absorption
      break;
  }

  // 如果块不在日志中，增加日志记录
  if (i == log.lh.n) {
    bpin(b);  // 固定 buffer，防止在事务提交前被释放
    log.lh.n++;  // 增加日志块数量
  }

  log.lh.block[i] = b->blockno;  // 记录日志块编号
  release(&log.lock);  // 释放日志的锁
}

• 日志吸收（Log Absorption）: 如果日志中已经记录了这个块的编号（blockno），那么这个块的写操作就不再重复记录，以减少冗余。
• 固定块（bpin(b)）: 确保在整个事务过程中，这个块不会从内存中被驱逐。

4. Logging 的重要性与事务管理

在 XV6 中，Logging 确保了多个写操作可以作为一个不可分割的事务处理。通过 log_write，所有的修改都首先记录在日志中，只有在整个事务成功结束后，日志中的数据才会被正式应用到文件系统的主数据区域。

这种机制有效防止了系统在执行到一半时崩溃所导致的数据不一致问题。即使在系统崩溃后，只要日志提交成功，文件系统可以通过重新应用日志中的记录恢复到一致的状态。

end_op中的流程

1. end_op 函数

end_op 函数是在每个文件系统调用结束时调用的，用于检查是否需要提交事务（即是否需要将所有累积的更改写入磁盘）。这个函数的工作原理如下：

void end_op(void)
{
  int do_commit = 0;

  acquire(&log.lock);             // 获取日志锁以保护共享数据
  log.outstanding -= 1;           // 减少当前活跃操作计数
  if(log.committing)              // 检查是否有正在提交的事务
    panic("log.committing");      // 如果是，则出错处理
  if(log.outstanding == 0){       // 如果没有其他操作在进行
    do_commit = 1;                // 标记需要提交
    log.committing = 1;           // 设置提交标志
  } else {
    wakeup(&log);                 // 唤醒可能等待日志空间的操作
  }
  release(&log.lock);             // 释放日志锁

  if(do_commit){                  // 如果需要提交
    commit();                     // 调用 commit 函数提交事务
    acquire(&log.lock);           // 再次获取日志锁
    log.committing = 0;           // 清除提交标志
    wakeup(&log);                 // 唤醒等待中的操作
    release(&log.lock);           // 释放日志锁
  }
}

• 活跃操作计数：log.outstanding 记录当前有多少文件系统操作正在进行中。end_op 会将其减 1，如果减到 0，表示所有操作都已完成，可以开始提交事务。
• 提交事务：如果没有其他操作在进行 (log.outstanding == 0)，end_op 将调用 commit 函数执行提交操作。

2. commit 函数

commit 函数负责将内存中的所有更改写入磁盘，并清除日志。它分为几个步骤：

static void commit()
{
  if (log.lh.n > 0) {              // 如果日志中有记录
    write_log();                   // 将缓存中的修改写入日志区域
    write_head();                  // 将日志头写入磁盘，表示提交
    install_trans(0);              // 将日志中的内容写入实际的文件系统位置
    log.lh.n = 0;                  // 重置日志块数量
    write_head();                  // 清除日志头
  }
}

• write_log：将内存中的日志数据写入磁盘的日志区域。这一步确保了日志中记录了所有需要修改的块。
• write_head：将日志头（包括日志块的数量等信息）写入磁盘。这一操作标志着事务的提交。
  • 在 commit 函数的 write_head 之前，系统还没有正式提交事务。如果系统在 write_head 之前崩溃，由于没有记录 commit 标志，重启后系统会认为这个事务从未发生。因此，系统在崩溃后可以安全地忽略这些未完成的操作，避免数据不一致。如果崩溃发生在 write_head 之后但 install_trans 之前，系统可以在重启时重新应用日志中的更改，确保数据完整性。这是通过 幂等性（重复应用同一操作不会改变结果）来保证的。
• install_trans：将日志中的数据写入实际的文件系统块，即将更改应用到文件系统中。

3. write_log 函数

write_log 函数负责将修改后的块从缓存（block cache）复制到日志区域，并将日志块写入磁盘。

static void write_log(void)
{
  int tail;

  for (tail = 0; tail < log.lh.n; tail++) {           // 遍历日志中记录的块
    struct buf *to = bread(log.dev, log.start+tail+1);  // 读取日志块
    struct buf *from = bread(log.dev, log.lh.block[tail]);  // 读取缓存中的块
    memmove(to->data, from->data, BSIZE);             // 将缓存数据拷贝到日志块
    bwrite(to);                                       // 将日志块写入磁盘
    brelse(from);                                     // 释放缓存块
    brelse(to);                                       // 释放日志块
  }
}

• 从缓存到日志：该函数从内存的缓存（block cache）中读取修改后的块数据，并将其复制到日志块中。
• 日志写入磁盘：日志块随后被写入磁盘的日志区域。

4. write_head 函数

write_head 函数是日志提交的关键点，在这个函数中，日志头信息被写入磁盘，从而将事务正式提交。

static void write_head(void)
{
  struct buf *buf = bread(log.dev, log.start);  // 读取日志头块
  struct logheader *hb = (struct logheader *) (buf->data);
  int i;
  
  hb->n = log.lh.n;  // 将内存中日志块的数量复制到日志头
  for (i = 0; i < log.lh.n; i++) {
    hb->block[i] = log.lh.block[i];  // 将日志块的实际块编号复制到日志头
  }
  
  bwrite(buf);  // 将日志头块写入磁盘（这是实际的提交点）
  brelse(buf);  // 释放缓存块
}

• 日志头块（Header Block）：这个块包含了日志的元数据，特别是日志中有效的块数（n）以及这些块对应的文件系统中的实际块编号。
• bwrite 是提交点：在 bwrite 之前，所有的更改仅记录在日志中，但还未正式应用到文件系统。在 bwrite 之后，事务就被认为已经提交，即使系统在 bwrite 之后崩溃，恢复程序也可以根据日志中的信息恢复事务。

5. install_trans 函数

install_trans 函数负责将日志中的数据写回到文件系统的实际位置，即将日志中的更改应用到文件系统。

static void install_trans(int recovering)
{
  int tail;

  for (tail = 0; tail < log.lh.n; tail++) {
    struct buf *lbuf = bread(log.dev, log.start+tail+1);  // 读取日志块
    struct buf *dbuf = bread(log.dev, log.lh.block[tail]);  // 读取目标文件系统块
    
    memmove(dbuf->data, lbuf->data, BSIZE);  // 将日志块的数据复制到目标块
    bwrite(dbuf);  // 将目标块写入磁盘
    
    if (recovering == 0)
      bunpin(dbuf);  // 解除块在缓存中的固定状态
    brelse(lbuf);  // 释放日志块缓存
    brelse(dbuf);  // 释放目标块缓存
  }
}

• 读取日志块：首先从日志区域读取日志块（lbuf），它包含了文件系统更改的数据。
• 写入目标块：然后读取目标文件系统块（dbuf），将日志块的数据复制到目标块，并将其写入磁盘。
• 清理操作：在完成写入后，解除块的固定状态（bunpin），并释放缓存块。

install_trans 函数的设计确保即使在日志安装过程中发生崩溃，系统也能够在恢复时重新执行日志安装操作。由于日志安装是幂等的，即使重复执行也不会影响最终结果，因而保证了文件系统的一致性。

在当前的 install_trans 实现中，目标块在写入之前会先被读取出来。这种设计虽然简单直观，但确实有优化空间。例如，可以直接将日志块的数据写入磁盘而不读取目标块，节省 I/O 操作。不过，当前实现的优先级是代码的简单性和易读性，而不是性能优化。

在 XV6 的启动过程中，文件系统的恢复流程至关重要，以确保在系统崩溃并重新启动后，文件系统能够恢复到一致的状态。下面是对 XV6 文件系统恢复流程的详细分析和解释。

1. initlog 函数

initlog 是在系统启动时调用的，用于初始化日志系统，并检查是否需要从日志中恢复文件系统状态。

void initlog(int dev, struct superblock *sb)
{
  if (sizeof(struct logheader) >= BSIZE)
    panic("initlog: too big logheader");

  initlock(&log.lock, "log");      // 初始化日志锁
  log.start = sb->logstart;        // 设置日志区域的起始位置
  log.size = sb->nlog;             // 设置日志区域的大小
  log.dev = dev;                   // 设置设备编号
  recover_from_log();              // 调用恢复函数
}

struct log {
  struct spinlock lock;
  int start;
  int size;
  int outstanding; // how many FS sys calls are executing.
  int committing;  // in commit(), please wait.
  int dev;
  struct logheader lh;
};
struct log log;

• 日志初始化：initlog 函数首先初始化日志锁，并从超级块（superblock）中读取日志区域的起始位置和大小。
• 恢复操作：在完成初始化后，initlog 调用了 recover_from_log 函数，负责检查并恢复文件系统的状态。

2. recover_from_log 函数

recover_from_log 函数是恢复文件系统的一部分，如果日志中有未完成的事务，它将完成这些事务并清除日志。

static void recover_from_log(void)
{
  read_head();             // 从磁盘读取日志头信息
  install_trans(1);        // 如果日志头中的 n > 0，将日志块应用到文件系统
  log.lh.n = 0;            // 将日志头中的 n 置为 0，清除日志
  write_head();            // 将更新后的日志头写回磁盘，清除日志记录
}

• 读取日志头：read_head 函数从磁盘中读取日志头块，检查是否有未完成的事务。
• 安装日志：install_trans(1) 函数将日志中的数据应用到文件系统块中。如果在前一次运行中事务已经提交但尚未完全应用，那么这一步将确保这些操作完成。
• 清除日志：恢复完成后，将日志头中的 n 置为 0 并写回磁盘，表示日志已清空，所有的更改都已应用到文件系统中。

3. 日志恢复机制

在系统启动时，recover_from_log 函数会被调用，确保在之前的运行中发生的所有事务都能被正确应用到文件系统中。即使在恢复的过程中系统再次崩溃，恢复机制依然能够在下一次启动时继续恢复，直到日志中的所有更改都被应用为止。

4. 关键点与常见问题

• 幂等性：install_trans 函数的设计确保了幂等性，即使在恢复过程中系统多次崩溃，重复应用日志中的操作也不会影响最终结果。每次启动时，只要日志中存在未完成的事务，install_trans 就会将日志中的数据再次应用到文件系统。

• 事务未完成的处理：如果进程在写入日志但尚未提交时崩溃，由于没有提交点（write_head），日志恢复时不会应用这些未完成的事务，文件系统的状态会恢复到事务开始之前的状态。这种设计保证了操作的原子性，即事务要么完全完成，要么完全不执行。

• 进程退出时的处理：在操作系统中，如果进程在文件系统调用中途崩溃或退出，内核仍会继续处理未完成的日志写入操作。最终的提交由内核控制，而不是由进程直接完成，因此，即使进程退出，只要内核仍在运行，日志中的更改仍然会被提交到文件系统。

在文件系统的日志机制中，如果在实际提交之前已经将一些数据写入到磁盘，但随后系统崩溃了，这些写入的数据被视为未提交的日志数据，不会对文件系统的最终状态产生影响。具体来说：

2. 崩溃前的写入

如果在 commit 之前已经将一些数据写入到磁盘，但系统在 commit 之前崩溃了，那么这些写入的数据会被视为未完成的事务。具体情况如下：

• 写入日志区域：如果写入的是日志区域的数据（例如，通过 log_write 函数写入的日志块），但尚未执行 write_head，这些日志数据不会被视为提交事务的一部分。系统重启时会发现日志头部没有 commit 记录，因此会忽略这些日志数据，就像它们从未发生过一样。

• 写入实际文件系统区域：如果出于某种原因，某些修改被直接写入到了文件系统的实际数据块中，而不是日志区域，这种情况会导致文件系统的不一致性。不过，在正确实现的日志机制中，这种情况不应发生，因为所有修改都应当先写入日志区域，并且仅在提交后（通过 install_trans）才应用到实际的文件系统块。

3. 未提交数据的影响

• 在 commit 之前的写入：这些写入操作即使已经落盘，因为还没有提交（即 write_head 还没有执行），这些数据不会被视为有效的文件系统更改。重启后，恢复机制会忽略它们，因此它们不会对文件系统的最终状态产生影响。

  当系统执行写操作时，修改首先记录在日志区域中。如果这些数据尚未提交（即 write_head 尚未写入），它们在崩溃后的恢复中将被忽略。

  这些数据在磁盘上确实占用了日志区域的一部分，但由于未提交，它们不会被应用到文件系统的实际数据区域。

  崩溃后的恢复过程

  • 恢复机制：在系统重启时，recover_from_log 函数会被调用，这个函数检查日志头（log header）中的提交记录。如果 log header 中的提交记录未完成（例如，n 为 0 或者 write_head 未执行），恢复机制会认为这些日志数据无效。
  • 清除未提交的日志数据：恢复机制将会通过将 log header 中的 n 值设置为 0，并将 log header 写回磁盘，从而清除这些未提交的日志数据。这一过程释放了日志区域的空间，使其可以用于后续的日志记录。
  • 日志清空（clean log）的过程是通过设置 log header 中的 n 为 0 来完成的。这表明日志区域中的数据已经无效，并且可以被新事务覆盖。这种机制确保了日志空间不会被未提交的日志数据长期占用，确保了日志区域的有效利用。

• 在 commit 之后的崩溃：如果崩溃发生在 commit 之后但在 install_trans 之前或者过程中，恢复机制会重新应用这些日志数据以完成事务操作。

4. 日志机制的安全保障

日志机制的一个重要保证就是幂等性，这意味着重复执行相同的操作不会改变最终结果。即使在 commit 之前发生崩溃，恢复机制会确保文件系统回到一致的状态。这是通过以下方式实现的：

• 在 commit 之前，任何日志写入都不会被视为文件系统的一部分。
• commit 之后，如果崩溃，恢复过程会再次执行日志应用操作，从而完成事务。

实际磁盘写入

通过在 bwrite 函数中添加 print 语句，你可以捕捉到每次实际的磁盘写入操作的具体情况。这与之前在 log_write 函数中的 print 不同，后者主要记录了文件系统操作的日志，而不是实际的磁盘写入。

通过在 bwrite 中加入 print 语句，可以监测到文件系统操作何时真正写入了磁盘。这反映了磁盘 I/O 的实际开销。很明显这里的记录要比log_write中记录的长的多。

$ echo hi > x
bwrite 3
bwrite 4
bwrite 5
bwrite 2
bwrite 33
bwrite 46
bwrite 32
bwrite 2
bwrite 3
bwrite 4
bwrite 5
bwrite 2
bwrite 45
bwrite 595
bwrite 33
bwrite 2
bwrite 3
bwrite 4
bwrite 2
bwrite 595
bwrite 33
bwrite 2

1. 日志写入 (Log Write)

• bwrite 3, 4, 5: 这些记录表明日志数据块 (Log Data Block) 被写入磁盘。Block 3, 4, 5 是日志区域的实际块，包含了对应于文件系统修改的日志数据。
• bwrite 2: 这是对日志头块 (Log Header Block) 的写入。Block 2 包含了日志头部信息，记录了日志数据块的数量和它们对应的文件系统块编号。这一步标志着日志提交 (commit) 的完成。

2. 日志安装 (Install Log)

• bwrite 33, 46, 32: 在日志提交之后，这些日志数据被安装到文件系统的主数据区域。Block 33, 46, 32 对应的文件系统块被实际更新。这一步将日志中的变更应用到文件系统的实际块中。

3. 日志清除 (Clean Log)

• bwrite 2: 再次写入日志头块，这次是将日志头中的 n 设置为 0，表示日志已被清空，准备好用于下一个事务的日志记录。这一操作完成后，日志区域被重置，可以开始记录新的操作。

4. 后续写入数据块

• bwrite 45, 595, 33: 这些记录表明后续的文件系统修改再次通过日志记录并被应用到文件系统。这些操作显示了日志机制对文件写入的完整性保护。

5. 性能分析与问题

从这次 bwrite 的输出可以看出，这里的记录要比log_write中记录的长的多，日志机制存在显著的性能开销，主要体现在数据块被多次写入磁盘。具体分析如下：

• 重复写入: 每个文件系统的修改首先写入日志，然后再写入文件系统实际位置。这意味着每个数据块在日志中和文件系统中都写了一次，导致磁盘 I/O 量翻倍。
• 性能瓶颈: 这种机制显著增加了磁盘写操作的次数，降低了文件系统的整体性能。这在处理大文件或频繁写入操作时尤为明显，因为数据块的两次写入加重了磁盘的负担。

6. 优化思考

• 减少写入次数: 在更复杂的日志系统中（如 Linux 的 ext3 文件系统），通过改进日志机制，如合并写入、异步写入和批量提交，可以显著减少重复写入的次数，从而提高系统的性能。
• 按需安装日志: 通过在合适的时间批量安装日志，而不是每次操作后立即安装日志，可以减少不必要的写操作。
• 延迟写入与缓存: 通过使用更高效的缓存机制，减少对磁盘的直接写入，并在确保数据安全的前提下，推迟不必要的写操作。

XV6 文件系统的复杂性和挑战

在介绍 XV6 文件系统的复杂性和挑战时，提到了三个主要的方面：缓存驱逐（cache eviction）、文件系统操作适配日志大小、以及 并发文件系统调用。

1. 缓存驱逐（Cache Eviction）

当文件系统在执行某个事务（transaction）时，如果需要更新某个 block（例如 block 45），而此时 buffer cache 已满且决定要驱逐这个 block，如果在事务完成之前将这个 block 写入到文件系统的主数据区域，这会破坏事务的原子性。这是因为事务还没有完全提交，如果此时系统崩溃，日志（log）中的操作未完成但 block 已被写入磁盘，导致文件系统进入不一致的状态。

为了解决这个问题，文件系统使用了块固定（Pinning Blocks）的机制，log_write 函数调用了 bpin 函数。在事务处理期间，调用 bpin 会增加缓存中块的引用计数。只要计数不为零，缓存管理系统就不会撤回该块，这样可以确保该块在事务结束前不会被写回到磁盘。当事务完成并且日志中的所有操作都已经被安全地写入日志区块之后，就可以安全地解除块的固定。此时，通过调用 bunpin 减少块的引用计数。如果引用计数降为零，该块就可以被安全地撤回。

2. 文件系统操作适配日志大小

在 XV6 中，日志区域的大小是有限的，总共有 30 个日志块。所有的文件系统操作都必须在这个大小限制内进行。如果某个文件系统操作尝试写入超过 30 个块的数据，那么部分数据必须直接写入文件系统主数据区域，但这会违背写前日志（write ahead logging）的规则。

为了确保日志大小限制不会被打破，XV6 中的文件系统操作在设计时考虑了这个限制。例如，创建文件的操作最多涉及写入 5 个块，远小于 30 块的限制。

为什么XV6的日志大小是30？

在XV6中，日志大小被设置为30块。这一选择是基于以下考虑：

• 日志大小适应性：教授检查了可能的文件系统操作，发现它们涉及的写操作数量都远小于30块。例如，创建一个文件通常只需要写5个块。为了确保日志能够处理所有的文件系统操作，将日志大小设置为30块。
• 大多数文件系统操作：大多数操作只会写入少量的块，因此30块的日志空间足够应对这些操作。通过设置这个大小，XV6可以有效地保证日志记录的效率，同时避免占用过多的磁盘空间。

处理超过日志大小限制的操作

在一些特殊情况下，例如写入一个大文件，写操作可能涉及大量的块。例如，写入1MB的数据需要写入大约1000个块，这显然超过了30块的日志大小限制。这时，XV6的文件系统如何处理？

为了应对这种情况，filewrite 函数采用了将大写操作分割成多个小写操作的方法。具体流程如下：

• 分块写入：filewrite 函数中，将大于日志容量限制的写操作分割成多个小的写操作，每次写入的块数控制在日志容量限制（即30块）之内。这样可以确保每个小操作都可以完整地记录在日志中，符合日志系统的要求。
• 事务处理：每个小写操作都是一个独立的事务（transaction）。通过调用 begin_op() 和 end_op()，每个小写操作在日志系统中作为一个完整的事务处理，保证文件系统的正确性。
• 缓存管理：在写入操作进行时，所有涉及的块都会被pin在缓存中，确保这些块在事务提交之前不会被驱逐。缓存的大小需要足够大，至少要大于日志的大小，以保证所有写入的块都可以被缓存。

以下是 filewrite 函数的相关代码段，它展示了如何将一个大的写入操作分割成多个小的写入操作：

int
filewrite(struct file *f, uint64 addr, int n)
{
    int r, ret = 0;
    if(f->writable == 0)
        return -1;

    if(f->type == FD_INODE){
        int max = ((MAXOPBLOCKS-1-1-2) / 2) * BSIZE;  // 最大写入块数限制
        int i = 0;
        while(i < n){
            int n1 = n - i;
            if(n1 > max)
                n1 = max;

            begin_op();  // 开始一个事务
            ilock(f->ip);
            if ((r = writei(f->ip, 1, addr + i, f->off, n1)) > 0)
                f->off += r;
            iunlock(f->ip);
            end_op();  // 结束一个事务

            if(r != n1){
                // writei函数发生错误
                break;
            }
            i += r;
        }
        ret = (i == n ? n : -1);
    } else {
        panic("filewrite");
    }

    return ret;
}

在这段代码中，如果写入的数据量超过了日志的容量限制，代码会将其分割为多个事务来执行。这种设计确保了即使是大的写操作，也能在符合日志大小限制的情况下正确完成。

3. 并发文件系统调用

在并发文件系统调用的场景下，为了确保文件系统的正确性和事务的原子性，XV6 采用了一些特殊的机制和策略。

日志空间的管理与并发事务

当多个文件系统操作（即事务）并发执行时，每个操作都会将自己的修改记录到日志中。如果不加以控制，多个并发事务可能会导致日志区域被迅速填满。如果在日志空间不足的情况下强行提交一个事务，会造成部分事务提交，从而破坏文件系统的完整性和原子性。这会违反我们之前提到的预写日志规则（Write-Ahead Logging, WAL）。

为了解决这个问题，XV6 中的 begin_op 函数在每次开始一个新的文件系统操作时都会检查当前有多少操作正在进行，并计算这些操作可能占用的日志空间。如果预期的日志空间不足以容纳新操作，系统会将该操作阻塞，直到现有的操作提交并释放日志空间。

顺序控制与 Group Commit

XV6 还必须确保日志中的事务按照提交的顺序执行。如果事务的提交顺序被打乱，可能会导致奇怪的行为。例如，用户可能会看到一部分文件系统操作在另外一些操作之前执行，尽管这些操作实际上是按顺序提交的。

为了避免这些情况，XV6 采取了以下策略：

1. 限制并发文件系统操作的数量：
   • 在 begin_op 函数中，系统会检查当前有多少文件系统操作正在进行。如果正在进行的操作数量过多，系统会阻止新的文件系统操作开始执行，直到当前的操作完成并提交（commit）日志。这通过让新的操作进入休眠状态（sleep）来实现，直到空间释放或者其他操作完成后再唤醒它们。
2. Group Commit：
   • 当日志中已经记录了多个事务时，系统不会单独提交每个事务，而是将所有正在进行的操作一起提交。这种方法被称为Group Commit，它确保了所有并发操作要么都成功提交，要么都不提交。这样可以避免部分提交的问题，并确保日志中事务的顺序与文件系统操作的顺序一致。
   • Group Commit 的优势在于：
     • 提高安全性：通过一次性提交多个事务，确保系统不会因为某个事务部分提交而进入不一致的状态。
     • 维护顺序：事务按照它们发生的顺序进行提交，防止日志中事务的顺序被打乱，这有助于保持系统的一致性。

begin_op 函数

begin_op 是在每个文件系统调用开始时调用的，用于管理日志空间和并发操作的数量。这个函数的核心任务是确保当前的文件系统操作有足够的日志空间，并且不会与正在进行的日志提交（commit）冲突。

void begin_op(void) {
    acquire(&log.lock);
    while(1) {
        if(log.committing) {
            sleep(&log, &log.lock);
        } else if(log.lh.n + (log.outstanding+1)*MAXOPBLOCKS > LOGSIZE) {
            sleep(&log, &log.lock);
        } else {
            log.outstanding += 1;
            release(&log.lock);
            break;
        }
    }
}

• 日志正在提交 (log.committing): 如果日志正在提交中，当前操作必须等待，避免在提交过程中修改日志。当前操作会进入 sleep 状态，直到日志提交完成。
• 日志空间检查: 如果当前操作可能导致日志空间不足（log.lh.n + (log.outstanding+1)*MAXOPBLOCKS > LOGSIZE），也必须等待。这里通过检查 log.lh.n（已使用的日志块数量）和 log.outstanding（正在执行的操作数量），确保日志空间足够。
• 增加并发操作计数: 如果日志空间足够，且日志没有正在提交，则增加 log.outstanding，表示一个新的操作正在执行。

end_op 函数

end_op 在每个文件系统调用结束时调用，用于处理日志提交和并发操作的管理。

void end_op(void) {
    int do_commit = 0;

    acquire(&log.lock);
    log.outstanding -= 1;
    if(log.committing)
        panic("log.committing");
    if(log.outstanding == 0) {
        do_commit = 1;
        log.committing = 1;
    } else {
        wakeup(&log);
    }
    release(&log.lock);

    if(do_commit) {
        commit();
        acquire(&log.lock);
        log.committing = 0;
        wakeup(&log);
        release(&log.lock);
    }
}

• 减少并发操作计数: 每次操作结束时，减少 log.outstanding 计数。
• 检查提交状态: 如果 log.outstanding 减少到 0，表示这是最后一个正在执行的操作，系统应执行 commit 来提交所有日志。如果当前已经有日志在提交中（log.committing），则触发 panic，因为这在设计上是不允许的。
• Group Commit: 当所有操作都结束时，通过设置 log.committing = 1，标记日志提交的开始，然后执行 commit 函数。

复杂性和挑战

即使在XV6这样一个简单的文件系统中，日志管理和并发操作控制仍然存在复杂性。特别是需要确保以下几点：

1. 日志空间的管理: 确保在并发操作中，不会出现日志空间耗尽的情况，这要求 begin_op 函数合理地管理并发操作的数量。

2. 原子性和一致性: 通过在 end_op 函数中使用 commit，保证每次文件系统调用的日志提交要么完全执行，要么完全不执行，确保系统的一致性。

3. Group Commit 的必要性: 为了确保操作的顺序和一致性，有时需要一次性提交多个操作，这就是 end_op 中的 Group Commit。

增加与减少的配对操作

• 每次 begin_op 调用：都会增加一次 log.outstanding。
• 每次 end_op 调用：都会减少一次 log.outstanding。

每个文件系统操作从 begin_op 开始，到 end_op 结束，因此 log.outstanding 增加和减少是成对出现的。这个计数器记录当前正在进行的操作数量。当所有正在进行的操作完成时，log.outstanding 会回到 0。

等待机制

• 在 begin_op 中的等待：当 log.outstanding 达到一定数量，或者日志正在提交时，begin_op 会让新的操作进入 sleep，等待当前操作完成并提交日志。这意味着在日志空间不足时，新的操作不会继续增加 log.outstanding。
• 在 end_op 中的检查：end_op 检查 log.outstanding，只有当它减少到 0 时，日志才会提交。这确保了所有操作都已经完成，日志可以安全提交。

确保操作不会无序进行

• 同步机制：通过锁和条件变量，确保操作按顺序进行。begin_op 会等待条件满足（如日志空间足够）再开始新的操作，而 end_op 会在所有操作完成时提交日志。这避免了任何不协调的增加和减少。

并发操作和 log.outstanding 的变化

尽管 begin_op 和 end_op 是成对出现的，但它们之间涉及到的操作并不是瞬时完成的，这就导致了“满了”或者“变为 0”的情况出现。

在 XV6 中，多个文件系统操作可以并发执行。每次执行 begin_op 时，log.outstanding 会增加，而这些操作并不会立即结束。每个操作的执行时间可能不同，这就导致在某一时刻，log.outstanding 是累积增加的。

• 比如说，在短时间内有多个操作都开始了（即多个 begin_op 调用），那么 log.outstanding 会不断增加，直到某个条件（如日志空间不足）触发这些操作暂停。

log.outstanding 达到上限

begin_op 会检查即将进行的操作是否会导致日志空间耗尽。如果预计会耗尽，begin_op 会让这个操作等待，直到一些操作完成（即 log.outstanding 减少）并释放出足够的日志空间。

• 当 log.outstanding 达到某个阈值时，新的操作会暂停，直到当前的某些操作完成，并触发 end_op，减少 log.outstanding。

log.outstanding 变为 0 的情况

当所有正在进行的操作都完成并调用了 end_op 时，log.outstanding 会减少到 0。这意味着目前没有文件系统操作正在进行，这时系统会决定是否提交日志。

• 如果 log.outstanding 变为 0，end_op 会触发日志的提交，因为没有任何未完成的操作，日志的提交是安全的。