Loading... # 操作系统导论 笔记 ## 第二章 操作系统介绍 有一类软件负责让程序运行变得容易（甚至允许你同时运行多个程序），允许程序共享内存，让程序能够与设备交互，以及其他类似的工作。这类软件称为操作系统（Operating System, OS） 要做到这一点，操作系统主要利用一种通用的技术，我们称之为虚拟化。 也就是说，操作系统将物理资源（如处理器、内存或磁盘）转换为更通用、更强大且更易于使用的虚拟形式。因此我们有时将操作系统称为虚拟机。 由于操作系统提供这些调用来运行程序、访问内存和设备，并进行其他相关操作，我们有时也会说操作系统为应用程序提供了一个标准库。 最后，因为虚拟化让许多程序运行，让许多程序可以同时访问自己的指令和数据，让许多设备访问设备，所以操作系统有时被称为资源管理器。 ### 2.1 虚拟化CPU 尽管只有一个处理器，但是4个程序似乎在同时运行。 在硬件的帮助下，操作系统负责提供这种假象，即系统拥有非常多的虚拟CPU的假象。将单个CPU（或其中的一部分）转换为看似无限数量的CPU，从而让许多程序看似同时运行，这就是所谓的虚拟化CPU。 ### 2.2 虚拟化内存 现代机器提供的物理内存模型非常简单。 内存就是一个字节数组。要读取内存，必须指定一个地址，才能访问存储在那里的数据。要写入或更新内存，还必须指定要写入给定地址的数据。 同时运行同一程序的多个实例，可以看到似乎每个程序都在相同的地址处分配了内存，但每个似乎都独立更新了那个地址处的值，就好像每个正在运行的程序都有自己的私有内存，而不是与其他正在运行的程序共享相同的物理内存。 实际上，这正是操作系统虚拟化内存时发生的情况。 每个进程访问自己的私有虚拟地址空间（地址空间），操作系统以某种方式映射到机器的物理内存上。一个正在运行的程序中的内存引用不会影响其他进程（或操作系统本身）的地址空间。 ### 2.3 并发 多个线程同时对一个共享变量（内存不可见）做自增 结果与预期不一致 自增需要三条指令：一条将计数器的值从内存加载到寄存器，一条将其递增，另一条将其保存回内存。 因为这三条指令并不是以__原子方式执行（所有指令一次性执行）__，所以导致这种情况发生。 注：《Java并发编程之美》中同样举了这个例子，这本书非常推荐学习Java的人阅读，语言朴素，易于理解 ### 持久性 内存这样的设备以易失的方式存储数值，一旦断电上面的所有数据都会丢失。 因此我们需要硬件和软件来持久地存储数据。 硬件以某种输入/输出（I/O）设备的形式出现，在现代系统中，硬盘驱动器是存储长期保存信息的通用存储库，尽管固态硬盘正在这个领域取得领先地位。 为了处理写入器件系统崩溃的问题，大多数文件系统都包含了某种复杂的写入协议，如日志或写时复制(copy-on-right)，仔细排序写入磁盘的操作，以确保如果在写入序列期间发生故障，系统可以在之后恢复到合理的状态。 为了使不同的通用操作更高效，文件系统采用了许多不同的数据结构和访问方法，如B树，或《数据结构与算法分析 Java语言表述》中提到的B+树等等。 ### 2.5 设计目标 最基本的目标，是建立一些抽象，让系统方便和易于使用。 设计和实现操作系统的一个目标，是提供高性能。 另一个目标是在应用之间以及在OS和应用程序之间提供保护。 保护是操作系统基本原理之一的核心，这就是隔离，让进程彼此隔离是保护的关键。 操作系统必须不间断的运行。当它失效时，系统上运行的所有应用程序也会失效。由于这种依赖型，操作系统往往力求高精度的可靠性。 其他：如能源利用率，安全性（保护的拓展），移动性 ### 简单历史 #### 早期：只是一些库 一开始，操作系统并没有做太多事情。基本上，它只是一组常用的函数库。 在老的大型机系统上，一次运行一个程序，由操作员来控制，这个操作员完成了许多现代操作系统会做的事情。 这种计算模式被称为_批处理_，先把一些工作准备好，然后由操作员以分批的形式运行。 #### 超越库：保护 在发展过程中，其中一个最重要的方面是：意识到代表操作系统运行的代码是特殊的，它控制了设备，因此对待它的方法应该与对待正常应用程序的代码方式不同。 因此，**系统调用**的概念诞生了。不是将操作系统里程作为一个库来提供（你只需要一个过程调用来访问它们），这里的想法是添加一些特殊的硬件指令和硬件状态，让向操作系统过渡变为更正式的、受控的过程。 系统调用和过程调用之间的关键区别在于，系统调用将控制转移到OS中，同时提高硬件特权级别。 用户应用程序以所谓的用户模式运行，这意味着硬件限制了应用程序的功能。例如，以用户模式运行的应用程序通常不能发起对磁盘的I/O请求，不能访问任何物理内存也或在网络上发送数据包。 在发起系统调用时（通常通过一个称为[**陷阱**]的特殊硬件指令），硬件将控制权转移到预先指定的陷阱处理程序（即预先设置的操作系统），并同时将特权级别提升到内核模式(kernel mode)。 在内核模式下，操作系统可以完全访问系统的硬件，因此可以执行注入发起I/O请求或为程序提供更多内存等功能。当操作系统完成请求的服务时，它通过特殊的陷阱返回指令将控制权交还给用户，该指令返回到瀛湖模式，同时将控制权交还给应用程序，回到应用离开的地方。 #### 多道程序时代 由于希望更好的利用机器资源，多道程序变得很普遍。 操作系统不是一次只运行一项作业，而是将大量作业加载到内存中并在他们之间快速切换（上下文切换，从而提高CPU利用率。 在I/O进行和任务中断时，要支持多道程序和重叠运行，这一愿望迫使操作系统创新，沿着多个方向进行概念发展。（已经实现） 内存保护等问题变得重要。我们不希望一个程序能访问另一个程序的内存，了解如何处理多道程序引入的并发问题也很关键。 当时主要的进展是引入了UNIX操作系统，主要归功于贝尔实验室 #### 摩登时代 除小型计算机之外，还有一种新型机器，便宜，速度更快，而且适用于大众：今天我们称之为个人计算机（PC）。在苹果公司早期的机器和IBM的引领下，这种新机器很快成为了计算的主导力量，因为它们的低成本让每个桌子上都有了一台机器，而不是每个工作小组共享一台小型机。 遗憾的是，对于操作系统来说，个人计算机期初代表了一次巨大的倒退，因为早期的系统忘记了小型机时代的经验教训，如内存保护等。 幸运的是，经过了一段时间的苦难之后，小型机操作系统的老功能开始进入台式机。 如，macOSX的核心是UNIX，包括人们期望从这样一个成熟的系统中获得的所有功能。 Windows在计算力使用同样采用了许多伟大的思想，特别是从Windows NT开始，这是微软操作系统技术的一次巨大飞跃。 即使在今天的手机上运行的操作系统(如Linux)，也更像小型机在20世纪70年代运行的。 > 补充： > 在操作系统的历史中，UNIX的重要性举足轻重。受早期系统影响，UNIX汇聚了许多了不起的思想，创造了既简单又强大的系统， > > UNIX的环境对于程序员和开发人员都很友好，并为新的C编程语言提供了编译器。程序员很容易编写自己的程序并分享它们，作为开源的早期形式，作者向所有请求的人免费提供副本，这可能帮助很大。 > > 代码的可得性和可读性也非常重要。用C语言编写的小内核吸引了其他人摆弄内核，添加新的功能。 > 例如：由Bill Joy领导的伯克利创业团队发布了一个非常棒的发行版（BSD），该发行版拥有先进的虚拟内存、文件系统和网络子系统。 > Joy后来和朋友共同创立了 Sun Microsystems，即Java开发者非常熟悉的(Sun公司) > > 随着贝尔实验室和一些公司的版权纠纷，UNIX的发展慢了下来，随着Windows的出现，人们想知道它能否活下来。 > > 然后出现了Linux > > 幸运的是，对于UNIX来说，一位名叫 Linux Torvalds 的年轻芬兰黑客决定编写他自己的 UNIX 版本，该版本严重依赖最初系统背后的原则和思想，但没有借用原来的代码集，从而避免了合法性问题。他征集了世界各地许多其他人的帮助，不久，Linux就诞生了（同时也开启了现代开源运动）。 ## 第四章 抽象：进程 操作系统提供的基本抽象——进程。进程的非正式定义非常简单：进程就是运行中的程序。 操作系统通过虚拟化CPU来提供有许多CPU的假象。通过让一个进程只运行一个时间片，然后切换到其他进程，操作系统提供了存在多个虚拟CPU的假象。这就是时分共享CPU技术，如果用户如愿运行多个并发程序。潜在的开销就是性能损失，因为如果CPU必须共享，每个进程的运行就会慢一些。 在这些机制之上，操作系统中有一些智能以策略的形式存在。策略是操作系统内做出某种决定的算法。 > 时分共享（和空分共享） > 时分共享是操作系统共享资源所使用的最基本的技术之一。通过允许资源由一个实体使用一小段时间，然后由另一个实体使用一小段时间，如此下去，所谓的资源（例如，CPU或网络连接）可以被许多人共享。时分共享的自然对应技术是空分共享，资源在空间上被划分给希望使用它的人。例如，磁盘空间自然是一个空分共享资源，因为一旦将块分配给文件，在用户删除文件之前，不可能将它分享给其他文件。 ### 4.1 抽象：进程 操作系统为正在运行的程序提供的抽象，就是所谓的进程。正如上面所说，一个进程只是一个正在运行的程序。从任何时刻，我们都可以清点它的执行过程中访问了或影响的系统的不同部分，从而概括一个进程， 进程的机器状态有一个明显的组成部分，就是它的内存。指令存在内存中，正在运行的程序读取和写入的数据也在内存中。因此进程可以访问的内存（称为地址空间）是该进程的一部分。 进程的机器状态的另一部分是寄存器。许多指令明确地读取或更新寄存器，因此显然它们对执行该进程很重要。 有一些非常特殊的寄存器构成了该机其状态的一部分，如程序计数器(PC)告诉我们程序当前正在执行哪个指令，栈指针和栈帧用于管理函数参数栈、局部变量和返回地址。 最后，程序也经常访问持久存储设备，此类I/O信息可能包含当前打开的文件列表。 ### 4.2 进程API - 创建(create)：操作系统必须包含一些创建新进程的方法 - 销毁(destory)：由于存在创建进程的接口，因此系统还提供了一个强制销毁进程的接口 - 等待(wait)：有时等待进程停止运行是有用的，因此经常提供某种等待接口 - 其它控制(miscellaneous control)：其他控制，如暂停进程(阻塞)，恢复 - 状态(statu) 获取进程状态，如运行时长，处于状态 ### 4.3 进程创建 操作系统运行程序必须做的第一件事是将代码和所有静态数据（如初始化变量）加载到内存中，加载到进程的地址空间中。 因此，将程序和静态数据加载到内存中的过程，需要操作系统从磁盘读取这些字节，并将它们放在内存中的某处 现代操作系统惰性执行该过程，即仅在执行程序期间需要加载的代码或数据片段，才会加载。 操作系统在运行此进程之前还需要执行其他一些操作。必须为程序的**运行时栈**分配一些内存。 操作系统也可能为程序的堆分配一些内存，还将执行一些其他初始化任务，特别是与I/O相关的任务。 然后它有最后一项任务：启动程序，在入口处运行，即main()。通过跳转到main()例程，OS将CPU的控制权转移到新创建的进程中，从而程序开始执行。 ### 进程状态 进程可以处于以下这些状态之一的 - 运行(running)：在运行状态下，进程正在处理器上运行，即它正在执行指令 - 就绪(ready)：在就绪状态下，进程已经准备好运行，但由于某种原因，操作系统选择不在此时运行 - 阻塞(blocked)：在阻塞状态下，一个进程执行了某种操作，直到发生了其他事件时才会准备运行。 进程可以在就绪和运行状态之间切换，从就绪到运行意味着该进程已经被调度，从运行到就绪说明该进程已经被取消调度。 一旦进程阻塞，OS将保持进程的状态，直到发生某种事件（如I/O）完成。 此时，进程再次转入就绪状态（也可能立刻运行） ### 4.5 数据结构 操作系统追踪进程的一些重要信息。对于停止的进程，寄存器上下文将保存其寄存器的内容。 当一个进程停止时，它的寄存器将被保存到这个内存位置。通过恢复这些寄存器，操作系统可以恢复该进程。它被称为上下文切换。 系统会有一个初始状态，表示进程在创建时处于的状态。另外，一个进程可以处于一退出但尚未清理的最终状态(UNIX 称为僵尸状态)。这个状态飞创游泳，因为它允许其他进程检查进程的返回代码，并查看刚刚完成的进程是否成功执行。 ## 第五章 插叙：进程API 略 ## 第六章 机制：受限直接执行 操作系统需要以某种方式让许多任务共享物理CPU，让他们看起来像是同时运行。基本思想很简单：运行一个进程一段时间，然后运行另一个进程，如此轮换。通过以这种方式时分共享CPU，就实现了虚拟化。 ### 6.1 基本技巧：受限直接执行 为了使程序尽可能快的运行，操作系统开发人员想出了一种技术——受限的直接执行 直接执行的概念很简单：只需要直接在CPU上运行程序即可。 因此，当OS希望启动程序运行时，它会在进程列表中为其创建一个进程条目，围棋分配一些内存，将及程序底阿妈（从磁盘）加载到内存中，找到入口点，跳转到那里，并开始运行用户的代码。 ### 6.2 问题1：受限制的操作 为了让不让程序直接调用一些硬件，我们采用的方法是引入一种新的处理器模式，称为用户模式，在用户模式下运行的代码会受到限制。如不能发出I/O请求，这样做会导致处理器引发异常，操作系统可能会终止进程。 与用户模式不同的内核模式，操作系统（或内核）就以这种模式运行，在此模式下，运行的代码可以做它喜欢的事，包括特权操作，如发出I/O请求。 但是，如果用户希望执行某种特权操作（如磁盘读取），该怎么做呢？ 为了实现这点，几乎所有现代硬件都提供了用户程序执行系统调用的能力，系统调用是在Atlas等古老机器上开创的，它允许内核小心的向用户程序暴露某些关键功能，例如访问文件系统、创建和销毁进程、与其它进程通信，以及分配更多内存。 要执行系统调用，程序必须执行特殊的陷阱(trap)指令。该指令同时跳入内核并将特权级别提升到内核模式，完成工作后，操作系统调用一个特殊的从陷阱返回指令，该指令返回到发起调用的用户程序中，同时将特权级别降低，回到用户模式。 执行陷阱时，硬件需要小心，因为它必须确保存储足够的调用者寄存器，一边在操作系统发出从陷阱返回指令时能够正确的返回。例如，在x86上，处理器会将程序计数器、标志和其他一些寄存器推送到每个进程的内核栈上。返回陷阱将从栈弹出这些值，并恢复执行用户程序。 陷阱如何知道在OS内运行哪些代码？显然，发起调用的过程不能指定要跳转到的地址，不然程序可以跳转到内核中的任意位置，因此内核必须谨慎的控制在陷阱上执行的代码。 内核通过启动时设置陷阱表来实现，当机器启动时，它在特权（内核）模式下执行，因此可以根据需要自由配置机器硬件。 操作系统要做的第一件事，就是告诉硬件在发生某些异常事件时要运行哪些代码。操作系统通过某种特殊的指令，通知硬件这些陷阱处理程序的位置，直到下一次重新启动机器，并且硬件知道在发生系统调用和其他异常事件是要做什么（即跳转到哪段代码） 最后，能够执行指令告诉硬件陷阱表的位置是一个非常强大的功能，因此，这也是一项特权操作。 如果你试图在用户模式下执行这个指令，硬件不会允许，并且进程会被操作系统杀死。 ### 6.3 问题2：在进程之间切换 #### 协作方式：等待系统调用 过去某些系统采用一种协作方式。 在这种风格下，操作系统相信系统的进程会合理运行。运行时间过长的进程被假定会定期放弃CPU，以便操作系统可以决定运行其他任务。 像这样的系统通常包括一个显示的yield系统调用，只用于将控制权交还给操作系统，以后系统可以运行其他进程。 因此，在协作调度系统中，OS通过等待系统调用，或某种非法操作发生，从而重新获得CPU的控制权。 #### 非协作方式：操作系统进行控制 没有硬件的额外帮助，如何进程拒绝进行系统调用（也不出错），从而将控制权交还给操作系统，那么操作系统无法做任何事情。事实上，在协作方式中，当进程陷入无限循环时，唯一的办法就是使用古老的解决方案来解决计算机系统中的所有问题——重启。 > 如何在没有协作的情况下获得控制权 答案很简单，许多年前构建计算机系统的许多人都发现了：**时钟中断** 时钟设备可以编程为每隔几毫秒产生一次中断，产生中断时，当前正在运行的系统停止，操作系统中预先配置的中断处理程序会运行。此时，操作系统重新获得CPU的控制权，因此可以做它想做的事，如停止当前进程，并启动另一个进程。 正如之前讨论过的系统调用一样，操作系统必须通知硬件哪些代码在发生时钟中断时运行。因此，在启动时，操作系统就是这样做的。其次，在启动过程中，操作系统也必须启动时钟，这当然是一项特殊操作。 注意，硬件在发生中断时有一定的责任，尤其咋中断发生时，要为正在运行的程序保存足够的状态，一边随后从陷阱返回指令能够正确恢复正在运行的程序。这一组操作与硬件在显示系统调用陷入内核时的行为非常相似，其中各种寄存器因此被保存进内核栈，从因此从陷阱返回指令可以容易的恢复。 #### 保存和恢复上下文 既然操作系统已经重新获得了控制权，无论是通过系统调用协作，还是通过时钟中断强制执行，都必须决定：是继续运行当前正在运行的进程，还是切换到另一个进程。这个决定是由调度程序做出的，它是操作系统的一部分。 如果决定进行切换，OS会执行一些底层代码，即所谓的上下文切换(context switch) 上下文切换的概念很简单：操作系统要做的就是为当前正在执行的进程保存一些寄存器的值（例如，到它的内核栈），并为即将恢复执行的进程恢复一些寄存器的值（从它的内核栈）。 这样一来，操作系统就可以确保最后执行从陷阱返回指令时，不是返回到之前运行的程序，而是继续执行另一个进程。 为了保存当前正在运行的进程的上下文，操作系统会执行一些底层汇编代码。来保存通用寄存器、程序计数器，以及当前正在运行的进程的内核栈指针，然后回复寄存器、程序计数器，并切换内核栈，以供给将运行的进程使用。 通过切换内核栈，内核在进入切换代码调用时，是一个进程（被中断的进程）的上下文，在返回时，是另一个进程（即将执行的进程）的上下文。 当操作系统最终执行从陷阱返回指令时，即将执行的进程变成了当前运行的进程，至此上下文切换完成。 在受限直接执行协议（时钟中断）中，有两种类型的寄存器保存/恢复： 第一种是发生时钟中断的时候，在这种情况下，运行进程的用户寄存器由硬件隐式保存，使用该进程的内核栈。 第二种是当前操作系统决定从A切换到B，在这种情况下，内核寄存器被OS明确地保存，但这次被存储在该进程的进程结构的内存中。 后一个操作让系统好像刚刚由A陷入内核，变成好像刚刚由B陷入内核。 > 补充：上下文切换需要多长时间 > 1996年在200MHz P6处理器上运行Linux 1.3.37，系统调用花费了大约 4μs > 现代操作系统的性能几乎可以提高一个数量级，在具有 2GHz 或 3GHz 的处理器的系统上的性能可以达到亚微秒级。 ### 6.4 担心并发吗 > 在处理一个中断的时候发生另一个中断，会发生什么？ 简单介绍操作系统如何处理这些棘手的情况，操作系统可能简单的决定 ，在中断处理期间禁止中断。这样做可以确保在处理一个中断时，不会将其他中断交给CPU。当然，操作系统这样做必须小心。禁用中断时间过长可能导致丢失中断，这在技术上是不好的。 操作系统还开发了许多复杂的加锁方案，以保护对内部数据结构的并发访问。这时的多个有活动可以同时在内核中进行，特别适用于多处理器。 ### 6.5 小结 本章介绍了CPU虚拟化的关键底层机制，我们将其统称为受限直接执行。 OS在启动时设置陷阱处理程序并启动时钟中断，然后仅在受限模式下运行进程，以此为CPU提供保护。这样做，操作系统能确信进程可以高效运行，只在执行特权操作，或当它们独占了CPU时间过长并因此需要切换时，才需要OS干预。 ## 第七章 进程调度：介绍 本章介绍操作系统调度程序采用的上层策略 ### 7.1 工作负载假设 在探讨可能的策略范围，我们先做一些简化假设。 这些假设与系统中运行的进程有关，有时候统称为工作负载。 确定工作负载是构建调度策略的关键部分。工作负载了解得越多，你的策略就越优化。 在这里做的工作负载假设是不切实际的，但目前没有问题，未来会放宽这些假定 一个完全可操作的调度准则： 1. 每一个工作运行相同的时间 2. 所有工作同时到达 3. 一旦开始，每个工作保持运行直到完成 4. 所有工作只是用CPU(不发起I/O) 5. 每个工作的运行时间是已知的 ### 7.2 调度指标 除了工作负载的假设之外，还需要一个东西让我们比较不同的调度策略：调度指标 在进程调度中，有一些不同的指标是有意义的。 现在，我们只用一个指标：周转时间，任务周转时间的定义为任务完成时间减去任务到达系统的时间。 周转时间是一个性能指标，是本章的首要关注点。另一个有趣的指标是公平。 性能和公平在调度系统中往往是矛盾的。 ### 7.3 先进先出 最基本的算法，FIFO调度 A运行100s，B、C运行10s 如果A先到，则B、C的周转时间为110s和120s，平均周转时间为110s，这是令人不快的。 这个问题通常被称为护航效应，一些好事较少的潜在资源消费者被排在重量级的资源消费者之后。 ### 7.4 最短任务优先（SJF） 新的调度策略被称为最短任务优先（Shortest Job First, SJF)，即先运行最短的任务，然后是次段的任务，如此下去。 在所有工作同时到达的假设下，SJF是最优的调度方法 > 补充：抢占式调度程序 > 在过去的批处理计算中，开发了一些非抢占式的调度程序。 > 这样的系统会将每项工作做完，在考虑是否运行新工作。几乎所有现代化的调度程序都是抢占式的，非常愿意停止一个线程以运行另一个线程。这意味着调度程序采用了我们之前学习的机制。特别是调度程序可以进行上下文切换，临时停止一个运行进程，并恢复（或启动）另一个进程。 但如果任务不是同时到达，即A比B、C早到，那么B、C仍然需要等待A运行100s。 ### 7.5 最短完成时间优先（STCF） 为了解决这个问题，我们需要放宽假设条件（工作必须保持运行直到完成）。 当B和C到达时，调度程序方然可以做其他事情：它可以抢占工作A，并决定运行另一个工作，或许稍后继续工作A。根据我们的定义，SJF是一种非抢占式的调度程序，因此存在上述问题。 幸运的是，有一个调度程序完全就是这样做的：向SJF添加抢占，称为最短完成时间优先(Shortest Time-to-Completion Forst, STCF) 每当新工作进入系统时，它就会确定剩余工作和新工作中，谁的剩余时间最少，然后调度该工作。 如果所有工作同时到达，SJF是最优的，那么随时到达时，STCF的最优性是符合直觉的。 ### 7.6 新度量指标：响应时间 引入分时系统改变了这一切。现在，用户将会坐在终端前面，同时也要要求系统的交互性好。 因此，一个新的度量标准诞生了：响应时间。 响应时间的定义为从任务到达系统到首次运行的时间。 ### 7.7 轮转 新的调度算法，通常称为**轮转**(Round-Robin, RR) 基本思想很简单：RR在一个**时间片**内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束。它反复执行，直到所有任务完成。因此RR有时被称为时间切片。 注意，时间片长度必须是时钟中断周期的倍数。因此，如果时钟中断是每10ms一次，在则时间片可以是 10ms、20ms 或10ms的其他任何倍数。 时间片长度对于RR是至关重要的。越短，RR在响应时间上表现越好。然而，时间片太短是有问题的：突然切换上下文的成本将影响整体性能。因此系统设计者需要权衡时间片的长度，使其足够长，以便摊销上下文切换的成本，而又不会使系统不及时响应。 上下文切换的成本不仅仅来自于保存和恢复少量寄存器的操作系统操作。程序运行时，它们在CPU高速缓存、TLB、分支预测器和其他片上硬件中建立了大量状态。切换到另一个工作会导致此状态被刷新，且与当前运行的作业相关的新状态被引入，这可能导致显著的性能成本。 任何公平的策略（如RR），即在小规模的时间内将CPU均匀分配到活动进程之间，在周转时间这类指标上表现不佳。实际上，这是固有的权衡：如果你愿意不公平，你可以运行较短的工作直到完成，但要以牺牲响应时间为代价。如果你重视公平性，则相应时间会较短，但会议周转时间为代价。 这种权衡在系统中很常见，你不能既要又要。 ### 7.8 结合 I/O 放宽假设4，允许程序执行I/O 调度程序显然要在工作发起I/O请求时作出决定，因为当前正在运行的作业在I/O期间不会使用CPU，它被阻塞等待I/O完成。因此，这时调度程序应该在CPU上安排另一项工作。 调度程序还必须在I/O完成时作出决定。发生这种情况时，会产生中断，操作系统运行并将发出I/O的进程从阻塞状态移回就绪状态。 当这些交互式作业正在执行I/O时，其他CPu密集型作业将会运行，从而更好地利用处理器。 ### 7.9 无法预知 调度程序并不知道每个进程的工作长度，因此我们如何建立一个没有这种先验知识的调度程序？ ### 7.10 小结 介绍了调度的基本思想，并开发了两类方法。 第一类是运行最短的工作，从而优化周转时间。SJF、STCF 第二类是交替运行所有工作，从而优化响应时间。RR 但很难做到鱼和熊掌兼得，这是系统账常见的、固有的这种。我们也看到了如何将I/O结合到场景中，但仍未解决操作系统根本无法看到未来的问题。 稍后，我们将看到如何通过构建一个调度程序，利用最近的历史预测未来，从而解决这个问题。这个调度程序称为**多级反馈队列**。 ## 第八章 调度：多级反馈队列 本章介绍一种著名的调度方法——**多级反馈队列**(Multi-level Feedback Queue, MLFQ) 多级反馈队列需要解决两方面的问题。首先它要优化周转时间；其次，降低响应时间。 ### 8.1 MLFQ：基本规则 MLFQ 中有许多独立的队列，每个队列有不同的优先级。任何时刻，一个工作只能存在于一个队列中。MLFQ总是优先执行较高优先级的工作（即在较高级的队列中工作） 每个队列中可能会有多个工作，具有同样的优先级。在这种情况之下，我们就对这些工作采用轮转调度。 因此MLFQ调度策略的关键就在于如何设置优先级： MLFQ没有为每个工作指定不变的优先级，而是根据观察到的行为调整它的优先级。 例如，如果一个工作不断放弃CPU全部等待键盘输入，这是交互型进程的可能性为，MLFQ因此会让它保持高优先级。相反，如果一个工作长时间的占用CPU，MLFQ会降低其优先级。通过这种方式，MLFQ在进程运行过程中学习其行为，从而利用工作的历史预测它未来的行为。 至此，我们得到了MLFQ的两条基本规则： - 规则1：如果A的优先级 > B的优先级，运行A，不运行B - 规则2：如果A的优先级 = B的优先级，轮转运行A和B ### 8.2 尝试1：如何改变优先级 我们必须决定，在一个工作的生命周期中，MLFQ如何改变其优先级。 要做到这一点，我们必须记得工作负载：既有运行时间很短、频繁放弃CPU的交互型工作，也有需要很多CPU时间、响应时间却不重要的长时间计算密集型工作。 暂定三条规则： 1. 工作进入系统时，放在最高优先级（最上层队列） 2. 工作用完整个时间片后，降低其优先级（移入下一层队列） 3. 如果工作在其时间片以内主动释放CPU，则优先级不变。 #### 实例1：单个长工作 给定三个队列(Q2, Q1, Q0)，工作时间为200ms 首先工作进入最高优先级队列Q2，执行一个10ms的时间片后，调度程序将工作的优先级减1，因此进入Q1。在Q1执行一个10ms的时间片后最终降低优先级进入系统的最低优先级队列Q0，一直留在那里。 #### 实例2：来了一个短工作 在上例的基础上，新增一个20ms的短工作，很显然，在Q1队列，该工作就会结束。 可以体会到，这个算法的一个主要目标：如果不知道是短工作还是长工作，那么久在开始的时候假设其是短工作，并赋予最高优先级。如果确实是短工作，则很快会执行完毕，否则将被慢慢移入低优先级队列，而这时该工作也被认为是长工作了。通过这种方式，MLFQ近似于SJF。 #### 实例3：如果有I/O呢 根据规则3，如果进程在时间片用完之前主动放弃CPU，则保持它的优先级不变。 这条规则的意图很简单：假设交互型工作中有大量 I/O 的操作，它会在时间片用完之前放弃CPU。在这种情况下，我们保持它的优先级不变，以保证交互型工作快速运行。 #### 当前 MLFQ 的一些问题 现在的MLFQ看起来似乎相当不错，长工作之间可以公平地分享CPU，又能给短工作或交互型工作很好的响应时间。 然而，这种算法有一些很严重的缺点： 首先，会饥饿问题。如果系统有太多交互型工作，就会不断占用CPU，导致长工作永远也无法的得到CPU。 其次，聪明的用户会重写程序，愚弄调度程序。愚弄调度程序指的是用一些卑鄙的手段欺骗调度程序，让它给你远超公平的资源。 最后，一个程序可能在不同时间表现不同。一个计算密集的进程可能在某段时间表现为一个交互型的进程。用我们目前的方法，它不会享受系统中其他交互型作的待遇。 ### 尝试2：提升优先级 要让CPU密集型工作也能取得一些进展，我们能做什么？ 一个简单的思路是周期性的提升所有工作的优先级。有很多方法可以做到，最简单的就是将所有工作扔到最高优先级队列。 - 规则5：经过一段时间S，就将系统中所有工作重新加入最高优先级队列 新规则解决了两个问题：首先，进程不会饿死——在最高优先级队列中，它会以轮转的方式，与其他高优先级工作分享CPU，从而最终获得执行。其次，如果一个CPU密集型工作变成了交互型，当它的优先级提升时，调度程序会正确对待它。 当然，时间段S的加入导致了明显的问题：S的值该如何设置？ 系统研究员 John Ousterhout 曾将这种值称为 “巫毒常量”。如果S的值设置得太高，长工作会饥饿；如果设置的太低，交互型工作又得不到合适的CPU时间比例。 ### 尝试3：更好的计时方式 为MLFQ的每层队列提供更完善的CPU计时方式。 调度程序应该记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时。只要进程用完了自己的配额，就将它降到低一优先级的队列中去。不论它是一次性用完，还是拆成很多次。 - 规则4：一旦工作用完了其在某一层中的时间配额，就降低其优先级 有了这样的保护后，不论进程的 I/O 行为如何，都慢慢降低其优先级，因而无法获得超过公平的CPU时间比例 ### MLFQ 调优及其他问题 其中一个大问题是如何配置一个调度程序，如：配置多少队列？每一层队列的时间片配置多大？ 这些问题都没有显而易见的答案，因此只有利用对工作负载的经验，以及后续对调度程序的调优，才会导致令人满意的平衡 大多数的 MLFQ 变体都支持不同队列可变的时间片长度。高优先级队列通常只有较短的时间片（如10ms或更少），因而这一层的交互工作可以更快地切换。相反，低优先级队列中更多的是CPU密集型工作，配置更长的时间片会取得更好的效果。 最后，许多调度程序有一些我们没提到的特征。例如，有些调度程序将最高优先级队列留给操作系统使用，因此通常的用户工作是无法得到系统的最高优先级的。有些系统允许用户给出优先级设置的建议，比如通过命令行工具 nice，可以增加或降低工作的优先级（有限），从而增加或降低它在某个时刻运行的机会。 ### 小结 本章介绍了一种调度方式，名为多级反馈队列（MLFQ）：它有多级队列，并利用反馈信息决定某个工作的优先级。以史为鉴，关注进程的一贯表现，然后区别对待。 ## 第九章 调度：比例份额 本章中，我们来看一个不同类型的调度程序——比例份额调度程序，有时也称为公平份额调度程序 比例份额算法基于一个简单的想法：调度程序的最终目标，是确保每个工作获得一定比例的CPU时间，而不是优化周转时间和响应时间。 比例份额调度有一个非常优秀的现代例子，名为彩票调度：每隔一段时间，都会举行一次彩票抽象，以确定接下来该运行哪个进程。越是应该频繁运行的进程，越是应该拥有更多地赢得彩票的机会。 ### 基本概念：彩票数表示份额 彩票调度背后是一个非常基本的概念：彩票数代表了进程（或用户或其他）占有某个资源的份额。 一个进程拥有的彩票数占总彩票数的百分比，就是它占有资源的份额。 > 彩票调度最精彩的地方在于利用了 随机性。当你需要作出决定时，采用随机的方式常常是既可靠又简单的选择 > 最急方法相对于传统的决策方式，至少有3点优势： - 随机方法常常可以避免奇怪的边界情况 - 随机方法很轻量，几乎不需要记录任何状态 - 随机方法很快 ### 彩票机制 彩票调度还提供了一些机制，以不同的方式来调度彩票，一种方式是利用彩票货币的概念。这种方式允许拥有一组彩票的用户以它们喜欢的某种货币，将彩票分给自己的不同工作。之后才做系统再自动将这种货币兑换为正确的全局彩票。 另一个有用的机制是彩票转让。通过转让，一个进程可以临时将自己的彩票交给另一个进程，这种机制在客户端/服务端交互的场景中尤其有用，在这种场景中，客户端可以向服务端发送消息，请求其按自己的需求执行工作，为了加速服务端的执行，客户端可以将自己的彩票转让给服务端，从而尽可能加速服务端执行自己的请求的速度。服务端执行结束后会将这部分彩票归还给客户端。 最后，彩票通胀。利用通胀，一个进程可以临时提升或降低自己拥有的彩票数量。 > 注：从这章开始，将跳过大部分细节的实现，因为作者想成为一个Java程序员，对于操作系统的底层实现并不怎么关心，有需要可以阅读《操作系统导论》原文，解释的较为清晰 ## 多处理器调度 多核CPU带来了新版多困难。主要困难是典型的应用程序都只用一个CPU，增加了更多CPU并没有让这类程序运行的更快。为了解决这个问题，不得不重写这些应用程序，使之能并行执行。多线程应用可以将工作分散到多个CPU上，因此CPU资源越多就运行越快。 ### 背景：多处理器架构 为了理解多处理器调度带来的新问题，必须知道它与单CPU之间的基本区别。 区别的核心在于对硬件缓存（cache）的使用，以及多处理器之间共享数据的方式。 #### 单CPU 在单CPU系统中，存在多级缓存，一般来说会让处理器更快的执行程序。缓存是很小但是很快的存储设备，通常拥有内存中最热的数据的备份。相比只写，内存很大且拥有所有的数据，但访问速度较慢。通过将频繁访问的数据放在缓存中，系统似乎拥有很大又快的内存。 程序第一次读取数据是，数据在内存中，因此需要花费较长的时间（可能数十或数百纳秒）。处理器判断该数据很可能会被再次使用，因此将其放入CPU缓存中。如果之后称许再次需要使用同样的数据，CPU会先查找缓存。因为在缓存中找到了数据，所以取数据快得多（几纳秒），程序也就运行更快。 缓存是基于局部性（locality）的概念，局部性有两种，即时间局部性和空间局部性： - 时间局部性是指当一个数据被访问后，它很有可能会在不久的将来被再次访问，比如循环代码中的数据或指令本身 - 空间局部性是指当程序访问地址为 x 的数据时，很有可能接着访问x周围的数据，比如遍历数组或者指令的顺序执行。 由于这两种局部性存在于大多数的程序中，硬件系统可以很好地预测哪些数据可以放入缓存，从而运行得更好。 #### 多CPU 在多CPU的情况下，缓存要复杂得多。例如，假设一个运行在CPU1上的程序从内存地址A读取数据。由于不在CPU1的缓存中，所以系统直接访问内存，得到值D。然后程序修改了地址A处的值，只是将它的缓存更新为新值D'，将数据写回内存比较慢，因此系统通常会稍后再做。 假设这是操作系统中断了该程序的运行，并将其交给CPU2，重新读取地址A的数据，由于CPU2的缓存中并没有该数据，所以直接从内存中读取到了旧值D。 这一普遍的问题称为 **缓存一致性** 问题 硬件提供了这个问题的基本解决方案：通过监控内存访问，硬件可以保证获得正确的数据，并保证共享数据的唯一性。在基于总线的系统中，一种方式是使用总线窥探。每个缓存都通过监听链接所有缓存和内存的总线，来发现内存访问。如果CPU发现对它放在缓存中的数据的更新，会作废本地副本（从缓存中移除），或更新它（修改为新值）。 > 注：这样的操作会导致内存不可见的问题，降低缓存利用率，可通过Java关键字 volatile 解决。 ### 别忘了同步 跨CPU访问（尤其是写入）共享数据或数据结构时，需要使用互斥源语（如锁），才能保证正确性（其他方法，如无锁的数据结构，很复杂，偶尔才用）。 例如：假设多CPU并发访问一个共享队列。如果没有锁，即使有底层一致性协议，并发地从队列增加或删除元素，依然不会得到预期结果，需要用锁来保证数据结构状态更新的原子性。 ### 最后一个问题：缓存亲和度 在设计多处理器调度时遇到的最后一个问题，是所谓的缓存亲和度（cache affinity）。 这个概念很简单：一个进程在某个CPU上运行时，会在该CPU的缓存中维护许多状态。 下次该进程在相同CPU上运行时，由于缓存中的数据而执行得更快。相反，在不同的CPU上执行，会由于需要重新加载数据而很慢（好在硬件保证的缓存一致性可以保证正确执行）。 因此多处理器调度应该考虑到这种缓存亲和性，并尽可能将进程保持在同一个CPU上。 ### 单队列调度 现在讨论如何设计一个多处理器系统的调度程序。 最基本的方式是简单的复用单处理器的基本架构，将所有需要调度的工作放入一个单独的队列，称之为单队列多处理器调度（SQMS）。 SQMS有几个明显的短板： - 第一个是缺乏可扩展性。为了保证在多CPU上正常运行，调度程序的开发者需要在代码中通过加锁来保证原子性，这可能会带来巨大的性能损失。 - 第二个是缓存亲和性不好，每个工作不断的在不同CPU之间转移，与缓存亲和的目标背道而驰。为了解决这个问题，大多数SQMS调度程序都引入了一些亲和度机制。 ### 多队列调度 有些系统使用了多队列的方案，比如每个CPU一个队列，称之为多队列多处理器调度（MQMS） 在MQMS中，基本调度框架包含多个调度队列，每个队列可以使用不同的调度规则，比如轮转或其他任何可能的算法。当一个工作进入系统后，系统会依照一些启发性原则（如随机或选择较空的队列）将其放入某个调度队列。这样一来，每个CPU调度之间相互独立，避免了单队列方式中由于数据共享以及同步带来的问题。 MQMS的问题是负载不均，每个工作都在固定CPU上运行，可能出现一核有难八核围观的情况。 为了解决这个问题，最简单的答案是让工作移动，这种技术称之为 迁移。通过工作的跨CPU迁移，可以真正地实现负载均衡。 系统如何决定发起这样的迁移？ 一个基本的方法是采用一种技术，名为 工作窃取。通过这种方法，工作量较少的（源）队列不定期地“偷看”其他（目标）队列是不是比自己工作多。如果目标队列比源队列更满，就从目标队列“窃取 ”一个或多个工作，实现负载均衡。 如果太频繁地检查其它队列，就会带来较高的开销，可扩展性不好，而这是多队列调度最初的全部目标；相反，如果检查的间隔太长，又可能会带来严重的负载不均。找到合适的阈值仍是黑魔法，这在系统策略设计中很常见。 ### Linux 多处理器调度 在构建多处理器调度程序方面，Linux社区一直没有达成共识。一直以来，存在 3 种不同的调度程序： - O(1)调度程序 多队列 基于优先级 - 完全公平调度程序 多队列 基于比例调度 - BF调度程序（BFS） 单队列 基于比例调度（最早最合适虚拟截止时间优先算法(EEBEF)） > 注：Brain Fuck Scheduler ## 第13章 抽象：地址空间 从内存来看，早期的机器并没有提供多少抽象给用户。操作系统曾是一组函数（库），在物理内存中，使用剩余的内存，这里几乎没有抽象。  ### 多道程序和时分共享 分时系统诞生了，许多人意识到了批量计算的局限性，交互性变得很重要 一种实现时分共享的方法，是让一个进程单独占用全部内存运行一小段时间，然后停止它，并将它所有的状态信息保存在磁盘上（包含所有的物理内存），加载其它进程的状态信息，再运行一段时间，这就实现了某种比较粗糙的机器共享。 这种方法有一个问题：太慢了，特别是当内存增长的时候。虽然保存和恢复寄存器级的状态信息相对较快，但将全部信息保存到磁盘就太慢了。因此，在进程切换时，我们仍将进程信息放在内存中，这样操作系统可以更有效率的实现时分共享。  在上图中，有 3 个进程，每个进程拥有从 512KB 物理内存中切出来给它们的一小部分内存。假定只有一个CPU，操作系统选择运行其中一个进程（A），同时其它进程（B和C）则在队列中等待运行。 随着时分共享变得更流行，人们对操作系统又有了新的要求。特别是多个程序同时驻留在内存中，使得 保护 成为重要的问题。人们不希望一个进程可以读取其它进程的内存，更别说修改了。 ### 地址空间 因此操作系统需要提供一个易用的物理内存抽象。这个抽象叫做 **地址空间**，是运行的程序看到的系统中的内存。理解这个基本的操作系统内存抽象，是了解内存虚拟化的关键。 一个进程的地址空间包含运行的程序的所有内存状态，比如：程序的代码必须在内存中，因此它们在地址空间里。当程序在运行时，利用栈来保存当前的函数调用信息（方法栈），分配空间给局部变量，传递参数和函数返回值。最后，堆用于管理动态分配的、用户管理的内存，就像 C语言的 malloc()函数 或 Java 的 new 一样。当然，还有其他东西，（如，静态初始化的变量），但现在假设只有这 3 部分。  在上图中，我们有一个很小的地址空间（16KB）。程序代码位于地址空间的顶部（本例中从 0 开始，并且装入到地址空间的前 1 KB）。代码是静态的（因此很容易放在内存中），所以可以将它放在地址空间的顶部，程序运行时不再需要新的（代码）空间。 接下来，在程序运行时，地址空间有两个区域可能增长（收缩）。他们就是堆和栈。 把它们放在那里，是因为它们都希望能增长。通过将他们放在地址空间的两端，我们可以允许这样的增长：它们只需要在相反的方向增长。 因此堆在代码（1KB）之下开始向下增长（new对象时），栈从16KB开始向上增长（方法调用时）。 然而，堆栈的这种放置方式只是一种约定，可以使用不同的方式安排地址空间。 当然，当我们描述地址空间是，所描述的是操作系统提供给运行程序的抽象。程序不在物理地址 0 ~ 16KB 的内存中，而是加载在任意的物理地址。 当操作系统这样做时，我们说操作系统在虚拟化内存（virtualizing memory），因为运行的程序认为它被加载到了某个特定位置（例如0）的内存中，并且具有非常大的地址空间（例如32位或64位）。现实很不一样。 例如，当图 13.2 中的进程A尝试在 地址 0 （我们称之为 **虚拟地址**，virtual address）执行加载操作时，然而操作系统在硬件的支持下，出于某种原因，必须确保不是加载到 物理地址 0，而是物理地址 320KB（这是A载入内存的地址）。这是内存虚拟化的关键，这是世界上每一个现代计算机系统的基础。 > 隔离原则 > 隔离是建立可靠操作系统的关键原则。如果两个实体相互隔离，这意味着一个实体的失败不会影响另一个实体，操作系统力求让进程彼此隔离，从而防止相互造成伤害。通过内存隔离，操作系统进一步确保运行程序不会影响底层操作系统的操作。一些现代操作系统通过将某些部分与操作系统的其他部分分离，实现进一步的隔离。这样的微内核可以比整体内核提供更大的可靠性。 ### 目标 本章触及操作系统的工作——虚拟化内存。 操作系统不进虚拟化内存，还有一定风格。为了确保操作系统这做，我们需要一些目标来指导。 - 虚拟内存（VM）系统的一个主要目标是透明（即操作系统提供的假象不应该被程序所看破）。 因此，程序不应该感知到内存被虚拟化的事实，相反，程序的行为就好像它拥有自己的私有物理内存。在幕后，操作系统和硬件完成了所有的工作，让不同的工作复用内存，从而实现了这个假象。 - 虚拟内存的另一个目标是效率。 操作系统应该追求虚拟化尽可能高效，包括时间上（即不会使程序运行得更慢）和空间上（即不需要太多额外的内存来支持虚拟化）。在实现高效虚拟化时，操作系统不得不依靠硬件支持。 - 虚拟内存的第三个目标是 保护。 操作系统应确保进程受到保护，不会受其他进程影响，操作系统本身也不会受进程影响。当一个进程执行加载、存储或指令提取时，它不应该以任何方式访问或影响任何其它进程或操作系统本身的内存内容（即它地址空间之外的任何内存）。因此，保护让我们能够在进程之间提供隔离的特性，每个进程都应该在自己的独立环境中运行，避免其他出错或恶意进程的影响。 > 补充：你看到的所有地址都不是真的 > 实际上，作为用户级程序的程序员，可以看到的任何地址都是虚拟的。只有操作系统，通过精妙的内存虚拟化技术，知道这些指令和数据所在的物理内存的位置。所以永远不要忘记：如果你在一个程序中打印出一个地址，那就是一个虚拟的地址。虚拟地址只是提供地址如何在内存中分布的假象，只有操作系统（和硬件）才知道物理地址。 接下来的章节中，主要介绍虚拟化内存所需的基本机制，包括硬件和操作系统的支持。我们还将研究一些较相关的策略，你会在操作系统中遇到它们。包括如何管理可用空间，以及在空间不足时哪些页面该释放。 ## 第14章 插叙：内存操作API ### 内存类型 在运行一个C程序的时候，会分配两种类型的内存。第一种称为栈内存，它的申请和释放操作是编译器来隐式管理的，所以有时也称为自动内存。 因为有对长期内存的需求，所以我们需要第二种类型的内存，即所谓的堆内存，其中所有的申请和释放操作都由程序员显示地完成。 ### 常见错误 在使用 malloc()和 free()时会出现一些常见的错误。以下是我们在教授本科操作系统课程时反复看到的情形。所有这些例子都可以通过编译器的编译并运行。对于构建一个正确的 C 程序来说，通过编译是必要的，但这远远不够，你会懂的（通常在吃了很多苦头之后）。 实际上，正确的内存管理就是这样一个问题，许多新语言都支持自动内存管理（automatic memory management）。在这样的语言中，当你调用类似 malloc()的机制来分配内存时（通常用 new 或类似的东西来分配一个新对象），你永远不需要调用某些东西来释放空间。垃圾收集器（garbage collector）会运行，找出你不再引用的内存，替你释放它。 #### 忘记释放内存 另一个常见错误称为内存泄露（memory leak），如果忘记释放内存，就会发生。在长时间运行的应用程序或系统（如操作系统本身）中，这是一个巨大的问题，因为缓慢泄露的内存会导致内存不足，此时需要重新启动。因此，一般来说，当你用完一段内存时，应该确保释放它。请注意，使用垃圾收集语言在这里没有什么帮助：如果你仍然拥有对某块内 存的引用，那么垃圾收集器就不会释放它，因此即使在较现代的语言中，内存泄露仍然是一个问题。 该问题通常会在程序运行时逐渐加剧，并且可能会导致程序崩溃或系统崩溃。 #### 在用完之前释放内存 有时候程序会在用完之前释放内存，这种错误称为悬挂指针（dangling pointer），正如你猜测的那样，这也是一件坏事。随后的使用可能会导致程序崩溃或覆盖有效的内存（例如，你调用了 free()，但随后再次调用 malloc()来分配其他内容，这重新利用了错误释放的内存）。 ## 第15章 机制：地址转换 在实现虚拟内存时，在实现高效和控制的同时，提供期望的虚拟化。高效决定了我们要利用硬件的支持，在这开始的时候非常初级（如使用一些寄存器），但会变得相当复杂（如TLB、页表等）。 控制意味着操作系统要确保应用程序只能访问它自己的内存空间。因此，要保护应用程序不会相互影响，也不会影响操作系统，我们需要硬件的帮助。 最后，我们队虚拟内存还有一点需求，即灵活性。具体来说，我们希望程序能以任何方式访问它自己的地址空间，从而让系统更容易编程。 > 如何高效、灵活的虚拟化内存 我们利用了一种通用技术，有时被称为基于硬件的地址转换，简称为地址转换。 它可以看成是受限直接执行的这种一般方式的补充。利用地址转换，硬件对每次内存访问进行处理（即指令获取、数据读取或写入），将指令中的虚拟地址转换为数据实际存储的物理地址。因此，在每次内存引用时，硬件都会进行地址转换，将应用程序的内存引用重定位到内存中实际的位置。 仅仅依靠硬件不足以实现虚拟内存，因为他只是提供了底层机制来提高效率。操作系统必须在关键的位置介入，设置好硬件，以便完成正确的地址转换。因此它必须管理内存，记录被占用和空闲的内存位置，并明智而谨慎地介入，保持对内存的控制。 通过虚拟化，操作系统将丑陋的机器现实转换为一种有用的、强大的、易于使用的抽象。 > 介入（Interposition）很强大 > 介入是一种很常见有很有用的技术，计算机系统中使用介入常常能带来很好的效果。在虚拟内存中，硬件可以介入到每次内存访问中，将进程提供的虚拟地址转换为数据实际存储的物理地址。 > 但是，一般化的介入技术有更广阔的应用空间，实际上几乎所有良好定义的接口都应该提供介入机制，以便增加功能或在其他方面提升系统。这种方式的最基本的优点是 透明，介入完成时通常不需要改动接口的客户端，因此客户端不需要任何改动。 ### 假设 我们先假设用户的地址空间必须连续的存放在物理内存中。同时，为了简单，我们假设地址空间不是很大，具体来说，小于物理内存的大小。最后，假设每个地址空间的大小完全一样。别担心这些假设听起来不切实际，我们会逐步放宽这些假设，从而得到现实的内存虚拟化。 ### 一个例子 我们来看一个简单的例子，它的地址空间如下图所示：  ```c void func() { int x; x = x + 3; } ``` ```assembly movl 0x0(%ebx), %eax; addl $0x03, %eax; movl %eax, 0x0(%ebx); ``` 这段代码相对简单，它假定 x 的地址已经写入寄存器 ebx；之后通过 movl 将这个地址的值加载到通用寄存器 eax；下一条对 eax 的内容加 3，最后将其写回内存的同一位置。 从进程的角度来看，发生了以下几次内存访问： - 从地址 128 获取指令； - 执行指令（从地址 15KB 加载数据）； - 从地址 132 获取指令； - 执行指令； - 从地址 135 获取指令； - 执行指令（新值存入地址 15KB）； 从程序的角度来看，它的地址空间从 0 开始到 16KB 结束。它包含的所有内存引用都应该在这个范围内。然而，对虚拟内存来说，操作系统希望将这个内存地址放在物理内存的其他位置，并不一定从地址 0 开始。 因此我们遇到如下问题：怎样在内存中重定位这个进程，同时对该进程透明？怎样提供一种虚拟地址空间从 0 开始的假象，而实际上地址空间位于另外某个物理地址？ 下图展示了一个例子，说明这个进程的地址空间被放入物理内存后可能的样子。 操作系统将第一块物理内存留给了自己，并将上述例子中的进程地址空间重定位到 32KB 开始的物理内存地址。剩下两块内存空闲（16~32KB 和 48~64KB）。  ### 动态（基于硬件）重定位 为了更好地理解基于硬件的及其转换，我们先来讨论它的第一次应用。在20世纪50年代后期，它在首次出现的时分机器中引入，那时只是一个简单的思想，称为 基址加界限基址，有时又称为 动态重定位，我们将互换使用这两个术语。 具体来说，每个CPU需要两个硬件寄存器：基址寄存器 和 界限寄存器，有时称为 限制寄存器。 这组基址和界限寄存器，让我们能够将地址空间放在物理内存的任何位置，同时又能确保进程只能访问自己的地址空间。 在上面的例子中，操作系统决定加载在物理地址 32KB 的进程，因此将基址寄存器设置为这个值。 当程序运行时，该进程产生的所有内存引用，都会被处理器通过以下方式转换为物理地址： `physical address = virtual address + base` > 补充：基于软件的重定位 > 在早期，在硬件支持重定位之前，一些系统曾经采用纯软件的重定位方式。基本技术被称为静态重定位，其中一个名为加载程序的软件接手将要运行的可执行程序，将它的地址重写到物理内存中期望的位置偏移。 > 然而，静态重定位有许多问题，首先也是最重要的是不提供访问保护，进程中的错误地址可能导致对其他程序或操作系统内存的非法访问，一般来说，需要硬件支持来实现真正的访问保护。静态重定位的另一个缺点是一旦完成，稍后很难将内存空间重定位到其他位置。 进程中使用的内存引用都是虚拟地址，硬件接下来将虚拟地址加上基址寄存器中的内容，得到物理地址，再发给内存系统。 将虚拟地址转换为物理地址，这正是所谓的地址转换技术。也就是说，硬件取得进程认为它要访问的地址，将它转换成数据实际位于的物理地址。由于这种重定位是在运行时发生的，而且我们甚至可以在进程开始运行后改变其地址空间，因此这种技术一般被称为动态重定位。 界限寄存器提供了访问保护。在上面的例子中，界限寄存器被设置为 16KB。如果进程需要访问超过这个界限或者为负数的虚拟地址，CPU将触发一场，进程最终可能被终止。 界限寄存器的用处在于，它确保了进程产生的所有地址都在进程的“界限”中。 这种基址寄存器配合界限寄存器的硬件结构是芯片中的（每个CPU一队）。有时我们将CPU的这个负责地址转换的部分统称为内存管理单元（Memory Management Unit，MMU）。 关于界限寄存器再补充一点，它通常有两种使用方式： - 一种方式（像上面一样），它记录地址空间的大小，硬件在将虚拟地址与基址寄存器内容求和前，就检查这个界限。 - 另一种方式是界限寄存器中记录地址空间结束的物理地址，硬件转化虚拟地址到物理地址之后才去检查这个界限。 > 补充：数据结构——空闲列表 > 操作系统必须记录哪些空闲内存没有使用，以便能够为进程分配内存。很多不同的数据结构可以用于这项任务，其中最简单的是空闲列表（free list）。它就是一个裂变，记录当前没有使用的物理内存的范围。 ### 硬件支持：总结 我们需要两种CPU模式，操作系统在特权模式或内核模式运行，可以访问整个机器资源；应用程序在用户模式运行，只能做有限的操作。只要一个位，也许保存在CPU状态字中，就能说明当前的CPU运行模式。 硬件还需要提供基址寄存器和界限寄存器。硬件也必须能检查地址是否有用，通过界限寄存器和CPU内的一些电路来实现。 硬件应该提供一些特殊的指令，用于修改基址寄存器和界限寄存器，允许操作系统在切换进程时改变它们。这些指令是特权指令，只有在内核模式下，才能修改这些寄存器。 最后，在用户程序尝试非法访问内存（越界）时，CPU必须能产生异常。在这种情况下，CPU应该阻止用户程序的执行，并安排操作系统的“越界”异常处理程序去处理。 类似的，如果用户程序尝试修改基址或界限寄存器时，CPU也应该产生异常并调用“用户模式尝试执行特权指令”的异常处理程序。 CPU还必须提供一种方法，来通知OS这些处理程序的位置，因此又需要另一些特权指令。 ### 操作系统的问题 在一些关键的时刻操作系统需要介入，以实现机制和界限方式的虚拟内存。 第一，在进程创建时，操作系统必须为进程的地址空间找到内存空间。当新进程创建时，操作系统检索这个数据结构（空闲列表），为新地址空间找到位置，并将其标记为已用。 第二，在进程终止时，操作系统回收它的所有内存，给其它进程或操作系统使用。在进程终止时，操作系统会将这些内存放回空闲列表，并根据需要清除相关的数据结构。 第三，在上下文切换时，操作系统也需要采取额外的行动。每个CPU毕竟只有一个基址寄存器和一个界限寄存器，但对于每个运行的程序，它的值都不同，因为每个程序被加载到内存中不同的物理地址。因此，在切换进程时，操作系统必须保存和恢复基址寄存器和界限寄存器。具体来说，当操作系统决定终止当前运行的程序时，它必须将当前基址和界限寄存器中的内容保存在内存中，放在某种每个进程都有的结构中，如进程结构或进程控制块中。类似的，当操作系统恢复执行某个进程时（或第一次执行），也必须给基址和界限寄存器设置正确的值。 注意，当进程停止时，操作系统可以改变其地址空间的物理位置，这很容易。操作系统首先让进程停止运行，然后将地址空间拷贝到新的位置，最后更新保存的基址寄存器，指向新的位置。当该进程恢复执行时，它的基址寄存器会被恢复，它再次开始运行，显然它的指令和数据都在新的内存位置了。 第四，操作系统必须提供异常处理程序，或一些要调用的函数，向上面提到的那样。操作系统在启动时加载这些处理程序（通过特权命令）。 ### 小结 这个简单的动态重定位有效率低下的问题，从图15.2中可以看到，重定位的进程使用了从 32KB 到 48KB 的物理内存，但由于该进程的栈区和堆区并不很大，导致这块内存区域中大量的空间被浪费。这种浪费称为 *内部碎片*，指的是已经分配的内存单元内部有未使用的空间。在当前我们的方式中，即使有足够的物理内存容纳更多进程，但我们目前要求将地址空间放在固定大小的槽块中，因此会出现内部碎片。所以，我们需要更加复杂的机制，以便更好地利用物理内存，避免内部碎片。第一次尝试是将基址加界限的概念稍稍泛化，得到 **分段** 的概念。 ## 第16章 分段 到目前为止，我们一直假设将所有进程的地址空间完整的加载到内存中。利用基址和界限寄存器，操作系统很容易将不同进程重定位到不同的物理内存区域。但对于这些内存区域，在栈和堆之间，存在一块空闲空间。  从上图可知，如果我们将整个地址空间放入物理内存，那么栈和堆之间的空间并没有被进程使用，缺依然占用了实际的物理内存。因此，简单的通过基址寄存器和界限寄存器实现的虚拟内存很浪费。另外，如果剩余物理内存无法提供连续区域来放置完整的地址空间，进程便无法进行。这种基址加界限的方式看来并不像我们期望的那样灵活。 ### 分段：泛化的基址/界限 为了解决这个问题，分段的概念应运而生。分段并不是一个新概念，它甚至可以追溯到20世纪60年代初期。这个想法很简单，在MMU中引入不止一个基址和界限寄存器对，而是给地址空间内的每个逻辑段一对。 一个段只是地址空间里的一个连续定长的区域，在典型的地址空间里有 3 个逻辑不同的段：代码、栈、堆。 分段机制使得操作系统能够将不同的段放到不同的物理内存区域，从而避免了 虚拟地址空间 中的 未使用部分 占用 物理内存。 通过给每个段一对基址和界限寄存器，可以将每个段独立的放入物理内存。如下图所示，64KB 的物理内存中放置了三个段（为操作系统保留 16KB）。   从图中可以看到，只有已使用的内存才在物理内存中分配空间，因此可以让那巨大的地址空间，其中包含大量未使用的地址空间（有时称为 稀疏地址空间）。 需要MMU中的硬件结构来支持分段：在这种情况下，需要一组 3 对基址和界限寄存器。从上表中可以看到上图中的寄存器值，每个界限寄存器记录一个段的大小。 > 补充：段错误 > 段错误指的是在支持分段的机器上发生了非法的内存访问。有趣的是，即使在不支持分段的机器上，这个术语依然保留。 ### 我们引用哪个段 硬件在地址转换时使用 段寄存器。它如何知道段内的偏移量，以及地址引用了哪个段？ 一种常见的方式，有时称为显式方式，就是用虚拟地址的开头几位来标识不同的短，VAX/VMS 系统使用了这种技术。 在之前的例子中，我们有三个段，因此需要两位来标识，如果我们用 14 位的虚拟地址的前两位来标识，那么虚拟地址如下图所示：  从图中可以看到，前两位告诉硬件我们引用哪个段。剩下12位是段内偏移：`0000 0110 1000` 即 十六进制 0x068 或 十进制 104。 因此，硬件就用前两位来决定使用哪个段寄存器，然后用后12位作为段内偏移。偏移量与与基址寄存器相加，硬件就得到了最终的物理地址。偏移量也简化了对段边界的判断，我们只要检查偏移量是否小于界限，大于界限的为非法地址。 上面使用两位来区分，但实际只有 3 个段，有一个段的地址空间被浪费。因此有些系统会将堆和栈当作同一个段，因此只需要 1 位 来做标识。 在隐式方法中，硬件通过地址产生的方式来确定段。例如，如果地址由PC产生（即它是指令获取），那么地址在代码段。如果基于栈或基址指针，它一定在栈段。其他则在堆段。 ### 栈怎么办 在表 16.1 中，栈被重定位到物理地址 28KB。但有一点关键区别，它反向增长。在物理内存中，它始于 28KB，增长回到 26KB，相应虚拟地址从 16KB 到 14KB。地址转换有所不同。 首先，我们需要一点硬件支持。除了基址和界限外，硬件还需要知道栈增长的方向（用一位区分，比如 1 代表自小而大增长，0 反之）。  硬件理解段可以反向增长后，这种虚拟的地址转换必须有点不同。 举一个例子，假设要访问虚拟地址 15KB，它应该映射到物理地址 27KB。该虚拟地址的二进制形式是 `11 1100 0000 0000`。硬件利用前两位指定段，然后处理偏移量 3KB。为了得到正确的反向偏移，我们从 3KB 中减去最大的段地址（栈段的栈底地址，即上表中的28KB，但并不是同一个例子）：在这个例子中，段可以是 4KB，因此正确的偏移量是 3KB 减去 4KB，即 -1KB。然后用这个反向偏移量加上基址 -1 + 28 = 27KB，得到正确的物理地址。用户可以进行界限检查，确保反向偏移量的绝对值小于段的大小。 ### 支持共享 要节省内存，有时候在地址空间之间共享某些内存段是有用的。尤其是，代码共享很常见，今天的系统仍然在使用。 为了支持共享，需要一些额外的硬件支持，这就是 保护位。 基本为每个段增加了几个位，表示程序是否能够读写该段，或执行其中的代码。通过将代码标记为只读，同样的代码可以被多个进程共享，而不用担心破坏隔离。虽然每个进程都认为自己独占这块内存，但操作系统秘密的共享了内存，进程不能修改这些内存，所以假象得以保持。 有了保护位，前面的算法也必须改变。除了检查虚拟地址是否越界，硬件还需要检查特定访问是否允许。如果用户试图写入只读段，或从非执行段执行指令，硬件会触发异常，让操作系统来处理出错进程。 ### 细粒度与粗粒度的分段 到目前为止，我们的例子大多数针对只有很少的几个段的系统（代码、栈、堆）。 我们可以认为这种分段是粗粒度的，因为它将地址空间分成较大的、粗粒度的块。 但是一些早期系统更灵活，允许将地址空间划分成大量较小的段，这被称作细粒度划分。 ### 操作系统支持 系统运行时，地址空间中的不同段被重定位到物理内存中，。与我们之前介绍的整个地址空间只有一对基址和界限寄存器的方式相比，节省了大量物理内存。 然而，分段也带来了新的问题： 第一个是老问题：操作系统在上下文切换时应该做什么？ 各个段寄存器中的内容必须保存和恢复。显然，每个进程都有自己独立的虚拟地址空间，操作系统必须在进程运行之前，确保这些寄存器被正确的赋值。 第二个问题更重要，即管理物理内存的空闲空间。新的地址空间被创建时，操作系统需要在物理内存中为它的段找到空间。之前，我们假设所有的地址空间大小相同，物理内存可以被认为是一些槽块，进程可以放进去。现在，每个进程都有一些段，每个段的大小也可能不同。 一般遇到的问题是，物理内存很快充满了许多空闲空间的小洞，因而很难分配给新的段，或扩大已有的段。这种问题被称为 外部碎片。如下图左所示。  该问题的一种解决方案是 紧凑 物理内存，重新安排原有的段。但是内存紧凑的成本很高，因为拷贝段是内存密集型的，一般会占用大量的处理器时间。上图右是紧凑后的内存。 一种更见的做法是利用空闲列表管理算法，试图保留大的内存块用于分配。 相关的算法包括传统的最优匹配，最坏匹配，首次匹配以及像伙伴算法这样更复杂的算法等。但遗憾的是，无论这些算法有多么精妙，都无法完全消除外部碎片了。因此，好的算法只是试图减小它。 ## 第17章 空闲空间管理 本章讨论所有内存管理系统的一个基本方面，无论是 malloc 库（管理进程中堆的页），还是操作系统本身（管理进程的地址空间）。具体来说，我们会讨论 空闲空间管理 的一些问题。 如果需要管理的空间被划分为固定大小的单元，就很容易。在这种情况下，只需要维护这些固定大小的单元的列表，如果有请求，就返回列表中的第一项 > 注：感觉更像在描述队列 如果要管理的空闲空间由大小不同的单元构成，管理就变得困难。这种情况出现在用户级的内存分配库（如 malloc())，或操作系统用分段的方式实现的虚拟内存。 在这两种情况下，出现了外部碎片的问题：空间被分割成大小不同的小块，成为碎片，后续的其你去可能失败，因为没有一块足够大的连续空闲空间，即使这时总的空闲空间超出了请求的大小。 ### 底层机制 #### 分割与合并 空间列表包含一组元素，记录了堆中哪些空间还没有分配。假设下面有 30 字节的堆：  这个堆的对应的空闲队列会有两个元素，一个描述第一个10字节的空闲区域（字节 0 ~ 9），第二个描述另一个空闲区域（字节 20 ~ 29）：  此时任何大于 10 字节的分配请求都会失败，因为没有足够的连续可用空间；而恰好 10字节的请求可以有两个空闲块中的任意一个满足。 如果申请小于 10字节的空间会发生什么？ 假设我们只申请一个字节的内存。这种情况下，分配程序会执行所谓的分割动作：它找到一块可以满足请求的空闲空间，将其分割，第一块返回给用户，第二块留在空闲列表中。如使用第二块空闲空间：  许多分配程序中因此也有一种机制，名为合并。还是看前面的例子。 对于这个堆，如果应用程序调用 free(10)，归还堆中间的空间，会发生什么？ 如果只是简单的将这块空间加入空闲列表，会得到如下的结果：  问题出现了：尽管整个堆现在完全空闲，但它似乎被分割成了 3 个 10字节的区域。 这时，如果用户请求 20字节 的空间，简单便利空闲列表会找不到这样的空闲块，因此返回失败。 为了避免这个问题，分配程序会在释放一块内存时合并可用空间。想法很简单：在归还一块空间是，查看附件的空闲空间块，如果相邻则合并。最后的空闲列表应该像这样：  > 注：后续介绍了在空闲空间内部建立这样的列表，以及管理空闲空间的基本策略，这里略过。 ## 第18章 分页：介绍 操作系统有两种方法，来解决大多数空间管理问题。第一种是将空间分割成不同长度的分片，就像虚拟内存管理中的分段。但遗憾的是，这个解决方法存在固有的问题，即 将空间切成不同长度的分片以后，空间本身会碎片化，随着时间推移，分配内存会变得比较困难。 因此，值得思考第二种方法：将空间分割成固定长度的分片。在虚拟内存中，这种思想称为 **分页**。分页可以追溯到一个早期的重要操作系统——Atlas。 分页不是将一个进程的地址空间分割成几个不同长度的逻辑段（代码、栈、堆），而是分割成固定大小的单元，每个单元称为一*页*。相应的，我们吧物理内存看成是定长槽块的阵列，叫做 **页帧**。每个这样的页帧包含一个虚拟内存页。 ### 一个简单例子 下图左展示了一个只有 64 字节的小地址空间，有 4 个 16字节 的页（虚拟页 0、1、2、3）。真实的地址空间大很多，32位有4GB的地址空间，64位有 2^64 位的地址空间。 物理内存，如下图右所示，也由一组固定大小的槽块组成。在这个例子中，有 8 个页帧（有128 字节物理内存组成，也是极小的）。从图中可以看出，虚拟地址空间的页存放在物理内存的不同位置，还可以看出，操作系统自己用了一些物理内存。 与我们之前的方法相比，分页有许多优点。可能最大的改进就是灵活性：通过完善的分页方法，操作系统能够高效地提供地址空间的抽象，不管进程如何使用地址空间。例如：我们不会假定堆和栈的增长方向，以及它们如何使用。 另一个优点是分页提供的空闲空间管理的简单性。例如，如果操作系统希望将 64 字节的小地址空间放到 8 页的物理地址空间中，它只需要找到 4 个空闲页。也许操作系统保存了一个所有空闲页的空闲列表，只需要从这个列表中拿出 4 个空闲页。在上图右的例子中，操作系统将地址空间的虚拟页 0 放在物理页帧 3，虚拟页 1 放在物理页帧 7，虚拟页 2 放在物理页帧 5，虚拟页 3 放在物理页帧 2。页帧 1、4、6 目前是空闲的。  为了记录地址空间的每个虚拟页放在物理内存中的位置，操作系统通常为每个进程保存一个数据结构，称为 页表。页表的主要作用是为地址空间的每个虚拟页面保存地址转换，从而让我们知道每个页在物理内存中的位置。 对于我们的示例，页表具有以下 4 个条目：（虚拟页 0 → 物理帧 3）、（VP 1 → PF 7）、（VP 2 → PF 5）、（VP 3 → PF 2）。 重要的是，这个页表是*每一个进程*的数据结构。如果在上面的示例中运行另一个进程，操作系统将不得不为它管理不同的页表，因为它的虚拟页显然映射到不同的物理页面（共享除外）。 为了转换该过程生成的虚拟地址，我们必须首先将它分成两个组件：虚拟页面号（virtual page number，VPN）和页内的偏移量。 对于这个例子，因为进程的虚拟地址空间是 64 字节的，因此虚拟地址需要 6 位来表。 在下图中，Va5是虚拟地址的最高位，Va0是最低位。因为我们知道页的大小（16字节），因此可以进一步划分虚拟地址：  页面大小为 16 字节，位于 64 字节的地址空间，因此我们能够选择 4 个页，地址的前 2 位就是做这件事的。因此，我们有一个 2 位的虚拟页号（VPN），其余位则是偏移量。 ### 页表存在哪里 页表可以变得非常大，比我们之前讨论过的小段表或基址/界限对要大得多。 设想一个典型的 32位地址空间，带有 4KB 的页。这个虚拟地址分成 20 位的 VPN 和 12 位的偏移量（1KB = 2^10，1KB << 2 = 4KB）。 一个 20 位的VPN意味着，操作系统必须为每个进程管理 2^20 个地址转换（大约一百万）。假设每个页表格条目（PTE）需要 4 字节，来保存物理地址转换和其他有用的东西，每个页表就需要 4MB 内存。 由于页表如此之大，我们没有在 MMU 中利用任何特殊的硬件来存储当前正在运行的页表的进程，而是将每个进程的页表存储在内存中（甚至可以交换到磁盘上）。 ### 列表中究竟有什么 页表就是一种数据结构，用于将虚拟地址（虚拟页号）映射到物理地址（物理帧号）。 因此，任何数据结构都可以采用，最简单的称为线性页表，就是一个数组。操作系统通过虚拟页号（VPN）检索该数组，并在该索引处查找页表项（PTE），以便找到期望的物理帧号（PFN）。 ### 分页：也很慢 内存中的页表，我们已经知道它们太大了。事实证明，它们也会让速度变慢。 以简单的指令为例：`movl 21, %eax` 在这个例子中，我们假定硬件为我们执行地址转换。要获取所需数据，系统必须首先将虚拟地址 21 转换为正确的物理地址 117。因此，在从地址 117 获取数据之前，系统必须首先从进程的页表中提取适当的页表项，执行转换，然后从物理内存中加载数据。 为此，硬件必须知道当前正在运行的进程的页表位置。现在我们假设一个页表基址寄存器包含页表的起始位置的物理地址。 对每个内存引用（无论是取指令还是显式加载或存储），分页都需要我们执行一个额外的内存引用，以便首先从页表中获取地址转换。工作量很大，额外的内存引用开销很大，在这种情况下，可能会使进程减慢两倍或更多。 如果不仔细设计硬件和软件，页表会导致系统运行速度过慢，并占用太多内存。虽然看起来是内存虚拟化需求的一个很好的解决方案，但这两个关键问题必须克服。 > 补充：数据结构——页表 > 现代操作系统的内存管理子系统中最重要的数据结构之一就是页表。通常，页表存储虚拟—物理地址转换，从而让系统知道地址空间的每个页实际驻留在物理内存中的哪个位置。由于每个地址空间都需要这种转换，因此一般来说，系统中每个进程都有一个页表。也表的确切结构要么由硬件确定，要么由操作系统更灵活的管理。 ## 第19章 分页：快速地址转换（TLB） 我们要增加所谓的 `地址转换旁路缓冲存储器（translation-lookaside buffer，TLB）`，它就是频繁发生的虚拟到物理地址转换的硬件缓存。因此，更好的名称应该是地址转换缓存。 对每次内存访问，硬件先检查TLB，看看其中是否有期望的转换映射，如果有，就完成转换，不用访问页表。TLB带来了巨大的性能提升，实际上，因此它使得虚拟内存称为可能。 ### 小结 通过增加一个小的，芯片内的TLB作为地址转换的缓存，大多数内存引用就不用访问内存中的页表了。因此，在大多数情况下，程序的性能就像内存没有虚拟化一样，这是操作系统的杰出成就，当然对现代操作系统中的分页非常必要。 但是，TLB也不能满足所有的程序需求。具体来说，如果一个程序短时间内访问的页数超过了TLB缓存的页数，就会产生大量的 TLB 缓存未命中，运行速度就会变慢。这种现象被称为超出TLB不凡范围，这队某些程序可能是相当严重的问题。解决这个问题的一种方案是支持更大的页，使TLB的有效覆盖率增加。对更大页的支持通常被数据库管理系统（Database Management System，DBMS）这样的程序利用，它们的数据结构比较大，而且是随机访问。 另一个TLB问题值得一提：访问 TLB 很容易成为CPU瓶颈，尤其是有所谓的物理地址索引缓存。 有了这种缓存，地址转换必须发生在访问该缓存之前，这会让操作变慢。为了解决这个潜在的问题，人们用虚拟地址 直接访问缓存，从而在缓存命中时避免昂贵的地址转换步骤。像这种虚拟地址缓存索引解决了一些性能问题，但也带来了新的问题。 ## 分页：较小的表 通常系统中的每个进程都有一个页表，有100个活动进程就要为也表分配数百兆的内存。因此，要寻找一种技术来减轻这种沉重的负担。 ### 简单的方案：更大的页 可以用一种简单的方法减小页表的大小：使用更大的页。 > 补充：多种页的大小 > 许多体系结构（如MIPS、SPARC、x86-64）现在都支持多种页大小。通常使用一个小的（4 / 8 KB）页大小。 这种方法的主要问题在于，大内存页会导致每页的浪费，称为内部碎片问题。 因此，大多数系统在常见情况下使用相对较小的页大小，如 4KB（x86）或 8KB（SPARCv9）。 ### 混合方法：分页和分段 将分页和分段相结合，以减少页表的内存开销。 ### 多级页表 另一种方法并不依赖与分段，但也试图解决相同的问题：如何去掉页表中的所有无效区域，而不是将他们全部保留在内存中？ 我们将这种方法称为多级页表，因为它将线性页表全部变成了类似于树的东西。这种方法非常有效，许多现代系统都用它（如 x86）。 多级页表的思想很简单。首先，将页表分成页大小的单元。然后，如果整页的页表项（PTE）无效，就完全不分配该页的页表。为了追踪页表的页是否有效（以及有效时在内存中的位置），使用了名为 页目录 的新结构。 与我们至今看到的方法相比，多级页表有一些明显的优势。首先，也许最明显的是，多级页表分配的页表空间，与你正在使用的地址空间内存量成比例。因此它通常很紧凑，并支持稀疏的地址空间。 > 在构建数据结构时，应始终考虑时间和空间的折中。不可能两者兼得，通常需要用空间换时间。 ### 反向页表 在反向页表中，可以看到页表世界中更极端的空间节省。在这里，我们保留了一个页表，其中的项代表系统的每个物理页，而不是有许多页表（系统的每个进程一个）。页表项告诉我们哪个进程正在使用此页，以及该进程的哪个虚拟页映射到物理页。 通常使用散列表。 ### 将页表交换到磁盘 即使我们有很多技巧来减小页表的大小，但是它仍有可能太大而无法一次装入内存。因此，一些系统将这样的页表放入内核虚拟内存，从而允许系统在内存压力较大时，将这些页表中的一部分交换到磁盘。 ## 第21章 超越物理内存：机制 为了支持更大的地址空间，操作系统需要把当前没有在用的那部分地址空间找个地方存起来。一般来说，这个地方有一个特点，就是比内存拥有更大容量，一般来说也更慢。在现在系统中，硬盘通常能满足这个需求。 一个反面例子是，一些早期系统使用“内存覆盖”，它需要程序员 根据需要 手动移入或移出内存中的代码或数据。 不仅是一个进程，增加交换空间让操作系统为多个并发运行的进程都提供巨大地址空间的假象。多道程序和易用性都需要操作系统支持比物理内存更大的地址空间。这是所有现代虚拟内存系统都会做的事情。 ### 交换空间 我们要做的第一件事就是，在硬盘上开辟一部分空间用于物理页的移入和移出。在操作系统中，一般这样的空间称为交换空间，因为我们将内存中的页交换到其中，并在需要的时候交换回去。 因此，我们会假设操作系统能够以页大小为单元读取或写入交换空间。为了达到这个目的，操作系统需要记住给定页的硬盘地址。 交换空间的大小是非常重要的，它决定了系统在某一时刻能够使用的最大内存页数。 ### 交换何时真正发生 为了保证有少量的空闲内存，大多数操作系统会设置高水位线（HW）和低水位线（LW），来帮助决定何时从内存中清除页。原理是这样的： 当操作系统发现有少于 LW 个页可用时，后台负责释放内存的线程会开始运行，知道有 HW 个可用的物理页。这个后台线程有时称为 交换守护进程 或 页守护进程，然后这个守护进程会进入休眠状态。 通过同时执行多个交换过程，我们可以进行一些性能优化。例如，许多系统会把多个要写入的页聚集或分组，同时写入到交换区间，从而提高硬盘的效率，这种合并操作减少了硬盘的寻道和旋转开销，从而显著提高了性能。 ## 第22章 超越物理内存：策略 当内存不够时，事情会变得更有趣。在这种情况下，由于内存压力 迫使操作系统换出了一些页，为常用的页腾出空间。确定要踢出哪些页封装在操作系统的替换策略中。 ### 缓存管理 由于内存中只包含系统中所有页的子集，因此可以将其视为系统中虚拟内存页的缓存。因此，在为这个缓存选择替换策略时，我们的目标是让缓存未命中最少。 ### 最优替换策略 最优替换策略是 Belady 多年前开发的。最优替换策略能达到总体命中率数量最少，即替换内存中在最远的将来才会访问的页，可以达到缓存命中率最低。 > 补充：缓存命中率的类型 > 在计算机体系结构世界中，架构师有时会将未命中分为 3 类：强制性、容量和冲突未命中，有时称为 3C。 > 发生 强制性未命中（或冷启动未命中）是因为缓存开始是空的，本次是对项目的第一次引用。 > 而由于缓存空间不足而不得不踢出一个项目以将新项目引入缓存，就发生了容量未命中。 > 第三种 冲突未命中，出现在硬件中，因为硬件缓存中对项的放置位置有限制，这是由于所谓的集合关联性。它不会出现阿紫操作系统页面缓存中，因为这样的缓存总是完全关联的，即对页面可以放置的内存位置没有限制。 ### LRU 正如在调度策略所做的那样，为了提高后续的命中率，我们再次通过历史的访问情况作为参考。 页替换策略可以使用的一个历史信息是频率。如果一个页被访问了很多次，也许它不该被替换，因为它显然更有价值。页更常用的属性是访问的近期性，越近被访问的页，也许再次访问的可能性也就越大。 这一系列的策略是基于人们所说的局部性原理，基本上只是对程序以及其行为的观察。这个原理简单地说就是倾向于频繁被访问的某些代码和数据结构，因此，我们应该尝试用历史数据来确定哪些页面更重要，并在需要踢出页时将这些页保存在内存中。 因此，一系列简单的基于历史的算法诞生了：“最不常用”（Least-Frequently-Used，LFU）策略会替换最不经常使用的页。同样，“最近最少使用”（Least-Recently-Used，LRU）策略会替换最近最少使用的页。 > 补充：局部性原则 > > 程序倾向于表现出两种类型的局部： > > - 第一种是空间局部性 > 它指出如果页 P 被访问，可能围绕它的页也会被访问 > - 第二种是时空局部性 > 它指出最近访问过的页很可能在不久的将来再次访问 还有一些完全相反的算法：最经常使用策略（MFU）和最近使用策略（MRU），在大多数情况下，这些策略的效果都不好，应为它们忽视了大多数程序都具有的局部性特点。 ### 近似 LRU 从计算开销的角度来看，近似 LRU 更为可行，实际上这也是许多现代操作系统的做法。 操作系统使用 时钟算法，实现近似 LRU。 ### 考虑脏页 时钟算法的一个小修改，是对内存中的页是否被修改的额外考虑。这样做的原因是：如果页已经被修改并因此变脏，则踢出它就必须将它写回磁盘，这很昂贵。如果它没有被修改，踢出就没成本。物理帧可以简单的重用于其他目的而无需I/O。因此，一些虚拟机系统更倾向于踢出干净页，而不是脏页。 ### 其他虚拟内存策略 页面替换不是虚拟内存子系统采用的位移策略。例如：操作系统还必须决定何时将页载入内存。该策略有时称为 页选择策略，它向操作系统提供了一些不同的选项。 对大多数页而言，操作系统只是使用按需分页，这意味着操作系统在页被访问时将页载入内存中，按需即可。 当然，操作系统可能会猜测一个页面即将被使用，从而提前载入，这种行为被称为 预取，只有在有合理的成功机会时，才应该这样做。 另一个策略决定了操作系统如何将页面写入磁盘。当然，它们可以简单地一次写入一个。然而，许多系统会在内存中收集一些待完成的写入，并以一种更高效的写入方式将它们写入硬盘。这种行为称为 聚集写入，或是 分组写入。这样做有效是因为硬盘驱动器的性质，单次执行大的写操作，比许多小的写操作更有效。 ### 抖动 当内存被超额请求时，操作系统应该做什么，这组正在运行的进程的内存需求是否超过了可用物理内存？在这种情况下，系统将不断地进行 换页，这种情况有时被称为 抖动。 目前的一些系统采用更严格的方式处理内存过载。例如，当内存超额请求时，某些版本的 Linux 会运行“out-of-memory killer”，。这个守护进程选择一个内存密集型进程并杀死它，从而以不怎么委婉的方式减少内存。虽然成功的减轻了内存压力，但很可能导致严重的问题。 ### 小结 在许多情况下，由于内存访问和磁盘访问时间之间的差异增加，这些算法的重要性降低了。由于分页到硬盘的成本非常昂贵，因此频繁分页的成本太高。所以，过度分页的最佳解决方案往往很简单：购买更多内存。 ## 第26章 并发：介绍 本章将介绍为单个运行进程提供的新抽象：线程。 经典观点是程序只有一个执行点（一个PC，用来存放要执行的指令），但多线程程序会有多个执行点（多个PC）。换一个角度来看，每个线程类似于独立的进程，只有一点区别：它们共享地址空间，从而能够访问相同的数据。 因此，单个线程的状态与进程状态非常类似。线程有一个PC，记录程序从那里获取指令。每个线程有自己的一组用于计算的寄存器。所以，如果有两个线程运行在一个CPU上，从一个线程切换到另一个线程时，必定发生上下文切换。线程之间的上下文切换类似于进程间的上下文切换。 对于进程，我们将进程状态保存到进程控制块（Process Control Block，PCB）。 现在，我们需要一个或多个线程控制块（Thread Control Block，TCB），保存每个线程的状态。但是，与进程相比，线程之间的上下文切换有一点主要区别：地址空间保持不变（即不需要切换页表）。 线程与进程之间的另一个主要区别在于栈。在简单的传统进程地址空间模型（单线程）中，只有一个栈，通常位于地址空间的底部。  然而，在多线程的进程中每个线程独立运行，当然可以调用各种例程来完成正在执行的任何工作。不是地址空间中只有一个栈，而是每个线程都有一个栈。假设有一个多线程的进程，它有两个线程，地址空间如上右图所示。 可以看到，两个栈跨越了进程的地址空间。因此，所有位于栈上的变量、参数、返回值和其他放在栈上的东西，将被放置在有时称为 `线程本地(thread-local)` 存储的地方，即相关线程的栈。 ### 核心问题：不可控的调度 例：自增不具有原子性 ```c x++ ``` ```assembly mov 0x8049alc, %eax add $0x1, %eax mov %eax, 0x8049alc ``` 在多线程下，对共享变量 x 做自增 设想线程1进入这个代码区域，它将 x 的值加载到它的寄存器 eax 中。因此，线程1 的 eax = 50，然后它向寄存器加 1，因此 eax = 51。此时，不幸的事情发生了：时钟中断发生。因此，操作系统将正在运行的线程的状态保存到线程的TCB中。 然后，线程2被选中运行，它将 x 的值加载到它的寄存器 eax 中，此时 x 的值仍为 50，然后它执行后续两条指令，并将 51 写回内存，因此现在 x 的值是 51。 最后，又发生了上下文切换，线程1恢复运行，它继续执行最后一条指令，将它寄存器中的 51 写回内存。 应该发生的情况是：x 从 50 变成 52，但实际是 51。 如上三条汇编指令，是各自执行，而非全部执行或全部不执行，不具备原子性。 这里展示的情况称为竞争状态：结果取决于代码的时间执行。由于在执行过程中发生了上下文切换，我们得到了错误的结果。实际上，可能每次都会得到不同结果。 由于执行这段代码的多个线程可能导致竞争状态，因此我们将此段代码称为临界区。 **临界区是访问共享变量（共享资源）的代码片段**。 ### 原子性愿望 原子方式的意思是“作为一个单元”，有时我们说“全部或没有”。 > 注：即 一个单元内的代码，要么全部执行，要么全部不执行，不存在中间态。 因此，我们要做的是要求硬件提供一些有用的指令，可以在这些指令上构建一个通用的集合，即所谓的 `同步原语`。通过使用这些硬件同步原语，加上操作系统的一些帮助，我们将能够构建多线程代码，以同步和受控的方式访问临界区，从而产生正确的结果。 > 补充：并发术语 > > - 临界区：是访问共享资源的一段代码，资源通常是一个变量或数据结构 > - 竞争状态：出现在多个执行线程大致同时进入临界区时，它们都试图更新共享的数据结构，导致了错误的结果 > - 不确定性：程序由一个或多个竞争状态组成，程序的输出因运行而异，具体取决于哪些线程在何时运行 > 为了避免这些问题，线程应该使用互斥原语。 > 注：其余部分见JUC ## 第30章 条件变量 线程可以使用条件变量，来等待一个条件变成 true。 条件变量是一个显示队列，当某些执行状态不满足时，线程可以把自己加入队列，等待该条件。另外某个线程，当改变了上述状态时，就可以唤醒一个或多个等待线程（通过阿紫该条件上发信号），让它们继续执行。 ## 第31章 信号量 信号量是有一个整数值的对象 信号量的初始值为 1，线程只会在信号量小于0时等待 当信号量的值为负数时，这个值就是等待线程的个数 ### 信号量用作条件变量 当一个线程进入临界区时，它把信号量的值减 1，然后进入，返回时将信号量的值加 1 如果减 1 后的信号量为非负数，则表明资源可用，如果为负，则等待 ## 常见的并发问题 ### 非死锁缺陷 - 违反原子性缺陷 - 错误顺序缺陷（编写错误或指令重排序） ### 死锁缺陷 #### 产生死锁的条件 - 互斥：线程对于需要的资源进行了互斥的访问 - 持有并等待：线程持有资源，同时又在等待其他资源 - 非抢占：线程已获得的资源不能被抢占 - 循环等待：线程之间存在一个环路。环路上的每个线程都额外持有一个资源，而这个资源又是下一个线程要申请的 如果这 4 个条件的任何一个没有满足，就不会产生死锁 #### 循环等待 让代码不会产生循环等待 最直接的方法就是获取锁时提供一个全序。即每次都按固定顺序获取锁，这样严格的顺序避免了循环等待。 更复杂的系统不会只有两个锁，锁的全序很难做到。因此，偏序 可能是一种更有用的方法，安排锁的获取并避免死锁。 #### 持有并等待 持有并等待，可以通过原子地抢占锁来避免 #### 非抢占 获取目标锁的状态，如果锁已被占有，则 稍后 重试 #### 互斥 很难避免 #### 检查和恢复 一种策略就是允许死锁偶尔发生，检查到死锁之后再采取行动。如，一个系统一年才死机一次，你会重启系统，然后愉快的（生气的）继续工作。如果死锁很少见，这种办法也是很实用的。 很多数据库使用了死锁检测和恢复技术。死锁检测器会定期运行，通过构建资源图来检查死锁（循环）。当死锁发生时，系统需要重启。如果还需要更复杂的数据结构相关的修复，那么需要人工参与。 ## 第33章 基于事件的并发 一些基于图形用户界面的应用，或某些类型的网络服务区，常常采用另一种并发方式。这种方式称为基于事件的并发，在一些在现代系统中较为流行，比如 node.js，但它源自于 C/UNIX 系统。 基于事件的并发针对两方面的问题：一方面是多线程应用中，正确处理并发很有难度。另一方面，开发者无法控制多线程在某一时刻的调度。 > 不用线程，如何构建并发服务器？ ### 基本想法：事件循环 基本方法就是基于事件的并发。该方法很简单：我们等待某事件的发生；当它发生时，检查事件类型，然后做少量的相应工作（可能是 I/O 请求，或调度其他事件准备后续处理）。 我们先看一个典型的基于事件的服务器。这种应用都是基于一个简单的结构，称为事件循环。 ```kotlin while (true) { events = getEvents(); for (e in events) { processEvent(e); } } ``` 主循环等待某些事件发生（通过getEvents()），然后依次处理这些发生的事件。处理事件的代码叫作事件处理程序。重要的是，处理程序在处理一个事件时，它是系统中发生的唯一活动。 因此，调度就是决定接下来处理哪个事件。这种对调度的显式控制，是基于事件方法的一个重要优点。 > 补充：阻塞与非阻塞接口 > 阻塞（或同步）接口在返回给调用者之前完成所有工作。 > 非阻塞（或异步）接口开始一些工作，但立刻返回，从而让所有需要完成的工作都在后台完成。 > 通常阻塞调用的主犯是某种 I/O。如果一个调用必须从磁盘读取才能完成，它可能会阻塞，等待发送到磁盘的 I/O 请求返回。 > 非阻塞接口可用于任何类型的编程，但在基于事件的方法中非常重要，因为阻塞的调用会阻止所有进展。 ### 阻塞系统调用 使用基于事件的方法时，没有其他线程可以运行：只是主事件循环。这意味着如果一个时间处理程序发出一个阻塞的调用，整个服务器就会阻塞直到完成。当事件循环阻塞时，系统处于闲置状态，是巨大资源浪费。因此，我们在基于事件的系统中必须遵守一条规则：不允许阻塞调用。 ### 结局方法：异步 I/O 现代操作系统引入新的方法来向磁盘发出 I/O 请求，一般称之为 异步I/O。 这些接口使应用程序能够发出 I/O 请求，并在 I/O 完成之前立即将控制权返回给调用者，另外的接口让应用程序能够确定各种 I/O 是否已完成。 检查一个 I/O 是否已完成是很痛苦的。如果一个程序在某个待定时间点发出数十或数百个 I/O，是否应该重复的检查它们中的每一个，或者其他操作。 为了解决这个问题，一些系统提供了基于中断的方法。此方法使用 UNIX 信号 在异步 I/O 完成时通知应用程序，从而消除了重复轮询的需要。这种轮询与中断问题也可以在设备中看到。 > 补充：UNIX 信号 > 所有现代 UNIX 变体都有一个称为 信号 的巨大而迷人的基础设施。最简单的信号提供了一种一种与进程进行通信的方式。具体来说，可以将信号传递给应用程序。这样做会让应用程序停止当前的任何工作，开始运行信号处理程序，即应用程序中某些处理该信号的代码。完成后，进程恢复先前的行为。 > 每个信号都有一个名称，如 HUP（挂断）、INT（中断）、SEGV（段违规）等。 > 有趣的是，有时是内核本身发出信号。如，当你的程序遇到段违规时，操作系统发送一个 SIGSEGV （在信号名前加上 SIG 是很常见的）。如果你的程序配置为捕获该信号，则实际上可以运行一些代码来相应这种错误的程序行为（可能对调试有用）。当信号被发送到一个没有配置处理该信号的进程时，一些默认行为就会生效。对于 SEGV 来说，这个进程会被杀死。 ### 另一个问题：状态管理 基于事件的方法的另一个问题是，这种代码通常被传统的基于线程的代码更复杂。原因如下：当事件处理程序发出异步I/O时，它必须打包一些程序状态，以便下一个事件处理程序在I/O最终完成时使用。这个额外的工作在基于线程的程序中是不需要的，因为程序需要的状态在线程栈中。 ### 其他问题 基于事件的方法还有其他一些困难 为了利用多个CPU，事件服务器必须并行运行多个事件处理程序。发生这种情况时，就会出现常见的同步问题，并且必须采用通常的解决方案。因此，在现代多核系统上，无锁的简单事件处理已不再可能。 基于事件的方法的另一个问题是，它不能很好地与某些类型的系统活动集成，如分页。 还有一个问题是随着时间推移，基于事件的代码可能难以管理，因为各种函数的确切语义也发生了变化。例如，如果函数从非阻塞变为阻塞，调用该例程的事件处理程序也必须更改以适应其新性质，方法是将其自身分解为两个部分。由于阻塞对于基于事件的服务器而言是灾难性的，因此程序员必须始终注意每个事件使用的 API 语义的这种变化。 ## 第36章 I/O设备 我们先介绍I/O设备的概念，并展示操作系统如何与它们交互。 ### 系统架构 在开始讨论之前，我们先看一个典型系统的架构。其中，CPU通过某种 `内存总线(memory bus)` 连接到系统内存。图像或其他高性能 I/O 设备通过常规的 `I/O总线(I/O bus)` 连接到系统，在许多现代系统中会是 PCI 或它的衍生形式（PCIe）。最后，更下面是 `外围总线`，比如 SATA 或 USB。它们将最慢的设备连接到系统，包括磁盘、鼠标以及其他设备。  为什么要用这样的分层架构？简单回答：因为物理布局及造价成本。越快的总线越短，因此高性能的内存总线没有足够的空间连接太多设备。另外，在工程上高性能总线的造价非常高。所以，系统的设计采用了这种分层的方式，这样可以让要求高性能的设备（如显卡）离 CPU 更近一些，低性能的设备离 CPU 远一些。将磁盘和其他低速设备连到外围总线的好处很多，其中较为突出的好处就是你可以在外围总线上连接大量的设备。 ### 标准设备 现在来看一个标准设备（不是真实存在的），可以看到一个包含两部分重要组件的设备。 第一部分是向系统其他部分展现的硬件接口。 同软件一样，硬件也需要一些接口，让操作系统来控制它的操作。因此，所有设备都有自己的特定接口以及典型交互的协议。 第二部分是它的内部结构。 这部分包含设备相关的特定实现，负责实现设备展示给系统的抽象接口。非常简单的设备通常用一个或几个芯片来实现它们的功能。更复杂的设备会包含简单的 CPU、一些通用内存、设备相关的特定芯片，来完成它们的工作。  ### 标准协议 一个简化的设备接口包含 3 个寄存器： - 状态寄存器：读取并查看设备的当前状态 - 命令寄存器：用于通知设备执行某个具体任务 - 数据寄存器：将数据传递给设备或从设备接受数据 通过读写这些寄存器，操作系统可以控制设备的行为。 ### 设备交互的方法 主要由两种方式来实现与设备的交互 第一种办法相对老一些，就是用明确的 I/O指令。这些指令规定了操作系统将数据发送到特定设备寄存器的方法，从而允许构造上文提到的协议。这些指令通常是特权指令。操作系统是唯一可以与设备交互的实体。 第二种方法是 `内存映射I/O(memory-mapped I/O)` 通过这种方式，硬件将设备寄存器作为内存地址提供。当需要访问设备寄存器时，操作系统装载（读取）或者存入（写入）到该内存地址；然后硬件会将装载/存入转移到设备上，而不是物理内存。 ### 纳入操作系统：设备驱动程序 如何实现一个设备无关的操作系统？ 这个问题可以通过古老的抽象技术来解决。在最底层，操作系统的一部分软件清楚地知道设备如何工作，我们将这部分软件称为 `设备驱动程序`，所有设备交互的细节都封装在其中。 有趣的是，因为所有需要插入系统的设备都需要安装对应的驱动程序，所以久而久之，驱动程序的代码在整个内核代码中的占比越来越大。查看Linux内核源码会发现，超过 70% 的代码都是各种驱动程序。在Windows系统中，这样的占比同样很高。 当然，任何安装进操作系统的驱动程序，大部分默认都不是激活状态（只有一小部分设备是在系统刚开启时就需要连接）。更加令人沮丧的是，因为驱动程序的开发者模式大部分是“业余的”（不是全职内核开发者），所以他们更容易写出缺陷，因此是内核崩溃的主要贡献者。 ## 磁盘驱动器 我们将更详细的介绍一种设备：磁盘驱动器 数十年来，这些驱动器一直是计算机系统中持久数据存储的主要形式，文件系统技术的大部分发展都是基于它们的行为。因此，在构建管理它的文件系统软件之前，有必要先了解磁盘操作的细节。 ### 接口 我们先来了解一个现代驱动器的接口。所有现代驱动器的基本接口都很简单。驱动器由大量扇区（512字节块）组成，每个扇区都可以读取或写入。在具有 n 个扇区的磁盘上，扇区从 0 到 n - 1 编号。因此，我们可以将磁盘视作一组扇区，0 到 n - 1 是驱动器的地址空间。 多扇区操作是可能的。实际上，许多文件系统一次读取或写入 4KB（或更多）。但是，*在更新磁盘时，驱动器制造商唯一保证的是单个 512 字节的写入是原子的。*因此，如果发生不合时宜的掉电，则只能完成较大写入的一部分（或称之为不完整写入）。 通常可以假设访问驱动器地址空间内两个彼此靠近的块将比访问两个相隔很远的块更快。人们通常也可以假设访问连续块（即顺序读取或写入）是最快的访问模式，并且通常比任何更随机的访问模式快很多。 ### 基本几何形状 了解现代磁盘的一些组件。 我们从一个盘片开始，它是一个圆形的坚硬的表面，通过引入磁性变化来永久存储数据。磁盘可能有一个或多个盘片。每个盘片有两面，每面都称为表面。这些盘片通常由一些硬质材料（如铝）制成，然后涂上薄薄的磁性层，即使驱动器断电，驱动器也能持久存储数据位。 所有盘片都围绕主轴（spindle）连接在一起，主轴连接到一个电机，以一个恒定（固定） 的速度旋转盘片（当驱动器接通电源时）。旋转速率通常以每分钟转数（Rotations Per Minute，RPM）来测量，典型的现代数值在 7200～15000 RPM 范围内。 请注意，我们经常会对单次旋转的时间感兴趣，例如，以 10000 RPM 旋转的驱动器意味着一次旋转需要大约 6ms。 数据在扇区的同心圆中的每个表面上被编码。我们称这样的同心圆为一个磁道（track）。 一个表面包含数以千计的磁道，紧密地排在一起，数百个磁道只有头发的宽度。 要从表面进行读写操作，我们需要一种机制，使我们能够感应（即读取）磁盘上的磁性图案，或者让它们发生变化（即写入）。 读写过程由磁头（disk head）完成，驱动器的每个表面有一个这样的磁头。磁头连接到单个磁盘臂（disk arm）上，磁盘臂在表面上移动， 将磁头定位在期望的磁道上。 ### 简单的磁盘驱动器  #### 单磁道延迟：旋转延迟 在我们的简单磁盘中，磁盘不必做太多工作。具体来说，它必须等待期望的扇区旋转到磁头下。 这种等待在现代的驱动器中经常发生，并且是 I/O 服务时间的重要组成部分，它有一个特殊的名称：`旋转延迟（rotational delay）` #### 多磁道：寻道时间  我们现在追踪请求发生在远处扇区的情况，例如，读取扇区 11。 为了服务这个读取请求，驱动器必须首先将磁盘臂移到正确的磁道，通过一个所谓的 `寻道（seek）` 过程。 寻道，以及旋转，是最昂贵的磁盘操作之一。 寻道有许多阶段：首先是磁盘臂移动时的加速阶段，然后随着磁盘臂全速移动而惯性滑动，然后减速，最后，在磁头小心地放置在正确的磁道上时停下来。停放时间通常不小，例如 0.5 ~ 2ms，因为驱动器必须确定找到正确的磁道。 在寻道过程中，磁盘臂已经移动到所需的磁道上，并且盘片已经开始旋转，在这个例子中，大约旋转了 3 个扇区。因此，扇区 9 即将通过磁头下方，我们只能承受短暂的转动延迟，以便完成传输。 当扇区 11 经过磁头时，I/O的最后阶段将发生，称为传输，数据从表面读取获取写入表面。因此，我们得到了完整的 I/O 时间图：寻道，等待旋转延迟，传输。 #### 其他细节 许多驱动器采用某种形式的磁道偏斜，以确保即使在跨越磁道边界时，顺序读取也可以很方便的服务。 另一个事实是，外圈磁道通常比内圈磁道具有更多扇区。这些刺刀通常被称为多区域磁盘驱动器，其中磁盘被组织成多个区域，区域是表面上一组连续的磁道。每个区域每个磁道具有相同的扇区数量，并且外圈区域具有比内圈区域更多的扇区。 最后，任何现代磁盘驱动器都有一个重要组成部分，即它的缓存，由于历史原因有时称为磁道缓冲区。 该缓存只是少量的内存，驱动器可以使用这些内存来保存或从磁盘读取或写入磁盘的数据。 在写入时，驱动器面临一个选择：它应该在将数据放入其内存之后，还是实际写入磁盘之后，回报写入完成？前者被称为后写缓存，后者被称为直写缓存。 ### 磁盘调度 由于 I/O 的高成本，操作系统在决定发送给磁盘的 I/O 顺序方面历来发挥作用。更具体地说，给定一组 I/O 请求，磁盘调度程序检查请求并决定下一个要调度的请求。 与任务调度不同，每个任务的长度通常是不知道的，对于磁盘调度，我们可以很好地猜测磁盘请求需要多长时间。 通过估计请求的查找和旋转延迟，磁盘的调度程序可以知道每个请求将花费多长时间，因此（贪婪的）选择先服务花费最少时间的请求。 因此，磁盘调度程序将尝试在其操作操作中遵守 SJF 的原则。 #### SSTF：最短寻道时间优先 一种早期的磁盘调度方法被称为最短寻道时间优先。SSTF 按磁道对 I/O 请求队列排序，选择在最近磁道上的请求先完成。 #### SCAN（C-SCAN） 改算法最初称为 SCAN，简单地以跨越磁道的顺序来服务磁盘请求。我们见一次跨越磁盘称为扫一遍。因此，如果请求的块所属的磁道在这次扫一遍中已经服务过了，它就不会立刻处理，而是排队等待下次扫一遍。 C-SCAN 是另一种常见的变体，即循环 SCAN（Circular SCAN）的缩写。不是在一个方向扫过磁盘，该算法从外圈扫到内圈，然后从内圈扫到外圈，如此下去。 由于现在很明显的原因，这种算法有时被称为 电梯算法。 然而，SCAN 及其变种并不是最好的调度技术，特别是，SCAN（甚至SSTF）实际上并没有严格遵守 SJF 的原则。 #### SPTF：最短定位时间优先 在讨论最短定位时间优先调度（SPTF），让我们先看一个例子。 在这个例子中， 磁头当前定位在内圈磁道上的扇区 30 上方。因此，调度程序必须决定：下一个请求应该安排为扇区 16 或 扇区 8。 答案是视情况而定。在工程中，视情况而定几乎总是答案，这反应了取舍是工程师生活的一部分。  这里的情况是旋转与寻道相比的相对时间。如果在我们的例子中，寻道时间远远高于旋转延迟，那么 SSTF 就可以了。但，如果寻道比旋转快得多，那么本例中服务扇区 8 的请求更好。 在现代驱动其中，正如上面看到的，查找和旋转大致相当，因此 SPTF 是有用的，它提高了性能。 然而，它在操作系统中实现起来更加困难，操作系统通常不太清楚磁道边界在哪，也不知道磁头当前的位置。因此，SPTF通常在驱动器内部执行。 #### 其他调度问题 在这个基本磁盘操作，调度和相关主题的简要描述中，还有很多问题我们没有讨论。 其中一个问题是：在现代操作系统上执行磁盘调度的地方在哪里？ 在较早的系统中，操作系统完成了所有的调度。在查看一系列挂起的请求后，操作系统会选择最好的一个，并将其发送到磁盘。当该请求完成时，将选择下一个，如此下去。 在现代系统中，磁盘可以接收多个分离的请求，它们本身具有复杂的内部调度程序。因此，操作系统调度程序通常会选择它认为最好的几个请求，并将其发送到磁盘，由磁盘服务。 另一个重要相关任务是 I/O合并。例如，图 37.8 中，请求读取块 33，8，34。在这种情况下，调度程序应该将块 33 和 34 的请求合并为两个单块请求。调度程序执行的所有请求都基于合并后的请求。合并在操作系统级别尤其重要，因为它减少了发送到磁盘的请求数量，从而降低了开销。 最后一个问题是：在想磁盘发出 I/O 之前，系统应该等待多久？ 有人可能认为，即使有一个磁盘 I/O，也应立即向驱动器发出请求。这种方法被称为 `工作保全`，因为如果有请求要服务，磁盘将永远不会闲下来。 然而，对预期磁盘调度的研究表明，有时最好等待一段时间，即所谓的 `非工作保全`方法。通过等待，新的和“更好”的请求可能会到达磁盘，从而整体效率提高。 ## 第38章 廉价冗余磁盘阵列（RAID） 本章介绍 廉价冗余磁盘阵列（Redundant Array of Inexpensive Disks），更多时候称为 RAID，这种技术使用多个磁盘一起构建更快、更大、更可靠的磁盘系统。 从外部看，RAID 看起来想一个磁盘：一族可以读取或写入的块。在内部，RAID 是一个复杂的庞然大物，由多个度盘、内存以及一个或多个处理器来管理系统。硬件 RAID 非常像一个计算机系统，专门用于管理一组磁盘。 与单个磁盘相比，RAID 具有许多优点。一个好处就是性能。并行使用多个磁盘可以大大加快 I/O 时间。另一个好处是容量。大型数据集需要大型磁盘。最后，RAID 可以提高可靠性。在多个磁盘上传输数据（无RAID）会是数据容易受到单个磁盘丢失的影响。通过某种形式的冗余，RAID 可以容许损失一个磁盘并保持运行，就像没有错误一样。 > 透明支持部署 > 在考虑如何向系统添加新功能时，应该是中考虑是否可以透明的添加这样的功能，而不需要对系统其余部分进行更改。要求彻底重写现有软件（或激进的硬件更改）会减少创意产生影响的机会。RAID 就是一个很好的例子，它的透明肯定有助于它的成功。 令人惊讶的是，RAID 为使用它们的系统透明的提供了这些优势，即 RAID 对主机系统看起来像一个大磁盘。当然，透明的好处在于它可以简单的用 RAID 替换磁盘，而不需要更换一行软件。操作系统和客户端应用程序无需修改，就可以运行。通过这种方式，透明极大的提高了 RAID 的可部署性。 ### 如何评估 RAID 我们从三个方面评估每种 RAID 设计： - 容量：在给定一组N个磁盘的情况下，RAID 的客户端可用的容量有多少 - 可靠性：给定设计允许有多少磁盘故障 - 性能：取决于工作负载 我们现在考虑 3 个重要的 RAID 设计：RAID 0 级（条带化），RAID 1 级（镜像）和 RAID 4/5 级（基于奇偶校验的冗余）。 这些设计中的每一个都被命名为一“级”，源于伯克利的三位教授 Patterson、Gibson 和 Katz 的开创性工作。 ### RAID 0：条带化 第一个 RAID 级别实际上不是 RAID 级别，因为没有冗余。但是，RAID 0 因其更为人所知，可作为性能和容量的优秀上线，值得了解。 容量：它是顶级的：给定 N 个磁盘，条带化提供 N 个磁盘的有用容量 可靠性：它是最差的，任何磁盘故障都会导致数据丢失 性能：非常好，通常并行使用所有磁盘来为用户 I/O 请求提供服务 ### RAID 1：镜像 第一个超越条带化的 RAID 级别称为 RAID 1 级，即镜像。 对于镜像系统，我们只需生成系统中每个块的多个副本。当然，每个副本应放在一个单独的磁盘上。通过这样做，我们可以容许磁盘故障。 可以将 RAID1 和 RAID 0 组合使用，通常称为 RAID 10（壹零），当然也可以使用 RAID 01 容量：昂贵，在镜像级别=2的情况下，我们只能获得峰值有用容量的一半，即 N / 2 可靠性：很好，可以容许任何一个磁盘故障。在镜像级别=2的情况下，最多可容许 N / 2 个磁盘故障（但十分看运气） 性能：从单个读取请求的延迟角度来看，与单磁盘相同。所有 RAID 1 都会将读取导向一个副本。写入有点不同：在完成写入之前，需要完成两次物理写入。这两个写入并行发生，因此时间大致等于单次写入的时间。 ### RAID 4：通过奇偶校验节省空间 现在展示一种向磁盘阵列添加冗余的不同方法，称为 `奇偶校验`。 基于奇偶校验的方法试图使用较少的容量，从而克服由镜像系统付出的巨大空间损失，但这样的代价是性能。 容量：RAID 4 使用 1 个磁盘作为它所保护的每组磁盘的奇偶校验信息，因此有用容量是 N - 1 可靠性：只容许1个磁盘故障，不允许更多 性能：连续读取性能可以利用除奇偶校验磁盘外所有的磁盘 ### RAID 5：旋转奇偶校验 为了解决小接入问题，Patterson、Gibson、Katz 推出了 RAID 5 RAID 5 的工作原理几乎与 RAID 4 完全相同，只是它将奇偶校验块跨驱动器旋转。 RAID 5 的大部分分析与 RAID 4 相同，只是随机写入性能明显提高。 ### RAID 比较   ### 小结 有很多可能的 RAID 级别可供选择，使用的确切 RAID 级别在很大程度上取决于最终用户的优先级。例如，RAID 1 是简单的、可靠的，并且通常提供良好的性能，但是容量成本很高。相比之下，RAID-5从容量角度来看是可靠和很高的，但在工作负载中有小写入时性能很差。为特定工作负载正确的挑选 RAID 并社会七参数，这非常有挑战性，更多的是艺术而不是科学。 ## 第39章 插叙：文件和目录 在这部分，我们加上虚拟化拼图中的关键一块：持久存储 永久存储设备永久的（至少长时间的）存储信息，如传统硬盘驱动器或更现代的固态存储设备。持久存储设备与内存不同。内存再断电时，其内容会丢失，而持久存储设备会保持这些数据不便。 ### 文件和目录 随着时间的推移，存储虚拟化形成了两个关键的抽象： - 第一个是文件（file）：文件就是 一个线性字节数组，每个字节都可以读取或写入。每个文件都有某种低级名称（low-level name），通常是某种数字。用户通常不知道这个名字（我们稍后会看到）。由于历史原因， 文件的低级名称通常称为 inode 号（inode number）。现在，只要假设每个文件都有一个与其关联的 inode 号。 在大多数系统中，操作系统不太了解文件的结构（例如，它是图片、文本文件还是 C 代码）。相反，文件系统的责任仅仅是将这些数据永久存储在磁盘上，并确保当你再次请求数据时，得到你原来放在那里的内容。 - 第二个抽象是目录（directory）。一个目录，像一个文件一样，也有一个低级名字（即 inode 号），但是它的内容非常具体：它包含一个（用户可读名字，低级名字）对的列表。例 如，假设存在一个低级别名称为“10”的文件，它的用户可读的名称为“foo”。“foo”所在 的目录因此会有条目（“foo”，“10”），将用户可读名称映射到低级名称。目录中的每个条目 都 指 向文件或其他目录。通过将目录放入其他目录中，用户可以构建任意的目录树（directory tree，或目录层次结构，directory hierarchy），在该目录树下存储所有文件和目录。 目录层次结构从根目录（root directory）开始（在基于 UNIX 的系统中，根目录就记为“/”），并使用某种分隔符（separator）来命名后续子目录 （sub-directories），直到命名所需的文件或目录。 > 请仔细考虑命名 > 命名是计算机系统的一个重要方面。在 UNIX 系统中，你几乎可以想到的所有内容都是通过文件系统命名的。除了文件、设备、管道，甚至进程[K84]都可以在一个看似普通的旧文件系统中看到。 > 这种命名的一致性简化了系统的概念模型，使系统更简单、更模块化。因此，无论何时创建系统或接口，都要仔细考虑你使用的是什么名称。 你可能还会注意到，这个例子中的文件名通常包含两部分：bar 和 txt，以句点分隔。第一部分是任意名称，而文件名的第二部分通常用于指示文件的类型（type）。 *然而，这通常只是一个惯例（convention）：一般不会强制名为 main.c 的文件中包含的数据确实是 C 源代码。* ### 符号链接 还有一种非常有用的链接类型，称为符号链接（symbolic link），有时称为软链接（soft link）。事实表明，硬链接有点局限：你不能创建目录的硬链接（因为担心会在目录树中创建一个环）。你不能硬链接到其他磁盘分区中的文件（因为 inode 号在特定文件系统中是唯一的，而不是跨文件系统），等等。因此，人们创建了一种称为符号链接的新型链接。 ## 第40章 文件系统实现 本章将介绍一个简单的文件系统实现，称为 VSFS（Very Simple File System，简单文件系统）。它是典型 UNIX 文件系统的简化版本，因此可用于介绍一些基本磁盘结构、访问方法和各种策略，你可以在当今许多文件系统中看到。 文件系统是纯软件。与 CPU 和内存虚拟化的开发不同，我们不会添加硬件功能来使文件系统的某些方面更好地工作（但我们需要注意设备特性，以确保文件系统运行良好）。由于在构建文件系统方面具有很大的灵活性，因此人们构建了许多不同的文件系统，从 AFS（Andrew 文件系统）到 ZFS（Sun 的 Zettabyte 文件系统）。所有这些文件系统都有不同的数据结构，在某些方面优于或逊于同类系统。 ### 思考方式 考虑文件系统时，我们通常建议考虑它们的两个不同方面： - 第一个方面是文件系统的数据结构（data structure）。换言之，文件系统在磁盘上使用哪些类型的结构来组织其数据和元数据？ - 文件系统的第二个方面是访问方法（access method）。如何将进程发出的调用映射到它的结构上？ ### 整体组织 VSFS 文件系统在磁盘上的数据结构的整体组织。我们需要做的第一件事是将磁盘分成块（block）。简单的文件系统只使用一种块大小，这里正是这样做的。我们选择常用的 4KB。 因此，我们对构建文件系统的磁盘分区的看法很简单：一系列块，每块大小为 4KB。在大小为 N 个 4KB 块的分区中，这些块的地址为从 0 到 N−1。假设我们有一个非常小的磁盘，只有 64 块。 任何文件系统中的大多数空间都是（并且应该是）用户数据。 我们将用于存放用户数据的磁盘区域称为数据区域（data region），简单起见，将磁盘的固定部分留给这些块，例如磁盘上 64 个块的最后 56 个：  文件系统必须记录每个文件的信息。该信息是 `元数据（metadata）`的关键部分，并且记录诸如文件包含哪些数据块（在数据区域中）、文件的大小，其所有者和访问权限、访问和修改时间以及其他类似信息的事情。为了存储这些信息，文件系统通常有一个名为 inode 的结构。 为了存放 inode，我们还需要在磁盘上留出一些空间。我们将这部分磁盘称为 inode 表（inode table），它只是保存了一个磁盘上 inode 的数组。因此，假设我们将 64 个块中的 5 块用于 inode，磁盘映像现在看起来如下：  在这里应该指出，inode 通常不是那么大，例如，只有 128 或 256 字节。假设每个 inode 有 256 字节，一个 4KB 块可以容纳 16 个 inode，这个数字表示文件系统中可以拥有的最大文件数量。 建立在更大磁盘上的相同文件系统可以简单地分配更大的 inode 表，从而容纳更多文件。 还需要某种方法来记录 inode 或数据块是空闲还是已分配。因此，这种分配结构（allocation structure）是所有文件系统中必需的部分。 当然，可能有许多分配记录方法。例如，我们可以用一个空闲列表（free list），指向第一个空闲块，然后它又指向下一个空闲块，依此类推。 我们选择一种简单而流行的结构，称为位图（bitmap），一种用于数据区域（数据位图，data bitmap），另一种用于 inode 表（inode位图，inode bitmap）。位图是一种简单的结构：每个位用于指示相应的对象/块是空闲（0）还是正在使用（1）。 对这些位图使用整个 4KB 块是有点杀鸡用牛刀。这样的位图可以记录 32KB（2^5）对象是否分配，但我们只有 80 个 inode 和 56 个数据块。但是，简单起见，我们就为每个位图使用整个 4KB 块。 在极简文件系统的磁盘结构设计中，还有一块。我们将它保留给 `超级块（superblock）`，在下图中用 S 表示。 超级块包含关于该特定文件系统的信息，包括例如文件系统中有多少个 inode 和数据块（在这个例子中分别为 80 和 56）、inode 表的开始位置（块 3）等等。它可能还包括一些幻数，来标识文件系统类型（在本例中为 VSFS）。  因此，在挂载文件系统时，操作系统将首先读取超级块，初始化各种参数，然后将该卷添加到文件系统树中。当卷中的文件被访问时，系统就会知道在哪里查找所需的磁盘上的结构。 ### 文件组织：inode 文件系统最重要的磁盘结构之一是 inode，几乎所有的文件系统都有类似的结构。名称 inode 是 index node（索引节点）的缩写，它是由 UNIX 开发人员 Ken Thompson 给出的历史性名称，因为这些节点最初放在一个数组中，在访问特定 inode 时会用到该数组的索引。 > 补充：数据结构—— inode > inode 是许多文件系统中使用的通用名称，用于描述保存给定文件的元数据的结构，例如其长度、权限以及其组成块的位置。 > 它是 index node（索引节点）的缩写，因为 inode 号用于索引磁盘上的 inode 数组，以便查找 > 该 inode 号对应的 inode。 > 大多数现代系统 对于它们记录的每个文件都有这样的结构，但也许用了不同的名字（如 dnodes、fnodes 等）。 每个 inode 都由一个数字（称为 inumber）隐式引用，我们之前称之为文件的低级名称（low-level name）。在 VSFS（和其他简单的文件系统）中，给定一个 inumber，你应该能够直接计算磁盘上相应节点的位置。 在每个 inode 中，实际上是所有关于文件的信息：文件类型（例如，常规文件、目录等）、大小、分配给它的块数、保护信息（如谁拥有该文件以及谁可以访问它）、一些时间信息（包括文件创建、修改或上次访问的时间文件下），以及有关其数据块驻留在磁盘上的位置的信息（如某种类型的指针）。我们将所有关于文件的信息称为元数据（metadata）。实际上，文件系统中除了纯粹的用户数据外，其他任何信息通常都称为元数据。 设计 inode 时，最重要的决定之一是它如何引用数据块的位置。一种简单的方法是在 inode 中有一个或多个直接指针（磁盘地址）。每个指针指向属于该文件的一个磁盘块。这种方法有局限：例如，如果你想要一个非常大的文件，那就不走运了（一个文件一堆指针）。 #### 多级索引 为了支持更大的文件，文件系统设计者必须在 inode 中引入不同的结构。一个常见的思路是有一个称为间接指针（indirect pointer）的特殊指针。它不是指向包含用户数据的块，而是指向包含更多指针的块，每个指针指向用户数据。 ### 目录组织 在 VSFS 中（像许多文件系统一样），目录的组织很简单。一个目录基本上只包含一个二元组（条目名称，inode 号）的列表。对于给定目录中的每个文件或目录，目录的数据块中都有一个字符串和一个数字。对于每个字符串，可能还有一个长度（假定采用可变大小的名称）。  ### 空闲空间管理 文件系统必须记录哪些 inode 和数据块是空闲的，哪些不是，这样在分配新文件或目录时，就可以为它找到空间。因此，空闲空间管理（free space management）对于所有文件系统都很重要。在 VSFS 中，我们用两个简单的位图来完成这个任务。 > 补充：空闲空间管理 > 管理空闲空间可以有很多方法，位图只是其中一种。一些早期的文件系统使用空闲列表（free list），其中超级块中的单个指针保持指向第一个空闲块。在该块内部保留下一个空闲指针，从而通过系统的空闲块形成列表。在需要块时，使用头块并相应地更新列表。 > 现代文件系统使用更复杂的数据结构。例如，SGI 的 XFS 使用某种形式的 B 树（B-tree）来 紧凑地表示磁盘的哪些块是空闲的。与所有数据结构一样，不同的 时间-空间 折中也是可能的。 ### 访问路径：读取和写入 #### 从磁盘读取文件 当你发出一个 open("/foo/bar", O_RDONLY)调用时，文件系统首先需要找到文件 bar 的 inode，从而获取关于该文件的一些基本信息（权限信息、文件大小等等）。为此，文件系统必须能够找到 inode，但它现在只有完整的路径名。文件系统必须遍历（traverse）路径名，从而找到所需的 inode。 所有遍历都从文件系统的根开始，即根目录（root directory），它就记为/。因此，文件系统的第一次磁盘读取是根目录的 inode。但是这个 inode 在哪里？要找到 inode，我们必须知道它的 i-number。通常，我们在其父目录中找到文件或目录的 i-number。 一旦 inode 被读入，文件系统可以在其中查找指向数据块的指针，数据块包含根目录的内容。因此，文件系统将使用这些磁盘上的指针来读取目录。 通过读入一个或多个目录数据块，它将找到 foo 的条目。一旦找到，文件系统也会找到下一个需要的 foo 的 inode 号（假定是 44）。 下一步是递归遍历路径名，直到找到所需的 inode。在这个例子中，文件系统读取包含 foo 的 inode 及其目录数据的块，最后找到 bar 的 inode 号。open()的最后一步是将 bar 的 inode 读入内存。然后文件系统进行最后的权限检查，在每个进程的打开文件表中，为此进程分配一个文件描述符，并将它返回给用户。 另外请注意，open 导致的 I/O 量与路径名的长度成正比。对于路径中的每个增加的目录，我们都必须读取它的 inode 及其数据。 #### 写入磁盘 与读取不同，写入文件也可能会分配（allocate）一个块（除非块被覆写）。 当写入一个新文件时，每次写入操作不仅需要将数据写入磁盘，还必须首先决定将哪个块分配给文件，从而相应地更新磁盘的其他结构（例如数据位图和 inode）。 因此，每次写入文件在逻辑上会导致 5 个 I/O：一个读取数据位图（然后更新以标记新分配的块被使用），一个写入位图（将它的新状态存入磁盘），再是两次读取，然后写入 inode（用新块的位置更新），最后一次写入真正的数据块本身。 ### 缓存和缓冲 读取和写入文件可能是昂贵的，会导致（慢速）磁盘的许多 I/O。 这显然是一个巨大的性能问题，为了弥补，大多数文件系统积极使用系统内存（DRAM）来缓存重要的块。 早期的文件系统因此引入了一个固定大小的缓存（fixed-size cache）来保存常用的块。LRU 及不同变体策略会决定哪些块保留在缓存中。 这个固定大小的缓存通常会在启动时分配，大约占总内存的 10%。然而，这种静态的内存划分（static partitioning）可能导致浪费。如果文件系统在给定的时间点不需要 10%的内存，文件高速缓存中的未使用页面不能被重新用于其他一些用途，因此导致浪费。 相比之下，现代系统采用动态划分（dynamic partitioning）方法。具体来说，许多现代操作系统将虚拟内存页面和文件系统页面集成到 `统一页面缓存中（unified page cache）`。 通过这种方式，可以在虚拟内存和文件系统之间更灵活地分配内存，具体取决于在给定时间哪种内存需要更多的内存。 我们也考虑一下缓存对写入的影响。尽管可以通过足够大的缓存完全避免读取 I/O，但写入流量必须进入磁盘，才能实现持久。因此，高速缓存不能减少写入流量，像对读取那样。虽然这么说，写缓冲（write buffering，人们有时这么说）肯定有许多优点： - 首先，通过延迟写入，文件系统可以将一些更新编成一批（batch），放入一组较小的 I/O 中。例如，如果在创建一个文件时，inode 位图被更新，稍后在创建另一个文件时又被更新，则文件系统会在第一次更新后延迟写入，从而节省一次 I/O。 - 其次，通过将一些写入缓冲在内存中，系统可以调度（schedule）后续的 I/O，从而提高性能。 - 最后，一些写入可以通过拖延来完全避免。例如，如果应用程序创建文件并将其删除，则将文件创建延迟写入磁盘，可以完全避免（avoid）写入。 由于上述原因，大多数现代文件系统将写入在内存中缓冲 5～30s，这代表了另一种折中：如果系统在更新传递到磁盘之前崩溃，更新就会丢失。但是，将内存写入时间延长，则可以通过批处理、调度甚至避免写入，提高性能。 某些应用程序（如数据库）不喜欢这种折中。因此，为了避免由于写入缓冲导致的意外数据丢失，它们就强制写入磁盘，通过调用 fsync()，使用绕过缓存的直接 I/O（direct I/O）接口，或者使用原始磁盘（raw disk）接口并完全避免使用文件系统。 ## 第42章 崩溃一致性：日志 文件系统面临的一个主要挑战在于，如何在出现断电（power loss）或系统崩溃（system crash）的情况下，更新持久数据结构。 由于断电和崩溃， 更新持久性数据结构可能非常棘手，并导致了文件系统实现中一个有趣的新问题，称为`崩溃一致性问题（crash-consistency problem）`。 这个问题很容易理解。想象一下，为了完成特定操作，你必须更新两个磁盘上的结构 A 和 B。由于磁盘一次只为一个请求提供服务，因此其中一个请求将首先到达磁盘（A 或 B）。如果在一次写入完成后系统崩溃或断电，则磁盘上的结构将处于不一致（inconsistent）的状态。 ### 一个详细的例子 为了开始对日志的调查，先看一个例子。我们需要一种工作负载（workload），它以某种方式更新磁盘结构。这里假设工作负载很简单：将单个数据块附加到原有文件。通过打开文件，将文件偏移量移动到文件末尾，然后在关闭文件之前，向文件发出单个4KB 写入来完成追加。 要实现这种转变，文件系统必须对磁盘执行 3 次单独写入，分别针对 inode，位图和数据块。 请注意，当用户发出 write()系统调用时，这些写操作通常不会立即发生。脏的 inode、位图和新数据先在内存中存在一段时间。然后，当文件系统最终决定将它们写入磁盘时，文件系统将向磁盘发出必要的写入请求。遗憾的是，可能会发生崩溃，从而干扰磁盘的这些更新。特别是，如果这些写入中的一个或两个完成后发生崩溃，而不是全部 3 个，则文件系统可能处于有趣的状态。 #### 崩溃场景 为了更好地理解这个问题，让我们看一些崩溃情景示例。想象一下，只有一次写入成功。因此有以下 3 种可能的结果： - **只将数据块（Db）写入磁盘。**在这种情况下，数据在磁盘上，但是没有指向它的 inode，也没有表示块已分配的位图。因此，就好像写入从未发生过一样。从文件系统崩溃一致性的角度来看，这种情况根本不是问题。 - **只有更新的 inode 写入了磁盘。**在这种情况下，inode 指向磁盘地址，其中 Db 即将写入，但 Db 尚未写入。因此，如果我们信任该指针，我们将从磁盘读取垃圾数据（磁盘地址 5 的旧内容）。 此外，遇到了一个新问题，我们将它称为文件系统不一致（file-system inconsistency）。磁盘上的位图告诉我们数据块 5 尚未分配，但是 inode 说它已经分配了。文件系统数据结构中的这种不同意见，是文件系统的数据结构不一致。要使用文件系统，我们必须以某种方式解决这个问题。 - **只有更新后的位图写入了磁盘。**在这种情况下，位图指示已分配块 5，但没有指向它的 inode。因此文件系统再次不一致。如果不解决，这种写入将导致 `空间泄露（space leak）`，因为文件系统永远不会使用块 5。在这个向磁盘写入 3 次的尝试中，还有 3 种崩溃场景。在这些情况下，两次写入成功， 最后一次失败。 - **inode 和位图写入了磁盘，但没有写入数据。**在这种情况下，文件系统元数据是完全一致的：inode 有一个指向块 5 的指针，位图指示 5 正在使用，因此从文件系统的元数据的角度来看，一切看起来都很正常。但是有一个问题：5 中又是垃圾。 - **写入了 inode 和数据块，但没有写入位图。**在这种情况下，inode 指向了磁盘上的正确数据，但同样在 inode 和位图的旧版本之间存在不一致。因此，我们在使用文件系统之前，又需要解决问题。 - **写入了位图和数据块，但没有写入 inode。**在这种情况下，inode 和数据位图之间再次存在不一致。但是，即使写入块并且位图指示其使用，我们也不知道它属于哪个文件，因为没有 inode 指向该块。 #### 崩溃一致性问题 理想的做法是将一个文件系统从一个一致状态（在文件被追加之前），原子地移动到另一个状态。遗憾的是，做到这一点不容易，因为磁盘一次只提交一次写入，而这些更新之间可能会发生崩溃或断电。我们将这个一般问题称为 `崩溃一致性问题(crash-consistency problem)`。 ### 解决方案：日志（预写日志） 对于一致更新问题，最流行的解决方案可能是从数据库管理系统的世界中借鉴的一个想法。这种名为 `预写日志（write-ahead logging）` 的想法，是为了解决这类问题而发明的。 在文件系统中，出于历史原因，我们通常将预写日志称为 `日志（journaling）`。第一个实现它的文件系统是 Cedar，但许多现代文件系统都使用这个想法，包括 Linux ext3 和 ext4、reiserfs、IBM 的 JFS、SGI 的 XFS 和 Windows NTFS。 基本思路如下。更新磁盘时，在覆写结构之前，首先写下一点小注记（在磁盘上的其他地方，在一个众所周知的位置），描述你将要做的事情。写下这个注记就是“预写”部分，我们把它写入一个结构，并组织成“日志”。因此，就有了预写日志。 通过将注释写入磁盘，可以保证在更新（覆写）正在更新的结构期间发生崩溃时，能够返回并查看你所做的注记，然后重试。因此，你会在崩溃后准确知道要修复的内容（以及如何修复它），而不必扫描整个磁盘。因此，通过设计，日志功能在更新期间增加了一些工作量，从而大大减少了恢复期间所需的工作量。 #### 数据日志 看一个简单的例子，来理解数据日志（data journaling）的工作原理。数据日志作为 Linux ext3 文件系统的一种模式提供，本讨论的大部分内容都来自于此。 假设再次进行标准的更新，我们再次希望将 inode、位图和数据块写入磁盘。在将它们写入最终磁盘位置之前，现在先将它们写入日志。  你可以看到，这里写了 5 个块： 事务开始（TxB）告诉我们有关此更新的信息，包括对文件系统即将进行的更新的相关信息（例如，块 I[v2]、B[v2]和 Db 的最终地址），以及某种事务标识符（transaction identifier，TID）。 中间的 3 个块只包含块本身的确切内容，这被称为物理日志（physical logging），因为我们将更新的确切物理内容放在日志中（另一种想法，逻辑日志（logical logging），在日志中放置更紧凑的更新逻辑表示，例如，“这次更新希望将数据块 Db 追加到文件 X”，这有点复杂，但可以节省日志中的空间，并可能提高性能）。 最后一个块（TxE）是该事务结束的标记，也会包含 TID。 一旦这个事务安全地存在于磁盘上，我们就可以覆写文件系统中的旧结构了。这个过程称为 `加检查点（checkpointing）`。因此，为了对文件系统加检查点（checkpoint，即让它与日志中即将进行的更新一致）。如果这些写入成功完成，我们已成功地为文件系统加上了检查点，基本上完成了。 在写入日志期间发生崩溃时，事情变得有点棘手。 在这里，我们试图将事务中的这些块（即 TxB、I[v2]、B[v2]、Db、TxE）写入磁盘。一种简单的方法是一次发出一个，等待每个完成，然后发出下一个。但是，这很慢。理想情况下，我们希望一次发出所有 5 个块写入，因为这会将 5 个写入转换为单个顺序写入，因此更快。然而，由于以下原因，这是不安全的：给定如此大的写入，磁盘内部可以执行调度并以任何顺序完成大批写入的小块。因此，磁盘内部可以（1）写入 TxB、I[v2]、B[v2]和 TxE，然后才写入 Db。遗憾的是，如果磁盘在（1）和（2）之间断电，那么磁盘上会变成：  为什么这是个问题？ 原因如下：事务看起来像一个有效的事务（它有一个匹配序列号的开头和结尾）。此外，文件系统无法查看第四个块并知道它是错误的。毕竟，它是任意的用户数据。因此，如果系统现在重新启动并运行恢复，它将重放此事务，并无知地将垃圾块“??”的内容复制到 Db 应该存在的位置。这对文件中的任意用户数据不利。如果它发生在文件系统的关键部分上，例如超级块，可能会导致文件系统无法挂装，那就更糟了。 > 补充：优化日志写入 > > 将事务写入日志时，在开始和结束块中包含日志内容的校验和。这样做可以使文件系统立即写入整个事务，而不会产生等待。如果在恢复期间，文件系统发现计算的校验和与事务中存储的校验和不匹配，则可以断定在写入事务期间发生了崩溃，从而丢弃了文件系统更新。因此，通过写入协议和恢复系统中的小调整，文件系统可以实现更快的通用情况性能。最重要的是，系统更可靠了，因为来自日志的任何读取现在都受到校验和的保护。 > > 这个简单的修复很吸引人，足以引起 Linux 文件系统开发人员的注意。他们后来将它合并到下一代 Linux 文件系统中，称为 Linux ext4（你猜对了！）。它现在可以在全球数百万台机器上运行，包括 Android 手持平台。因此，每次在许多基于 Linux 的系统上写入磁盘时，威斯康星大学开发的一些代码都会使你的系统更快、更可靠。 为避免该问题，文件系统分两步发出事务写入。首先，它将除 TxE 块之外的所有块写入日志，同时发出这些写入。当这些写入完成时，日志将看起来像这样（假设又是文件追加的工作负载）：  当这些写入完成时，文件系统会发出 TxE 块的写入，从而使日志处于最终的安全状态：  此过程的一个重要方面是磁盘提供的原子性保证。事实证明，磁盘保证任何 512 字节写入都会发生或不发生（永远不会半写）。因此，为了确保 TxE 的写入是原子的，应该使它成为一个 512 字节的块。因此，我们当前更新文件系统的协议如下，3 个阶段中的每一个都标上了名称。 #### 恢复 现在来了解文件系统如何利用日志内容从崩溃中恢复（recover）。 在这个更新序列期间，任何时候都可能发生崩溃。如果崩溃发生在事务被安全地写入日志之前，那么我们的工作很简单：简单地跳过待执行的更新。 如果在事务已提交到日志之后但在加检查点完成之前发生崩溃，则文件系统可以按如下方式恢复（recover）更新。 系统引导时，文件系统恢复过程将扫描日志，并查找已提交到磁盘的事务。然后，这些事务被 `重放（replayed，按顺序）`，文件系统再次尝试将事务中的块写入它们最终的磁盘位置。 这种形式的日志是最简单的形式之一，称为重做日志（redo logging）。通过在日志中恢复已提交的事务，文件系统确保磁盘上的结构是一致的，因此可以继续工作，挂载文件系统并为新请求做好准备。 在最坏的情况下，其中一些更新只是在恢复期间再次执行。因为恢复是一种罕见的操作（仅在系统意外崩溃之后发生），所以几次冗余写入无须担心。 #### 批处理日志更新 你可能已经注意到，基本协议可能会增加大量额外的磁盘流量。 为了解决这个问题，一些文件系统不会一次一个地向磁盘提交每个更新（例如，Linux ext3）。与此不同，可以将所有更新缓冲到全局事务中。 #### 使日志有限 日志的大小有限。如果不断向它添加事务（如下所示），它将很快填满。 日志满时会出现两个问题： - 第一个问题比较简单，但不太重要：日志越大，恢复时间越长，因为恢复过程必须重放日志中的所有事务（按顺序）才能恢复。 - 第二个问题更重要： 当日志已满（或接近满）时，不能向磁盘提交进一步的事务，从而使文件系统无用。 为了解决这些问题，日志文件系统将日志视为循环数据结构，一遍又一遍地重复使用。这就是为什么日志有时被称为循环日志（circular log）。为此，文件系统必须在加检查点之后的某个时间执行操作。具体来说，一旦事务被加检查点，文件系统应释放它在日志中占用的空间，允许重用日志空间。 #### 元数据日志 尽管恢复现在很快，但文件系统的正常操作比我们想要的要慢。特别是，对于每次写入磁盘，我们现在也要先写入日志，从而使写入流量加倍。在顺序写入工作负载期间，这种加倍尤为痛苦，现在将以驱动器峰值写入带宽的一半进行。此外，在写入日志和写入主文件系统之间，存在代价高昂的寻道，这为某些工作负载增加了显著的开销。 由于将每个数据块写入磁盘的成本很高，人们为了提高性能，尝试了一些不同的东西。 我们上面描述的日志模式通常称为数据日志（data journaling，如在 Linux ext3 中），因为它记录了所有用户数据（除了文件系统的元数据之外）。一种更简单（也更常见）的日志形式有时称为 `有序日志（ordered journaling，或称为元数据日志，metadata journaling）`，它几乎相同，只是用户数据没有写入日志。因此，在执行与上述相同的更新时，以下信息将写入日志：  先前写入日志的数据块 Db 将改为写入文件系统，避免额外写入。考虑到磁盘的大多数 I/O 流量是数据，不用两次写入数据会大大减少日志的 I/O 负载。然而，修改确实提出了一个有趣的问题：我们何时应该将数据块写入磁盘？ 事实证明，数据写入的顺序对于仅元数据日志很重要。 在将相关元数据写入磁盘之前，一些文件系统（例如，Linux ext3）先将数据块（常规文件）写入磁盘。具体来说，协议有以下几个： 1. 数据写入：将数据写入最终位置，等待完成（等待是可选的）。 2. 日志元数据写入：将开始块和元数据写入日志，等待写入完成。 3. 日志提交：将事务提交块（包括 TxE）写入日志，等待写完成，现在认为事务（包括数据）已提交（committed）。 4. 加检查点元数据：将元数据更新的内容写入文件系统中的最终位置。 5. 释放：稍后，在日志超级块中将事务标记为空闲。 通过强制先写入数据，文件系统可以保证指针永远不会指向垃圾。实际上，这个“先写入被指对象，再写入指针对象”的规则是崩溃一致性的核心，并且被其他崩溃一致性方案进一步利用。 在大多数系统中，元数据日志（类似于 ext3 的有序日志）比完整数据日志更受欢迎。 例如，Windows NTFS 和 SGI 的 XFS 都使用无序的元数据日志。Linux ext3 为你提供了选择数据、有序或无序模式的选项（在无序模式下，可以随时写入数据）。所有这些模式都保持元数据一致，它们的数据语义各不相同。 #### 块复用 具体例子如下。假设你正在使用某种形式的元数据日志（因此不记录文件的数据块）。假设你有一个名为 foo 的目录。用户向 foo 添加一个条目（例如通过创建文件），因此 foo 的内容（因为目录被认为是元数据）被写入日志。假设 foo 目录数据的位置是块 1000。因此日志包含如下内容：  此时，用户删除目录中的所有内容以及目录本身，从而释放块 1000 以供复用。最后，用户创建了一个新文件（比如 foobar），结果复用了过去属于 foo 的相同块（1000）。foobar 的 inode 提交给磁盘，其数据也是如此。但是，请注意，因为正在使用元数据日志，所以只有 foobar 的 inode 被提交给日志，文件 foobar 中块 1000 中新写入的数据没有写入日志。  假设用户有两个文件，一个名为 "foo"，另一个名为 "foobar"，它们都存储在磁盘上，并且 "foobar" 文件是在 "foo" 文件之后创建的。当用户删除 "foo" 文件时，它占用的磁盘块会被标记为空闲，并可以被重新分配给 "foobar" 文件使用。此时，如果 "foobar" 文件向磁盘写入内容，其中一些数据可能会被写入 "foo" 文件的磁盘块中。如果这些磁盘块没有被完全覆盖，"foo" 文件中的部分数据可能仍然可以从磁盘块中读取，从而泄露敏感信息。 现在假设发生了崩溃，所有这些信息仍然在日志中。在重放期间，恢复过程简单地重放日志中的所有内容，包括在块 1000 中写入目录数据。因此，重放会用旧目录内容覆盖当前文件 foobar 的用户数据！显然，这不是一个正确的恢复操作。 这个问题有一些解决方案。例如，可以永远不再重复使用块，直到所述块的删除加上检查点，从日志中清除。Linux ext3 的做法是将新类型的记录添加到日志中，称为撤销（revoke）记录。在上面的情况中，删除目录将导致撤销记录被写入日志。在重放日志时，系统首先扫描这样的重新记录。任何此类被撤销的数据都不会被重放，从而避免了上述问题。 #### 其他解决方案 Ganger 和 Patt 引入了一种称为软更新的方法。这种方法仔细地对文件系统的所有写入排序，以确保磁盘上的结构永远不会处于不一致的状态。 另一种方法称为写时复制（Copy-On-Write，COW），并且在许多流行的文件系统中使用，包括 Sun 的 ZFS。这种技术永远不会覆写文件或目录。相反，它会对磁盘上以前未使用的位置进行新的更新。 另一种方法是我们刚刚在威斯这星大学开发的方法。这种技术名为基于反向指针的一致性（Backpointer-Based Consistency，BBC），它在写入之间不强制执行排序。为了实现一致性，系统中的每个块都会添加一个额外的反向指针。 ## 第44章 数据完整性和保护 ### 硬盘故障模式 现代磁盘展示的所有其他类型的故障模式。 现代磁盘似乎大部分时间正常工作，但是无法成功访问一个或几个块。具体来说，两种类型的单块故障是常见的，值得考虑：潜在扇区错误（Latent-Sector Errors，LSE）和块讹误（block corruption）。 当磁盘扇区（或扇区组）以某种方式讹误时，会出现 LSE。例如，如果磁头由于某种原因接触到表面（磁头碰撞，head crash，在正常操作期间不应发生的情况），则可能会讹误表面，使得数据位不可读。宇宙射线也会导致数据位翻转，使内容不正确。幸运的是，驱动器使用磁盘内纠错码（Error Correcting Code，ECC）来确定块中的磁盘位是否良好，并且在某些情况下，修复它们。如果它们不好，并且驱动器没有足够的信息来修复错误，则在发出请求读取它们时，磁盘会返回错误。 ### 处理潜在的扇区错误 潜在的扇区错误很容易处理，因为它们（根据定义）很容易被检测到。当存储系统尝试访问块，并且磁盘返回错误时，存储系统应该就用它具有的任何冗余机制，来返回正确的数据。例如，在镜像 RAID 中，系统应该访问备用副本。在基于奇偶校验的 RAID-4 或 RAID-5 系统中，系统应通过奇偶校验组中的其他块重建该块。因此，利用标准冗余机制，可以容易地恢复诸如 LSE 这样的容易检测到的问题。 ### 检测讹误：校验和 与潜在的扇区错误不同，检测讹误是一个关键问题。客户如何判断一个块坏了？一旦知道特定块是坏的，恢复就像以前一样：你需要有该块的其他副本（希望没有讹误！）。因此，我们将重点放在检测技术上。 现代存储系统用于保持数据完整性的主要机制称为校验和（checksum）。校验和就是一个函数的结果，该函数以一块数据（例如 4KB 块）作为输入，并计算这段数据的函数，产生数据内容的小概要（比如 4 字节或 8 字节）。此摘要称为校验和。这种计算的目的在于，让系统将校验和与数据一起存储，然后在访问时确认数据的当前校验和与原始存储值匹配，从而检测数据是否以某种方式被破坏或改变。 #### 常见的校验和函数 许多不同的函数用于计算校验和，并且强度（即它们在保护数据完整性方面有多好）和速度（即它们能够以多快的速度计算）不同。 XOR 是一个合理的校验和，但有其局限性。例如，如果每个校验和单元内相同位置的两个位发生变化，则校验和将不会检测到讹误。出于这个原因，人们研究了其他校验和函数。另一个简单的校验和函数是加法。这种方法具有快速的优点。计算它只需要在每个数据块上执行二进制补码加法，忽略溢出。它可以检测到数据中的许多变化，但如果数据被移位，则不好。 稍微复杂的算法被称为 Fletcher 校验和（Fletcher checksum）。它非常简单，涉及两个校验字节 s1 和 s2 的计算。 最后常用的校验和称为循环冗余校验（CRC）。虽然听起来很奇特，但基本想法很简单。假设你希望计算数据块 D 的校验和。你所做的只是将 D 视为一个大的二进制数（毕竟它只是一串位）并将其除以约定的值（k）。该除法的其余部分是 CRC 的值。事实证明，人们可以相当有效地实现这种二进制模运算，因此也可以在网络中普及 CRC。 无论使用何种方法，很明显没有完美的校验和：两个具有不相同内容的数据块可能具 有相同的校验和，这被称为碰撞（collision）。 #### 校验和布局 第一个问题是校验和的布局，即如何将校验和存储在磁盘上？ 最基本的方法就是为每个磁盘扇区（或块）存储校验和。驱动器制造商采用的一种解决方案是使用 520 字节扇区格式化驱动器，每个扇区额外的 8 个字节可用于存储校验和。  ### 使用校验和 读取块 D 时，客户端（即文件系统或存储控制器）也从磁盘 Cs（D）读取其校验和，这称为存储的校验和（stored checksum，因此有下标 Cs）。然后，客户端计算读取的块 D 上的校验和，这称为计算的校验和（computed checksum）Cc（D）。此时，客户端比较存储和计算的校验和。如果它们相等 [即 Cs（D）== Cc（D）]，数据很可能没有被破坏，因此可以安全地返回给用户。如果它们不匹配 [即 Cs（D）!= Cc（D）]，则表示数据自存储之后已经改变（因为存储的校验和反映了当时数据的值）。在这种情况下，存在讹误，校验和帮助我们检测到了。 发现了讹误，自然的问题是我们应该怎么做呢？如果存储系统有冗余副本，答案很简单：尝试使用它。如果存储系统没有此类副本，则可能的答案是返回错误。 ### 一个新问题：错误的写入 上述基本方案对一般情况的讹误块工作良好。但是，现代磁盘有几种不同的故障模式，需要不同的解决方案。 第一种感兴趣的失败模式称为“错误位置的写入（misdirected write）”。这出现在磁盘和 RAID 控制器中，它们正确地将数据写入磁盘，但位置错误。 存储系统或磁盘控制器应该如何检测错误位置的写入？ 答案很简单：在每个校验和中添加更多信息。 ### 最后一个问题：丢失的写入 错误位置的写入并不是我们要解决的最后一个问题。具体来说，一些现代存储设备还有一个问题，称为丢失的写入（lost write）。当设备通知上层写入已完成，但事实上它从未持久，就会发生这种问题。因此，磁盘上留下的是该块的旧内容，而不是更新的新内容。 这里显而易见的问题是：上面做的所有校验和策略（例如，基本校验和或物理 ID），是否有助于检测丢失的写入？遗憾的是，答案是否定的：旧块很可能具有匹配的校验和，上面使用的物理 ID（磁盘号和块偏移）也是正确的。 有许多可能的解决方案有助于解决该问题[K+08]。一种经典方法[BS04]是执行写入验证（ write verify），或写入后读取（read-after-write）。通过在写入后立即读回数据，系统可以确保数据确实到达磁盘表面。然而，这种方法非常慢，使完成写入所需的 I/O 数量翻了一番。 某些系统在系统的其他位置添加校验和，以检测丢失的写入。例如，Sun 的 Zettabyte 文件系统（ZFS）在文件系统的每个 inode 和间接块中，包含文件中每个块的校验和。 ### 擦净 这些校验和何时实际得到检查？ 许多系统利用各种形式的磁盘擦净（disk scrubbing）。通过定期读取系统的每个块，并检查校验和是否仍然有效，磁盘系统可以减少某个数据项的所有副本都被破坏的可能性。典型的系统每晚或每周安排扫描。 ### 校验的开销 空间开销有两种形式： - 第一种是磁盘（或其他存储介质）本身。 - 第二种空间开销来自系统的内存。 虽然空间开销很小，但校验和引起的时间开销可能非常明显。至少，CPU 必须计算每个块的校验和，包括存储数据时（确定存储的校验和的值），以及访问时（再次计算校验和，并将其与存储的校验和进行比较）。 许多使用校验和的系统（包括网络栈）采用了一种降低 CPU 开销的方法，将数据复制和校验和组合成一个简化的活动。因为无论如何都需要拷贝（例如，将数据从内核页面缓存复制到用户缓冲区中），组合的复制/校验和可能非常有效。 除了 CPU 开销之外，一些校验和方案可能会导致外部 I/O 开销，特别是当校验和与数据分开存储时（因此需要额外的 I/O 来访问它们），以及后台擦净所需的所有额外 I/O。前者可以通过设计减少，后者影响有限，因为可以调整，也许通过控制何时进行这种擦净活动。半夜，当大多数（不是全部）努力工作的人们上床睡觉时，可能是进行这种擦净活动、增加存储系统健壮性的好时机。 最后修改：2023 年 03 月 27 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 3 本作品采用 CC BY-NC-SA 4.0 International License 进行许可。
