OSTEP - notes

  《Operating Systems: Three Easy Pieces》笔记。

Part I：Virtualization（虚拟化）

一. CPU

• 只有少量的物理 CPU 可用，如何提供几乎有无数个 CPU 可用的假象？
• 虚拟化 CPU：让许多任务共享 CPU。
• 时分共享（time sharing) 技术：运行一个进程一段时间，然后运行另一个进程，如此轮换。
• 如何高效、可控地虚拟化 CPU ? 保持控制权的同时获得高性能。
• 低级机制（mechanism) 和 高级策略（policy)。
• 实现进程所需的低级机制和调度进程所需的高级策略。
• 上下文切换（context switch) 和 调度策略（scheduling policy)。

1.The Process (进程)

  进程 —— 操作系统为正在运行的程序提供的抽象：任何时刻都可以清点一个正在运行的程序在执行过程中访问或影响的系统的不同部分，从而概括一个进程。
  进程的机器状态（machine state): 进程可以访问的内存（地址空间，address space)，寄存器，I/O 信息，… 。

进程创建：

• OS 运行程序必须做的第一件事是将代码和所有静态数据（例如初始化变量）加载（load) 到内存中，（从磁盘）加载到进程的地址空间中。现代操作系统惰性执行该过程，即仅在程序执行期间需要加载的代码或数据片段，才会加载。
• OS 为程序的运行时栈（run-time stack) 分配内存并用参数初始化栈，提供给进程。例如，将 argc 和 argv 填入 main() 函数。
• OS 可能为程序的堆（heap) 分配一些内存（随着程序运行，可能会分配更多内存给进程）。
• OS 还将执行一些其他初始化任务，特别是 I/O 相关的任务。在 UNIX 系统中，默认情况下，每个进程都有三个打开的文件描述符（file descriptor) ，用于标准输入、输出和错误。
• 最后一项任务：启动程序，在入口处运行，即 main() 。通过跳转到 main() 例程，OS 将 CPU 的控制权转移到新创建的进程中，从而程序开始运行。

  进程状态：运行（running），就绪（ready)，阻塞（blocked）。

  上下文切换（context switch)：对于停止的进程，寄存器上下文将保存其寄存器的内容。当一个进程停止时，它的寄存器将被保存到 OS 这个应用程序里表示进程的数据结构（进程控制块，Process Control Block, PCB）中 的某个内存位置（寄存器上下文），通过恢复这些寄存器（将它们的值放回到实际的物理寄存器中），操作系统可以恢复该进程。

  进程可以处于的其他状态：

• 初始状态 —— 进程在创建时处于的状态；
• 最终状态 —— 已退出但尚未清理。

  数据结构：

• 进程列表（process list) —— 跟踪系统中正在运行的所有程序；
• 进程控制块 —— 谈论包含每个进程信息的 C 结构的一种方式。

2.进程 API

  创建并控制进程？
  fork() 系统调用。操作系统提供创建新进程的方法，新创建的进程（子进程）几乎与调用进程（父进程）完全一样，对 OS 来说，看起来有两个完全一样的程序在运行，都从 fork() 系统调用返回（子进程返回 0 ，父进程返回新创建子进程的进程描述符（process identifier, PID))。子进程不从 main() 函数开始运行，而是直接从 fork() 系统调用返回，就好像是它自己调用了 fork()。子进程拥有自己的地址空间（即自己的私有内存）、寄存器、程序计数器等，但并不是完全拷贝了父进程，比如 fork() 的返回值，依据这个差别编写代码处理两种不同的情况（子父进程的不同代码）。在单个 CPU 的系统上，CPU 调度程序决定了某个时刻哪个进程被执行。
  wait() 系统调用。父进程调用 wait() ，延迟自己的执行，直到子进程执行完毕，子进程结束时，wait() 才返回至父进程，返回值为子进程的 PID 。
  exec() 系统调用有很多变体，让子进程执行与父进程不同的程序。给定可执行程序的名称及需要的参数后，exec() 会从可执行程序中加载代码和静态数据，并用它覆写自己的代码段（以及静态数据），堆、栈及其他内存空间也会被重新初始化。然后操作系统就执行该程序，将参数通过 argv 传递给该进程。因此，它并未创建新进程，而是直接将当前运行的程序替换为不同的运行程序。对 exec() 的成功调用永远不会返回，因为当前程序已经被替换了，运行替换程序去了，还返回运行被替换程序是不行的。
  shell 也是一个用户程序，它首先显示一个提示符（prompt），然后等待用户输入。向它输入一个命令（一个可执行程序的名称及需要的参数），shell 在文件系统中找到这个可执行程序，调用 fork() 创建新进程，并调用 exec() 的某个变体来执行这个可执行程序，调用 wait() 等待该命令完成。子进程执行结束后，shell 从 wait() 返回并再次输出一个提示符，等待用户输入下一条命令。
  kill() 系统调用向进程发送信号（signal)，包括要求进程睡眠、终止或其他有用的指令。ps 命令查看当前在运行的进程，top 展示当前系统中进程消耗资源的情况。

3.虚拟化 CPU 的基本机制

  程序直接在 CPU 上运行，设置好硬件，以便限制进程可以执行的操作。

a. 受限直接执行（limited direct execution)

  直接执行 —— 直接在 CPU 上运行程序，目的：高效。
  受限 —— 采用受保护的控制权转移，目的：可控。
  硬件通过提供不同的执行模式来协助操作系统，即处理器模式：

• 用户模式（user mode）：应用程序不能完全访问硬件资源，用户模式下运行的代码会受到限制。
• 内核模式（kernel mode）：操作系统可以访问机器的全部资源，操作系统（或内核）以这种模式运行。

  系统调用：为了实现用户执行某种特权操作，操作系统提供了用户程序执行系统调用的能力，它允许内核小心地向用户程序暴露某些关键功能，例如访问文件系统、创建和销毁进程、分配内存等。

  执行系统调用的过程 —— 陷入（trap)内核和从陷阱返回（return-from-trap)：

• 程序执行特殊的陷阱（trap）指令，该指令同时跳入内核并将特权级别提升到内核模式。执行陷阱时，硬件小心确保存储足够的调用者寄存器，以便操作系统发出从陷阱返回指令时能够正确返回。在 x86 上，处理器会将程序计数器、标志和其他一些寄存器推送到每个进程的内核栈（kernel stack) 上。
• 进入内核，系统就可以执行任何需要的特权操作（如果允许），从而为调用进程执行所需的工作。
• 完成后，操作系统调用一个特殊的从陷阱返回（retuen-from-trap) 指令，返回到发起调用的用户程序中，同时将特权级别降低，回到用户模式。在 x86 上，从陷阱返回将从内核栈弹出陷入时保存的那些值，并恢复执行用户模式程序。

  类似 open() 这种看起来像过程调用的系统调用，隐藏在其内部的是著名的陷阱指令，库使用与内核一致的调用约定来将参数放在众所周知的位置（例如，栈或特定的寄存器中），将系统调用号也放入，然后执行上述陷阱指令，库中陷阱之后的代码准备好返回值，并将控制权返回给发出系统调用的程序。因此，C 库中进行系统调用的部分是用汇编手工编码的，它们需要仔细遵循约定，正确处理参数和返回值，以及执行硬件特定的陷阱指令。
  内核必须小心谨慎地控制在陷阱上执行的代码。内核在启动时设置陷阱表（trap table)。操作系统通常通过某种特殊的指令（这也是种特权操作），通知硬件这些陷阱处理程序（陷阱）的位置，一旦硬件被通知，它就会记住这些处理程序的位置，直到下一次重新启动机器，并且硬件知道在发生系统调用和其他异常事件时要做什么（即跳转到哪段代码）。

LDE 协议的两个阶段：

• 在系统引导时，内核初始化陷阱表，CPU 记住位置以供随后使用。
• 在运行进程时，内核设置了一些内容（例如，分配进程节点的内存），之后进程从陷阱返回指令开始执行，CPU 切换到用户模式并开始运行进程。当进程希望发出系统调用时，它会重新陷入操作系统，然后再次通过从陷阱返回，将控制权还给进程。

b. 在进程之间切换

  直接执行 ——> OS 如何实现进程之间的切换？ ——> 进程在 CPU 上运行，OS 没有运行 ——> OS 如何重获 CPU 的控制权？
  协作（cooperative）调度系统：OS 等待系统调用，或某种非法操作发生，从而重新获得 CPU 的控制权。
  非协作方式：时钟中断（timer interrupt)。时钟设备可以编程为每隔几毫秒产生一次中断。产生中断时，当前正在运行的进程停止，操作系统中预先配置的中断处理程序（interrupt handler）会运行，操作系统重新获得 CPU 的控制权，因此可以做它想做的事：停止当前进程，并启动另一个进程。硬件在发生中断时要为正在运行的程序保存足够的状态，以便随后 return-from-trap 指令能够正确恢复正在运行的程序，这一组操作与硬件在显式系统调用陷入内核时的行为非常相似。
  保存和恢复上下文：
  OS 获得控制权后（通过系统调用或时钟中断），决定是否切换进程由调度程序（scheduler）做出。当其决定切换后，OS 执行一些底层代码，即所谓的上下文切换（context switch）：硬件将当前正在执行进程的一些寄存器保存到其内核栈（为了之后的某次从陷阱返回后继续执行）中，跳到陷阱处理程序，并进入内核（切换到内核模式），OS 决定切换，调用 switch() 例程，该例程保存通用寄存器、程序计数器，以及当前正在运行的进程的内核栈指针（保存到进程结构），然后从要切换进程的进程结构中恢复寄存器、程序计数器，并切换内核栈，然后切换上下文，即通过改变栈指针来使用切换后进程的内核栈（而不是被中断进程的）。最后 OS 从陷阱返回，从内核栈恢复寄存器并开始运行，即继续执行另一个进程，而不是返回到之前运行的进程。通过切换栈，内核在进入切换代码调用时，是一个进程（被中断进程）的上下文，在返回时，是另一进程（切换后进程）的上下文，操作系统执行从陷阱返回指令时，切换后的进程变成了当前运行的进程，上下文切换完成。
  注意以上存在两种类型的寄存器保存/恢复，一是陷入内核时，运行进程的用户寄存器（user registers）由硬件隐式保存（到内核栈），恢复发生在从陷阱返回时，从内核栈恢复到用户寄存器；二是 OS 决定切换时，内核寄存器（kernel registers）被软件 OS 明确地保存，存储到该进程的进程结构的内存中，恢复发生在切换回来时，从进程结构恢复到内核寄存器。

c. 总结

  OS 首先（在启动时）设置陷阱处理程序并启动时钟中断，然后仅在受限模式下运行进程，为 CPU 提供 “宝宝防护“。OS 确信进程可以高效运行，只在执行特权操作（系统调用），或当它们独占 CPU 时间过长（时钟中断）并因此需要切换时，OS 才进行干预。

4. 虚拟化 CPU 的高级策略：调度

a. 调度策略的基本框架

• 工作负载假设 —— 进程假设。
• 调度指标：
  • 周转时间（turnaround time）：任务完成时间 - 任务到达时间。
  • 平均周转时间。
  • 响应时间（response time)：任务首次运行时间 - 任务到达时间。
• 调度算法：
  • FIFO（先进先出）/FCFS（先到先服务）：问题 》护航效应（convoy effect）：耗时较少的任务排在重量级任务之后。
  • SJF(最短任务优先)：一种非抢占式（non-preemptive）调度程序，所有工作同时到达假设下的最优调度算法。去掉假设，护航问题仍然存在。
  • STCF（最短完成时间优先）：向 SJF 添加抢占。工作随机到达，当新工作进入系统，调度程序抢占运行另一个工作，依据剩余时间来调度。平均周转时间最优，但在响应时间上并不是很好。
  • 轮转（Round-Robin,RR)：在一个时间片（time slice）/调度量子（scheduling quantum）内运行一个工作，然后切换到运行队列中的下一个任务，而非运行一个任务直到结束，反复执行至所有任务完成。时间片长度必须是时钟中断周期的倍数，越短，RR 在响应时间上表现越好，太短则上下文切换的成本将影响整体性能。时间片的长度应足够长，摊销上下文切换成本，且不会使系统响应不及时。但是，RR 在周转时间指标上表现不佳。

  任何公平（fair）的政策（如 RR）,在效率（周转时间指标）上表现不佳，这是固有的权衡，若要追求效率（运行较短的工作直到完成），则要以公平（响应时间）为代价。你不能既保留蛋糕，又吃它。SJF、STCF 优化周转时间，RR 优化响应时间。
  结合 I/O ，调度程序实现重叠（overlap），一个进程在等待另一个进程的 I/O 完成时使用 CPU。每个 CPU 突发（I/O 之间间隔的 CPU 使用）作为一项工作，调度程序确保“交互”的进程经常运行。

b. 多级反馈队列（Multi-level Feedback Queue, MLFQ）

  OS 通常不知道工作的运行时间，而这又是 SJF(STCF) 等算法必须的。RR 的周转时间体验很差。如何设计一个优化周转时间且又降低响应时间的调度程序？——> MLFQ：它有多级队列，并利用反馈信息决定某个工作的优先级，关注进程的一贯表现，然后区别对待。

规则：

• Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t).

• Rule 2: If Priority(A) = Priority(B), A & B run in round-robin fash- ion using the time slice (quantum length) of the given queue.

• Rule 3: When a job enters the system, it is placed at the highest priority (the topmost queue).

• Rule 4: Once a job uses up its time allotment at a given level (re- gardless of how many times it has given up the CPU), its priority is reduced (i.e., it moves down one queue).

• Rule 5: After some time period S, move all the jobs in the system to the topmost queue.

  MLFQ 不需要对工作的运行方式有先验知识，通过观察工作的运行来给出对应的优先级，对于短时间运行的交互性工作，获得类似于 SJF/STCF 的很好的全局性能，同时对于长时间运行的 CPU 密集型负载也可以公平地、不断地稳步向前。

二. 内存

• 基本抽象：地址空间
• 基本机制：地址转换
  • 基址加界限的动态重定位。
    • 基址/界限寄存器对
    • 分段（segmentation）
    • 空闲空间管理
  • 分页（paging）
    • 访问页表的大量额外内存访问 —— TLB 。
    • 页表很大造成的内存浪费 —— 更小的表。
      • 更大的页
      • 混合方法：分页和分段
      • 多级页表
• 超越物理内存（交换到磁盘）
  • 机制
  • 策略
• VAX/VMS 虚拟内存系统

1. 抽象：地址空间

a. 演变

• 早期系统，没有抽象，简单的线性内存。
• 多道程序系统时代，效率（efficiency）变得重要。
• 分时系统时代，交互性（interactivity)变得重要。
• 时分共享系统，保护（protection）成为重要问题。

b. 地址空间（address space）

  操作系统提供的一个易用的物理内存抽象，是运行的程序看到的系统中的内存。一个进程的地址空间包含运行的程序的所有内存状态：程序的代码（code, 指令），运行时栈（保存函数调用信息，分配空间给局部变量，传递参数和函数返回值），堆（heap）用于管理动态分配的、用户管理的内存，还有其他的东西（例如，静态初始化的变量）。程序代码位于地址空间的顶部，接着是堆，然后栈位于底部，堆在程序代码之下开始并向下增长，栈从底部向上增长，这种放置方法只是一种约定。地址空间是操作系统提供给运行程序的抽象，因此程序并不在物理地址的某个 0~16 KB 的连续内存中，而是加载在任意的物理地址。
  虚拟化内存 —— 操作系统在单一的物理内存上为多个运行的进程（所有进程共享内存）构建一个私有的、可能很大的地址空间的抽象。进程在地址 0（虚拟地址），执行加载操作时，操作系统在硬件的支持下，出于某种原因，必须确保不是加载到物理地址 0，而是物理地址 320KB (比如说，这是该进程载入内存的地址)。

c. 目标

• 透明（transparency)。对于程序而言，内存虚拟化是透明的，程序感知到的是拥有自己的私有物理内存。操作系统（和硬件）让不同的工作复用内存，实现这个假象。
• 效率。包括时间上和空间上。因此，不得不依靠硬件支持。
• 保护。进程、操作系统本身，隔离（isolation)。

  作为用户级程序的程序员看到的任何地址都是虚拟地址，只有操作系统通过精妙的虚拟化内存技术，知道这些指令和数据所在的物理内存的位置。

2. 内存操作 API

  运行 C 程序时分配的两种类型的内存：

• 栈内存/自动内存，申请和释放操作由编译器隐式管理。
• 堆内存，申请和释放操作由程序员显式管理。

  malloc() 和 free() 不是系统调用，而是库调用。它们管理虚拟地址空间内的空间，但是本身是建立在一些系统调用之上的，这些系统调用会进入操作系统，来请求更多内存或者将一些内容释放回系统。例如，内存分配库使用 brk 和 sbrk 等系统调用。

常见错误：

• 忘记分配内存（便使用）—— 段错误（segmentation fault）。
• 没有分配足够的内存 —— 缓冲区溢出（buffer overflow）。
• 忘记初始化分配的内存 —— 未初始化的读取（uninitialized read）。
• 忘记释放内存 —— 内存泄露（memory leak）。
• 在用完之前释放内存 —— 悬挂指针（dangling pointer）。
• 反复释放内存 —— 重复释放（double free）未定义。
• 错误调用 free() —— 无效释放（invalid free）。

存在两级内存管理：

• 由操作系统执行的内存管理，在进程运行时将内存交给进程，在进程退出时（或以其它方式结束）时将其收回。
• 在每个进程中。例如，堆内管理。

3. 机制：地址转换

  通用技术：基于硬件的地址转换（hardware-based address translation），简称为地址转换（address translation）：硬件介入到每次内存访问中（即指令获取、数据读取或写入），将指令中的虚拟地址（进程提供的）转换为数据实际存储的物理地址，即：将应用程序的内存引用重定位到内存中实际的位置。为了虚拟化内存（创造一种每个程序都拥有私有内存的假象），硬件提供底层机制提高效率，操作系统在关键位置介入，设置好硬件，以便完成正确的地址转换，同时操作系统管理内存（manage memory），记录被占用和空闲的内存位置（空闲列表），并明智而谨慎地介入，保持对内存的控制。

a. 基址加界限机制（base and bound）/ 动态重定位（dynamic relocation）

  使用基址加界限的动态重定位这种虚拟化方式实施地址转换这一特殊机制。地址转换扩展了受限直接执行（LMD）的概念，OS 控制进程的所有内存访问，确保访问在地址空间的界限内。

  每个 CPU 需要两个硬件寄存器：基址（base）寄存器和界限（bound）寄存器/限制（limit）寄存器。进程中使用的内存引用都是虚拟地址，硬件将虚拟地址加上基址寄存器中的内容，得到物理地址，再发给内存系统。界限（限制）寄存器确保这个地址在进程地址空间的范围内，即确保进程产生的所有地址都在进程地址的“界限”中，进程不能访问超过这个界限或者为负数的虚拟地址。这种硬件结构（电路）是芯片中的，负责地址转换的部分有时也统称为内存管理单元（Memory Management Unit, MMU）。

动态重定位的硬件支持：

动态重定位：操作系统的职责

  内部碎片：已经分配的内存单元内部有未使用的空间（即碎片），造成了浪费。比如，进程的地址空间若位于固定大小的连续物理区域，根据进程地址空间的结构，向下增长的堆和向上增长的栈之间大量的内存区域。

b. 分段

  在 MMU（硬件结构中） 中引入不止一个基址和界限寄存器对，而是给地址空间内的每个逻辑段（segment）一对。一个段只是地址空间里的一个连续定长的区域，在典型的地址空间里有三个逻辑不同的段：代码、栈和堆。OS 能够将不同的段放到不同的物理内存区域，从而避免地址空间中的未使用部分占用物理内存。因此，只有已用的内存才在物理内存中分配空间，巨大的地址空间都能被容纳，毕竟其中包含大量未使用的地址空间（稀疏地址空间，spare address spaces）。除了基址和界限外，硬件还需知道段的增长方向，需要一位区分段寄存器是否反向增长，例如栈段。为支持共享，添加一个保护位（protection bit）：标识程序是否能够读写该段，或执行其中的代码。标记只读的代码可以被多个进程共享，而不用担心破坏隔离。
  段错误（segmentation fault）/段异常（segmentation violation）：在支持（或不支持）分段的机器上发生了非法的内存访问。

段的两种区分（表示）方式：

• 显式方式：VAX/VMS 系统使用该技术，虚拟地址开头的几位（2位）用于标识不同的段，剩下的位（12位）表示段内偏移。偏移量与基址寄存器相加，硬件就得到了最终的物理地址。
• 隐式方式：通过地址的产生方式。程序计数器 》代码段；基于栈或基址指针 》 栈；其他 》 堆。

  引入段后地址转换的计算依然简单：物理地址 = 段的基址 + 段内偏移，段内偏移（地址在段中的相对位置） = 虚拟地址（地址在地址空间的虚拟位置） - 段的虚拟地址。
  粗粒度（coarse-grained）分段：将地址空间分成较大的、粗粒度的块（即代码、栈、堆）。细粒度（fine-grained)分段：将地址空间分为大量较小的段（代码段和数据段都能划分成许多不同的部分），需要进一步硬件支持：在内存中保存某种段表（segment table）。

  系统运行时，地址空间中的不同段被重定位到物理内存中。与整个地址空间只有一个基址/界限寄存器对的方式相比，栈和堆之间没有使用的区域就不需要再分配物理内存，大量节省了物理内存。每个进程都有独立的虚拟地址空间，OS 确保在进程运行前，各个段寄存器被正确的赋值，同时上下文切换时，各个段寄存器中的内容必须保存和恢复。

  OS 需要管理物理内存的空闲空间，外部碎片（external fragmentation）问题：物理内存中充满许多空闲空间的小洞，很难分配给新的段或扩大已有的段。解决方法：

• 紧凑（compact）物理内存，重新安排原有的段。成本高，存在段的拷贝，且是内存密集型，占用大量处理器时间。
• 空间列表管理算法，保留大的内存块用于分配。例如，最优匹配（best-fit）、最坏匹配（worst-fit）、首次匹配（first-fit)以及伙伴算法（buddy algorithm）。无论算法多么精妙，都无法完全消除外部碎片，好的算法只是试图减小它。

d. 空闲空间管理（free-space management）

  这是所有内存管理系统的一个基本方面，无论是 malloc 库（管理进程中堆的页），还是操作系统本身（管理进程的地址空间）。用户级的内存分配库（如 malloc() 和 free() ），或者操作系统用分段（segmentation）的方式实现虚拟内存，都会出现外部碎片（external fragmentation）的问题。因此讨论最基本的内存程序形式，如何管理？碎片最小化策略？时空开销？

假设：

• 聚焦于用户级内存分配库，即堆的内存分配库，就像 malloc() 和 free() 那样。
• 数据结构：空闲列表（free list），包含了管理内存区域中所有空闲块的引用。
• 主要关心：外部碎片。
• 分配到归还之间的内存固定无法重定位。
• 分配程序管理的区域连续且大小固定。

底层机制：

• 分割与合并。
  • 分割：请求的空间大小小于某块空闲块，分配程序分割该块，一块给用户，一块留在空闲列表。
  • 合并：分配程序在释放一块内存时合并可用空间，通过查看要归还的内存块的地址以及邻近的空闲空间块。确保大块空闲空间能提供给应用程序。
• 追踪已分配空间的大小。分配程序在头块（header）中（返回的内存块之前）保存额外信息。头块的大小固定，库很容易通过简单的指针运算得到头块的位置，然后再得到释放的空间大小（即头块大小加上区域长度）。free(void *ptr) 接口没有块大小的参数，实际释放的却是头块大小加上分配给用户的空间大小。
• 嵌入空闲列表。空闲空间列表也需要内存，列表分配新节点又需要分配内存，通过在空闲内存内部嵌入节点建立空闲列表。堆初始化从系统调用获得地址空间，空闲列表的第一个元素即是整个堆，堆获得的空间减去空闲列表的第一个元素节点的空间便是当前空闲列表这唯一一个节点代表的内存块的大小。随后，堆分配一块块内存，头块记录大小信息，当堆释放内存时，新的空闲列表节点产生，头块已经记录了大小信息，还要记录 next 指针，使得释放后的内存块加入空闲列表（作为头或尾），同时遍历列表，合并相邻块，块又变成了整体。
• 让堆增长。分配程序从很小的堆开始，当空间耗尽，进行系统调用，操作系统在执行 sbrk 系统调用时，会找到空闲的物理内存页，将它们映射到请求进程的地址空间中去，并返回新的堆的末尾地址。返回 NULL 也是一种体面的方式。

基本策略：分配程序应同时保证快速和碎片最小化。但任何特定的策略在某组不匹配的输入下都会变得非常差。

• 最优匹配（best-fit）
• 最坏匹配（worst-fit）
• 首次匹配（first-fit)
• 下次匹配 （next-fit）

改进内存分配的其他方式：

• 分离空闲列表（segregated list）：用一个独立的列表管理某个应用程序进程经常申请的一种（或几种）大小的内存空间的对象，其他大小的请求交给更通用的内存分配程序。例如，厚块分配程序（slab allocator）。

• 二分伙伴分配程序（binary buddy allocator）。

优化内存分配程序：

• 更先进的分配程序采用更复杂的数据结构来优化查找开销，牺牲简单性换取性能，例如平衡二叉树、伸展树和偏序树。
• 提升在现代操作系统的多核多线程上的表现。

3. 分页

a. 介绍

  分页（paging）不是将一个进程的地址空间分割成几个不同长度的逻辑块（即代码、堆、栈，例如分段），而是分割成固定大小的单元，每个单元称为一页，物理内存看作是定长槽块的阵列，叫做页帧（page frame）。每个页帧（PF）包含一个虚拟内存页（VP）。

  OS 为每个进程保存一个数据结构 —— 页表（page table），存储虚拟 —— 物理地址转换，从而让系统知道地址空间的每个页实际驻留在物理内存中的哪个位置。系统中的每个进程都有一个页表，其确切结构要么由硬件（旧系统）确定，要么由 OS（现代系统）更灵活地管理。页表存在于由操作系统管理的物理内存中，而非在 MMU 中利用任何特殊的片上硬件，毕竟它可以很大。

  地址转换：

• 虚拟页面号（virtual page number, VPN），通过虚拟页号检索页表，从而找到该虚拟地址所属的虚拟页所在的物理页面，即物理帧号（PFN）。

• 页内偏移量（offset）：该地址在页中的相对位置，即该物理页帧的哪个字节。

  转换：用 PFN 替换 VPN，偏移量保持不变。

  页表的组织：最简单的线性页表（linear page table），一个数组。OS 通过虚拟页号（VPN）检索该数组，并在索引处查找页表项（PTE），以便找到期望的物理帧号（PFN）。页表项（PTE）除了存储物理帧号（PFN）还有许多不同的位，例如：

• 有效位（valid bit）：指示特定地址转换是否有效。例如，代码和堆在地址空间的一端，栈在另一端，所有未使用的中间空间都将被标记为无效。
• 保护位（protection bit）：表明页是否可读、写入或执行。
• 存在位（present bit）：表示该页是在物理存储器还是在磁盘上（即它已被换出，swapped out）。
• 脏位（dirty bit）：表明页面被带入内存后是否被修改过。
• 参考位（reference bit）/访问位（accessed bit）:追踪页是否被访问，确定受欢迎的页（应该保留在内存中）。
• ……

一个 x86 的页表项（PTE）：一个存在位（P）、读/写位（R/W，确定是否允许写入该页面）、用户/超级用户位（U/S，确定用户模式进程是否可以访问该页面），（PWT、PCD、PAT、G）确定硬件缓存如何为这些页面工作，一个访问位（A）、一个脏位（D），最后是页帧号（PFN）本身。

分页的内存访问的过程：

• 硬件必须知道当前正在运行的进程的页表的位置 —— 一个页表基址寄存器（page-table base register）包含页表的起始位置的物理地址。

• 取指令：每个取指令产生两个内存引用：一个访问页表查找指令所在的物理框架，另一个访问指令本身将其提取到 CPU 进行处理。

• 执行指令：若指令中存在显式的内存引用，这首先会增加一个页表访问，通过页表（存在一次对页表的物理内存访问）将虚拟地址转换为正确的物理地址，然后是内存引用访问本身，获取所需的数据并将其放入相关的寄存器。

• 注意：对于每个内存引用（无论是取指令还是显示加载或存储），分页都需要执行一个额外的内存引用，以便首先从页表中获取地址转换所需的页表项（PTE）。

分页的优点：不会导致外部碎片，更加灵活、简单，支持稀疏虚拟地址空间（有效位在发挥作用）。

分页的缺点：

• 每次内存访问先要访问页表 —— 大量额外的内存访问 —— 解决办法：TLB 。
• 页表很大造成的内存浪费 —— 解决办法：使表更小。

b. 快速地址转换（TLB）

  为了加速地址转换，避免额外的内存访问，增加一个小的、芯片内的地址转换旁路缓冲存储器（translation-lookaside buffer, TLB），即频繁发生的虚拟到物理地址转换的硬件缓存（cache），即地址转换缓存（address- translation cache）。对于每次内存访问，硬件先检查 TLB ，看看其中是否有期望的转换映射，如果有就完成转换（很快），不用访问页表（其中有全部的转换映射）。

TLB 的基本算法（硬件管理的 TLB ）：

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True)   // TLB Hit
    if (CanAccess(TlbEntry.ProtectBits) == True)
        Offset   = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else
        RaiseException(PROTECTION_FAULT)
else                  // TLB Miss
    PTEAddr = PTBR + (VPN * sizeof(PTE))
    PTE = AccessMemory(PTEAddr)
    if (PTE.Valid == False)
        RaiseException(SEGMENTATION_FAULT)
    else if (CanAccess(PTE.ProtectBits) == False)
        RaiseException(PROTECTION_FAULT)
    else
        TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
        RetryInstruction()

  缓存是计算机系统中最基本的性能改进技术之一。硬件缓存背后的思想是利用指令和数据引用的局部性（locality）。通常有两种局部性：

• 时间局部性（temporal locality）：最近访问过的指令或数据可能很快会再次访问，例如循环中的变量和指令。
• 空间局部性（spatial locality）：当程序访问内存地址 x 时，可能很快会访问邻近的 x 的内存。例如，遍历某种数组。

  命中的次数除以总的访问次数，得到 TLB 的命中率（hit rate）。对页中地址的第一次访问才会导致未命中，使得 TLB 得益于空间局部性。短时间内对内存的再次引用，TLB 又得益于时间局部性。注意一个物理定律的限制：快速的缓存必须小，大的缓存注定慢。

处理 TLB 未命中：

  复杂指令集计算机（Complex-Instruction Set Computer, CISC）的硬件有复杂的指令集，硬件全权处理 TLB 未命中，硬件通过页表基址寄存器（page-table base register）得到页表在内存中的确切位置，如同上面的示例代码那样更新 TLB。x86 架构采用固定的多级页表，当前页表由 CR3 寄存器指出。
  更现代的体系结构 —— 精简指令集计算机（Reduced-Instruction Set Computer, RISC）有所谓的软件管理 TLB（software-managed TLB）。发生 TLB 未命中时，硬件系统会抛出一个异常，这会暂停当前的指令流，将特权级别提升至内核模式，跳转至陷阱处理程序（trap handler）。这个陷阱处理程序是操作系统的一段代码，用于处理 TLB 未命中。它查找页表中的转换映射，然后用特别的“特权”指令更新 TLB ，并从陷阱返回。注意，不同于服务于系统调用的从陷阱返回（陷阱返回继续执行陷入操作系统之后那条指令），在从 TLB 未命中的陷阱返回后，硬件必须从导致陷阱的指令继续执行，重试该指令，但这次会命中 TLB 。因此，根据陷阱或异常的原因，系统在陷入内核时必须保存不同的程序计数器，以便将来能够正确地继续执行。在运行 TLB 未命中处理代码时，操作系统还要格外小心避免引起 TLB 未命中的无限递归。通过在 TLB 中保留一些项，记录永久的地址转换或者将 TLB 未命中陷阱处理程序直接放到物理内存中（未映射过且不用经过地址转换）来解决这个问题。软件管理的方法，兼具灵活性和简单性。TLB 控制流算法（操作系统处理）：

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True)   // TLB Hit
    if (CanAccess(TlbEntry.ProtectBits) == True)
        Offset   = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else
        RaiseException(PROTECTION_FAULT)
else                  // TLB Miss
    RaiseException(TLB_MISS)

  补充：CISC 指令集倾向于拥有许多指令，每条指令比较强大。CISC 背后的思想是，指令应该是高级原语，这让汇编语言本身易于使用，代码更紧凑。RISC 背后的关键观点是，指令集实际上是编译器的最终目标，所有编译器实际上需要少量简单的原语，可以用于生成高性能的代码。RISC 倡导者们主张，尽可能从硬件中拿掉不必要的东西（尤其微代码），让剩下的东西简单、统一、快捷。像 Intel 这样的 CISC 芯片制造商采纳了许多 RISC 芯片的优点，这些创新，加上每个芯片中晶体管数量的增长，两种类型的处理器都可以跑得很快。

TLB 的内容和实际系统的 TLB 表项：

  硬件 TLB 有32项、64项或128项（容量，即包含多少个地址转换映射），并且是全相联的（fully associative）。一条地址映射可能存在于 TLB 中的任意位置，硬件会并行地查找 TLB，找到期望的地址转换。
  来自 MIPS R4000（一种现代系统，采用软件管理 TLB）的稍微简化的 MIPS TLB 项：

  MIPS R4000 支持 32 位的地址空间，页大小为 4KB。在典型的虚拟地址中，预期会看到 20 位的 VPN 和 12 位的偏移量（2^32 = 4 * 2^30, 4kb = 2^12 = 4 * 2^10, 2^32 / 4kb = 2^20）。但是，在 TLB 中只有 19 位的 VPN。事实上，用户地址占地址空间的一半（剩下的留给内核），所以只需要 19 位的 VPN。VPN 转换成最大 24 位的物理帧号（PFN），因此可以支持最多有 64 GB物理内存（2^24 个 4KB 内存页）的系统。全局位（G）指示这个页是不是所有进程全局共享的，若置为 1，8位的 ASID 就会被忽略。三个一致性位（Coherence, C）决定硬件如何缓存该页。有效位（valid)，告诉硬件该项的地址映射是否有效（注意，不同于页表中页表项的有效位，页表中的有效位意味着该页并没有被进程申请使用，正常运行的程序不应该访问该地址）。还有未展示出的页掩码（page mask）字段，用来支持不同的页大小。64 位中灰色部分的位未使用。
  MIPS 的 TLB 通常有32项或64项，OS 可以设置一个被监听的寄存器，告诉硬件需要为自己预留多少 TLB 项。MIPS 的 TLB 是软件管理的，系统提供了一些更新 TLB 的特权指令：

• TLBP，查找指定的转换映射是否在 TLB 中。
• TLBR，将 TLB 中的内容读取到指定寄存器中。
• TLBWI，替换指定的 TLB 项。
• TLBWR，随机替换一个 TLB 项。

上下文切换：

  TLB 中包含的虚拟到物理的地址映射只对当前进程有效。在发生进程切换时，硬件或操作系统（或二者）必须注意确保即将运行的进程不要误读了之前进程的地址映射。切换进程时如何管理 TLB 的内容，让 TLB 正确而高效地支持跨多进程的虚拟化？一种方法是清空（flush）TLB，把全部有效位置为0，确保将要运行的进程不会错误地使用前一个进程的虚拟到物理地址转换映射，本质上清空了 TLB，同时在上下文切换时，操作系统必须改变页表基址寄存器（PTBR）的值。这种方法如果操作系统频繁切换进程的话，开销会很高。为此，一些系统增加了硬件支持，实现跨上下文的 TLB 共享。比如，在 TLB 添加一个地址空间标识符（Address Space Identifier, ASID），可以将其看作是进程标识符（Process Identifuer, PID），但通常比 PID 位数少（PID 一般 32 位，，ASID 一般是 8 位）。有了 ASID ，TLB 可以同时缓存不同进程的地址空间映射，没有任何冲突。操作系统在上下文切换时，必须将某个特权寄存器设置为当前进程的 ASID，以便让硬件知道当前是哪个进程正在运行。

TLB 替换策略：

  缓存替换 —— 向 TLB 添加新项时，应该替换哪个旧项（回忆一下，快速的缓存必须小）？目标是减小 TLB 未命中率，从而改进性能。

• 替换最近最少使用的（least-recently-used, LRU）的项。
• 随机（random）策略，即随机选择一项换出去。

c. 分页：较小的表

• 使用更大的页。许多体系结构（例如 MIPS、SPARC、x86-64）现在都支持多种页大小。“聪明的”应用程序请求可以为地址空间的特定部分使用一个大型页（例如，大小为 4 MB），从而让这些应用程序可以将常用的（大型的）数据结构放入一个 TLB 项。这种类型的大页在数据库管理系统和其他高端商业应用程序中很常见。但是大内存页会导致每页内的浪费，即内部碎片问题。多种页大小的主要原因是为了减少 TLB 的压力（不会遭受太多 TLB 未命中之苦），而不是为了节省页表空间。

• 混合方法：分页和分段。分段的内存管理复杂且有外部碎片问题，分段通过寄存器减小了一些开销。分页存在内部碎片问题，内存管理相对简单，但有很大的页表存储开销。将页表和分段相结合：为每个逻辑分段提供一个页表，而不是进程的整个地址空间的单个页表。例如，进程可能有三个页表，地址空间的代码、堆和栈部分各有一个。在 MMU 中我们仍然有基址寄存器，保存该段的页表的物理地址，界限寄存器用于指示页表的结尾（即它有多少有效页）。硬件中，应该有三个基本/界限对，代码、堆和栈各一个。当进程运行时，每个段的基址寄存器都包含该段的线性页表的物理地址。因此，系统中的每个进程现在都有三个与其关联的页表。在上下文切换时，必须更改这些寄存器，已反映新运行进程的页表的位置。在 TLB 未命中时，硬件使用分段位（SN）来确定要用哪个基址和界限对，然后硬件将其中的物理地址与 VPN 结合起来，形成页表项（PTE）的地址：

SN           = (VirtualAddress & SEG_MASK) >> SN_SHIFT
VPN          = (VirtualAddress & VPN_MASK) >> VPN_SHIFT
AddressOfPTE = Base[SN] + (VPN * sizeof(PTE))

每个分段都有界限寄存器，保存段中最大有效页的值，超出段的界限寄存器的访问将产生一个异常，栈和堆之间未分配的页不再占用页表中的空间。混合方法汲取了优点，也还是有一些缺点，分段依旧不灵活，内部碎片（一个大而稀疏的堆）问题仍然存在，页表本身可以是任意大小的了（取决于段被分配的大小，是 PTE 的倍数），因此，在内存中管理页表空间又是个复杂问题。

• 多级页表（multi-level page table）：将页表分成页大小的单元，若整页的页表项（PTE）无效，就完全不分配该页的页表，使用名为页目录（page directory）的新结构追踪页表的页是否有效（以及如果有效，它在内存中的位置）。经典的线性页表即使地址空间的大部分中间区域无效，仍需要为这些区域分配页表空间。在简单的两级页表中，页目录为每页页表包含了一项。它由多个页目录项（Page Directory Entries, PDE）组成。PDE 至少拥有有效位（valid bit）和页帧号（PFN），类似于 PTE。如果 PDE 有效，该项指向的页表（通过 PFN）中至少有一页是有效，即在该 PDE 所指向的页中，至少有一个 PTE ，其有效位被设置为 1。如果 PDE 无效，则 PDE 其余部分无定义。

多级页表分配的页表空间与正在使用的地址空间内存量成比例，它紧凑且支持稀疏地址空间。同时，仔细构建使得页表的每个部分都可以整齐地放入一页中，从而更容易管理内存。页表页可以放在物理内存的任何地方，而不要求线性列表那样的连续物理内存。多级页表在 TLB 未命中时，需要从内存加载两次，才能从页表中获取正确的地址转换信息（一次用于页目录，另一次用于 PTE 本身。因此，多级页表是一个时间-空间折中（time-space trade-off），同时复杂性也增加了。

• 超过两级的多级页表。页的大小决定了多级页表的分配方式，在页表中，当页表项（PTE）太多导致页目录项（PDT)太多从而使得整个页目录无法整齐地放入一页中，即让多级页表的每一部分放入一页的目标失败了。为树再加一层，将页目录本身拆成多个页，然后在其上添加另一个页目录，指向页目录中的项。相当于将一级标题变为二级标题，再加个一级标题。

• 使用两级页表的地址转换过程：

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Loolup(VPN)
if(Success == True)     // TLB Hit
    if(CanAccess(TlbEntry.ProtectBits) == True)
        Offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else
        RaiseException(PROTECTION_FAULT);
else                    // TLB Miss
    // first, get page directory entry
    PDIndex = (VPN & PD_MASK) >> PD_SHIFT
    PDEAddr = PDBR + (PDIndex * sizeof(PDE))
    PDE = AccessMemory(PDEAddr)
    if(PDE.Valid == False)
        RaiseException(SEGMENTATION_FAULT)
    else
        // PDE is valid: now fetch PTE from page table
        PTIndex = (VPN & PT_MASK) >> PT_SHIFT
        PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))
        PTE  = AccessMemory(PTEAddr)
        if(PTE.Valid == False)
            RaiseException(SEGMENTATION_FAULT)
        else if(CanAccess(PTE.ProtectBits) == False)
            RaiseException(PROTECTION_FAULT)
        else
            TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
            RetryInstruction()

• 反向页表（inverted page table)。其中的项代表系统的每个物理页，而不是有许多页表（系统的每个进程一个）那样的方式，页表项表示我们哪个进程正在使用该页，以及该进程的哪个虚拟页映射到此物理页。通常在线性表的基础机构上建立散列表，以加速查找。

• 将页表交换到磁盘。页表仍然有可能太大而无法一次装入内存，一些系统将这样的页表放入内核虚拟内存（kernel virtual memory），从而允许系统在内存压力较大时，将这些页表中的一部分交换（swap）到磁盘。

3. 超越物理内存

a. 机制

• 如何利用大而慢的设备，透明地提供巨大虚拟地址空间的假象？
• 页表结构的额外信息 —— 存在位（present bit），告诉页是否在内存中。
• 如果不存在，操作系统的页错误处理程序（page-fault handler）运行以处理页错误，将需要的页从硬盘读取到内存，可能存在页的交换。
• 页交换策略。

  交换空间（swap space）：硬盘上一部分用于物理页的移入和移出的空间。操作系统能够以页大小为单位读取或者写入交换空间，为此，操作系统需要记住给定页的硬盘地址（disk address）。
  如果希望允许页交换到硬盘，必须添加更多的机制。当硬件在 PTE 中查找时，可能发现页不在物理内存中。硬件（或操作系统）判断是否在内存中的方法，是通过页表项中的一项新信息，即存在位（present bit）。如果存在位置为 0，则页不在内存中，而在硬盘上。访问不在物理内存中的页，这种行为通常被称为页错误（page fault）。当一个程序 “页错误” 时，意味着它正在访问的虚拟地址空间的一部分，被操作系统交换到了硬盘上。之所以称为 “错误”，是因为操作系统中的处理机制。当一些不同寻常的事情发生的时候，即硬件不知道如何处理的时候，硬件只是简单地把控制权交给操作系统（例如，触发异常），希望操作系统解决。“页错误处理程序（page-fault handler）”的代码会处理页错误。
  无论硬件还是软件管理的 TLB，都由操作系统负责处理页错误。在许多系统中，页表是存储交换位置信息最自然的地方。操作系统可以用 PTE 中的某些位来存储硬盘地址，这些位通常用来存储像页的 PFN 这样的数据。当操作系统收到页错误时，它会在 PTE 中查找地址，并将请求发送到硬盘，将页读取到内存中。当硬盘 I/O 完成时，操作系统会更新页表，将此页标记为存在，更新页表项（PTE）的 PFN 字段以记录新获取页的内存位置，并重试指令。下一次重新访问 TLB 还是未命中，然而这次因为页在内存中，因此会将页表中的地址更新到 TLB 中（也可以在处理页错误时更新 TLB 以避免此步骤）。最后再一次重试操作会成功。注意，一个进程进行 I/O (页错误) 时会执行另一个进程。
  物理内存往往是固定的，内存可能会满，操作系统选择哪些页被交换出或被替换出（replace）的过程，被称为页交换策略（page-replacement policy）。这些策略建立在以上描述的机制之上。
  粗略描述内存访问的完整流程：

• 硬件在地址转换过程中所做的工作：

// 页错误控制流算法（硬件）
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True)   // TLB Hit
    if (CanAccess(TlbEntry.ProtectBits) == True) 
        Offset = VirtualAddress & OFFSET_MASK 
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset 
        Register = AccessMemory(PhysAddr)
    else
        RaiseException(PROTECTION_FAULT)
else    // TLB Miss
    PTEAddr = PTBR + (VPN * sizeof(PTE))
    PTE = AccessMemory(PTEAddr)
    if (PTE.Valid == False)
        RaiseException(SEGMENTATION_FAULT)
    else
        if (CanAccess(PTE.ProtectBits) == False)
            RaiseException(PROTECTION_FAULT)
        else if (PTE.Present == True)
            // assuming hardware-managed TLB
            TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
            RetryInstruction()
        else if (PTE.Present == False)
            RaiseException(PAGE_FAULT)

• 操作系统在页错误时所做的工作：

// 页错误控制流算法（软件）
PFN = FindFreePhysicalPage()
if (PFN == -1)              // no free page found
    PFN = EvictPage()       // run replacement algorithm
DiskRead(PTE.DiskAddr, PFN) // sleep (waiting for I/O)
PTE.present = True          // update page table with present
PTE.PFN = PFN               // bit and translation (PFN)
RetryInstruction()          // retry instruction

  为了保证有少量的空闲内存，大多数操作系统会设置高水位线（High Watermark, HW）和低水位线（Low Watermark, LW），来帮助决定何时从内存中清除页。当操作系统发现有少于 LW 个页可用时，后台负责释放内存的线程（交换守护进程，swap daemon）会开始运行，直到有 HW 个可用的物理页。

b. 策略

  由于内存压力（memory pressure）迫使操作系统换出（paging out) 一些页，为常用的页腾出空间。而确定要踢出（evict）哪个页（或哪些页）封装在操作系统的替换策略（replacement policy）中。内存只包含系统中所有页的子集，因此，将其视为系统中虚拟内存页的缓存（cache），替换策略的目标是让缓存未命中（cache miss）最少。
  程序的平均内存访问时间（Average Memory Access Time, AMAT, 计算机架构师衡量硬件缓存的指标）：AMAT = (Phit * Tm) + (Pmiss * Td)。Tm 表示访问内存的成本，Td 表示访问磁盘的成本，Phit 表示在缓存中找到数据的概率（命中），Pmiss 表示在缓存中找不到数据的概率（未命中）。Pmiss + Phit = 1.0 。在现代系统中，磁盘访问的成本非常高，即使很小概率的未命中也会拉低正在运行的程序的总体 AMAT。因此，一个聪明的策略很重要，避免缓存未命中，程序以磁盘速度运行。

• 最优替换策略。替换内存中在最远将来才会被访问到的页，可以达到缓存未命中率最低。正如开发调度策略时，未来的访问是无法知道的，因而无法为通用操作系统实现最优策略。最优策略可以用于比较其他的策略有多接近“完美”。

• 简单策略：FIFO（先入先出）替换策略。页在进入系统时，简单地放入一个队列，当发生替换时，队列尾部的页（“先入”页）被踢出。FIFO 实现相当简单。但是 FIFO 根本无法确定页的重要性，明显不如最优策略。

• 随机替换策略。随机策略取决于当时的运气。

• 利用历史数据：LRU 。页替换策略可以使用的历史信息是频率（frequency）和访问的近期性（recency），同时基于局部性原则（principle of locality） ，用历史信息来确定哪些页面重要，从而在需要踢出页时将这些页保存在内存中。“最不经常使用”（Least-Frequently-Used, LFU）策略会替换最不经常使用的页。“最少最近使用”（Least-Recently-Used, LRU）策略替换最近最少使用的页面。与这些算法完全相反的：“最近经常使用策略”（Most-Frequently-Used, MFU）和“最近使用策略”（Most-Recently-Used, MRU）忽视了大多数程序都具有的局部性特点。

  在没有局部性的工作负载（workload）中，每个引用都是访问一个随机页。LRU、FIFO和随机策略都执行相同的操作，命中率完全由缓存的大小决定。最优策略的表现明显好于实际的策略。
  “80-20” 的负载场景中，80% 的引用时访问 20% 的页（“热门”页）。剩下的 20% 是对剩余的 80% 的页（“冷门”页）访问。随机和 FIFO 都能很好运行，但 LRU 更好，最优策略再次表现地更好。如果每次未命中的代价非常大（并不罕见），那么即使小幅度提高命中率（降低未命中率）也会对性能产生巨大的影响。如果未命中的代价不那么大，那么 LRU 带来的好处就不会那么重要。
  在“循环顺序”工作负载中，LRU 和 FIFO 出现最差情况。这些算法在循环顺序的工作负载下，踢出较旧的页，这些较旧的页要比因为决策决定保存在缓存中的页更早被访问。随机策略明显更好，不会出现特殊情况下奇怪的结果。最优策略依旧最优。

• 近似 LRU。这是许多现代系统的做法。实现完美的 LRU 代价昂贵，实现一个近似的 LRU 算法，并且依然能够获得预期的效果。
  • 系统的每个页都有一个使用位（use bit, 有时称为引用位，reference bit）,这些使用位存储在某个地方（例如，每个进程的页表中，或者只在某个数组中）。每当页被引用（即读或写）时，硬件将使用位设置为 1 。由操作系统负责清除该位。时钟算法（clock algorithm）：系统中的所有页都放在一个循环列表中，时钟指针（clock hand）开始时指向某个特定的页（哪个页不重要）。当必须进行页替换时，操作系统检查当前指向的页 P 的使用位是 1 还是 0 。如果是 1 意味着页面 P 最近被使用，因此不适合替换。然后，P 的使用位被设置为 0 ，时钟指针递增到下一页（P+1）。该算法一直持续到找到一个使用位为 0 的页，使用位为 0 意味着这个页最近没有被使用过（在最坏情况下，所有的页都已经被使用了，那么就将所有页的使用位都设置为 0）。时钟算法具有不重复扫描内存来寻找未使用页的特点。但这不是通过使用位来实现近似 LRU 的唯一方法。
  • 时钟算法的一个小修改是对内存中的页是否被修改的额外考虑。如果页已被修改（modified）并因此变脏（dirty），则踢出它就必须将它写回磁盘，这很昂贵。如果它没有被修改（因此是干净的，clean），踢出就没成本（再需要的时候，从磁盘交换区取即可）。物理帧可以简单地重用于其他目的而无需额外I/O。硬件包括一个修改位（modified bit, 又名脏位，dirty bit），每次写入页时都会设置此位，因此可以将其合并到页面替换算法中。
• 其他虚拟内存策略。页面替换不是虚拟内存子系统采用的唯一策略（尽管它可能是最重要的）。
  • 页选择（page selection）策略。决定何时将页载入内存。
  • 预取（prefetching）。对于大多数页，操作系统使用按需分页（demand paging），即操作系统在页被访问时将页载入内存中，“按需”即可。在合理的成功机会时，操作系统猜测一个页面即将被使用从而提前载入。
  • 聚集（clustering）写入/分组写入（grouping）。磁盘驱动器执行单次大的写操作，比许多小的写操作更有效，许多系统会在内存中收集一些待完成写入，并以一种（更高效）的写入方式将它们写入硬盘。
• 抖动（thrashing）：当内存被超额请求时（许多进程对其虚拟内存空间多次大范围地引用，因而需要更多的虚拟内存实际处于物理内存上，而非磁盘的交换区中），这组正在运行的进程的内存需求超过了可用物理内存（就是内存不够了），系统将不断地进行换页（所以就变慢变卡了，毕竟磁盘很慢）。
  • 准入控制（admission control），系统决定不运行部分进程，希望减少的进程工作集（它们活跃使用的页面）能放入内存。
  • “内存不足的杀手程序（out-of-memory killer）“。当内存超额请求时，运行这个守护进程，它选择一个内存密集型进程并杀死它，从而以不怎么委婉的方式减少内存。

  扫描抗性（scan resistance）算法类似 LRU ，但它试图阻止 LRU 的最坏情况行为（循环工作负载中的情况）。页替换算法的发展仍在继续。由于内存访问和磁盘访问时间的差异增加，这些算法的重要性降低了。分页到磁盘非常昂贵，因此频繁分页的成本太高，所以，过度分页的解决方案往往很简单：购买更多的内存。

4. VAX/VMS 虚拟内存系统

  数字设备公司（DEC）在 20 世纪 70 年代末推出了 VAX-11 小型机体系结构。该系统的操作系统被称为 VAX/VMS（或者简单的 VMS）。VMS 面临通用性的问题，即它将运行在各种机器上，包括非常便宜的 VAXen（VAX 的复数形式），以及同一架构系列中极高端和强大的机器。因此，操作系统必须具有一些机制和策略，适用于这一系列广泛的系统（并且运行良好），为广泛的应用程序和系统提供一般支持。尽管操作系统依靠硬件来构建高效的假象和抽象，但有时硬件设计人员并没有把所有事情都做好。在 VAX 硬件中，尽管存在这些硬件缺陷，VMS 操作系统也将构建一个有效的工作系统。

a. 内存管理硬件

  VAX-11 为每个进程提供一个 32 位的虚拟地址空间，分为 512（2^9）字节的页。因此，虚拟地址由 23 位 VPN 和 9 位偏移组成。VPN 的高两位用于区分页所在的段。因此，该系统是分页和分段的混合体。
  地址空间的下半部分为“进程空间”，对于每个进程都是唯一的。在进程空间的前半部分（称为 P0）中，有用户程序和一个向下增长的堆。在进程空间的后半部分（P1），有向上增长的栈。地址空间的上半部分称为系统空间（S），受保护的操作系统代码和数据驻留在此处，操作系统以这种方式跨进程共享。
  VAX 硬件中的页大小非常小（512字节）。因此，VMS 设计人员的首要目标之一是确保 VMS 不会用页表占满内存。将用户地址空间分成两部分，VAX-11 为每个进程的每个区域（P0和P1）提供了一个页表。因而堆和栈之间未使用的地址空间部分不需要页表空间。基址寄存器保存该段的页表的地址，界限寄存器保存其大小（即页表项的数量）。通过在内核虚拟内存中放置用户页表（对于P0和P1，因此每个进程两个），操作系统进一步降低了内存压力。因此，在分配或增长页表时，内核在段 S 中分配自己的虚拟内存空间。如果内存受到严重压力，内核可以将这些页表的页面交换到磁盘，从而使物理内存可以用于其他用途。将页表放入内核虚拟内存意味着地址转换更加复杂。例如，转换 P0 或 P1 中的虚拟地址，硬件必须首先尝试在其页表中查找该页的页表项（该进程的 P0 或 P1 页表）。硬件可能首先需要查阅系统页表（它存在于物理内存中），随着地址转换完成，硬件可以知道段页表的页的地址，然后最终知道所需内存访问的物理地址。VAX 的硬件管理的 TLB 会让所有这些工作更快，TLB 通常会绕过这种费力的查找。

b. 一个真实的地址空间

  使用一个空指针引用，进程生成了一个虚拟地址 0 。硬件试图在 TLB 中查找 VPN（也是0），遇到 TLB 未命中。查询页表，并且发现 VPN 0 的条目被标记为无效。因此，遇到无效的访问，控制权交与操作系统，这可能会终止进程（在 UNIX 系统上，会向进程发出一个信号，让它们对这样的错误做出反应。但是如果信号未被捕获，则会终止进程）。这也是空指针访问会导致段错误的原因。代码段永远不会从第 0 页开始。该页被标记为不可访问，以便为检测空指针（null-pointer）访问提供一些支持。因此，设计地址空间需要考虑的一个问题是对调试的支持，这正是无法访问的零页所提供的。

  内核虚拟地址空间（即其数据结构和代码）是每个用户进程地址空间的一部分。在上下文切换时，操作系统改变 P0 和 P1 寄存器以指向即将运行的进程的适当页表。但是，它不会更改 S 基址和界限寄存器，并因此将“相同的”内核结构映射到每个用户的地址空间。这种结构使得内核的运转更轻松，内核几乎就像应用程序库一样，尽管是受保护的。
  VAX 通过在页表的保护位中指定 CPU 访问特定页面所需的特权级别来实现页面的不同保护级别的目的。

c. 页替换

  VAX 中的页表项（PTE）包含以下位：一个有效位，一个保护字段（4位），一个修改（或脏位）位，为 OS 使用保留的字段（5位），最后的一个物理帧号码（PFN）将页面的位置存储在物理内存中。
  没有引用位。因此 VMS 替换算法必须在没有硬件支持的情况下确定活跃页（一种方法是使用保护位模拟引用位）。同时，一些程序占用大量内存使其他程序难以运行（毕竟不清楚哪个页属于哪个进程），大部分全局策略（例如，LRU）会受到这种内存的影响，不会在进程间公平分享内存。
  分段的 FIFO （segmented FIFO）替换策略。每个进程都有一个可以保存在内存中的最大页数，称为驻留集大小（Resident Set Size, RSS）。每个页都保存在进程的 FIFO 列表中。当一个进程超过其 RSS 时，“先入”的页被驱逐。FIFO 显然不需要硬件的任何支持，因此很容易实现。为了提高 FIFO 的性能，VMS 引入了两个二次机会列表（second-chance list），全局的干净页空闲列表和脏页列表，页在从内存中被踢出之前被放在其中。当进程 P 超过其 RSS 时，将从其 FIFO 中移除一个页。如果干净（未修改），则将其放在干净页列表的末尾。如果脏（已修改），则将其放在脏页列表的末尾。如果另一个进程 Q 需要一个空闲页，它会从全局干净列表中取出第一个空闲页。但是，如果原来的进程 P 在回收之前在该页上出现页错误（访问不在物理内存的页），则 P 会从空闲（或脏）列表中回收，从而避免昂贵的磁盘访问。这些全局的二次机会列表越大，分段的 FIFO 算法越接近 LRU。

d. 页聚集

  VMS 的小页面在交换过程中的硬盘 I/O 可能效率非常低。VMS 增加聚集（clustering）优化。通过聚集，VMS 将大批量的页从全局脏列表中分组到一起，并将它们一举写入磁盘（从而使它们变干净）。聚集用于大多数现代操作系统，因为可以在交换空间的任意位置放置页，所以操作系统对页分组，执行更少和更大的写入，从而提高性能。

e. 其他漂亮的虚拟内存技巧

  惰性使工作推迟，这在操作系统中是有益的。推迟工作减少当前操作的延迟，从而提高响应能力。同时，惰性有时完全避免完成这项工作。VMS 的两个现在成为标准的惰性（lazy）优化技巧：

• 按需置零（demand zeroing）。即当页添加到地址空间时，操作系统仅在页表中放入一个标记页不可访问的条目。在进程读取或写入页时，则会向操作系统发送陷阱，在处理陷阱时，操作系统注意到这是一个按需置零页（通常通过页表项中“保留的操作系统字段”部分标记的一些位）。此时，操作系统才完成寻找物理页的必要工作，将它置零并映射到进程的地址空间。如果进程从不访问该页，则所有这些工作都可以避免，从而体现按需置零的好处。
• 写时复制（copy-on-write, COW）。如果操作系统需要将一个页面从一个地址空间复制到另一个地址空间，不是实际复制它，二是将其映射到目标地址空间，并在两个地址空间中将其标记为只读。如果其中一个地址空间确实尝试写入页面，就会陷入操作系统。操作系统注意到这是一个 COW 页面，因此（惰性地）分配一个新页，填充数据，并将这个新页映射到错误处理的地址空间。该进程接着继续，现在有了该页的私人副本。任何类型的共享库都可以通过写时复制，映射到许多进程的地址空间中，从而节省宝贵的内存空间。在 UNIX 系统中，fork() 会创建调用者地址空间的精确副本，大部分地址空间会被随后的 exec() 调用立即覆盖，它用即将执行的程序覆盖调用进程的地址空间。写时复制避免了大量不必要的复制，从而保留了正确的语义，同时提高了性能。

Part II: Concurrency（并发）

一. 线程

1. 基本概念

  为单个运行进程提供的新抽象：线程（thread）。每个线程拥有自己的执行点（一个程序计数器，用于取指令和执行），因此多线程（multi-threaded）程序有多个执行点，每个线程类似于独立的进程，不过线程共享地址空间，从而能够访问相同的数据。线程有一个程序计数器（PC），每个线程有自己的一组用于计算的寄存器。因此，线程也存在类似于进程的上下文切换（context swithch），类似进程控制块（Process Control Block，PCB）保存进程状态，需要一个或多个线程控制块（Thread Control Block, TCB）保存每个线程的状态。不同于进程的上下文切换，线程的上下文切换，地址空间保持不变，即不需要切换当前使用的页表。
  单线程（single-threaded）进程的进程地址空间模型是简单的传统地址空间模型，只有一个栈，通常位于地址空间的底部。在多线程的进程中，每个线程独立运行，每个线程都有一个栈。因此，所有位于栈上的变量、参数、返回值和其他放在栈上的东西，被放置在称为线程本地（thread-local）存储的地方，即相关线程的栈。除了使用大量递归的程序，通常栈不会很大。

  线程创建后可能会立即运行（取决于调度程序），或者处于就绪状态，等待执行。调度程序决定在给定时刻运行哪个线程。线程创建类似于函数调用，但它是为被调用的例程创建一个新的执行线程，独立于调用者运行，可能在调用者返回之前运行，也可能在这之后晚得多。
  由于执行过程中会发生上下文切换，线程在访问共享数据时将产生相互作用，在临界区出现竞态条件，从而产生不确定的程序结果。关键并发术语：

• 临界区（critical section）是访问共享资源的一段代码，资源通常是一个变量或数据结构。
• 竞态条件（race condition）出现在多个执行线程大致同时进入临界区时，它们都试图更新共享的数据结构，导致了不希望的结果。
• 不确定性（indeterminate）程序由一个或多个竞态条件组成，程序的输出因运行而异，具体取决于哪些线程在何时运行。这导致结果是不确定的（deterministic），而我们通常期望计算机系统给出确定的结果。
• 为了避免这些问题，线程应该使用某种互斥（mutual exclusion）原语。保证只有一个线程进入临界区，从而避免出现竞态，并产生确定的程序输出。

  原子化（atomic）。解决以上问题的一种途径是拥有更强大的指令，单步就能完成要做的事，从而消除不合时宜的中断的可能性。硬件保证发生中断时，指令根本没有运行，或者运行完成，没有中间状态。将一系列动作原子化背后的想法可以简单用一个短语表达：“作为一个单元” 或 “全部或没有”。要么一切发生，要么都没发生，不会看到中间状态。将许多行为组合为单个原子动作称为事物（transaction），这是一个在数据库和事务处理世界中非常流行的概念。在探讨并发时，我们将使用同步原语，将指令的短序列变成原子性的执行块。硬件提供一些有用的指令，在这些指令上构建一个通用的集合，即所谓的同步原语（synchronization primitive）。通过使用这些硬件同步原语，加上操作系统的一些帮助，将能够构建多线程代码，以同步和受控的方式访问临界区，从而可靠地产生正确的结果，尽管有并发执行的挑战。
  操作系统是第一个并发程序，许多技术都是在操作系统内部使用的。后来，在多线程的进程中，应用程序员也必须考虑这些事情。从引入中断开始，OS 设计人员就不得不担心操作系统如何更新内部结构。不合时宜的中断会导致上述所有问题。页表、进程列表、文件系统结构以及几乎每个内核数据结构都必须小心访问，并使用正确的同步原语才能正常工作。

  线程之间的交互：

• 访问共享变量 ——> 为临界区支持原子性 ——> 研究如何构建对同步原语的支持来支持原子性 ——> 锁。
• 等待另一个线程 ——> 研究支持在多线程程序中常见的睡眠/唤醒交互的机制 ——> 条件变量。

2. 线程 API

a. 线程创建

#include <pthread.h>
      int
      pthread_create(pthread_t      *thread,
               const pthread_attr_t *attr,
                     void           *(*start_routine)(void*),
                     void           *arg);

• thread 是指向 pthread_t 结构类型的指针，该结构用于与线程交互，将它传入 pthread_create() 以便将它初始化。
• attr 用于指定该线程可能具有的任何属性。大多数情况下，传入 NULL 表示默认值。
• start_routine 是一个函数指针，线程在该函数指针所表示的函数中运行。void 指针作为返回值，允许线程返回任何类型的结果。
• arg 表示传递给线程开始执行的函数（start_routine）的参数。void 指针作为形参允许我们传入任何类型的实参。

  一旦创建一个线程，就拥有了另一个活着的执行实体，它有自己的调用栈，与程序中所有当前存在的线程在相同的地址空间内运行。

b. 线程完成

int pthread_join(pthread_t thread, void **value_ptr);

• thread 是 pthread_t 类型，用于指定要等待的线程。它是由线程创建函数初始化的（当你将一个指针作为参数传递给 pthread_create() 时）。
• value_ptr 是一个指针，指向线程完后的返回值，那是一个 void 指针，因此这儿的参数是一个 void 指针的指针。因为 pthread_join() 函数改变了传入参数的值，所以需要传入一个指向该值的指针，尽管该值本身就是一个指针。

c. 锁

  POSIX 线程库提供的最有用的函数集，即通过锁（lock）来提供互斥进入临界区的函数。最基本的一对函数是：

int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&lock);
x = x + 1;  // or whatever your critical section is
pthread_mutex_unlock(&lock);

  在调用 pthread_mutex_lock() 时没有其他线程持有锁，线程将获取该锁并进入临界区。如果另一个线程持有该锁，则尝试获取该锁的线程将不会从调用中返回，直到获得该锁（意味着持有该锁的线程通过解锁调用释放该锁）。当然，在给定的时间内，许多线程可能会卡住，在获取锁的函数内部等待。只有获得锁的线程才应该调用解锁。所有锁必须正确初始化，以确保它们具有正确的值，并在锁和解锁被调用时按照需要工作。除了使用 PTHREAD_MUTEX_INITIALIZER ，初始化的动态方法是调用 pthread_mutex_init()，第一个参数是锁本身的地址，第二个参数是一组可选属性，传入 NULL 表示使用默认值。请注意，当用完锁时，该应该调用相应的 pthread_mutex_destroy()。所有细节请参阅手册。

int rc = pthread_mutex_init(&lock, NULL);
assert(rc == 0);    // always check success!

  就像 UNIX 系统中调用的任何库函数一样，这些函数也可能会失败！应该正确地检查错误代码，防止多个线程进入临界区。至少要使用包装的函数，它对函数成功加上断言（见下面）。更复杂的程序在出现问题时，应该检查失败并在获取锁和释放锁未成功时执行适当的操作。

// Use this to keep your code clean but check for failures
// Only use if exiting program is OK upon failure
void Pthread_mutex_lock(pthread_mutex_t *mutex) {
    int rc = pthread_mutex_lock(mutex);
    assert(rc == 0);
}

// 在避免卡在（可能无限期的）获取锁的函数中会很有用的两个函数：
// 1. 如果锁被占用，则 trylock 版本将失败 
int pthread_mutex_trylock(pthread_mutex_t *mutex);
// 2. 在超时或获取锁后返回，以先发生者为准
int pthread_mutex_timedlock(pthread_mutex_t *mutex, 
                            struct timespace *abs_timeout);

d. 条件变量

二. 锁

  并发编程的一个最基本问题：我们希望原子式执行一系列指令，但由于单处理器上的中断（或者多个线程在多处理器上并发执行），我们做不到。锁（lock）直接解决这一问题。程序员在源代码中加锁，放在临界区周围，保证临界区能够像单条原子指令一样执行。

1. 锁的基本思想

  从程序员的角度，理解锁是如何工作：

lock_t mutex; // some globally-allocated lock ’mutex’
...
lock(&mutex);
balance = balance + 1;  // 临界区
unlock(&mutex);

  锁就是一个变量。声明一个某种类型的锁变量（lock variable，如上面的 mutex）来使用，这个锁变量保存锁在某一时刻的状态，可用（available,unlocked,free）表示没有线程持有该锁，被占用（acquired,locked,held）表示有一个线程持有该锁，正处于临界区。它也可以保存其他信息，比如持有锁的线程，或请求获取锁的线程队列（这些信息会隐藏起来，锁的使用者不会发现）。
  调用 lock() 尝试获取锁，若无其他线程持有锁（即它是可用的），该线程便会获得锁，进入临界区。这个线程也被称为锁的持有者（owner）。若锁被另一线程持有，该调用不会返回。这样，当持有锁的线程在临界区时，其他线程就无法进入临界区。锁的持有者一旦调用 unlock() ，锁就变为可用了。如果没有等待线程（即没有其他线程调用过 lock() 并卡在那里），锁的状态就变为可用了。如果有等待线程（卡在 lock() 里），其中一个会最终注意到（或收到通知）锁状态的变化，获取该锁，进入临界区。
  锁为程序员提供了最小程度的调度控制。线程是程序员创建的实体，却被操作系统调度，锁让程序员获得一些控制权。通过给临界区加锁，可以保证临界区内只有一个线程活跃。锁将原本由操作系统调度的混乱状态变得更为可控。

2. Pthread 锁

  POSIX 库将锁称为互斥量（mutex），因为它被用来提供线程之间的互斥。即当一个线程在临界区，它能够阻止其他线程进入直到本线程离开临界区。POSIX 的 lock 和 unlock 函数会传入一个变量，因为我们用不同的锁来保护不同的变量，从而增加并发。不同于任何临界区都使用同一个大锁（粗粒度的锁策略），用不同的锁保护不同的数据和结构，从而允许更多的线程进入临界区（细粒度的方案）。

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
Pthread_mutex_lock(&lock); // wrapper; exits on failure
balance = balance + 1;
Pthread_mutex_unlock(&lock) // wrapper for pthread_mutex_unlock()

3. 实现一个锁

  关键问题：怎样实现一个锁？硬件支持？操作系统支持？各种计算机体系结构的指令集都增加了一些不同的硬件原语，我们不研究这些指令是如何实现的（毕竟，这是计算机体系结构课程的主题），只研究如何使用它们来实现像锁这样的互斥原语。操作系统如何发展完善，支持实现成熟复杂的锁库。

• 硬件支持 —— 通过硬件原语 —— 实现了正确、公平（通过 ticket 锁）的锁。
• 操作系统支持 —— 通过操作系统原语和杂合方案 —— 满足不同场景下的性能要求。

  评价锁：

• 正确性（correctness）。锁是否能完成它的基本任务，即提供互斥（mutual exclusion），能否阻止多个线程进入临界区。
• 公平性（fairness）。当锁可用时，是否每一个竞争线程有公平的机会抢到锁？/是否有竞争锁的线程会饿死（starve），一直无法获得锁？
• 性能（performance）。不同竞争场景下（一个线程，一个CPU多个线程，多个CPU多个线程）不同锁技术对性能的影响。

（1）控制中断

  最早提供的互斥解决方案之一 —— 在临界区关闭中断（为单处理器系统开发）。代码如下：

void lock() {
    DisableInterrupts();
}
void unlock() {
    EnableInterrupts();
}

  通过在进入临界区之前关闭中断（使用特殊的硬件指令），保证临界区的代码不会被中断，从而原子式地执行。结束之后重新打开中断（同样通过硬件指令），程序正常运行。这个方法简单，但这种机制很容易被滥用：

• 关闭中断对应用要求太多，不太适合作为通用的同步解决方案。
• 不支持多处理器。多个线程运行在不同 CPU ，每个线程试图进入同一个临界区，关闭中断也没有用。
• 中断丢失，可能会导致严重的系统问题。操作系统如何重获控制权？
• 效率低。
    基于以上原因，只在很有限的情况下用关闭中断来实现互斥原语。例如，在某些情况下操作系统本身会采用屏蔽中断的方式，保证访问自己数据结构的原子性，或至少避免某些复杂的中断处理情况。

（2）测试并设置指令（原子交换）

  最简单的硬件支持是测试并设置指令（test-and-set instruction），也叫做原子交换（atomic exchange）。用一个变量标记锁是否被持有，并通过自旋等待（spin-waiting）技术不停地检查标志（变量标记）的值可以实现一个不依赖 test-and-set 的锁，不过由于不合时宜的中断，互斥无法满足（正确性）。同时，自旋等待在等待其他线程释放锁的时候会浪费时间，尤其是在单处理器上（性能）。
  基于变量标记这种概念创建简单的锁，需要硬件的支持。在 SPARC 上，这个指令叫 ldstub（load/store unsigned byte, 加载/保存无符号字节）；在 x86 上，是 xchg （atomic exchange, 原子交换）指令。它们在不同的平台做同样的事，通称为测试并设置指令（test-and-set），下面是它的 C 语言伪代码：

int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr; // fetch old value at old_ptr
    *old_ptr = new;     // store 'new' into old_ptr
    return old;         // return the old value
}

  测试并设置指令，返回旧值（可以测试旧值），同时更新为新的值（设置新值），关键是这些代码原子地（atomically）执行。这一条指令完全可以实现一个简单的自旋锁（spin lock）：

typedef struct look_t {
    int flag;
} lock_t;

void init(lock_t *lock){
    // o indicates that lock is available, 1 that it is held
    lock->flag = 0;
}

void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag, 1) == 1)
        ;   // spin-wait (do nothing)
}

void unlock(lock_t *lock){
    lock->flag = 0;
}

  自旋锁（spin lock）是最简单的一种锁，一直自旋，利用 CPU 周期，直到锁可用。在单处理器上需要抢占式的调度器（preemptive scheduler，即不断通过时钟中断一个线程，运行其他线程）。

• 将测试（test 旧的锁值）和设置（set 新的值）合并为一个原子操作之后，自旋锁一次只允许一个线程获得锁，进入临界区，实现了一个有效的互斥原语，保证了正确性。
• 自旋锁不提供任何公平性保证，自旋的线程在竞争条件下可能会永远自旋，可能会导致饿死。
• 在单 CPU 的情况下，线程在竞争锁，都会在放弃 CPU 之前，自旋一个时间片，浪费 CPU 周期。在多 CPU 上，由于临界区很短，锁很快可用，在另一个 CPU 上自旋的线程很快会获得锁。自旋等待其他处理器上的锁，并没有浪费很多 CPU 周期。

(3) 比较并交换

  另一个硬件原语 —— 比较并交换指令。SPARC 系统中是 compare-and-swap，x86 系统是 compare-and-exchange。这条指令的 C 语言伪代码：

int CompareAndSwap(int *ptr, int expected, int new) {
    int actual = *ptr;
    if (actual == expected)
        *ptr = new;
    return actual;
}

  用比较交换指令实现一个锁，类似于测试并设置那样。只要用下面的代码替换 lock() 函数：

void lock(lock_t *lock) {
    while (CompareAndSwap(&lock->flag, 0, 1) == 1)
        ;   // spin
}

  比较并交换指令比测试并设置更强大。在将来简单探讨无等待同步（wait-free synchronization）时，会用到这条指令的强大之处。用它实现一个简单的自旋锁，行为等价于测试并设置实现的自旋锁。

(4) 链接的加载和条件式存储指令

  一些平台提供了实现临界区的一对指令。例如，MIPS 架构中，链接的加载（load-linked）和条件式存储（store-conditinal）可以用来配合使用，实现其他并发结构。这些指令的 C 语言代码（Alpha、PowerPC、ARM 都提供类似的指令）：

int LoadLinked(int *ptr){
    return *ptr;
}

int StoreConditional(int *ptr, int value){
    if (no one has updated *ptr since the LoadLinked to this address) {
        *ptr = value;
        return 1;   // success!
    } else {
        return 0;   // failed to update
    }
}

  链接的加载指令和典型的加载指令类似，都是从内存中取出值存入一个寄存器。条件式存储是指，只有上一次加载的地址在期间都没有更新时，才会成功，同时更新刚才链接加载的地址的值。用链接的加载和条件式存储实现一个锁：

void lock(lock_t *lock) {
    while (1) {
        while (LoadLinked(&lock->flag) == 1)
            ;   // spin until it's zero
        if (StoreConditional(&lock->flag, 1) == 1)
            return; // if set-it-to-1 was a success: all done
                    // otherwise: try it over again
    }
}

void unlock(lock_t *lock) {
    lock->flag = 0;
}

  请注意条件式存储失败是如何发生的。一个线程调用 lock()，执行了链接的加载指令，返回 0。在执行条件式存储之前，中断产生了，另一个线程进入 lock 的代码，也执行链接的加载指令，同样返回 0 。现在，两个线程都执行了链接式加载指令，将要执行条件存储。重点是还有一个线程能够成功更新标志为 1，从而获得锁；第二个执行条件存储的线程会失败（因为另一个线程已经成功执行了条件更新），必须重新尝试获取锁。一种利用了布尔条件短路的更为简洁的实现：

void lock(lock_t *lock) {
    while (LoadLinked(&lock->flag) || !StoreConditional(&lock->flag, 1))
        ;   // spin
}

(5) 获取并增加

  硬件原语获取并增加（fetch-and-add）指令原子地返回特定地址的旧值，并且让该值自增一。下面是它的 C 语言伪代码以及用它实现的一个 ticket 锁：

int FetchAndAdd(int *ptr) {
    int old = *ptr;
    *ptr = old + 1;
    return old;
}

typedef struct lock_t {
    int ticket;
    int turn;
} lock_t;

void lock_init(lock_t *lock) {
    lock->ticket = 0;
    lock->turn = 0;
}

void lock(lock_t *lock) {
    int myturn = FetchAndAdd(&lock->ticket);
    while (lock->turn != myturn)
        ;   // spin
}

void unlock(lock_t *lock) {
    FetchAndAdd(&lock->turn);
}

  这个解决方案使用了 ticket 和 turn 变量来构建锁。如果线程希望获取锁，首先对一个 ticket 值执行一个原子的获取并增加指令。这个值作为线程的 “turn“（顺位，即 myturn）。根据全局共享的 lock->turn 变量，当某一个线程的 myturn == turn 时，则轮到这个线程进入临界区。unlock 增加 turn，从而下一个等待线程可以进入临界区。
  不同于之前的方案，本方案能够保证所有线程都能抢到锁。只要一个线程获得了 ticket 值，它最终会被调度。

(6) yield() 原语

  如果临界区的线程发生上下文切换，其他线程只能一直自旋，等待被中断的（持有锁的）线程重新运行。一种简单友好的方法是，在要自旋的时候，放弃 CPU。就像：

void init() {
    flag = 0;
}

void lock() {
    while (TestAndSet(&flag, 1) == 1)
        yield();    // give up the CPU
}

void unlock() {
    flag = 0;
}

  假定操作系统提供原语 yield() 原语，线程可以调用它主动放弃 CPU，让其他线程运行。yield() 系统调用能够让运行（running）态变为就绪（ready）态，从而允许其他线程运行。当多个线程一直处于 运行-让出 这种模式，直到持有锁的线程再次运行，虽然比原来浪费多个时间片的自旋方案好，但这种方法的上下文切换的成本是实实在在的，因此浪费很大。也会存在饿死的问题，一个线程可能一直处于让出的循环，而其他线程反复进入临界区。

(7) 使用队列：休眠代替自旋

  调度程序决定如何调度，因此前面的方案存在太多的偶然性。如果调度不合理，线程或者一直自旋（第一种方法），或者立刻让出 CPU（第二种方法），不管怎样，都有潜在的浪费以及饿死的可能。因此，必须显式地施加某种控制，决定锁释放时，谁能抢到锁。操作系统提供更多的支持，用一个队列来保存等待锁的线程。
  Solaris 提供的支持，两个调用：park() 能够让调用线程休眠；unpark(threadID) 则会唤醒 threadID 标识的线程。可以用这两个调度来实现锁，让调用者在获取不到锁时睡眠，在锁可用时被唤醒。这组原语的一种可能用法：

typedef struct lock_t {
    int flag;
    int guard;
    queue_t  *q;
} lock_t;

void lock_init(lock_t *m) {
    m->flag = 0;
    m->guard = 0;
    queue_init(m->q);
}

void lock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1)
        ;   // acquire guard lock by spinning
    if (m->flag == 0) {
        m->flag = 1;    // lock is acquired
        m->guard = 0;
    } else {
        queue_add(m->q, gettid());
        m->guard = 0;
        park();
    }
}

void unlock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1) 
        ;   // acquire guard lock by spining
    if(queue_empty(m->q))
        m->flag = 0;    // let go of lock; no one wants it
    else
        unpark(queue_remove(m->q)); // hold lock (for next thread!)
    m->guard = 0;
}

  这个例子将测试并设置和等待队列结合，实现了一个更高性能的锁。通过队列来控制谁会获得锁，避免了饿死。guard 基本上起到了自旋锁的作用，围绕着 flag 和队列操作。线程在获取锁或者释放锁时可能被中断，从而导致其他线程自旋等待。但是这个自旋时间是有很有限的（不是用户定义的临界区，并不需要等待临界区结束，锁被释放，只是在 lock 和 unlock 代码中的几个指令），因此，这种方法也许是合理的。
  在 lock() 函数中，如果线程不能获取锁（它已被持有），线程会把自己加入队列，将 guard 设置为 0，然后让出 CPU。
  在 unlock() 中，线程被唤醒时，就像是从 park() 调用返回。但是，此时它没有持有 guard，所以不能将 flag 设置为 1。因此，直接把锁从释放的线程传递给下一个获得锁的线程，期间 flag 不必设置为 0。若在 park() 之后才把 guard 设置为 0 释放锁，则其他线程将会一直自旋下去。
  若在 park() 调用之前（即一个线程将要 park，它应该睡到锁可用时），也就是将 guard 设置为 0 后，上下文切换发生了，切换到持有锁的线程，且该线程随后释放了锁。则第一个线程的 park 会永远睡下去（可能）。这种问题被称为唤醒/等待竞争（wakeup/waiting race）。Solaris 通过增加第三个系统调用 setpark() 来解决这个问题。通过 setpark()，一个线程表明自己马上要 park，如果刚好另一个线程被调度，并且调用了 unpark，那么后续的 park 调用就会直接返回，而不是一直睡眠。因此，lock() 可以做一点小修改：

queue_add(m->q, gettid());
setpark();  // new code
m->guard = 0;
park();

(8) Linux 的 futex

  Linux 提供了 futex，它类似于 Solaris 的接口，但提供了更多内核功能。具体来说，每个 futex 都关联一个特定的物理内存位置，也有一个事先建好的内核队列。调用者通过 futex 调用来睡眠或者唤醒。futex_wait(address, expected) 当 address 处的值等于 expected 时，就会让调用线程睡眠；调用 futex_wake(address) 唤醒等待队列中的一个线程。基于 Linux 的 futex 锁：

void mutex_lock(int *mutex) {
    int v;
    /* Bit 31 was clear, we got the mutex (this is the fastpath) */
    if (atomic_bit_test_set(mutex, 31) == 0)  // mutex 最高位为0,
        return;     // 并设置其为1，获得锁返回
    atomic_increment(mutex);  // 否则，增加等待线程队列数
    while (1) {
        if (atomic_bit_test_set(mutex, 31) == 0) {  // 再一次尝试获取锁
            atomic_decrement(mutex);    // 成功，减少等待线程队列数
            return; // 返回
        }// 失败，不得不进入等待
        /* We have to wait now. First make sure the futex value
           we are monitoring is truly negative (i.e. locked). */
        v = *mutex;
        if(v >= 0)  // 判断锁是否可用
            continue;   // 锁可用，继续循环获取锁
        futex_wait(mutex, v);   // 锁不可用，进入睡眠，等待锁可用
    }
}

void mutex_unlock(int *mutex) {
    /* Adding Ox80000000 to the counter results in 0 if and only if 
        there are not other interested threads */
    if (atomic_add_zero (mutex, 0x80000000)) // 最高位进1，溢出后为0，锁被释放，其余位不变
        return; // 结果为0，则无等待线程，锁已释放，直接退出

    /* There are other threads waiting for this mutex,
        wake one of them up. */
    futex_wake(mutex);  // 否则存在等待线程，唤醒一个等待线程 
}

  这段代码来自 nptl 库（gnu libc 库的一部分）中 lowlevellock.h。它利用一个整数，同时记录锁是否被持有（整数的最高位，31），以及等待者的个数（整数的其余所有位）。因此，如果锁是负的，它就被持有（因为最高位被设置，该位决定了整数的符号）。这段代码同时展示了如何优化常见情况，即没有竞争时：只有一个线程获取和释放锁，所做的工作很少（获取锁时测试和设置的原子位运算，释放锁时原子的加法）。

  Linux 采用的是一种古老的锁方案，现在也称为两阶段锁（two-phase lock）。两阶段锁意识到自旋可能很有用，尤其是在很快就要释放锁的场景。因此，两阶段锁的第一阶段会先自旋一段时间，希望它可以获得锁。如果第一个自旋阶段没有获得锁，第二阶段调用者会睡眠，直到锁可用。上文的 Linux 锁就是这种锁，不过只自旋一次；更常见的方式是在循环中自旋固定的次数，然后使用 futex 睡眠。
  两阶段锁是一个杂合（hybrid）方案的例子。硬件环境、线程数、其他负载等因素都会影响锁的效果。让单个通用目标的锁在所有可能的场景下都很好是巨大的挑战。

(9) 总结

  如今真实的锁的实现：一些硬件支持（更加强大的指令）和一些操作系统支持（例如 Solaris 的 park() 和 unpark() 原语，Linux 的 futex）。当然，细节有所不同，执行这些锁的代码通常是高度优化的。

4. 基于锁的并发数据结构

  通过锁可以使数据结构线程安全（thread safe）。关键问题：如何给数据结构加锁？能够保证功能正确、高性能、并发访问。

(1) 并发计数器

  计数器是最简单的一种数据结构，使用广泛且接口简单。一个简单、正确的并发计数器，它遵循了最简单、最基本的并发数据结构中常见的数据模式：它只是加了一把锁，在调用函数操作该数据结构时获取锁，从调用返回时释放锁。

typedef struct counter_t {
    int value;
    pthread_mutex_t lock;
} counter_t;

void init(counter_t *c) {
    c->value = 0;
    Pthread_mutex_init(&c->lock, NULL);
}

void increment(counter_t *c) {
    Pthread_mutex_lock(&c->lock);
    c->value++;
    Pthread_mutex_unlock(&c->lock);
}

void decrement(counter_t *c) {
    Pthread_mutex_lock(&c->lock);
    c->value--;
    Pthread_mutex_unlock(&c->lock):
}

int get(counter_t *c) {
    Pthread_mutex_lock(&c->lock);
    int rc = c->value;
    Pthread_mutex_unlock(&c->lock);
    return rc;
}

  理想情况下，多处理器上运行的多线程就像单线程一样快，达到这种状态称为完美扩展（perfect scaling）。例如，运行一个线程更新 100 万次计数器，与在 4 个 CPU 上运行四个线程共更新 400 万次计数器一样快，虽然总工作量增多，但是并发执行后，完成任务的时间并没有增加。上面的同步的计数器扩展性不好，线程更多时，性能更差，无论是否多处理器。因为每次操作都伴随着锁的操作，必然会带来性能的下降。
  懒惰计数器（sloppy counter）通过多个局部计数器和一个全局计数器来实现一个逻辑计数器，其中每个 CPU 核心有一个局部计数器。除了这些计数器，还有锁：每个局部计数器有一个锁，全局计数器有一个。懒惰计数器的基本思想是，一个核心上的线程想增加计数器，增加它的局部计数器，通过这个局部计数器对应的局部锁同步。因为每个 CPU 有自己的局部计数器，不同 CPU 上的线程不会竞争，所以计数器的更新操作可扩展性好。为了保持全局计数器更新（以防某个线程要读取该值），通过一个阙值 S（sloppiness）。当局部计数器达到 S 时，则转移给全局计数器，方法是获取全局锁，让全局计数器加上局部计数器的值，然后将局部计数器置零。S 越小，懒惰计数器则越趋近于非扩展的计数器；S 越大，扩展性越强，但是全局计数器与实际计数的偏差越大。可以抢占所有的局部锁和全局锁（以特定顺序，避免死锁），以获得精确值，但这种方法没有扩展性。懒惰计数器就是在准确性和性能之间折中，在多核情况下，因为分布的锁（本地锁和全局锁）而更加高效。懒惰计数器的实现：

typedef struct counter_t {
    int global;                     // global count
    pthread_mutex_t glock;          // global lock
    int local[NUMCPUS];             // local count (per cpu)
    pthread_mutex_t llock[NUMCPUS]; //... and locks
    int threshold;                  // update frequency
} counter_t;

// init: record threshold, init locks, init values
// of all local counts and global count
void init(counter_t *c, int threshold) {
    c->threshold = threshold;

    c->global = 0;
    pthread_mutex_init(&c->glock, NULL);

    int i;
    for (i = 0; i < NUMCPUS; i++) {
        c->local[i] = 0;
        pthread_mutex_init(&c->llock[i], NULL);
    }
}

// update: usually, just grab local lock and update local amount
// once local count has risen by 'threshold', grab global
// lock and transfer local values to it
void update(counter_t *c, int threadID, int amt) {
    pthread_mutex_lock(&c->llock[threadID]);
    c->local[threadID] += amt;      // assumes amt > 0
    if (c->local[threadID] >= c->threshold) {   // transfer to global
        pthread_mutex_lock(&c->glock);
        c->global += c->local[threadID];
        pthread_mutex_unlock(&c->glock);
        c->local[threadID] = 0;
    }
    pthread_mutex_unlock(&c->llock[threadID]);
}

// get: just return global amount (which way not be perfect)
int get(counter_t *c) {
    pthread_mutex_lock(&c->glock);
    int val = c->global;
    pthread_mutex_unlock(&c->glock);
    return val; // only approximate!
}

(2) 并发链表

  在操作的前后加锁这种传统方式实现的并发链表：

// basic node structure
typedef struct node_t {
    int key;
    struct node_t *next;
} node_t;

// basic list structure (one used per list)
typedef list_t {
    node_t *head;
    pthread_mutex_t lock;
} list_t;

void List_Init(list_t *L){
    L->head = NULL;
    pthread_mutex_init(&L->lock, NULL);
}

int List_Insert(list_t *L, int key) {
    pthread_mutex_lock(&L->lock);
    node_t *new = malloc(sizeof(node_t));
    if (new == NULL) {
        perror("malloc");
        pthread_mutex_unlock(&L->lock);
        return -1;  // fail
    }
    new->key = key;
    new->next = L->head;
    L->head = new;
    pthread_mutex_unlock(&L->lock);
    return 0;   // success
}

int List_Lookup(list_t *L, int key) {
    pthread_mutex_lock(L->lock);
    node_t *curr = L->head;
    while (curr) {
        if (curr->key == key) {
            pthread_mutex_unlock(&L->lock);
            return 0;   // success
        }
        curr = curr->next;
    }
    pthread_mutex_unlock(&L->lock);
    return -1;  // faulure
}

  异常控制流容易产生错误。比如，必须在失败情况下的错误处理中释放锁。通过最小化锁代码的区域，只在更新共享列表时需要持有锁，降低代码中不小心引入缺陷（诸如在返回前忘记释放锁）的可能性。调整后的代码（让获取锁和释放锁只环绕代码的真正临界区）：

void List_Init(list_t *L) {
    L->head = NULL;
    pthread_mutex_init(&L->lock, NULL);
}

void List_Insert(list_t *L, int key) {
    // synchronization not needed
    node_t *new = malloc(sizeof(node_t));
    if (new == NULL) {
        perror("malloc");
        return;
    }
    new->key = key;

    // just lock critical section
    pthread_mutex_lock(&L->lock);
    new->next = L->head;
    L->head = new;
    pthread_mutex_unlock(&L->lock);
}

int List_Lookup(list_t *L, int key) {
    int rv = -1;
    pthread_mutex_lock(&L->lock);
    node_t *curr = L->head;
    while (curr) {
        if (curr->key == key) {
            rv = 0;
            break;
        }
        curr = curr->next;
    }
    pthread_mutex_unlock(&L->lock);
    return rv;  // now both success and failure
}

  这个基本的并发链表的扩展性依旧不好。因为多线程情况下依然有大量的锁操作。在增加链表并发的技术中，有一种叫做过手锁（hand-over-hand locking，也叫锁耦合，lock coupling）。每一个节点都有一个锁，替代之前整个链表一个锁。遍历链表的时候，首先抢占下一个节点的锁，然后释放当前节点的锁。过手锁链表增加了链表操作的并发程度，但实际上遍历的时候，每个节点获取锁、释放锁的开销巨大，很难比单锁快。即使有大量的线程和很大的链表，这种并发方案也不一定比单锁的方案快。也许某种杂合的方案（一定数量的节点用一个锁）值得去研究。

Tips:

• 更多并发并不一定更快。高并发可能带来大量的开销（频繁获取、释放锁），简单的方案很少的高开销调用通常会更有效。两种方案，在性能上，要么更快，要么不快。
• 当心锁和控制流。最好组织好代码，减少控制流的变化和错误处理导致的改变状态的操作。

(3) 并发队列

  总有一个标准方案创建一个并发数据结构：添加一把大锁。Michael 和 Scott 跳过这种方法设计的更并发的队列：

typedef struct __node_t {
    int value;
    struct __node_t *next;
} node_t;

typedef struct queue_t {
    node_t *head;
    node_t *tail;
    pthread_mutex_t headLock;
    pthread_mutex_t tailLock;
} queue_t;

void Queue_Init(queue_t *q) {
    node_t *tmp = malloc(sizeof(node_t));
    tmp->next = NULL;
    q->head = q->tail = tmp;
    pthread_mutex_init(&q->headLock, NULL);
    pthread_mutex_init(&q->tailLock, NULL);
}

void Queue_Enqueue(queue_t *q, int value) {
    node_t *tmp = malloc(sizeof(node_t));
    assert(tmp != NULL);
    tmp->value = value;
    tmp->next = NULL;

    pthread_mutex_lock(&q->tailLock);
    q->tail->next = tmp;
    q->tail = tmp;
    pthread_mutex_unlock(&q->tailLock);
}

int Queue_Dequeue(queue_t *q, int *value) {
    pthread_mutex_lock(&q->headLock);
    node_t *tmp = q->head;
    node_t *newHead = tmp->next;
    if (newHead == NULL) {
        pthread_mutex_unlock(&q->headLock);
        return -1;  // queue was empty
    }
    *value = newHead->value;
    q->head = newHead;
    pthread_mutex_unlock(&q->headLock);
    free(tmp);
    return 0;
}

  有两个锁，一个负责队列头，另一个负责队列尾。使得入队和出队可以并发执行（即使在队列为空时），因为如入队只访问 tail 锁，而出队只访问 head 锁。使用添加一个假节点的技巧分开了头和尾操作。这里的队列（只是加了锁）通常不能完全满足多线程程序的需求。更完善的有界队列，在队列空或者满时，能让线程等待。

(4) 并发散列表

  本例的散列表使用之前实现的并发链表。每个散列桶（每个桶都是一个链表）都有一个锁，而不是整个散列表只有一个锁，从而支持许多并发操作。这是一个不需要调整大小的简单散列表，这个简单的并发散列表扩展性极好，而链表则相反。这是因为，散列表的操作往往是对单个的桶的操作，每个桶都有自己的锁，而链表只有一个锁，它的操作是对其所有节点整个的操作。

#define BUCKETS (101)

typedef struct __hash_t {
    list_t lists[BUCKETS];
} hash_t;

void Hash_Init(hash_t *H) {
    int i;
    for (i = 0; i < BUCKETS; i++) {
        List_Init(&H->lists[i]);
    }
}

int Hash_Insert(hash_t *H, int key) {
    int bucket = key % BUCKETS;
    return List_Insert(&H->lists[bucket], key);
}

int Hash_Lookup(hash_t *H, int key) {
    int bucket = key % BUCKETS;
    return List_Lookup(&H->lists[bucket], key);
}

Tips：避免不成熟的优化（Knuth 定律）。实现并发数据结构时，先从最简单的方案开始，即加一把大锁来同步。若有性能问题，再优化改进满足需要即可。许多操作系统最初过滤到多处理器时都是用一把大锁。Linux 也是从早期的大内核锁 Big kernel lock (BKL) 到使用多个 lock 代替单个锁，SUN 直接写了个新的操作系统，也就是 Solaris。

三. 条件变量

  锁并不是并发程序设计所需的唯一原语。在很多情况下，线程需要检查某一条件（condition）满足之后，才会继续运行。比如，父线程检查子线程是否执行完毕（这常被称为 join()）所进行的等待。
  关键问题：如何等待一个条件？在多线程程序中，一个线程等待某些条件是很常见的。简单的方案是自旋直到条件满足，这是极其低效，某些情况下甚至是错误的。自旋检查浪费 CPU 时间，一种方式是让父线程休眠，直到等待的条件满足（即子线程完成执行）。条件变量便是如此，一种代替自旋实现等待一个条件的方式，这种变量并不是表示条件本身，不要被它的名字所迷惑，它使线程进入休眠状态或唤醒线程。

1. 定义和程序

  线程使用条件变量（condition variable），来等待一个条件变为真。条件变量是一个显式队列，当某些执行状态（即条件，condition）不满足时，线程把自己加入队列，等待（waiting）该条件。另外某个线程改变了上述状态时，就可以唤醒一个或者多个等待线程（通过在该条件上发信号），让它们继续执行。条件变量的类型为 pthread_cond_t ，需要适当的初始化。它的两种相关联的操作：wait() 【线程要睡眠的时候调用】和 signal()【线程想唤醒等待在某个条件变量上的睡眠线程时调用】。POSIX 调用如下所示：

pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m);
pthread_cond_signal(pthread_cond_t *c);

  一个简单的 join 示例，展示使用条件变量的一些基本要求：

int done = 0;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t c = PTHREAD_COND_INITIALIZER;

void thr_exit() {
    Pthread_mutex_lock(&m);
    done = 1;
    Pthread_cond_signal(&c);
    Pthread_mutex_unlock(&m);
}

void *child(void *arg) {
    printf("child\n");
    thr_exit();
    return NULL;
}

void thr_join() {
    Pthread_mutex_lock(&m);
    while (done == 0) 
        Pthread_cond_wait(&c, &m);
    Pthread_mutex_unlock(&m);
}

int main(int argc, char *argv[]) {
    printf("parent:begin\n");
    pthread_t p;
    Pthread_create(&p, NULL, child, NULL);
    thr_join();
    printf("parent:end\n");
    return 0;
}

  wait() 调用有一个参数，它是互斥量。它假定在 wait() 调用时，这个互斥量是已上锁状态。wait() 的职责是释放锁，并让调用线程休眠（原子地）。当线程被唤醒时（在另外某个线程发信号给它后），它必须重新获取锁，再返回调用者。这些复杂的步骤是为了避免在线程陷入休眠时，产生一些竞态条件。
  调用 signal() 唤醒其他线程。若没有其他线程，signal() 调用会直接结束。若存在其他线程等待在睡眠状态，则会让它不再睡在条件变量上，进入就绪队列（可以运行，但不一定立即运行）。注意，发信号给线程只是唤醒它们，暗示状态发生了改变（条件满足），但并不会保证在它运行之前状态一直是期望的情况。信号的这种释义常称为 Mesa 语义（Mesa semantic）。另一种释义是 Hoare 语义，虽然实现难度大，但是会保证被唤醒的线程立刻执行。实际上，几乎所有系统都采用了 Mesa 语义。由于 Mesa 语义，记住一条关于条件变量的简单规则：总是使用 while 循环（always use while loop）。
  确保理解 thr_exit() 和 thr_join() 中每个部分的重要性。状态变量 done 记录了线程感兴趣的值（真正的条件），睡眠、唤醒和锁都离不开它，锁避免了一些微妙的竞态条件。使用 while 循环而不是 if 判断也是重要的，别忘了 Mesa 语义并不保证唤醒到执行前值还是期望的值。

Tips: 发信号时总是持有锁。调用 wait 时持有锁是 wait 语义的强制要求，调用 signal 时也应该持有锁。因此，调用 signal 和 wait 时要持有锁（hold the lock when calling signal or wait）。

2. 生产者/消费者（有界缓冲区）问题

  生产者/消费者（producer/consumer）问题，也叫做有界缓冲区（bounded buffer）问题。正是通过研究这一问题，Dijkstra 和他的同事发明了通用的信号量（它可用作锁和条件变量）。
  假设有一个或多个生产者（producer）线程和一个或多个消费者（consumer）线程。生产者把生成的数据项放入缓冲区；消费者从缓冲区取走数据项，以某种方式消费。很多实际的系统中都会有这种场景。因为有界缓冲区是共享资源，所以我们必须通过同步机制来访问它，以免产生竞态条件。
  这种情况，读写有界缓冲区的代码就是临界区，而光给代码加锁是没有用的，有了锁我们只是确认可以读写缓冲区的共享资源，不会存在竞态条件，但有界缓存区是否处于能够读写的状态是不得而知的，写入满的缓冲区以及读取空的缓冲区都是错误的。因此我们还需要别的东西，也就是某些条件变量，当然，以及它们相关的锁。
  生产者线程在缓冲区满时，发出信号，从而唤醒消费者线程，并开始休眠，等待消费者信号的唤醒，再继续生产，生产后再向消费者发信号；消费者线程在缓冲区空时，发出信号，从而唤醒生产者线程，并开始休眠，等待生产者信号唤醒，再继续消费，消费后再向生产者发信号。
  可能存在很多个生产者线程和消费者线程，因此，信号必须有指向性，消费者不应该唤醒消费者，而应该只唤醒生产者，反之亦然。因此，一个信号是行不通的，缓冲区满和缓冲区空是两个完全不同的条件。所以需要使用两个条件变量，而不是一个，以便正确地发出信号，在系统状态改变时，哪类线程应该唤醒。生产者线程等待条件变量 empty（表示缓冲区不满），发信号给变量 fill（表示缓冲区不空）。消费者线程等待 fill，发信号给 empty。这样做从设计上避免了问题，消费者再也不会唤醒消费者，生产者也不会唤醒生产者。下面是一个共享缓冲区，让生产者放入数据，消费者取出数据：

int buffer[MAX];
int fill_ptr = 0;
int use_ptr = 0;
int count = 0;

void put(int value) {
    buffer[fill_ptr] = value;
    fill_ptr = (fill_ptr + 1) % MAX;
    count++;
}

void get() {
    int tmp = buffer[use];
    use_ptr = (use_ptr + 1) % MAX;
    count--;
    return tmp;
}

  从一个整数的缓冲区到更多缓冲区槽位，在睡眠之前可以生产多个值，同样，睡眠之前可以消费多个值。单个生产者和消费者时，上下文切换少，提高了效率。多个生产者和消费者时，支持并发生产和消费，从而提高了并发。生产者/消费者：

cond_t empty, fill;
mutex_t mutex;

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);
        while (count == MAX)
            Pthread_cond_wait(&empty, &mutex);
        put(i);
        Pthread_cond_signal(&fill);
        Pthread_mutex_unlock(&mutex);
    }
}

void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);
        while (count == 0)
            Pthread_cond_wait(&fill, &mutex);
        int tmp = get();
        Pthread_cond_signal(&empty);
        Pthread_mutex_unlock(&mutex);
        printf("%d\n", tmp);
    }
}

  等待和信号逻辑。生产者只有在缓冲区满了的时候才会睡眠，消费者也只有在队列为空的时候睡眠。

Tips: 对条件变量使用 while（不是 if）。多线程程序在检查条件变量时，使用 while 循环总是对的。if 语句可能会对，这取决于发信号的语义，Mesa 还是 Hoare。使用 while 循环也解决了假唤醒（spurious wakeup）的情况（一个信号唤醒两个线程），再次检查线程的等待条件，假唤醒是另一个原因。

3. 覆盖条件

  一个简单的多线程内存分配库：

// how many bytes of the heap are free?
int bytesLeft = MAX_HEAP_SIZE;

// need lock and condition too
cond_t c;
mutex_t m;

void *allocate(int size) {
    Pthread_mutex_lock(&m);
    while (bytesLeft < size) 
        Pthread_cond_wait(&c, &m);
    void *ptr = ...;    // get mem from heap
    bytesLeft -= size;
    Pthread_mutex_unlock(&m);
    return ptr;
}

void free(void *ptr, int size) {
    Pthread_mutex_lock(&m);
    bytesLeft += size;
//    Pthread_cond_signal(&c);      // whom to signal ?
    Pthread_cond_broadcast(&c);     // signal all waitting threads  
    Pthread_mutex_unlock(&m);
}

  当线程调用进入内存分配代码时，可能会因为内存不足而等待。线程释放内存时，会发信号说有更多内存空间。但是，使用 signal() 的话，应该唤醒哪个等待线程（可能有多个线程）？若空闲内存依旧无法满足被唤醒的线程的内存要求，则被唤醒线程又将睡眠等待，而空闲内存可能满足某个未被唤醒的线程的内存要求，但它依旧等待在条件上并睡眠。
  用 pthread_cond_broadcast() 代替 pthread_cond_signal()，唤醒所有的等待线程。这样做，确保了所有等待在该条件变量上的线程都被唤醒。因为不必要地唤醒了其他许多等待的线程，可能会影响性能，这些不应被唤醒的线程被唤醒后，重新检查条件，马上再次睡眠。
  Lampson 和 Redell 把这种条件变量叫做覆盖条件（convering condition），因为它能覆盖所有需要唤醒线程的场景（保守策略）。在单个条件变量的生产者/消费者问题中，也可以使用这种方法，但我们用了更好的方法。一般来说，如果你发现程序只有改成广播信号时才能工作（但你认为不需要），可能是程序有缺陷，修复它！在上述内存分配的例子中，广播可能是最直接有效的方案。

4. 总结

  引入锁之外的另一个重要同步原语：条件变量。当某些程序状态不符合要求时，通过允许线程进入休眠状态，条件变量使我们能够漂亮地解决许多重要的同步问题，包括著名的生产者/消费者问题，以及覆盖条件。

四. 信号量

1. 信号量的定义

  Dijkstra 及其同事发明了信号量，作为与同步有关的所有工作的唯一原语。关键问题：如何使用信号量？如何代替锁和条件变量？什么是信号量？如何实现信号量？
  信号量是有一个整数值的对象，可以用两个函数操作。在 POSIX 标准中，是 sem_wait() 和 sem_post()。信号量的初始值决定其行为，所以首先要初始化信号量。sem_init() 的第一个参数是信号量对象的地址，第二个参数设置为 0 时，表示信号量是在同一进程的多个线程共享的（信号量可以用于跨不同进程的同步访问，这要求第二个参数用不同的值）。第三个参数，用于初始化信号量的整数值。

#include <semaphore.h>
sem_t s;
sem_init(&s, 0 ,1);

  信号量初始化之后，可以调用 sem_wait() 或 sem_post() 与之交互。多个线程会调用它们，显然需要管理这些临界区。sem_wait() 先减一信号量的值，若信号量的值为负（<0）了，则让调用线程挂起，直到之后的一个 post 操作，不为负则立刻返回；sem_post() 增一信号量的值，如果有等待线程，唤醒其中一个，然后返回。当信号量的值为负数时，这个值就是等待线程的个数。信号量：Wait 和 Post 的定义：

int sem_wait(sem_t *s) {
    decrement the value of semaphore s by one
    wait if value of semaphore s is negative
}

int sem_post(sem_t *s) {
    increment the value of semaphore s by one 
    if there are one or more threads waiting, wake one
}

2. 二值信号量（锁）

  使用信号量作为锁：直接把临界区用一对 sem_wait()/sem_post() 环绕。下面代码中信号量 m 的初始值 X 是至关重要的。根据 sem_wait() 和 sem_post() 的函数的定义，它应该是 1。因为锁只有两个状态（持有和没持有），所以这种用法也叫二值信号量（binary semaphore）。二值信号量（就是锁）：

sem_t m;
sem_init(&m, 0, X); // initialize semaphore to X; waht should X be?

sem_wait(&m);
// critical section here
sem_post(&m);

3. 信号量用作条件变量

  信号量也可以用在一个线程暂停执行，等待某一条件成立的场景。比如，一个线程创建另外一个线程，并且等待它结束。因为等待线程在等待某些条件（condition）发生变化，所以我们将信号量作为条件变量（condition variable），别忘了信号量有一个整数值，信号量的等待逻辑是以这个值作为判断条件的。父线程等待子线程：

sem_t s;

void *child(void *arg) {
    printf("child\n");
    sem_post(&s);   // signal here: child is done
    return NULL;
}

int main(int argc, char *argv[]) {
    sem_init(&s, 0, X); // what should x be? yes, X is 0.
    printf("parent:begin\n");
    pthread_t c;
    Pthread_create(c, NULL, child, NULL);
    sem_wait(&s);   // wait here for child
    printf("parent:end\n");
    return 0;
}

4. 生产者/消费者（有界缓冲区）问题

  put() 和 get() 函数：

int buffer[MAX];
int fill = 0;
int use = 0;

void put(int value) {
    buffer[fill] = value;
    fill = (fill + 1) % MAX;
}

int get() {
    int tmp = buffer[use];
    use = (use + 1) % MAX;
    return tmp;
}

  除了两个信号量 empty 和 full 分别表示缓冲区空或者满，还有一个二值信号量 mutex 作为锁。因为，向缓冲区加入元素和增加缓冲区的索引是临界区，需要小心保护起来。简单而有效的有界缓冲区，多线程程序的常用模式：

sem_t empty;
sem_t full;
sem_t mutex;

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&empty);
        sem_wait(&mutex);   // mutex is here !
        put(i);
        sem_post(&mutex);   // and here !
        sem_post(&full);
    }
}

void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&full);
        sem_wait(&mutex);   // mutex is here !
        int tmp = get();
        sem_post(&mutex);   // and here !
        sem_post(&empty);
        printf("%d\n", tmp);
    }
}

int main(int argc, char *argv[]) {
    // ...
    sem_init(&empty, 0, MAX);   // MAX buffers are empty to begin with...
    sem_init(&full, 0, 0);      // ... and 0 are full
    sem_init(&mutex, 0, 1);     // mutex=1 because it is a lock
}

  注意，我们这儿最小化了锁的作用，把获取和释放互斥量的操作紧挨着临界区，full、empty 的唤醒和等待操作在锁外面。如果不这样，即放在外面，将会导致死锁的发生。消费者调用外面的 sem_wait() 休眠等待后（它依旧持有锁未释放），生产者调用里面的 sem_wait() 尝试获取锁（锁已被持有）失败便休眠等待，这样生产者和消费者互相等待对方 —— 典型的死锁。

5. 读者 —— 写者锁

  一个经典问题源于对更加灵活的锁定原语的渴望，它承认不同的数据结构访问可能需要不同类型的锁。例如，一个并发链表有很多插入和查找操作。插入操作会修改链表的状态（因此传统的临界区有用），而查找操作只是读取该结构，只要没有进行插入操作，就可以并发地执行多个查找操作。读者 —— 写者锁（reader-writer lock）就是用来完成这种操作的。

typedef struct _rwlock_t {
    sem_t lock;         // binary semaphore (basic lock)
    sem_t wirtelock;    // used to allow ONE writer or MANY readers
    int readers;        // count of readers reading in critical section
} rwlock_t;

void rwlock_init(rwlock_t *rw) {
    rw->readers = 0;
    sem_init(&rw->lock, 0, 1);
    sem_init(&rw->writelock, 0, 1);
}

void rwlock_acquire_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers++;
    if (rw->readers == 1)
        sem_wait(&rw->writelock);   // first reader acquires writelock
    sem_post(&rw->lock);
}

void rwlock_release_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers--;
    if (rw->readers == 0)
        sem_post(&rw->writelock);   // last reader release writelock
    sem_post(&rw->lock);
}

void rwlock_acquire_writelock(rwlock_t *rw) {
    sem_wait(&rw->writelock);
}

void rwlock_release_writelock(rwlock_t *rw) {
    sem_post(&rw->writelock);
}

  如果某个线程要更新数据结构，需要调用 rwlock_acquire_writelock() 获得写锁，调用 rwlock_release_writelock() 释放锁，内部通过一个 writelock 信号量保证只有一个写者能获得锁进入临界区。reader 变量追踪目前有多少个读者在访问该数据结构，lock 信号量是实现读写锁所需的内部临界区资源（即 reader）的锁，该锁也会存在多线程时获取锁的等待开销，但只是在获取和释放读写锁的函数内部几行代码的等待，而非整个读写临界区的等待。在 rwlock_acquire_readlock() 内，当第一个读者获取该锁时，读者也会获取写锁，而想要获得写锁的线程就必须等到所有的读者都结束，最后一个读者在 wirtelock 信号量上调用 sem_post() ，从而让等待的写锁能够获取该锁。因此，这一方案在公平性上有所缺陷，读者很容易饿死写者，存在复杂一些的解决方法解决这个问题。读写锁同时加入了更多的开锁（尤其是更复杂的实现），和一些简单快速的锁相比，它在性能方面没有优势。

Tips：简单的笨办法可能更好（Hill 定律）。某些时候简单的自旋锁反而是最有效的，因为它容易实现而且高效。虽然读者-写者锁听起来很酷，但是却很复杂，复杂意味着慢。因此，总是优先尝试简单的笨办法。

6. 哲学家就餐问题

  哲学家就餐问题（dining philosopher’s problem）是由 Dijkstra 提出并解决的一个著名的并发问题。这个问题的基本情况是：假定有五位“哲学家”围着一个圆桌，每两位哲学家之间有一把餐叉（一共 5 把）。哲学家有时要思考一会，不需要餐叉，有时又要就餐。一位哲学家只有同时拿到了左手边和右手边的两把餐叉，才能吃到东西。关键挑战是保证没有死锁，没有哲学家饿死，并且并发度更高（尽可能让更多哲学家同时吃东西）。

7. 如何实现信号量

  用底层的同步原语（锁和条件变量）实现信号量 Zemahpore ：

typedef struct _Zem_t {
    int value;
    pthread_cond_t cond;
    pthread_mutex_t lock;
} Zem_t;

// only one thread can call this
void Zem_init(Zem_t *s, int value) {
    s->value = value;
    Cond_init(&s->cond);
    Mutex_init(&s->lock);
}

void Zem_wait(Zem_t *s) {
    Mutex_lock(&s->lock);
    while (s->value <= 0)
        Cond_wait(&s->cond, &s->lock);
    s->value--;
    Mutex_unlock(&s->lock);
}

void Zem_post(Zem_t *s) {
    Mutex_lock(&s->lock);
    s->value++;
    Cond_signal(&s->cond);
    Mutex_unlock(&s->lock);
}

  只用了一把锁、一个条件变量和一个状态的变量来记录信号量的值。我们实现的 Zemaphore 和 Dijkstra 定义的信号量有一点细微区别，就是我们没有保持当信号量的值为负数时，让它反映出等待的线程数。事实上，该值永远不会小于 0。这一行为更容易实现，且符合现有的 Linux 实现，即在 Linux 上使用信号量时，其值永远不会小于 0。当调用 wai() 时，若值等于 0，则等待 post() 将值增加后，再将其减一（减一后最小为 0 ），然后返回。

Tips：小心泛化。在系统设计中，泛化的抽象技术是很有用处的。一个好的想法稍微扩展之后，就可以解决更大一类问题。我们可以把信号量当作锁和条件变量的泛化，这种泛化有必要吗？利用信号量实现锁和条件变量是棘手得多的问题。为什么使用信号量实现条件变量比看起来更困难？

  信号量是编写并发程序的强大而灵活的原语。

五. 常见并发问题

关键问题：如何处理常见并发缺陷？并发缺陷会有很多常见的模式。了解这些模式是写出健壮、正确程序的第一步。在复杂并发程序中，有两种类型的缺陷：非死锁缺陷和死锁缺陷。

1. 非死锁缺陷

  Lu 的研究表明，非死锁问题占了并发问题的大多数，大部分（97%）的非死锁问题是违反了原子性和违反顺序这两种。有些问题需要对应用程序的更深的了解，以及大量代码及数据结构的调整。

(1) 违反原子性（atomicity violation）缺陷

  违反了多次内存访问中预期的可串行性，即代码段本意是原子的，但在执行中并没有强制实现原子性。例如，常见的指针的非空检查和随后的解引用操作应该是原子的，假如另外一个线程将指针置空，配合上不合时宜的上下文切换，由于引用空指针，程序将崩溃。修复方案通常（但不总是）很简单。我们只要给共享变量（上例的指针）的访问加锁，确保每个线程访问时都持有锁。

(2) 错误顺序（order violation）缺陷

  两个内存访问的预期顺序被打破了，即 A 应该在 B 之前执行，但是实际运行中却不是这个顺序。通过强制顺序修复这种缺陷，条件变量（condition variable）就是一种简单可靠的方式。注意，我们通常同时需要一个锁、一个条件变量以及状态的变量（表示真正的条件变化）。

2. 死锁缺陷

  死锁是一种在许多复杂并发系统中出现的经典问题。例如，当线程 1 持有锁 L1，正在等待另外一个锁 L2，而线程 2 持有锁 L2，却在等待锁 L1 释放时，死锁就产生了。当然，死锁的发生也要借助于不合时宜的线程切换才行。以下代码片段就有可能出现死锁：

Thread 1:   Thread 2:
lock(L1);   lock(L2);
lock(L2);   lock(L1);

上面的例子，只有线程1和线程2都用相同的抢锁顺序，死锁就不会发生。那么，为什么还会发生死锁？

• 在大型的代码库里，组件之间会有复杂的依赖。在设计大型系统的锁机制时，必须要仔细地去避免循环依赖导致的死锁。
• 另一个原因是封装（encapsulation）。软件开发者一直倾向于隐藏实现细节，以模块化的方式让软件开发更容易。然而，模块化和锁不是很契合。某些看起来没有关系的接口可能会导致死锁。

产生死锁的条件：

• 互斥：线程对于需要的资源进行互斥的访问（例如一个线程抢到锁）。
• 持有并等待：线程持有了资源（例如已经持有的锁），同时又在等待其他资源（例如，需要获得的锁）。
• 非抢占：线程获得的资源（例如锁），不能被抢占。
• 循环等待：线程之间存在一个环路，环路上每个线程都持有一个资源，而这个资源又是下一个线程要申请的。

  以上 4 个条件任何一个无法满足，死锁就不会发生。预防死锁的 4 个方法：每个策略都设法阻止上面的某一个条件，从而解决死锁的问题。

(1) 预防死锁的方法

• 避免循环等待
    严格的顺序能够避免循环等待，让代码不会产生循环等待，也就不会产生死锁，获取锁时提供一个全序（total ordering）。锁的全序可能很难做到，因此，偏序（partial ordering）可能是一种有用的方法，安排锁的获取并避免死锁。Linux 中的内存映射代码就是一个偏序锁的好例子，代码开头的注释表明了 10 组不同的加锁顺序。
    全序和偏序都需要细致的锁策略的实现和设计。而顺序只是一种约定，程序员很容易忽略，导致死锁。有序加锁需要深入理解代码库，了解各种函数的调用关系，即使一个错误，也会导致死锁。
  Tips: 通过锁的地址来强制锁的顺序。按照锁的地址从高到低，或者从低到高的顺序加锁。就可以保证无论传入参数（锁）是什么顺序，函数都会用固定的顺序加锁：

  void do_something(mutex_t *m1, mutex_t *m2) {
    if (m1 > m2) {  // grab locks in high-to-low address order
        pthread_mutex_lock(m1);
        pthread_mutex_lock(m2);
    } else {
        pthread_mutex_lock(m2);
        pthread_mutex_lock(m1);
    }
    // Code assumes that m1 != m2 (it is not the same lock)
  }
  

• 原子式抢锁
    死锁的持有并等待条件，可以通过原子地抢锁来避免。这需要任何线程在任何时候抢占锁时，先抢到全局的 prevetion 锁，代码保证了在抢锁的过程中，不会有不合时宜的线程切换，从而避免了死锁。这种方法不适合封装，也降低了并发。

lock(prevention);
lock(L1);
lock(L2);
// 一次性抢到了两个锁，要么都发生，要么没发生
...
unlock(prevention);

• 非抢占
    在调用 unlock 之前，都认为锁是被占有的，多个抢锁操作通常会带来麻烦，因为我们等待一个锁时，同时持有另一个锁。很多线程库提供更为灵活的接口来避免这种情况。tyrlock() 函数会尝试获取锁，或者返回 -1 ，表示锁已经被占有。用这一接口实现的无死锁的加锁方法：

top:
    lock(L1);
    if (trylock(L2) == -1) {
        unlock(L1);
        goto top;
    }

  注意，另一个线程可以使用相同的加锁方式，但是不同的加锁顺序（L2然后L1），程序依然不会产生死锁。但会有一个新问题：活锁（livelock）。两个线程有可能一直重复这一序列，又同时抢都抢锁失败。这种情况下，系统一直运行这段代码（因此不是死锁），但是又不会有进展，因此名为活锁。解决方法是可以在循环结束时，先随机等待一个时间，然后再重复整个动作，这样可以降低线程之间的重复互相干扰。由于 goto 语句的局限性，在某些场景下，这种方法才很有效。

• 完全避免互斥
    通常代码都会有临界区，因此很难避免互斥。Herlihy 提出了设计各种无等待（wait-free）数据结构的思想：通过强大的硬件指令，可以构造出不需要锁的数据结构。这也被称为无等待同步，在一些通用库和系统中，包括 Linux，都已经又了一些无等待的实现。

(2) 通过调度避免死锁

  除了死锁预防，某些场景更适合死锁避免（avoidance）。我们需要了解全局的信息，包括不同线程在运行中对锁的需求情况，从而使得后续的调度能够避免产生死锁。这种方案的适用场景很局限。例如，在嵌入式系统中，你知道所有任务以及它们需要的锁。这种方法会限制并发，还会付出性能的代价。因此，通过调度来避免死锁不是广泛使用的通用方案。

(3) 检查和恢复

  一种常用策略是允许死锁偶尔发生，检查到死锁时再采取行动。很多数据库系统使用了死锁检测和恢复技术。
Tips: 不要总是完美。不是所有值得做的事情都值得做好。如果坏事很少发生，并且造成的影响很小，那么我们不应该去花费大量的精力去预防它。

3. 总结

  并发编程中出现的缺陷类型，非死锁缺陷非常常见，包括违反原子性和违反顺序。死锁缺陷，为何会发生，以及如何处理。实践中是自行设计抢锁的顺序，从而避免死锁的发生。无等待的方案也很有希望，但不够通用，设计极其复杂以至于不够实用。也许，最好的解决方案是开发一种新的并发编程模型：在类似 MapReduce 这样的系统中，程序员可以完成一些类型的并行计算，无需任何锁。锁必然带来各种困难，也许我们应该尽可能地避免使用锁，除非确信必须使用。

六. 基于事件的并发

Part III: Persistence（持久性）

一. I/O 设备

关键问题：如何将 I/O 集成进计算机系统中？一般机制与高效策略？

一个典型的系统的架构：CPU 通过某种内存总线（memory bus）或互连电缆连接到系统内存；图像或者其他高性能 I/O 设备通过常规的 I/O 总线（I/O bus）连接到系统。更下面的是外围总线（peripheral bus），比如 SCSI、SATA 或者 USB，将最慢的设备连接到系统，包括磁盘、鼠标及其他类似设备。如下图：

一个标准设备（不是真实存在的），包含两部分重要组件：向系统其他部分展现的硬件接口（interface），让系统软件来控制它的操作；包含设备相关的特定实现的内部结构（internal structure），负责具体实现设备展示给系统的抽象接口。如下图：

一个简化的设备接口包含 3 个寄存器：一个状态（status）寄存器，可以读取并查看设备的当前状态；一个命令（command）寄存器，用于通知设备执行某个具体任务；一个数据（data）寄存器，将数据传给设备或从设备接收数据。操作系统通过读写这些寄存器，从而控制设备的行为。

1. 编程的 I/O (PIO)

操作系统与设备的典型交互（编程的 I/O，programmend I/O, PIO）协议：

while (STATUS == BUSY)
    ;   // wait until device is not busy
Write data to DATA register
Write command to COMMAND register
    (Doing so starts the device and executes the command)
while (STATUS == BUSY)
    ;   // wait until device is done with your request

第一步，轮询（polling）设备，反复读取状态寄存器，等待设备进入可以接收命令的就绪状态。第二步，操作系统下发数据到数据寄存器，如果主 CPU 参与数据移动（就像这个示例协议一样），就称之为编程的 I/O（programmend I/O, PIO）。第三步，写入命令，设备知道数据已经准备好，开始执行命令。最后，操作系统再次通过不断轮询设备，等待并判断设备是否执行完成命令。

2. 中断

中断（interrupt）使得 CPU 不再需要不断轮询设备，而是向设备发出一个请求，让对应进程睡眠，切换执行其他任务。当设备完成了自身操作，会抛出一个硬件中断，引发 CPU 跳转执行操作系统预先定义好的中断服务例程（Interrupt Service Routine, ISR），或更为简单的中断处理程序（interrupt handler），结束之前的请求（比如从设备读取到了数据或者错误码）并且唤醒等待 I/O 的进程继续执行。中断允许计算与 I/O 重叠（overlap），提高了 CPU 利用率。

Tips: 中断并非总是比 PIO 好。额外的中断处理和上下文切换的代价可能会超过其收益，如果设备非常快，那么最好的办法反而是轮询。如果短时间内出现大量的中断，可能会使得系统过载并且引发活锁（例如网络）。另一种基于中断的优化就是合并（coalescing），多次中断可以合并为一次中断抛出，从而降低处理中断的代价。

3. DMA

标准协议使用编程的 I/O 将一大块数据传给设备，CPU 因而负载加重，浪费了时间和算力。如何减少 PIO 的开销？解决方案是 DMA（Direct Memory Access），DMA 引擎是系统中的一个特殊设备，它可以协调完成内存和设备间的数据传递，不需要 CPU 介入。操作系统通过编程告诉 DMA 引擎数据在内存的位置，要拷贝的大小以及要拷贝到哪个设备，在此之后，操作系统就可以处理其他请求了。当 DMA 的任务完成后，DMA 控制器会抛出一个中断来告诉操作系统自己已经完成数据传输。数据的拷贝工作都是由 DMA 控制器完成的。

4. 设备交互

操作系统如何与设备通信？有两种都在使用的方式来实现与设备的交互。

• 用明确的 I/O 指令。这些指令规定了操作系统将数据发送到特定设备寄存器的方法，从而允许构造上文提到的协议。例如，在 x86 上，in 和 out 指令。
• 内存映射 I/O（memory- mapped I/O）。硬件将设备寄存器作为内存地址提供，当需要访问设备寄存器时，操作系统装载（读取）或者存入（写入）到该内存地址，然后硬件会将装载/存入转移到设备上，而不是物理内存。

5. 设备驱动程序

每个设备都有非常具体的接口，如何将它们纳入操作系统？我们希望操作系统尽可能通用。例如文件系统，一个文件系统可以工作在SCSI硬盘、IDE硬盘、USB钥匙串设备等设备之上，这个文件系统不那么清楚对这些不同设备发出读写请求的全部细节。

如何实现一个与设备无关的操作系统？在最底层，操作系统的一部分软件清楚地知道设备如何工作，所有的设备交互的细节都封装在其中 —— 设备驱动程序（device driver）。Linux 的文件系统栈展现了抽象技术如何应用于操作系统的设计与实现：文件系统（包括在其之上的应用程序）完全不清楚它使用的是什么类型的磁盘，它只需要简单地向通用块设备层发送读写请求即可，块设备层会将这些请求路由给对应的设备驱动，然后设备驱动来完成真正的底层操作。

大多数操作系统不得不提供一个通用的接口，使得设备自身的特殊功能无法使用。所有需要插入系统的设备都需要安装对应的驱动程序，所以久而久之，驱动程序的代码在整个内核代码中的占比越来越大。Linux 内核代码的 70% 都是各种驱动程序。

6. 总结

中断、DMA 及相关的思想都是在快速 CPU 和慢速设备之间的权衡结果。操作系统如何与设备交互的基本理解，中断和 DMA 用于提高设备效率，访问设备寄存器的两种方式，I/O 指令和内存映射 I/O 。通过设备驱动程序，操作系统本身如何封装底层细节，从而更容易以设备无关的方式构建操作系统的其余部分。

二. 磁盘驱动器

磁盘驱动器（hard disk drive）一直是计算机系统中持久数据存储的主要形式，文件系统技术的大部分发展都是基于它们的行为。

1. 接口

驱动器由大量扇区（512字节）组成，每个扇区可读可写。在具有 n 个扇区的磁盘上，扇区从 0 到 n-1 编号。因此，我们可以将磁盘视为一组扇区，0 到 n-1 是驱动器的地址空间（address space）。许多文件系统一次读取或写入 4KB（或更多），而在更新磁盘时，驱动器制造商唯一保证的是单个 512 字节的写入是原子的，因此，多扇区操作是可能的，发生不合时宜的掉电，不完整写入也是可能的。大多数磁盘驱动器的客户端会做出一些假设，访问驱动器地址空间内两个彼此靠近的块将比访问两个相隔很远的块更快；访问连续块（即顺序读取或写入）是最快的访问模式，并且通常比任何随机的访问模式快得多。

2. 简单的磁盘驱动器

磁盘可能有一个或多个盘片，盘片（platter）是一个圆形坚硬的表面，通过引入磁性变化永久存储数据。每个盘片有两面，每面都称为表面。所有盘片围绕主轴（spindle）连接在一起，主轴连接到一个电机，以一个恒定（固定）的速度旋转盘片（当驱动器接通电源时）。旋转速率以每分钟转速（Rotations Per Minute, RPM）来测量，典型的现代数值在 7200～15000 RPM 范围内。我们经常会对单次旋转时间感兴趣。一个表面包含数以千计的磁道，紧密排在一起，数百个磁道只有头发的宽度。磁道（track）是每个表面上的同心环，数据在每个表面的同心环（磁道）的扇区上被编码。读取磁盘上的磁性图案，或者让它们发生变化（即写入）的读写过程由磁头（disk head）完成，每个表面上有一个这样的磁头。磁头连接到单个磁盘臂（disk arm）上，磁盘臂在表面上移动，将磁头定位在期望的磁道上。

单磁道加磁头：

单磁道延迟：延迟旋转（rotational delay）：等待期望的扇区旋转到磁头下面。这种等待在现代驱动器中经常发生，并且是 I/O 服务时间的重要组成部分。

现代磁盘有数以百万计的磁道，驱动器必须首先将磁盘臂移动到正确的磁道，通过一个所谓的寻道（seek）过程。寻道，以及旋转，是最昂贵的磁盘操作之一。

三条磁道加上一个磁头（右：带寻道）：

寻道有许多阶段：磁盘臂移动的加速阶段，然后磁盘臂全速移动而惯性滑动，接着磁盘臂减速，最后磁头小心地放置在正确的磁道上。停放时间（settling time）通常不小，例如 0.5~2 ms。

寻道之后，磁盘臂将磁头定位在正确的磁道上，盘片当然已经开始旋转，通过短暂的转动延迟，当扇区经过磁盘磁头时，I/O 的最后阶段——传输（transfer）将发生，数据从表面读取或写入表面。

完整的 I/O 时间图：寻道，等待转动延迟，传输。

许多驱动器采用某种形式的磁道偏斜（track skew），确保即使在跨越磁道边界时，顺序读取也可以方便地服务。顺序读取时，磁头如果需要移动到另一个磁道，所需的块已经旋转过了磁头，则不得不等待整个旋转延迟，才能访问了。因此，扇区往往会偏斜。

另一事实是，外圈磁道比内圈磁道具有更多扇区。多区域（multi-zoned）磁盘驱动器的磁盘被组织成多个区域，区域是表面上连续的一组磁道，每个区域每个磁道具有相同的扇区数量，外圈区域具有比内圈区域更多的扇区。

任何现代磁盘驱动器都有一个重要组成部分 —— 缓存（cache）/磁道缓冲区（track buffer）。该缓存只是少量的内存（通常大约是 8MB 或 16MB），驱动器使用这些内存来保存从磁盘读取或写入磁盘的数据。

在写入时，驱动器应该将数据放入其内存之后，还是实际写入磁盘之后，回报写入完成？前者被称为后写（write back）缓存，后者则称为直写（write through）。后写缓存看起来更快，但可能有危险。

3. I/O 时间

有了一个抽象的磁盘模型，I/O 时间可以表示为三个主要部分之和：

T(I/O) = T(寻道) + T(旋转) + T(传输)

驱动器的 I/O 速率：

R(I/O) = 大小（传输）/ T(I/O)

工作负载：

• 随机（random）工作负载，向磁盘上的随机位置发出小的（例如，4KB）读取请求。
• 顺序（sequential）工作负载，从磁盘连续读取大量的扇区，不会跳过。

有两种类型的磁盘，高性能以及高容量。无论在哪种特性的磁盘驱动器上，随机和顺序工作负载之间的性能差距都很大，出于此，人们往往更愿意购买高端“性能”驱动器，而非低端“容量”驱动器，尽管前者的价格更高。

Tips: 尽可能以顺序方式使用磁盘。如果顺序不可行，至少应考虑大块传输数据，越大越好。小而随机的 I/O，性能将受到显著影响。

4. 磁盘调度

由于 I/O 的高成本，磁盘调度程序如何检查 I/O 请求并决定下一个要调度的请求，是十分重要的。对于磁盘调度，通过估计请求（任务）的查找和可能的旋转延迟，可以知道每个请求将花费多长时间。因此，调度程序将尝试在其操作中遵循 SJF（最短任务优先）的原则（principle of SJF, shortest job first）。

• SSTF: 最短寻道时间优先，按磁道对 I/O 请求队列排序，选择在最近磁道上的请求先完成。主机操作系统无法利用驱动器的几何结构，而是只会看到一系列的块，操作系统可以简单地实现最近块优先（Nearest-Block_First，NBF）。SSTF 会造成饥饿（starvation）问题，对磁头当前所在位置的稳定请求，将忽略对其他磁道的请求。
• 电梯（又称 SCAN 或 C-SCAN）。简单地以跨越磁道的顺序来服务磁盘请求，如同电梯一层一层（磁道）扫过整栋楼（磁盘），从内圈到外圈，再从外圈到内圈。SCAN 和 SSTF 实际上并没有严格遵守 SJF 原则，它们忽视了旋转。
• SPTF: 最短定位时间优先（Shortest Positioning Time First, SPTF）。在现代驱动器中，查找和旋转大致相当，因此 SPTF 是有用的，它提高了性能。操作系统通常不知道磁道边界在哪儿，也不知道磁头当前的位置。因此，SPTF 通常在驱动器内部执行。

在现代系统中，磁盘可以接受多个分离的请求，具有复杂的内部调度程序（可以准确实现 SPTF，磁盘控制器内部，所有相关细节都可以得到）。因此，操作系统调度程序通常会选择它认为最好的几个请求，并将它们全部发送到磁盘。磁盘然后利用其磁头位置和详细的磁道布局信息等内部知识，以最佳可能（SPTF）顺序服务于这些请求。

I/O 合并（I/O merging）可能将相邻块的请求合并为单个两块请求。调度程序执行的所有请求都基于合并后的请求，合并在操作系统级别尤其重要，因为它减少了发送到磁盘的请求数量，从而降低了开销。

在向磁盘发出 I/O 之前，系统应该等待多久？

• 工作保全（work-conserving），有一个磁盘 I/O 便立即向驱动器发出请求。
• 非工作保全（non-work-conserving），等待一段时间，新的和“更好”的请求可能会到达磁盘，从而整体效率提高。当然，决定何时等待以及多久可能会非常棘手。

5. 总结

一个磁盘如何工作的概述，即一个详细的功能模型，使用该模型，在这些令人难以置信的设备之上构建更多有趣的系统。

三. 廉价冗余磁盘阵列（RAID）

如何得到大型、快速、可靠的磁盘，即如何构建一个大型、快速和可道的存储系统？

廉价冗余磁盘阵列（Redundant Array of Inexpensive Disks, RAID）使用多个磁盘一起构成更快、更大、更可靠的磁盘系统。从外部看，RAID 看起来像一个磁盘：一组可以读取或写入的块；在内部，RAID 是一个复杂的庞然大物，由多个磁盘、内存（包括易失性和非易失性）以及一个或多个处理器来管理系统。硬件 RAID 非常像一个计算机系统，专门用于管理一组磁盘。

性能：并行使用多个磁盘大大加快 I/O 时间。
容量：多个磁盘能提供大型数据集。
可靠性：通过某种形式的冗余（redundancy），RAID 可以容许损失一个磁盘并保持运行，就像没有错误一样。
透明性：RAID 对于主机系统看起来就像一个大磁盘。可以简单地用 RAID 存储阵列替换磁盘，而不需要更换一行软件。

1. 接口和 RAID 内部

就像使用单个磁盘一样，RAID 将自己展现为线性的块数组，每个块都可以由文件系统（或其他客户端）读取或写入。当文件系统向 RAID 发出逻辑 I/O 请求时，RAID 内部计算要访问的磁盘（或多少个磁盘）以完成请求，然后发出一个或多个物理 I/O 来执行此操作。这些物理 I/O 的确切性质取决于 RAID 级别。

RAID 系统通常构建为单独的硬件盒，并通过标准连接（例如，SCSI 或 SATA）接入主机。然后，在内部，RAID 相当复杂。它包括一个微控制器，运行固件以指导 RAID 的操作；DRAM 这样的易失性存储器，在读取和写入时缓冲数据块；非易失性存储器，安全地缓冲写入；专用的逻辑电路，执行奇偶校验计算（在某些 RAID 级别中非常有用）。

在很高的层面上，RAID 是一个非常专业的计算机系统：它有一个处理器，内存和磁盘，运行专门用于操作 RAID 的软件。

2. 故障模型和评估

3. RAID 0 级：条带化

没有冗余，可作为性能和容量的优秀上限。RAID 0 级在系统的磁盘上将块条带化（stripe），基本思想是，以轮转方式将磁盘阵列的块分布在磁盘上。这种方法的目的是在对数组的连续块进行请求时，从阵列中获取最大的并行性。将同一行中的块称为条带，下面的块 0、1、2 和 3 在相同的条带中。

上面一个条带仅在每个磁盘上上放一个块（每个大小为 4 KB），此 RAID 阵列的大块大小（chunk size）为 4 KB；下面一个条带在每个磁盘上放置两个 4 KB 块，然后移动到下一个磁盘，此 RAID 阵列的大块大小（chunk size）为 8 KB，条带由 4 个大块（32KB）数据组成。

大块大小影响阵列的性能。小的大块意味着许多文件跨多个磁盘进行条带化，从而增加了对单个文件的读写的并行性，但是跨多个磁盘访问，块的定位时间会增加，整个请求的定位时间由所有驱动器上请求的最大定位时间决定；大的大块减少了这种文件内的并行性，但也减少了定位时间。大多数阵列使用较大的大块大小（例如，64KB）。下面的讨论用一个单独的块，确切的块大小无关紧要。

容量：给定 N 个磁盘，条带化提供 N 个磁盘的有用容量。
可靠性：糟糕，任何磁盘故障都会导致数据丢失。
性能：非常好，并行使用所有磁盘为用户 I/O 请求提供服务。

Tips: RAID 映射问题。给定一个逻辑块来读或写，RAID 如何确切地知道要访问哪个物理磁盘和偏移量？给定逻辑地址 A，RAID 可以使用两个简单的公式计算要访问的磁盘和偏移量：磁盘 = A % 磁盘数；偏移量 = A / 磁盘数。

评估 RAID 性能的两种不同的性能指标：

• 单请求延迟，单个 I/O 请求对 RAID 的满意度。单个逻辑 I/O 操作期间可以存在多少并行性。
• RAID 的稳定吞吐量，即许多并发请求的总带宽。
  • 顺序工作负载，对阵列的请求大部分是连续的。少寻道和旋转，多传输。
  • 随机工作负载，每个请求小，且是到不同磁盘上不同的随机位置。多寻道和旋转，少传输。
  • 假设磁盘在顺序工作负载下以 S MB/s 传输数据，在随机工作负载下以 R MB/s 传输数据。一般来说，S 比 R 大得多。由于大量时间用于传输数据，S 非常接近磁盘的峰值带宽（寻道和旋转成本已经摊销）。

RAID 0 性能分析：

• RAID 0 简单地将单块请求重定向到其磁盘之一，单块请求的延迟应该与单个磁盘的延迟几乎相同。
• 吞吐量
  • 顺序工作负载，等于 N（磁盘数量）乘以 S（单个磁盘的顺序带宽）。
  • 对于大量随机 I/O，使用所有磁盘，从而获得 N * R MB/s 。

4. RAID 1 级：镜像

第一个超越条带化的 RAID 级别称为 RAID 1 级，即镜像。生成系统中每个块的多个副本，每个副本应该放在一个单独的磁盘上，从而容许磁盘故障。

在一个典型的镜像系统中，对于每个逻辑块，RAID 保留两个物理副本。

上面的安排使用镜像对（RAID-1），然后在其上使用条带化（RAID-0），称为 RAID-10。另一种安排是RAID-01，两个大型条带化（RAID-0）阵列，后一个是镜像（RAID-1）。

从镜像阵列读取块时，RAID 可以读取任一副本。写入块时，RAID 必须更新两个副本的数据，以保持可靠性，这些写入可以并行进行。

RAID-1 分析：

• 容量：代价昂贵，镜像的有用容量为 N/2。
• 可靠性：表现良好，容许一个磁盘故障，或最多 N/2 个磁盘故障（依靠运气）。
• 性能：
  • 单个读取请求的延迟与单个磁盘上的延迟相同；写入需要两次物理写入，并行发生则大致等于单次写入的时间，逻辑写入必须等待两个物理写入完成，遭遇两个请求中最差的寻道和旋转延迟，平均而言比单个磁盘略高。
  • 吞吐量：
    • 顺序写入：(N/2)*S，即峰值带宽的一半。
    • 顺序读取：镜像对是顺序的，而读取只需读取一个块，某些块的读取发生在它的镜像块的磁盘上，因而磁盘可能在跳过的块上旋转，因此每个磁盘只提供一半的峰值宽带，即 (N/2) * S 。
    • 随机读取，在所有磁盘上分配读取数据，N * R MB/s 。
    • 随机写入，每个逻辑写入变为两个物理写入，尽管存在并行，许多小型请求的带宽只能达到条带化的一半，（N/2) * R MB/s。获得一半的可用带宽实际上相当不错。

Tips: RAID 一致更新问题（consistent-update problem），任何单个逻辑操作期间必须更新多个磁盘。考虑镜像磁盘阵列，两个磁盘的状态都原子地改变，两者都应该最终成为新版本或者两者都不是。解决此问题的一般方法是，使用某种预写日志（write-ahead log），在做之前首先记录 RAID 将要执行的操作，确保在发生崩溃时，会发生正确的事。通过运行一个恢复（recovery）过程，将所有未完成的事务重新在 RAID 上执行。

5. RAID 4 级：通过奇偶校验节省空间

一种向磁盘阵列添加冗余的不同方法 —— 奇偶校验（parity），试图使用较少的容量，从而克服由镜像系统付出的巨大空间损失，代价便是性能。

RAID-4 系统，对于每一条带数据，添加一个奇偶校验块，用于存储该条带的冗余信息。例如，奇偶校验块 P1 具有从块 4、5、6 和 7 计算出的冗余信息。

奇偶校验：使用异或（XOR）函数计算奇偶性，使得能够承受条带中任何一个块的损失。对于给定的一组比特，如果比特中有偶数个 1 ，则所有这些比特的 XOR 返回 0，如果有奇数个 1，则返回 1，如下表所示。任何一行中的 1 的数量必须是偶数，这是 RAID 必须保持的不变性，以便奇偶校验正确。利用奇偶校验信息从故障中恢复，当某一列丢失了，只需读取该行中的所有其他值（包括奇偶校验位）并重构（reconstruct）正确的答案。计算重构值只需将数据位和奇偶校验位异或，就像开始计算奇偶校验一样。

RAID 在每个磁盘上放置了 4KB（或更大）的块，只需在数据块的每一个位上执行按位异或，将结果放入奇偶校验块的相应位置（位）中，便可将 XOR 应用于一堆块来计算奇偶校验。每个块的每个比特计算奇偶校验，结果放在奇偶校验块中：

RAID-4 分析：

• 容量：N-1
• 可靠性：容许一个磁盘故障，不允许更多。
• 性能：
  • 连续读取可以利用除奇偶校验磁盘以外的所有磁盘，(N-1) * S MB/s。
  • 顺序写入，RAID-4 执行一种简单优化，称为全条带写入（full-stripe write），即通过并行写入一整个条带的数据（包括奇偶块）从而写入数据并更新奇偶校验块，这是 RAID-4 写入磁盘的最有效方式。顺序写入的性能如同全条带写入，带宽也是（N-1) * S MB/s 。
  • 一组一块的随机读取将分布在系统的数据磁盘上，而不是奇偶校验磁盘上，因此，有效性能是（N-1) * R MB/s。
  • 随机写入，奇偶校验块如何重新准确反映条带的正确奇偶校验值？
    • 加法奇偶校验（additive parity），并行读取条带中所有其他数据块，并与新块进行异或，结果是新的校验块，再并行写入新数据和新奇偶校验块到其各自的磁盘。在较大的 RAID 中，需大量读取来计算，导致了减法奇偶校验（subtractive parity）方法。
    • 减法奇偶校验（subtractive parity），比较（写入块）旧数据和新数据，相同则奇偶校验位也将保持相同（新的等于旧的，不变），不同则将旧的奇偶校验位翻转到其当前状态的相反位置。对块中的所有位执行此计算（例如，每个块的 4096 个字节乘以每个字节的 8 位）。
  • 假定使用减法方法做性能分析，对于每次写入，RAID 必须执行 4 次物理 I/O（两次读取和两次写入），对于位于不同磁盘的不同块的数据读写操作可以并行进行，但每个条带的奇偶校验块都位于奇偶校验磁盘。因此，在这种类型的工作负载下，奇偶校验磁盘是瓶颈。称为基于奇偶校验的 RAID 的小写入问题（small-write problem）。因此，即使可以并行访问数据磁盘，奇偶校验磁盘必须为每个逻辑 I/O 执行两次 I/O（一次读取，一次写入）。我们可以通过计算奇偶校验磁盘在这两个 I/O 上的性能来计算 RAID-4 中的小的随机写入的性能，从而得到 (R/2) MB/s，吞吐量很糟糕，向系统添加磁盘也不会改善。
  • 单次读取延迟等同于单个磁盘请求的延迟。
  • 单次写入的延迟需要两次读取，然后是两次写入。读操作（先）和写操作（后）都可以并行进行，因此总延迟大约是单个磁盘的两倍。

6. RAID 5 级：旋转奇偶校验

为解决小写入问题（至少部分解决），RAID-5 推出，它的工作原理与 RAID-4 几乎完全相同，只是它将奇偶校验块跨磁盘驱动器旋转（见下表），以消除 RAID-4 的奇偶校验磁盘瓶颈。

RAID-5 分析：RAID-5 大部分分析与 RAID-4 相同。随机读取性能稍好一点，数据磁盘和奇偶校验磁盘可以并行进行，如果有大量的随机请求，所有磁盘可以保持均匀忙碌，小写入的总带宽将是 (N/4) * R MB/s。4 倍的损失是由于每个 RAID-5 写入仍然产生总计四个 I/O 操作（两次读取和两次写入），这是使用奇偶校验的 RAID 的成本。

除了系统知道自己绝不会执行大写入以外的任何事情，从而完全避免了小写入问题，RAID-5 几乎完全取代了 RAID-4，RAID-4 的构建稍微简单。

7. RAID 比较

使用 T 来表示对单个磁盘的请求所需的时间。

8. 总结

RAID 将大量独立磁盘扩充成更大、更可靠的单一实体，且是透明的。有很多 RAID 级别可供选择，使用的确切 RAID 级别在很大程度上取决于最终用户的优先级。镜像 RAID 是简单的、可靠的，性能良好的，但是容量成本高。RAID-5 从容量角度来看是可靠和更好的，但在工作负载中有小写入时性能很差。为特定工作负载正确地挑选 RAID 并设置其参数（块大小、磁盘数量等），这非常具有挑战性，更多的是艺术而不是科学。

四. 文件和目录

存储虚拟化形成了两个关键抽象：

• 文件（file），一个线性字节数组，每个字节可以读取或写入。每个文件都有一个与其关联的低级名称 —— inode 号（inode number）。在大多数系统中，操作系统不太了解文件的结构（图片还是文本文件），文件系统的责任仅仅是将这些数据永久存储在磁盘上，并确保当你再次请求数据时，得到你原来放在那里的内容。
• 目录（directory)，像一个文件一样，也有一个低级名字（即 inode 号）。目录包含一个（用户可读名字，低级名字）对的列表，将用户可读名称映射到低级名称，列表的每个条目都指向文件或其他目录。通过将目录放入其他目录中，用户可以构建任意的目录树（directory tree，或目录层次结构，directory hierarchy），在该目录树下存储所有文件和目录。

目录层次结构从根目录（root directory）开始（在基于 UNIX 的系统中，根目录就记为 “/”），并使用某种分隔符（separator）来命名后续子目录（sub-directories），直到命名所需的文件或目录。对于一个文件，可以通过它的绝对路径名（absolute pathname）来引用该文件。目录和文件可以具有相同的名称，只要它们位于文件系统树的不同位置。文件名通常包含两部分，以句点分隔，第一部分是任意名称，第二部分通常用于指示文件的类型（type）。这通常只是一个惯例（convention）：一般不会强制名为 main.c 的文件中包含的数据确实是 C 源代码。

文件系统提供了一种方便的方式（上面说明的）来命名我们感兴趣的所有文件。名称在系统中很重要，因为访问任何资源的第一步是能够命名它。在 UNIX 系统中，文件系统提供了一种统一的方式来访问磁盘、U 盘、CD-ROM、许多其他设备上的文件（事实上，还有很多其他东西），都位于单一目录树下。

1. 文件系统接口

(1) 创建文件

创建一个文件，通过 open() 系统调用。在当前工作目录中创建名为 foo 的文件：

    int fd = open("foo", O_CREAT | O_WRONLY | O_TRUNC);

函数 open() 接受一些不同的标志，返回值是文件描述符（file descriptor）。文件描述符只是一个整数，是每个进程私有的，在 UNIX 系统中用于访问文件。一个文件描述符就是一种权限（capability），即一个不透明的句柄，它可以让你执行某些操作。或是将它作为指向文件类型对象的指针，可以调用其他方法来访问文件，如 read() 和 write() 。

(2) 读写文件

Tips: 使用 strace（和类似工具）。strace 工具跟踪程序生成的系统调用，查看参数和返回代码。该工具还接受一些非常有用的参数。

cat 在做什么（使用 stace）：

prompt> strace cat foo
...
open("foo", O_RDONLY | O_LARGEFILE)     = 3
read(3, "hello\n", 4096)                = 6
write(1, "hello\n", 6)                  = 6
hello
read(3, "", 4096)                       = 0
close(3)                                = 0
...
prompt>

每个正在运行的进程已经打开了 3 个文件：标准输入（进程可以读取以接收输入），标准输出（进程可以写入以便将信息显示到屏幕），以及标准错误（进程可以写入错误消息），分别由文件描述符 0、1 和 2 表示。因此，当第一个次打开另一个文件时，它几乎总是文件描述符 3。

read() 的第一个参数是文件描述符（告诉文件系统读取哪个文件），第二个参数指向一个用于放置 read() 结果的缓冲区（strace 显示了这时的读取结果 “hello” ），第三个参数是缓冲区大小。read() 调用本身返回读取的字节数（6，“hello” 中的 5 个字母和一个行尾标记）。

write() 的第一个参数是文件描述符（告诉系统写入哪个文件），接着是写入的缓冲区内容，以及字节数。

读取或写入文件中的特定偏移量，例如从某些文件中的某些随机偏移量中读取数据，使用 lseek() 系统调用。

调用 write() 只是告诉文件系统：请在将来的某个时刻，将此数据写入持久存储。出于性能的原因，文件系统会将这些写入在内存中缓冲（buffer）一段时间，在稍后的时间点，写入将实际发送到存储设备。在 UNIX 中，fsync(int fd) 使进程针对特定文件描述符引用的文件，让文件系统通过强制将所有脏（dirty）数据写入磁盘来响应。一旦所有这些写入完成，fsync() 例程就会返回：

int fd = open("foo", O_CREAT | O_WRONLY | O_TRUNC);
assert(fd > -1);
int rc = write(fd, buffer, size);
assert(rc == size);
rc = fsync(fd);
assert(rc == 0);

(3) 文件重命名

prompt> mv foo bar

mv 命令使用了系统调用 rename(char *old, char *new)，两个参数：文件原来的名称和新名称。rename() 调用提供了原子调用保证，不论系统是否崩溃。对于某些需要对文件状态进行原子更新的应用程序，rename() 非常重要。一个原子文件更新的例程：

int fd = open("foo.txt.tmp", O_WRONLY | O_CREAT | O_TRUNC);
write(fd, buffer, size);    // write out new version of file
fsync(fd);
close(fd);
rename("foo.txt.tmp", "foo.txt");   // 自动将新文件交换到位，同时删除旧版本的文件，从而实现原子文件更新

(4) 获取文件信息

文件系统保存了关于它正在存储的每个文件的大量信息，这些数据称为文件元数据（metadata）。使用 stat() 或 fstat() 系统调用查看特定文件的元数据。这些调用将一个路径名（或文件描述符）添加到一个文件中，并填充一个 stat 结构（包含大量信息）。要查看此信息，可以使用命令行工具 stat：

prompt> stat foo
  File: foo
  Size: 6               Blocks: 8          IO Block: 4096   regular file
Device: fc01h/64513d    Inode: 655858      Links: 1
Access: (0644/-rw-r--r--)  Uid: (    0/    root)   Gid: (    0/    root)
Access: 2021-12-17 17:22:04.977804852 +0800
Modify: 2021-12-17 17:22:04.977804852 +0800
Change: 2021-12-17 17:22:04.977804852 +0800
 Birth: -
prompt>

每个文件系统通常将这种类型的信息保存在一个名为 inode 的结构中。inode 是由文件系统保存的持久数据结构。

(5) 删除文件

程序 rm 使用 unlink() 系统调用。unlinke() 只需要删除文件的名称，并在成功时返回零。

Tips: 小心强大的命令。
prompt> rm * ：其中 * 将匹配当前目录中的所有文件。 prompt> rm -rf *：告诉 rm 以递归方式进入每个目录并删除其内容。

(6) 创建目录

文件系统提供了一组与目录相关的的系统调用来创建、读取和删除目录。注意，永远不能直接写入（write）目录，目录的格式被视为文件系统元数据，所以只能间接更新目录，例如，通过在其中创建文件、目录或其他对象类型。

创建目录用系统调用 mkdir()，同名的 mkdir 程序可以用来创建一个目录。

prompt> strace mkdir foo
...
mkdir("foo", 0777)              = 0
...
prompt>

这样创建的目录被认为是空的，空目录有两个条目：一个引用自身的条目（称为 “.” 目录，一个引用其父目录的条目（称为 “..” 目录）。可以通过向程序 ls 传递一个标志（-a）来查看这些目录。

(7) 读取目录

ls 程序正会读取目录，该程序使用了 opendir()、readdir() 和 closedir() 这三个调用完成工作。使用一个简单的循环就可以一次读取一个目录条目，并打印目录中每个文件的名称和 inode 编号：

int main(int argc, char *argc[]) {
    DIR *dp = opendir(".");
    assert(dp != NULL);
    struct dirent *d;
    while ((d = readdir(dp)) != NULL) {
        printf("%d %s\n", (int)d->d_ino, d->d_name);
    }
    closedir(dp);
    return 0;
}

目录只有少量的信息，基本上只是将名称映射到 inode 号，以及少量其他细节。ls 带有 -l 标志时，需要在每个文件上调用 stat() 以获取每个文件的更多信息。

(8) 删除目录

通过调用 rmdir() 删除目录，程序名称相同是 rmdir。rmdir() 要求该目录在被删除之前是空的（只有 “.” 和 “..” 条目）。

2. 硬链接

在文件系统树中创建条目的新方法：link() 系统调用，两个参数：一个旧的路径名和一个新的路径名。当你将一个新的文件名“链接”到一个旧的文件名时，实际上创建了另一种引用同一个文件的方法。命令行程序 ln 用于执行此操作。

prompt> echo hello > file
prompt> cat file
hello
prompt> ln file file2
prompt> cat file2
hello

link 只是在要创建链接的目录中创建了另一个名称，并将其指向原有文件的相同 inode 号。该文件不以任何方式复制，现在只是有了两个人类可读的名称（file 和 file2），都指向同一个文件。

rm 使用 unlink() 的由来：创建一个文件时，首先构建了一个结构 inode 跟踪几乎所有关于文件的信息，包括其大小、文件块在磁盘上的位置等等，然后将人类可读的名称链接到该文件，并将该链接放入目录中。为了从文件系统中删除一个文件，调用 unlink()，因为当文件系统取消链接文件时，它检查 inode 号中的引用计数（reference count）。该引用计数（也叫链接计数，link count）允许文件系统跟踪有多少不同的文件名已链接到这个 inode。调用 unlink() 会删除人类可读的名称（正在删除的文件）与给定 inode 号之间的“链接”，并减少引用计数。只有当引用计数达到零时，文件系统才会释放 inode 和相关数据块，从而真正“删除”该文件。可以使用 stat() 来查看文件的引用计数。

3. 符号链接

硬链接的局限：

• 不能创建目录的硬链接（因为担心会在目录树中创建一个环）。
• 不能硬链接到其他磁盘分区中的文件（因为 inode 号会在特定文件系统中是唯一的，而不是跨文件系统）。

因此，人们创建了一种新型链接 —— 符号链接（symbolic link），有时称为软链接（soft-link）。创建软链接，使用相同的程序 ln，但使用 -s 标志：

prompt> echo hello > file
prompt> ln -s file file2
prompt> cat file2
hello

软链接几乎与硬链接相同，第一个区别是符号链接本身实际上是一个不同类型的文件（除了常规文件和目录，符号链接是文件系统知道的第三种类型），对符号链接运行 stat 揭示一切：

prompt> stat file
 ... regular file ...
prompt> stat file2
 ... symbolic link ...

运行 ls 程序，它输出的长格式的第一个字符，常规文件最左列中的第一个字符是 “-”，目录是 “d”，软链接是 “l”。符号链接的大小在于形成符号链接的方式，即将链接指向文件的路径名作为链接文件的数据。如果链接到更长的路径名，链接文件会更大。而这种创建符号链接的方式，有可能造成所谓的悬空引用（dangling reference），符号链接与硬链接完全不同的地方，删除名为 file 的原始文件会导致符号链接指向不再存在的路径名：

prompt> rm file
prompt> cat file2
cat: file2: No such file or directory

4. 创建并挂载文件系统

如何从许多底层文件系统组建完整的目录树：先制作文件系统，然后挂载它们，使其内容可以访问。

• mkfs（发音为 “make fs”），以一个设备（例如磁盘分区，例如 /dev/sdal）作为输入，加上一种文件系统类型（例如 ext3）。它在该磁盘分区上写入一个空文件系统，从根目录开始。创建了文件系统，就需要在统一的文件系统树中进行访问。
• mount 程序使用底层的系统调用 mount() 完成实际工作。以现有目录作为目标挂载点（mount point），本质上是将新的文件系统粘贴到目录树的这个点上。

prompt> mount -t ext3 /dev/sdal /home/users

有一个未挂载的 ext3 文件系统，存储在设备分区 /dev/sdal 中，在挂载点 /home/users 上挂载此文件系统。路径名 /home/users/ 现在指的是新挂载目录的根。

mount 将所有文件系统统一到一棵树中，而不是拥有多个独立的文件系统，这让命名统一而且更方便。

运行 mount 程序可以查看系统上挂载的内容，以及在哪些位置挂载。它会展示许多不同的文件系统，包括 ext3（标准的基于磁盘的文件系统）、proc文件系统（用于访问当前进程信息的文件系统）、tmpfs（仅用于临时文件的文件系统）和 AFS（分布式文件系统）。它们都“粘”在一台机器的文件系统树上。

五. 文件系统实现

一个简单的文件系统实现 VSFS（Very Simple File System，简单文件系统），典型 UNIX 文件系统的简化版本，用于介绍一些基本磁盘结构、访问方法和各种策略。文件系统是纯软件，只需要注意设备特性，以确保文件系统运行良好。

如何实现简单的文件系统？磁盘上需要什么结构？它们需要记录什么？它们如何访问？

文件系统的数据结构（data structure）和访问方法（access method）是关于它如何工作的良好心智模型，通过理解这两个方面，来理解文件系统的基本工作原理。

1. 整体组织

磁盘需要分块（block），简单的文件系统只使用一种块大小。构建文件系统的磁盘分区：一系列块，每块大小 4 KB，在大小为 N 个 4 KB 块的分区中，这些块的地址为从 0 到 N-1 。假设一个非常小的磁盘，只有 64 块，VSFS 文件系统在这个磁盘上的数据结构的整体组织：

任何文件系统中的大多数空间都是（并且应该是）用户数据。用于存放用户数据的磁盘区域称为数据区域（data region），例如 64 个块的最后 56 个。

文件系统必须记录每个文件的信息，该信息是元数据（metadata）的关键部分，并且记录诸如文件包含哪些数据块（在数据区域中）、文件的大小，其所有者和访问权限、访问和修改时间以及其他类似信息的事情。文件系统通常有一个名为 inode 的结构存储这些信息。为了存放 inode，在磁盘上需留出一些空间，称为 inode 表（inode table），它只是保存了一个磁盘上 inode 的数组。例如，64 个块中的 5 块（假设每个 inode 有 256 字节，一个 4KB 块可以容纳 16 个 inode，上面的文件系统包含 80 个inode）。在更大磁盘上的相同文件系统可以简单地分配更大的 inode 表，从而容纳更多文件。

记录 inode 块或数据块是空闲还是已分配，需要一种分配结构（allocation structure），这是所有文件系统中必需的部分。可以使用空闲列表，指向第一个空闲块，它又指向下一个空闲块，依此类推。一种简单而流行的结构 —— 位图（bitmap），一种用于数据区域（数据位图，data bitmap），另一种用于 inode 表（inode bitmap）。位图是一种简单的结构：每个位用于指示相应的对象/块是空闲（0）还是正在使用（1）。

S 表示超级块（superblock），包含关于该特定文件系统的信息，包括例如文件系统中有多少个 inode 和数据块（80 和 56）、inode 表的开始位置（块3）、一些幻数标识文件系统类型（VSFS）。

在挂载文件系统时，操作系统将首先读取超级块，初始化各种参数，然后将该卷添加到文件系统树中。当卷中的文件被访问时，系统就会知道在哪里查找所需的磁盘上的结构。

2. 文件组织：inode

inode 是文件系统中使用的通用名称，用于描述保存给定文件的元数据的结构。它是 index node（索引节点）的缩写，inode 拥有索引文件数据块的功能。 inode 号（inumber）用于索引磁盘上的 inode 数组，以便查找该 inode 号对应的 inode，进一步通过 inode 找到文件对应的数据块。

每个 inode 都由一个数组（称为 inumber）隐式引用，即之前的文件的低级名称。在 VSFS（和其他简单的文件系统）中，给定一个 inumber ，能够直接计算磁盘上相应节点的位置。

读取 inumber（32），首先计算 inode 区域的偏移量（32 * sizeof(inode_t，即 32 * 256 = 8192），将它加上磁盘 inode 表的起始地址（inodeStartAddr = 12 KB），从而得到 inode 块的正确字节地址：20 KB。磁盘不是按字节寻址的，而是由大量可寻址扇区组成，通常是 512 字节，因此文件系统将向节点 40（20KB/512) 发出读取请求。inode 块的扇区地址 iaddr 计算如下：

blk     = (inumber * sizeof(inode_t)) / blockSize;
sector  = ((blk * blockSize) + inodeStartAddr) /sectorSize;

每个 inode 中实际是所有关于文件的信息，称为元数据。文件系统除了纯粹的用户数据外，其他任何信息通常都称为元数据。下面是 ext2 的 inode 的例子：

元数据中包括其数据块驻留在磁盘上的位置的信息（如某种类型的指针）。设计 inode 时，最重要的决定之一是它如何引用数据块的位置。一种简单的方法是在 inode 中有一个或多个直接指针（磁盘地址）指向属于该文件的磁盘块。对于一个非常大的文件（大于直接指针数乘以块大小），这种方法就有局限了。

为了支持更大的文件，在 inode 中引入了不同的结构 —— 间接指针（indirect pointer），指向包含更多指针的块，其中每个指针指向用户数据。inode 可以有一些固定数量的直接指针（例如 12 个）和一个间接指针。如果文件变得足够大，则会分配一个间接块（来自磁盘的数据块区域），并将 inode 的间接指针设置为指向它。文件可以增长到 (12+1024)*4KB = 4144 KB。

希望支持更大的文件，只需添加另一个指向 inode 的指针：双重间接指针（double indirect pointer），指向一个包含间接块指针的块，每个间接块指针指向间接块，每个间接块都包含指向数据块的指针。文件可以增长到 (12 + 1024 + 1024^2)*4KB ，支持超过 4 GB 大小的文件。当然，还有三重间接指针（triple indirect pointer）。

许多文件系统使用多级索引，包括常用的文件系统，如 Linux ext2 和 ext3，NetApp 的 WAFL，以及原始的 UNIX 文件系统。其他文件系统，包括 SGI XFS 和 Linux ext4，使用范围而不是简单的指针。

为什么使用这样的不平衡树（这些指针合起来）？一个真相是，大多数文件很小。这种不平衡的设计反映了这样的现实。因此，使用少量的直接指针（12 是一个典型数字），inode 可以直接指向 48 KB 的数据，需要一个（或多个）间接块来处理较大的文件。

Tips:基于范围（extent）的方法。范围就是一个磁盘指针加一个长度（以块为单位），通常允许多个范围，从而在文件分配期间给予文件系统更多的自由。

Tips:基于链接的方法。在一个 inode 中，不是有多个指针，只需要一个，指向文件的第一个块，在数据块的末尾添加另一个指针，以支持大文件。链接式文件分配对于某些工作负载表现不佳（例如随机访问），一些系统在内存中保留链接信息表，即所谓的文件分配表（File Allocation Table, FAT）。

inode 只是一个数据结构，在 inode 设计的空间中存在许多其他的可能性。

3. 目录组织

在 VSFS 中，一个目录基本上只包含一个二元组（条目名称，inode 号）的列表。对于给定目录中的每个文件或目录，目录的数据块中都有一个字符串和一个数字，对于每个字符串，可能还有一个长度（假定采用可变大小的名称）。

假定目录 dir（inode 号是 5）中有 3 个文件（foo、bar 和 foobar），它们的 inode 号分别是 12、13 和 24。dir 在磁盘上的数据可能如下：

每个条目都有一个 inode 号，记录长度（名称的总字节数加上所有的剩余空间），字符串长度（名称的实际长度），最后是条目的名称。每个目录有两个额外的条目：.（点）和 ..（点点）。

删除一个文件（例如调用 unlink()）会在目录中间留下一段空白空间，有一些方法来标记它（例如，用一个保留的 inode 号，比如 0）。这种删除是使用记录长度的一个原因：新条目可能会重复使用旧的、更大的条目，从而在其中留有额外的空间。

文件系统将目录视为特殊类型的文件。因此，目录有一个 inode，位于 inode 表中的某处（inode 表中的 inode 标记为 “目录” 的类型字段，而不是 “常规文件” ）。该目录具有由 inode 指向的数据块（也可能是间接块），这些数据存在于简单文件系统的数据区域中，磁盘结构因此保持不变。

这个线性的简单目录列表并不是存储这些信息的唯一方法，任何数据结构都是可能的。例如，XFS 以 B 树形式存储目录，使文件创建操作快于使用简单列表的文件系统，因为后者必须扫描其中的条目（确保文件名在创建之前未被使用）。

4. 空闲空间管理

文件系统必须记录哪些 inode 和数据块是空闲的，哪些不是，以便分配新文件或目录时找到空间。空闲空间管理（free space management）对于所有文件系统都很重要。在 VSFS 中，使用两个简单的位图来完成这个任务。

创建文件需要为该文件分配一个 inode，文件系统通过位图（inode 位图）搜索一个空闲的内容，并将其分配给该文件。文件系统必须将 inode 标记为已使用（用1），并最终用正确的信息更新磁盘上的位图（记住，位图存储在磁盘上）。分配数据块时会发生类似的一组活动（数据位图）。

预分配（pre-allocation）策略：一些 Linux 文件系统（比如 ext2 和 ext3）在创建新文件并需要数据块时，会寻找一系列空闲块，然后将它们分配给新创建的文件，文件系统因此保证文件的一部分将在磁盘上并且是连续的，从而提高性能。

Tips:空闲空间管理。位图只是其中一种，一些早期的文件系统使用空闲列表，其中超级块的单个指针保持指向第一个空闲块，在该块内部保留一个空闲指针，从而通过系统的空闲块形成列表。在需要块时，使用头块并相应地更新。现代文件系统使用更复杂的数据结构。例如，SGI 的 XFS 使用某种形式的 B 树。

5. 访问路径：读取和写入

理解读取或写入文件的操作过程（访问路径）是开发人员理解文件系统如何工作的第二个关键。假设文件系统已经挂载，因此超级块已经在内存中，其他所有内容（如 inode、目录）仍在磁盘上。

从磁盘读取：

当发出一个 open("/foo/bar", O_RDONLY) 调用时：

• 文件系统遍历路径名，找到文件 bar 的 inode。所有遍历都是从文件系统的根开始，即根目录。
• 第一次读取 根目录的 inode（在挂载文件系统时，文件系统已经知道根的 inode 号，在大多数 UNIX 文件系统中，根的 inode 号为 2）。因此，文件系统会读入 inode 号 2 的块（第一个 inode 块）。
• inode 被读入，文件系统在其中查找指向数据块的指针，数据块包含根目录的内容。文件系统使用这些磁盘上的指针来读取目录内容，寻找 foo 条目（通过读入一个或多个数据块），文件系统找到 foo 的 inode 号。
• 递归遍历路径名，直到所需的 inode 号，即最后找到 bar 的 inode 号。open() 的最后一步将 bar 的 inode 读入内存，然后文件系统进行最后的权限检查，在每个进程的打开文件表中，为此进程分配一个文件描述符，并将它返回给用户。注意，open() 并未访问要打开文件的数据区域，访问了 inode 块和inode 数据块，读取 inode 到内存。

打开后，程序可以发出 read() 调用从文件中读取。第一次读取（除非 lseek() 已被调用，则在偏移量 0 处）将在文件的第一块中读取，查阅 inode 以查找这个块的位置。它也会用新的最后访问时间更新 inode 。读取将进一步更新此文件描述符在内存中的打开文件表，更新文件偏移量，以便下一次读取会读取第二个文件块，等等。最后文件会被关闭，文件描述符被释放，关闭没有磁盘 I/O 发生。

Tips：读取不会访问分配结构（例如，位图）。

open() 导致的 I/O 量与路径名的长度成正比。对于路径中每个增加的目录，我们都必须读取它的 inode 及其数据，通过 inumber 找到 inode，再找到数据块（它们都在磁盘上）。更糟糕的是，对于大型目录，可能需要读取很多数据块才能找到所需的条目。

文件读取时间线（向下时间递增），不会读取位图：

写入磁盘：

写入文件类似读取过程。首先，文件必须打开，其次，应用程序可以发出 write 调用以用新内容更新文件，也可能会分配一个块（除非块被覆写）。最后，关闭该文件。

当写入一个新文件时，每次写入操作不仅需要将数据写入磁盘，还必须首先决定将哪个块分配给文件，从而相应地更新磁盘的其他结构（例如数据位图和 inode）。因此，每次写入文件在逻辑上会导致 5 个 I/O：

• 一对读取和更新 inode
• 一对读取和更新数据位图
• 一次写入真正的数据块本身

创建文件，文件系统不仅要分配一个 inode，还要在包含新文件的目录中分配空间：

• 一对读取和写入 inode 位图（查找空闲 inode 将其标记为已分配）
• 一个写入新的 inode 本身（初始化它）
• 一个读取和写入目录 inode（更新它）
• 一个写入目录的数据（将文件的高级名称链接到它的 inode 号）

如果目录需要增长以容纳新条目，则还需要额外的 I/O（即数据位图和新目录块）。

一个具体的例子，创建 file/foo/bar，并向它写入 3 个块：

6. 缓存和缓冲

关键问题：如何降低文件系统 I/O 成本。打开、读取或写入文件会产生大量的 I/O 操作，分散在磁盘上。大多数文件系统积极使用系统内存（DRAM）来缓存重要的块。

早期的文件系统引入了一个固定大小的缓存（fixed-size cache）来保存常用的块（LRU 及不同变体策略会决定哪些块保留在缓存中），这个固定大小的缓存通常会在启动时分配，大约占总内存的 10%。

现代文件系统采用动态划分（dynamic partitioning）方法，将虚拟内存页面和文件系统页面集成到统一页面缓存中（unified page cache），在虚拟内存和文件系统之间更灵活地分配内存，具体取决于在给定时间哪种内存需要更多的内存。

缓存对文件打开、读取和写入都有影响。第一次打开产生的大量 I/O 流量在随后文件打开的同一文件，将会命中缓存。虽然，写入流量必须进入磁盘才能实现永久持久，写缓冲（write buffering）仍有许多优点。大多数现代文件系统将写入在内存中缓冲 5～30s，将内存写入时间延长，则可以通过批处理、调度甚至避免写入，提高性能，尽管数据可能存在丢失。

为了避免由于缓冲写入导致的意外数据丢失，通过调用 fsync()，使用绕过缓存的直接 I/O（direct I/O）接口，或者使用原始磁盘（raw disk）接口并完全避免使用文件系统。

Tips: 了解耐用性/性能权衡。存储系统通常会向用户提供耐用性/性能折中（数据安全和性能）。

7. 总结

文件系统设计的极好方面是它的自由。接下来的章节利用这种自由优化文件系统的某些方面。

六. 局部性和快速文件系统

1. 老 Unix 文件系统

Ken Thompson 为 Unix 编写了第一个文件系统，它的数据结构在磁盘上看起来像这样：

超级块（S）包含有关整个文件系统的信息：卷的大小、有多少 inode、指向空闲列表块的头部的指针等等。磁盘的 inode 区域包含文件系统的所有 inode 。老文件系统简单，支持文件系统试图提供的基本抽象：文件和目录层次结构。

问题：性能不佳。

• 它将磁盘当成随机存取内存，数据遍布各处，保存数据的介质是磁盘，具有实实在在的、昂贵的定位成本。例如，文件的数据块通常离其 inode 非常远，导致昂贵的寻道。
• 空闲空间没有得到精心管理，文件系统会变得非常碎片化（fragmented），可能分配碎片化的空间给文件，使得在磁盘上来回访问逻辑上连续的文件，从而大大地降低了性能。（插一句：磁盘碎片整理工具重新组织磁盘数据以连续放置文件，并为让空闲空间成为一个或几个连续区域，移动数据，然后重写 inode 等以反映变化。）
• 原始块大小太小（512字节）。虽然减少了内部碎片问题，但是每个块需要一个定位开销，因此传输不佳。

关键问题：如何组织磁盘数据以提高性能？

2. 快速文件系统（Fast File System, FFS）

让文件系统的结构和分配策略具有“磁盘意识”，从而提高性能。

（1）组织结构

第一步，更改磁盘上的结构。FFS 将磁盘划分为一些分组，称为柱面组（cylinder group，一些现代文件系统，如 Linux ext2 和 ext3，称为块组，即 block group）。一个具有柱面组的磁盘：

这些分组是 FFS 用于改善性能的核心机制。FFS 需要能够在每个组中分配文件和目录，每个组看起来像这样：

一个柱面组的构成：

• 一个超级块（super block）副本，出于可靠性原因（例如，如果一个被损坏或划伤，仍然可以通过使用其中一个副本来挂载和访问文件系统）。
• inode 位图（inode bitmap, ib）和数据位图（data bitmap, db），记录该组的 inode 和数据块是否已分配。不同于旧文件系统的空闲列表，位图很容易找到大块可用空间并将其分配给文件，这可能会避免旧文件系统中空闲列表的某些碎片问题，因此是管理文件系统中可用空间的绝佳方法。
• inode 和数据块区域，就像之前的 VSFS 一样。每个柱面组的大部分都包含数据块。

Tips: FFS 文件创建。假设用户创建了一个新文件 /foo/bar.txt，长度为一个块（4KB）。inode 位图和新分配的 inode 都将写入磁盘，数据位图和数据块也将写入磁盘。因此，至少需要四次写入（在发生写入之前，可以在存储器中缓冲一段时间）。同时，还得更新目录，将文件放在文件系统层次结构中。此更新可能放入 foo 现有数据块，或者需要分配新块（包含关联的数据位图），还必须更新 foo 的 inode ，以反映目录的新长度及更新时间字段。

（2）策略：如何分配文件和目录

有了这个分组结构，FFS 必须决定，如何在磁盘上放置文件和目录以及相关的元数据，以提高性能：相关的东西放一起。

一些简单的放置推断方法：

• 目录的放置：找到分配数量少的柱面组（跨组平衡目录）和大量的自由 inode（随后能够分配一堆文件），并将目录数据和 inode 放在该分组中。
• 文件的放置：
  • 确保（在一般情况下）将文件的数据块分配到与其 inode 相同的组中，从而防止 inode 和数据之间的长时间寻道（如在老文件系统中）。
  • 将位于同一目录中的所有文件放在它们所在目录的柱面组中。

这些推断方法并非基于对文件系统流量的广泛研究，而是建立在良好的老式常识基础之上。目录中的文件通常一起访问（例如编译一堆文件然后将它们链接到单个可执行文件中）。确保相关文件之间的寻道时间很短，FFS 通常会提高性能。

例外：大文件的放置：

• 将一定数量的块分配到第一个块组（例如，12 个块，或 inode 中可用的直接指针的数量），
• 将文件的下一个 “大” 块（即第一个间接块指向的那些部分）放在另一个块组中，
• 然后文件的下一个块放在另一个不同的块组中，依此类推。

没有大文件例外，大文件将填满它首先放入的块组（也可能填满其他组），妨碍了随后的“相关”文件放置在该块组内，因此可能破坏文件访问的局部性。单个文件会将其所有块放入磁盘的一部分：

有了大文件例外，文件以大块形式分布在磁盘上：

在磁盘上分散文件块会损害性能，特别是在顺序文件访问时。我们可以通过仔细选择大块大小，来改善这一点。如果大块大小足够大，大部分时间仍然花在从磁盘传输数据上（毕竟大的大小传输时间久），而在大块之间寻道的时间相对较少。每次开销（寻道）做更多工作（寻道后可以传输的大小），从而减少开销，即计算机系统中的常用技术 —— 摊销（amortization）。

FFS 没有使用这种类型的计算来跨组分布大文件，而是采用基于 inode 本身结构的一种简单方法：前 12 个直接块与 inode 放在同一组中，每个后续的间接块，以及它指向的所有块都放在不同的组中。

随着磁盘驱动器的传输速率的提高，驱动器的机械方面与寻道相关（磁盘臂速度和旋转速度）却改善缓慢。这意味着，随着时间推移，机械成本变得相对昂贵，因此，为了摊销所述成本，必须在寻道之间传输更多数据。

（3）关于 FFS 的其他几件事

• 许多小文件（2KB左右）使用 4KB 块，虽然有利于传输数据，却有内部碎片问题。FFS 引入子块（sub-block），有 512 字节，文件系统可以将它们分配给文件。随着文件增长，文件系统将继续为其分配 512 字节的子块，直到它达到 4KB 数据。此时，FFS 将找到一个 4KB 块，将子块复制到其中，并释放子块以备小文件将来使用。但是这个过程效率低下，FFS 通常通过修改 libc 库，该库将缓冲写入，然后以 4KB 块的形式将它们发送到文件系统，从而在大多数情况下完全避免子块的特殊情况。
• 针对性能进行优化的磁盘布局。
  当文件放在磁盘的连续扇区上时，FFS 顺序读取期间，当发出一个请求，读取块 0 ，当读取完成后，FFS 向块 1 发出读取，但为时已晚：块 1 已在磁头下方旋转，现在对块 1 的读取将导致完全旋转（一圈）。FFS 使用不同的布局解决这个问题，通过每次跳过个别块，在下一块经过磁头之前，FFS有足够的时间发出请求。参数化 —— FFS 会找出磁盘的特定性能参数，并利用它们来确定准确的交错布局方案。
  FFS的标准与参数化放置：
  
  现代磁盘更加智能：它们在内部读取整个磁道并将其缓冲在内部磁盘缓存中（通常称为磁道缓冲区，track buffer）。然后，在对磁道的后续读取中，磁盘就从其高速缓存中返回所需数据。因此，文件系统不再需要担心这些低级细节。
• 引入长文件名、符号链接、原子化的重命名（rename()）操作。

3. 小结

所有现代文件系统都要感谢 FFS 的主要经验：将磁盘当作磁盘。

七. 崩溃一致性：FSCK 和日志

文件系统管理一组数据结构以实现预期的抽象：文件、目录，以及所有其他元数据，以支持从文件系统获得的基本抽象。与内存中的数据结构不同，文件系统数据结构必须持久。一个主要挑战在于，如何在出现断电（power loss）或系统崩溃（system crash）的情况下，更新持久数据结构。

考虑一个例子：将单个数据块附加到原有文件中，即向文件追加内容，添加一个新数据块。因此，必须更新 3 个磁盘上的结构：inode（必须指向新块，并且由于追加而具有更大的大小），新数据块，以及新版本的数据位图（表示新数据块已被分配）。

要实现这样的磁盘数据结构的转变，文件系统必须对磁盘执行 3 次单独写入，分别针对 inode，位图和数据块。如果发生崩溃，磁盘的这些更新将被干扰。由于存在许多不同的崩溃场景，因此，磁盘文件系统映像可能出现许多不同的问题：在文件系统数据结构中可能存在不一致性；可能有空间泄漏；可能将垃圾数据返回给用户，等等。

理想的做法是将文件系统从一个一致状态（在文件被追加之前），原子地移动到另一个状态（在 inode、位图和新数据块被写入磁盘之后）。但是磁盘一次只提交一次写入，而这些更新之间可能会发生崩溃或者断电。我们将这个问题称为崩溃一致性问题（crash-consistency problem，也可以称为一致性更新问题，consistent-update problem）。

1. FSCK

解决方案 1：文件系统检查程序（file system chechker）。早期文件系统采用的简单方法来处理崩溃一致性：让不一致的事情发生，然后再修复它们（重启时）。Unix 工具 fsck，用于查找这些不一致并修复它们。在不同的系统上，存在检查和修复磁盘分区的类似工具。这种方法无法解决所有问题，只是确保文件系统元数据内部一致。例如，文件系统看起来一致，但是 inode 指向垃圾数据。

工具 fsck 在许多阶段运行，它在文件系统挂载并可用之前运行（fsck 假定在运行时没有其他文件系统活动正在进行）。一旦完成，磁盘上的文件系统应该是一致的，因此可以让用户访问。

构建有效工具的 fsck 需要复杂的文件系统知识，而且 fsck 的性能很糟糕，对于非常大的磁盘卷，扫描整个磁盘，以查找所有已分配的块并读取整个目录树。尽管只修复更新 3 个块期间出现的问题，也是如此，这是非常昂贵的。

2. 日志

解决方案 2：日志（journaling，或预写日志，write-ahead logging），从数据库管理系统的世界中借鉴的一个想法。许多现代文件系统使用这个想法，包括 Linux ext3 和 ext4、reiserfs、IBM 的 JFS、SGI 的 XFS 和 Windows NTFS。

基本思路：在更新磁盘时，在覆写结构之前，写入一点小注记（在磁盘的其他地方，一个众所周知的位置），描述将要做的事情。写下这个注记就是“预写”部分，我们把它写入一个结构，并组织成“日志”。在更新（覆写）正在更新的结构期间发生崩溃时，能够返回并查看注记，然后重试。通过设计，日志功能在更新期间增加了一些工作量，从而大大减少了回复期间所需的工作量。

Linux ext3 ，一种流行的日志文件系统，它的大多数磁盘上的结构与 Linux ext2 相同（磁盘被分成块组，每个块组都有一个 inode 和数据位图以及 inode 和数据块），新的关键结构是日志本身，它占用分区内或其他设备上的少量空间。

ext2 文件系统（没有日志）看起来像这样：

带有日志的 ext3 文件系统（假设日志放在同一个文件系统映像中，虽然有时将它放在单独的设备上，或作为文件系统中的文件）：

（1）数据日志

数据日志（data journaling）作为 Linux ext3 文件系统的一种模式提供。假设进行标准的更新，将 inode、位图和数据块写入磁盘，在将它们写入最终磁盘位置之前，先将它们写入日志。这就是日志中样子：

事务开始（TxB）包含有关此次更新的信息，以及某种事务标识符（transaction identifier, TID）。中间的三个块只包含块本身的确切内容，这被称为物理日志（physical logging），因为我们将更新的确切物理内容放在日志中（另一种想法，逻辑日志，logical logging）。最后一个块（TxE）是该事务结束的标记，也会包含 TID。

一旦事务安全地存于磁盘上，就可以覆写文件系统中的旧结构了。这个过程称为加检查点（checkpointing)，让文件系统与日志中即将进行的更新一致，将 I[v2]、B[v2] 和 Db 写入其磁盘位置。

在写入日志期间发生崩溃，这是可能的，为避免该问题，文件系统分两步发出事务写入。首先，将除 TxE 块之外的所有块写入日志，同时发出这些写入。当这些写入完成，文件系统会发出 TxE 块的写入，从而使日志处于最终的安全状态。磁盘保证任何 512 字节写入都会发生或不发生（永远不会半写）。因此，应使 TxE 块成为一个 512 字节的块。当 TxE 的原子写入完成，则写入日志完成。

Tips: 强制写入磁盘。为了在两次磁盘写入之间强制执行顺序，现代文件系统必须采取一些额外的预防措施。磁盘中存在写入缓存（有时称为立即报告，immediate reporting），无法保证写入之间的顺序。一种方法是禁用缓冲。然后，更现代的系统采取额外的预防措施，发出明确的写入屏障（write barrier）。这样的屏障，当它完成时，能确保在屏障之前发出的所有写入，先于屏障之后发出的所有写入到达磁盘。

Tips: 优化日志写入。如前所述，写入事务中途存在等待，通常还会产生额外的旋转（日志到数据区域）。等待的目的不就是为了避免中途的崩溃发生，而崩溃发生不就会使得日志内容出错嘛。一个简单的想法：将事务写入日志时，在开始和结束块中包含日志内容的校验和。因此，文件系统可以立即写入整个事务，而不会产生等待。如果在恢复期间，文件系统发现计算的校验和与事务中存储的校验和不匹配，则可以断定在写入事务期间发生了崩溃，从而丢弃文件系统更新。

如果崩溃发生在事务被安全地写入日志之前（例如，TxE 写入完成之前），简单地跳过待执行的更新。如果在事务已提交到日志之后，在加检查点完成之前发生崩溃，则文件系统按如下方式恢复更新：系统引导时，文件系统恢复过程将扫描日志，并查到已提交到磁盘的事务。然后，这些事务被重放（replayed，按顺序），文件系统再次尝试将事务中的块写入它们最终的磁盘位置。这种形式的日志称为重做日志（redo logging），是最简单的形式之一。

为避免对同一块的多个事务提交，所造成重复写入相同块的额外磁盘流量。文件系统不会一次一个地向磁盘提交每个更新，而是将所有更新缓冲到全局事务中，仅将数据标记为脏，并将它们添加到块列表中，形成当前的事务。当最后应该将这些块写入磁盘时，会提交包含所有更新的单个全局事务。因此，通过缓冲更新，文件系统在许多情况下可以避免对磁盘的过多的写入流量。

日志文件系统将日志视为循环数据结构，一遍又一遍地重复使用。一旦事务被加检查点，文件系统应该释放它在日志中占用的空间，允许重用日志空间。有很多方法可以达到这个目的。例如，在日志超级块（journal superblock）中标记日志中最旧和最新的事务，所有其他空间都是空闲的：

日志超级块（不要与主文件系统的超级块混淆）记录了足够的信息，以了解哪些事务尚未加检查点，从而减少了恢复时间，并允许以循环的方式重新使用日志。

最终的数据日志协议：

1. 日志写入：将事务的内容（包括 TxB 和更新内容）写入日志，等待这些写入完成。
2. 日志提交：将事务提交块（包括 TxE）写入日志，等待写完成，事务被认为已提交（committed）。
3. 加检查点：将更新内容写入其最终的磁盘位置。
4. 释放：一段时间后，通过更新日志超级块，在日志中标记该事务为空闲。

（2）元数据日志

数据日志（data journaling）记录了所有用户数据（除了文件系统的元数据之外），因而成本很高。一种更简单（也更常见）的日志形式又称为有序日志（ordered journaling，或称为元数据日志，metadata journaling），它几乎相同，只是用户数据没有写入日志。写入日志的数据块将改为写入文件系统，避免额外写入。考虑到磁盘的大多数 I/O 流量是数据，不用两次写入数据会大大减少日志的 I/O 负载。

数据写入的顺序对于元数据日志很重要。考虑写入了元数据，但用户数据没有写入磁盘的情况。然后文件系统尝试恢复，由于用户数据不在日志中，因此文件系统将重放元数据的写入，并生成一致的文件系统（从文件系统元数据的角度看）。但是，元数据将指向垃圾数据。在将相关元数据写入磁盘之前，一些文件系统先将数据块（常规文件）写入磁盘。

元数据日志协议：

1. 数据写入：将数据写入最终位置，等待完成（等待是可选的，只要在发出日志提交块（步骤3）之前完成步骤 1 和步骤 2）。
2. 日志元数据写入：将开始块和元数据写入日志，等待写入完成。
3. 日志提交：将事务提交块（包括 TxE）写入日志，等待写完成，现在认为事务（包括数据）已提交（committed）。
4. 加检查点元数据：将元数据更新的内容写入文件系统中的最终位置。
5. 释放：稍后，在日志超级块中将事务标记为空闲。

通过强制先写入数据，文件系统可以保证指针永远不会指向垃圾。“先写入被指对象，再写入指针对象” 的规则是崩溃一致性的核心，并且被其他崩溃一致性发方案进一步利用。

Windows NTFS 和 XFS 都使用无序的元数据日志，Linux ext3 提供了选择数据、有序或无序模式的选项（在无序模式下，可以随时写入数据）。所有这些模式都保持元数据一致，它们的数据语义更不相同。

注意，目录被认为是元数据。在向目录添加条目时，目录的内容（数据区域中的块）将被写入日志。若随后删除该目录，且之后的某个创建新文件的操作复用了这个删除的目录的数据块当做新文件的数据块，新创建文件仅有元数据写入日志，而数据块中的数据没有写入日志。若发生了崩溃，重放将恢复日志中的所有内容，因此，会在数据块中写入目录数据，则新创建文件的用户数据将会被已被删除的目录数据覆盖。Linux ext3 的做法是将新类型的记录添加到日志中，称为撤销（revoke）记录。删除目录将导致撤销记录被写入日志，此类被撤销的数据都不会被重放，从而避免了上述问题。

（4）总结日志：时间线

用时间线描述每个协议，时间向下增加，水平虚线表示必须遵守的写入顺序要求：

数据日志的时间线：

元数据日志的时间线：

时间线中每次写入标记的完成时间是任意的。在实际系统中，完成时间由 I/O 子系统确定，I/O 子系统可能会重新排序写入以提高性能。对于顺序的唯一保证，是那些必须强制执行，才能确保协议正确性的顺序。

3. 其他方法

• Ganger 和 Patt 引入了一种称为软更新的方法。这种方法仔细地对文件系统的所有写入排序，以确保磁盘上的结构永远不会处于不一致的状态。
• 写时复制（Copy-On-Write, COW）。
• 基于反向指针的一致性（Backpointer-Based Consistency, BBC），一种新形式的惰性崩溃一致性。
• 乐观崩溃一致性（optimistic crash consistency）。

4. 小结

处理崩溃一致性问题，许多文件系统现在使用日志，将恢复时间从 O(磁盘大小的卷) 减少到 O(日志大小)。最常用的是有序元数据日志，它可以减少日志流量，同时仍然保证文件系统元数据和用户数据的合理一致性。

八. 日志结构文件系统

日志结构文件系统的设计基于以下观察：

• 内存大小不断增长。内存可以缓存更多数据，磁盘流量将越来越多地由写入组成。
• 随机 I/O 性能与顺序 I/O 性能之间存在巨大的差异，且不断扩大：传输带宽每年增加约 50%～100%；寻道和旋转延迟成本下降得较慢，可能每年 5%～10%。
• 现有文件系统在许多常见工作负载上表现不佳。例如，FFS 尽管存在块组，但是仍然有许多短寻道和随后的旋转延迟（块组中），因此性能远远低于峰值顺序带宽。
• 文件系统不支持 RAID。例如，RAID-4 和 RAID-5 具有小写入问题，即对单个块的逻辑写入会导致 4 个物理 I/O 发生（读取旧数据块和奇偶校验块，随后两次写入）。现有的文件系统不会试图避免这种最坏情况的 RAID 写入行为。

理想的文件系统专注于写入性能，并尝试利用磁盘的顺序带宽，在常见工作负载上表现良好（这种负载不仅写出数据，还经常更新磁盘上的元数据结构），在 RAID 和单个磁盘上运行良好。

日志结构文件系统（Log-structured File System, LFS）：写入磁盘时，LFS 首先将所有更新（包括元数据）缓冲在内存段中。当段已满时，它会在一次长时间的顺序写入中写入磁盘，并传输到磁盘的未使用部分（空闲位置）。简单地将所有更新（例如数据块、inode 等）顺序写入磁盘的这一基本思想是 LFS 的核心。就像所有复杂的系统一样，魔鬼藏在细节中。

Tips: 细节至关重要。就像 LFS 中那样，一般的想法很容易理解，但要真正构建一个能工作的系统，必须仔细考虑所有棘手的情况。

顺序而高效的写入

简单按顺序写入磁盘不能实现最佳性能，向驱动器发出大量连续写入（或一次大写入）才能获得良好的写入性能。

LFS 使用写缓冲这种古老技术。在写入磁盘之前，LFS 跟踪内存中的更新，收到足够数量的更新时，会立即将它们写入磁盘，从而确保有效使用磁盘。

LFS 一次写入的大块更新被称为段（segment），这里的意思是 LFS 用来对写入进行分组的大块。在写入磁盘时，LFS 缓冲内存段中的更新，然后将该段一次性写入磁盘。只要段足够大，写入就会很有效。

例如，LFS 将两组更新缓冲到一个小段中（实际段更大，几 MB）。第一次更新是对 文件 j 的 4 次块写入，第二次是添加到文件 k 的一个块。然后，LFS 立即将这 7 个块的段提交到磁盘。这些块的磁盘布局如下：

LFS 在写入磁盘之前应该缓冲多少次更新（段的大小是多少）？答案取决于磁盘本身，特别是与传输速率相比定位开销有多高，目的是让有效速率（写入的数据量/写入的总时间，总时间=定位时间+传输时间）接近峰值速率。

inode 映射

在典型的文件系统（如 FFS）甚至老 UNIX 文件系统，inode 以数组形式组织，并放在磁盘的固定位置上。给定一个 inode 号，基于数组的索引是快速而直接的。FFS 将 inode 表拆分为块并在每个柱面组中放置一组 inode，知道每个 inode 块的大小和每个 inode 的起始地址，计算类似，也很容易。

在 LFS 中，inode 分散在整个磁盘上。而且我们永远不会覆盖，最新版本的 inode（即我们想要的那个）会不断移动。LFS 的设计者通过名为 inode 映射（inode map, imap）的数据结构，在 inode 号和 inode 之间引入了一个间接层（level of indirection）。imap 是一个结构，它将 inode 号作为输入，并生成最新版本的 inode 的磁盘地址。

imap 需要保持持久（写入磁盘），它还需要经常更新，若存在于磁盘的固定部分，性能会受到影响（每次的更新和 imap 的固定位置之间，会有更多的磁盘寻道）。LFS 将 inode 映射的块放在它写入所有其他新信息的位置旁边。因此，当将数据块追加到文件 k 时，LFS 实际上将新数据，其 inode 和一段 inode 映射一起写入磁盘，如下所示：

imap 数组存储在标记为 imap 的块中，它告诉 LFS，inode k 位于磁盘地址 A1，这个 inode 告诉 LFS 它的数据块 D 在地址 A0。

检查点区域

imap 的各个部分分布在整个磁盘上，文件系统必须在磁盘上有一些固定且已知的位置，才能开始文件查找。LFS 在磁盘上有一个固定的位置 —— 检查点区域（checkpoint region, CR）。CR 包含指向所有最新的 inode 映射片段的指针（即地址），因此可以通过首先读取 CR 来找到 inode 映射片段。请注意，CR 仅定期更新（例如每 30 s 左右），因此性能不会受到影响。

因此，磁盘布局的整体结构包含一个检查点区域（指向内部映射的最新部分），每个 inode 映射块包含 inode 的地址，inode 指向文件（和目录），就像典型的 UNIX 文件系统一样。

检查点区域（注意它始终位于磁盘的开头，地址为 0 ），以及单个 imap 块，inode 和数据块：

一个真正的文件系统当然会有一个更大的 CR（事实上，它将有 2 个），许多 imap 块，更多的 inode、数据块等。

从磁盘读取文件（假设内存中没有任何东西）：

• 必须读读取的第一个磁盘数据结构是检查点区域（包含指向整个 inode 映射的指针（磁盘地址）），LFS 读入整个 inode 映射并将其缓存在内存中。
• 给定文件的 inode 号时，LFS 在 imap 中查找 inode 号到 inode 磁盘地址的映射，并读入最新版本 的 inode。
• 从文件读取块，LFS 完全按照典型的 UNIX 文件系统进行操作（使用直接指针或间接指针或双重间接指针）。

整个 imap 被缓存，因此，LFS 在读取过程中所做的额外工作是在 imap 中查找 inode 的地址。

目录如何

LFS 如何存储目录数据？目录结构与传统的 UNIX 文件系统基本相同，目录只是（名称，inode 号）映射的集合。

例如，在创建文件时，LFS 必须同时写入新的 inode，一些数据，以及引用此文件的目录数据及其 inode（你可能还会想到引用此文件的目录的目录也需要更新）。LFS 将在磁盘上按顺序写入（在缓冲更新一段时间后）。因此，在目录中创建文件 foo ，将导致磁盘上的以下新结构：

inode 映射的片段包含目录文件 dir 以及新创建的文件 f 的位置信息。因此，访问文件的路径为：imap ，A3，A2，imap，A1，A0。

递归更新问题（recursive update problem）：每当更新 inode 时，它在磁盘上的位置都会发生变化，因此会导致对指向该文件的目录的更新，然后必须更改该目录的父目录，依此类推，一路沿着文件系统树向上。任何永远不会原地更新的文件系统（例如 LFS）都会遇到该问题。

inode 映射解决了 LFS 中的这一严重问题。imap 结构是 inumber 到 inode 的映射，即使 inode 的位置可能会发生变化，更改也不会反映在目录本身中。事实上，imap 结构被更新，而目录保持相同的名称到 inumber 的映射，在 imap 中修改 inumber 对应的映射 inode 地址值。因此，通过间接，LFS 避免了递归更新问题（inumber 不变，则目录数据不需要改变，imap 变化将原 inumber 映射到新 inode）。

垃圾收集

LFS 会在整个磁盘中分散旧版本的文件结构，即垃圾（garbage）。

可以保=保留那些旧版本并允许用户恢复旧文件版本，这样的文件系统称为版本控制文件系统（versioning file system），因为它跟踪文件的不同版本。

LFS 只保留文件的最新活版本。因此（在后台），LFS 必须定期查找文件数据，索引节点和其他结构的旧的死版本，并清理（clean）它们。清理过程是垃圾收集（garbage collection）的一种形式，这种技术在编程语言中出现，可以自动为程序释放未使用的内存。

之前讨论的段是在 LFS 中实现对磁盘的大段写入的机制，它们也是有效清理的重要组成部分。LFS 清理程序按段工作，从而为后续写入清理出大块空间。LFS 清理程序定期读取许多旧的（部分使用的）段，确定哪些块在这些段中存在，然后写出一组新的段，只包含其中活着的块，从而释放旧段用于写入。

给定磁盘段 S 内的数据块 D，LFS 必须能够确定 D 是不是活的。为此，LFS 会为描述每个块的每个段添加一些额外信息。LFS 增加一个数据结构，位于段头部，称为段摘要块（segment summary block），对于每个数据块 D，包括其 inode 号（它属于哪个文件）及其偏移量（这是该文件的哪一块）。通过 inumber 查找 imap ，从而反向查找块 D 的 inode，然后利用偏移量，查看文件的该偏移块是否位于块 D 的位置，从而判断块 D 的死活。一个描述机制的图：

其中段摘要块（标记为 SS）记录了地址 A0 处的数据块，实际上是文件 k 在偏移 0 处的部分。通过检查 imap 的 k，可以找到 inode，并且看到它确实指向该位置。

LFS 更有效地确定死活：当文件被截断或删除时，LFS 增加其版本号（version number），并在 imap 中记录新版本号。通过在磁盘上的段中记录版本号，LFS 可以简单地将磁盘版本号与 imap 中的版本号进行比较，跳过上述较长的检查，从而避免额外的读取。

在上述机制的基础上，LFS 必须包含一组策略，确定何时清理以及哪些块值得清理。

• 何时清理：周期性的/空闲时间/磁盘已满时。

• 哪些块清理：一种试图分离冷热段的方法，尽快清理冷段，延迟清理热段。

  • 热段：经常覆盖内容的段，在清理之前等待很长时间，因为越来越多的块被覆盖。
  • 冷段：有一些死块，但其余内容相对稳定。

崩溃恢复和日志

LFS 在日志中组织缓冲在段中的写入，即指向头部段和尾部段的检查点区域（日志包含在 CR 中）。LFS 还定期更新检查点区域（CR）。确保 CR 更新以原子方式发生，LFS 实际上保留了两个 CR，每个位于磁盘的一端，并交替写入它们。

小结

LFS 总是写入磁盘的未使用部分，然后通过清理回收旧空间，而不是在原来的位置覆盖文件。这种方法在数据库系统中称为影子分页（shadow paging），在文件系统中有时称为写时复制（copy-on-write）。

一些现代商业文件系统，包括 NetApp 的 WAFL、Sun 的 ZFS 和 Linux btrfs 采用了类似的写时复制方法来写入磁盘。特别是，WAFL 通过将清理问题转化为特征来解决问题，通过快照（snapshots）提供旧版本的文件系统。

九. Flash-based SSDs

英文原版新增的章节，中文版没有。

十. 数据完整性和保护

鉴于现代存储设备的不可靠性，文件系统或存储系统应如何确保数据安全？这一领域称为数据完整性（data integrity）或数据保护（data protection），确保存储系统返回的数据就是放入存储系统的数据。

磁盘故障模式：

• 故障-停止（fail-stop）模型
• 故障-部分（fail-partial）模型
  • 潜在扇区错误（Latent-Sector Errors, LSE）
  • 块讹误（block corruption）
• 错误的写入（misdirected write）
• 丢失的写入（lost write）

LSE：数据位不可读或内容不正确。驱动器使用磁盘内纠错码（Error Correcting Code, ECC）来确定块中的磁盘位是否良好，并在某些情况下修复它们或者返回错误。

块讹误：磁盘块出现讹误（corrupt），但磁盘本身无法检测到。一种无声的故障（silent fault）。例如，写入错误的数据或写到错误的位置。返回故障数据时，磁盘没有报告问题。

这两种类型的故障都有点罕见，至少出现一次 LSE 或块讹误的驱动器百分比（大约 3 年，超过 150 万个磁盘驱动器）：

建立一个可靠的存储系统，必须包括一些机制来检测和恢复 LSE 并阻止讹误。

处理潜在的扇区错误

当存储系统尝试访问块，并且磁盘返回错误时，存储系统应该就用它具有的任何冗余机制，来返回正确的数据。但是，冗余的磁盘上也会遇到 LSE，一些系统因此增加了额外的冗余度。例如，NetApp 的 RAID-DP 相当于两个奇偶校验磁盘，而不是一个。

检测讹误：校验和

如何处理数据讹误导致的无声故障？

现代存储系统用于保持数据完整性的主要机制称为校验和（checksum）。校验和就是一个函数的结果，以一块数据（例如 4KB 块）作为输入，产生这块数据的小概要（比如 4 字节或 8 字节），即校验和。让系统将校验和与数据一起存储，然后在访问时确认数据的当前校验和与原始存储值匹配，从而检测数据是否以某种方式被破坏或改变。

常见的校验和函数：

• 异或（XOR）
• 加法
• Fletcher 校验和
• 常用的循环冗余校验（CRC）

这些函数的强度（保护数据完整性的程度）和速度（计算速度）都不同，也没有完美的校验和：两个具有不相同内容的数据块可能具有相同的校验和，这被称为碰撞（collision）。

校验和的布局：

• 给定数据块 D，该数据的校验和为 C(D)。没有校验和，磁盘的布局：

• 为每个磁盘扇区（或块）存储校验和，即为每个块添加一个校验和。校验和通常很小（例如，8 字节），并且磁盘通常只能以扇区大小的块（512 字节）或其倍数写入。驱动器制造商采用的一种解决方案是使用 520 字节的扇区格式化磁盘，每个扇区额外的 8 字节用于存储校验和。

• 将打包的校验和存储到 512 字节的块中：

客户端比较存储的校验和与计算的校验和，进行讹误检测。若存在讹误，尝试使用系统的冗余副本，也可能返回错误（没有此类副本）。

错误的写入

这出现在 RAID 控制器中，它正确地将数据写入磁盘，但位置错误。可能写入错误的地址，也可能写入错误的磁盘。

在校验和中添加更多信息 —— 物理标识符（Physical Identifier, 物理 ID）。例如，块的磁盘和扇区号。如果信息不匹配，则发生了错误的写入。如下所示：

丢失的写入

当设备通知上层写入完成，但事实上它从未持久。磁盘上留下的是该块的旧内容，旧块很可能具有匹配的校验和和正确的物理 ID（磁盘号和块偏移）。

一种经典方法是执行写入验证（write verify），或写入后读取（read-after-write）。某些系统在系统的其他位置添加校验和，以检测丢失的写入。例如，Sun 的 Zettabyte 文件系统（ZFS）在文件系统的每个 inode 和间接块中，包含文件中每个块的校验和。数据块本身的丢失，inode 内部的校验和不会与旧数据匹配。同时丢失对 inode 和数据的写入也是可能发生的情况。

擦净

数据被访问时，校验和得到检查。但大多数数据很少被访问，数据位衰减最终可能会影响特定数据的所有副本。

许多系统利用各种形式的磁盘擦净（disk scrubbing），通过定期读取系统的每个块，并检查校验和是否仍然有效，磁盘系统可以减少某个数据项的所有副本都被破坏的可能性。典型的系统每晚或每周安排扫描。

校验和的开销

• 空间开销
  • 磁盘（存储介质）本身，典型的比率可能是每 4KB 数据块的 8 字节校验和，磁盘空间开销为 0.19%。
  • 系统内存，将校验和保存内存中是可能的。
• 时间开销
  • CPU 计算每个块的校验和（包括存储数据和访问数据）
  • 外部 I/O 开销：校验和和数据分开存储时；后台擦净所需的所有额外 I/O

小结

讨论了现代存储系统中的数据保护，重点是校验和的实现和使用。不同的校验和可以防止不同类型的故障。

完