HeZephyr's Blog

1 思维模型

要考虑文件系统，我们通常建议考虑它们的两个不同方面；如果您了解这两个方面，您可能就会了解文件系统的基本工作原理。

1 文件和目录

随着时间的推移，在存储虚拟化过程中形成了两个关键的抽象概念。第一个是文件。文件只是一个由字节组成的线性数组，每个字节都可以读写。每个文件都有某种底层名称，通常是某个数字；通常情况下，用户并不知道这个名称（我们将看到）。由于历史原因，文件的底层名称通常被称为其inode number（索引节点号）。

1 引言

当我们使用磁盘时，

• 有时我们希望它更快； I/O 操作速度很慢，因此可能成为整个系统的瓶颈。
• 有时我们希望它更大；越来越多的数据被放到网上，因此我们的磁盘变得越来越满。
• 有时我们希望它更加可靠；当磁盘发生故障时，如果我们的数据没有备份，所有有价值的数据都会消失。

所以关键问题是：我们怎样才能制作大型、快速、可靠的存储系统？有哪些关键技术？不同方法之间的权衡是什么？

几十年来，硬盘驱动器一直是计算机系统中持久数据存储的主要形式，文件系统技术的大部分发展都是基于它们的行为。因此，在构建管理磁盘的文件系统软件之前，有必要了解磁盘操作的细节。

关键问题

现代硬盘驱动器如何存储数据？接口是什么？数据实际上是如何布局和访问的？磁盘调度如何提高性能？

1 接口

让我们先来了解一下现代磁盘驱动器的接口。所有现代硬盘的基本接口都很简单。硬盘由大量扇区（512 字节块）组成，每个扇区都可读写。在有 n 个扇区的磁盘上，扇区的编号从 0 到 n - 1。因此，我们可以将磁盘视为一个扇区数组；0 至 n - 1 就是硬盘的地址空间。

1 系统架构

为了开始我们的讨论，让我们看一下典型系统的“经典”图。

该图显示了通过某种内存总线或互连连接到系统主内存的单个 CPU。一些设备通过通用 I/O 总线连接到系统，在许多现代系统中，该总线是 PCI（或其众多衍生产品之一）；显卡和其他一些更高性能的 I/O 设备可能会在这里找到。最后，更底层的是我们所说的一种或多种外围总线，例如 SCSI、SATA 或 USB。它们将慢速设备连接到系统，包括磁盘、鼠标和键盘。

到目前为止，我们在写并发性的时候，好像构建并发应用程序的唯一方法就是使用线程。就像生活中的许多事情一样，这并不完全正确。具体来说，基于图形用户界面的应用程序和某些类型的互联网服务器经常使用不同风格的并发编程。这种风格被称为基于事件的并发，已在一些现代系统中流行起来，包括 node.js 等服务器端框架，但其根源在于 C/UNIX 系统，我们将在下文讨论。

基于事件的并发解决了两个方面的问题。首先，在多线程应用程序中正确管理并发性是一项挑战；正如我们所讨论的，可能会出现锁丢失、死锁和其他令人讨厌的问题。其次，在多线程应用程序中，开发人员几乎无法控制特定时刻的调度；相反，程序员只需创建线程，然后寄希望于底层操作系统以合理的方式在可用 CPU 上调度这些线程。由于很难构建一个通用的调度程序，在所有情况下都能很好地处理所有工作负载，操作系统有时会以非最佳的方式调度工作。因此，我们的关键是：

1 存在哪些类型的并发bug？

第一个也是最明显的问题是：复杂的并发程序中会出现哪些类型的并发bug？这个问题一般来说很难回答，但幸运的是，其他一些人已经为我们完成了这项工作。具体来说，我们依赖于 Lu 等人的一项研究。它详细分析了许多流行的并发应用程序，以了解实践中出现的bug类型。

1 信号量：定义

信号量是一个具有整数值的对象，我们可以使用两个例程对其进行操作；在 POSIX 标准中，这些例程是 sem_wait() 和 sem_post()。因为信号量的初始值决定了它的行为，所以在调用任何其他例程与信号量交互之前，我们必须首先将其初始化为某个值，代码所下示。

到目前为止，我们已经开发了锁的概念，并了解了如何通过正确的硬件和操作系统支持组合来正确构建锁。不幸的是，锁并不是构建并发程序所需的唯一原语。

特别是，在很多情况下，线程希望在继续执行之前检查条件是否为真。例如，父线程可能希望在继续之前检查子线程是否已完成（这通常称为 join()）；这样的等待应该如何实现呢？我们来看下面这段代码。

在讨论锁之前，我们首先描述如何在一些常见的数据结构中使用锁。向数据结构添加锁以使其可由线程使用，从而使该结构成为线程安全的。如何加锁决定了数据结构的正确性和性能。因此，我们面临着关键挑战：当给定一个特定的数据结构时，我们应该如何向它添加锁，以使其正常工作？此外，我们如何添加锁以使数据结构产生高性能，使许多线程能够同时（即并发）访问该结构？

1 并发计数器

计数器是最简单的数据结构之一。它是一种常用的结构，具有简单的接口。下面代码中中定义了一个简单的非并发计数器。