剖析虚幻渲染体系（18）- 操作系统（文件和I/O）_block read ahead

18.11 文件和I/O

18.11.1 文件和I/O综述

计算机可以操作多种设备，一般类型包括存储设备（磁盘、磁带）、传输设备（网卡、调制解调器）和人机界面设备（屏幕、键盘、鼠标）。设备通过电缆甚至通过空气发送信号来与计算机系统通信，通过一个称为端口（如串行端口）的连接点与机器通信。如果一个或多个设备使用一组公共电线，则该连接称为总线（bus）。

当设备A有一根电缆插入设备B，设备B有一条电缆插入设备C，设备C插入计算机上的端口时，这种安排称为菊花链，通常用作总线。典型的PC总线结构如图所示，PCI总线（通用PC系统总线）将处理器-内存子系统连接到快速设备，扩展总线连接相对较慢的设备，如键盘、串行和USB端口。

在下图的右上部分，四个磁盘在插入SCSI控制器的小型计算机系统接口（SCSI）总线上连接在一起。用于互连计算机主要部件的其他常见总线包括PCI Express（PCIe），其吞吐量高达每秒16 GB，以及Hyper Transport，其吞吐量达每秒25 GB。

计算机系统包含多个I/O设备及其各自的控制器：网卡、图形适配器、磁盘控制器、DVD-ROM控制器、串行端口、通用串口总线、声卡等。控制器是可以操作端口、总线或设备的电子设备的集合。串口控制器是简单设备控制器的一个示例，是计算机中的一个单片机，用于控制串行端口导线上的信号。SCSI总线控制器通常作为一个单独的电路板（主机适配器）插入计算机。它通常包含一个处理器、微码和一些专用内存，以使其能够处理SCSI协议消息。一些设备有自己的内置控制器。

I/O端口通常由四个寄存器组成：状态寄存器、控制寄存器、寄存器中的数据、数据输出寄存器。状态寄存器包含主机可以读取的位，这些位表示的状态：当前命令是否已完成、是否可以从寄存器中的数据读取字节、是否存在设备错误。

主机可以写入控制寄存器来启动命令或更改设备的模式，例如，串行端口控制寄存器中的某个位在全双工和半双工通信之间进行选择，另一个启用奇偶校验，第三位将单词长度设置为7或8位，其他位选择串行端口支持的速度之一。主机读取寄存器中的数据以获取输入，数据输出寄存器由主机写入以发送输出，数据寄存器通常为1至4字节。一些控制器具有FIFO芯片，可以保存几个字节的输入或输出数据，以将控制器的容量扩展到数据寄存器的大小之外。FIFO芯片可以保存少量数据，直到设备或主机能够接收这些数据。

轮询：主机和控制器之间交互的不完整协议可能很复杂，但基本握手概念很简单。控制器通过状态寄存器中的忙位指示其状态（记住，设置位意味着向位中写入1，清除位意味着将0写入位），在忙于工作时设置忙位，并在准备接受下一个命令时清除忙位。主机通过命令寄存器中的命令就绪位发出其愿望。当控制器可以执行命令时，主机设置命令就绪位。在本例中，主机通过端口写入输出，通过如下握手与控制器协调：

1、主机反复读取忙位，直到该位变为清零。

2、主机在命令寄存器中设置写入位，并将一个字节写入数据输出寄存器。

3、主机设置命令就绪位。

4、当控制器注意到命令就绪位已设置时，它将设置为“忙碌”。

5、控制器读取命令寄存器并看到写入命令。

6、它读取数据输出寄存器以获取字节，并对设备进行I/O操作。

7、控制器清除命令就绪位，清除状态寄存器中的错误位以指示设备I/O成功，并清除忙位以指示完成。

主机正忙于等待或轮询：它处于一个循环中，反复读取状态寄存器，直到忙位被清除。如果控制器和设备速度快，则此方法是合理的。但如果等待时间可能很长，主机可能会切换到另一个任务。

I/O设备的类别有：

• 人类可读。适合与计算机用户通信，例如打印机、视频显示终端、键盘等。
• 机器可读。适用于与电子设备通信，例如磁盘和磁带驱动器、传感器、控制器和执行器。
• 通信。适合与远程设备通信，例如数字线路驱动器和调制解调器。

I/O设备之间的差异：

• 数据速率：数据传输速率之间可能存在几个数量级的差异。
• 应用：不同的设备在系统中有不同的用途。
• 控制的复杂性：磁盘要复杂得多，而打印机需要简单的控制界面。
• 传输单元：数据可以作为字节或字符流或更大的块进行传输。
• 数据表示：不同的设备使用不同的数据编码方案。
• 错误条件：错误的性质因设备而异。

直接内存访问（Direct Memory Access，DMA）的描述如下：

• 可以提供一个特殊的控制单元，允许在外部设备和主存储器之间直接传输数据块，而无需处理器的持续干预，这种方法称为直接内存访问（DMA）。
• 可以与轮询或中断软件一起使用。在诸如磁盘之类的设备上特别有用，在这些设备上，可以在单个I/O操作中传输许多字节的信息。当与中断一起使用时，只有在传输了整个数据块后，才会通知CPU。
• 对于传输的每个字节或字，它必须提供存储器地址和控制数据传输的所有总线信号。
• 通过设备驱动程序管理与设备控制器的交互。设备驱动程序是操作系统的一部分，但不一定是操作系统内核的一部分。
• 操作系统为用户应用程序提供了设备的简化视图（例如，UNIX中的字符设备与块设备）。在某些操作系统（例如Linux）中，也可以通过/dev文件系统访问设备。
• 在某些情况下，操作系统会缓冲在设备和用户空间程序（磁盘缓存、网络缓冲区）之间传输的数据。
• 通常会提高性能，但并不总是如此。

I/O系统的主要目的是抽象对物理和逻辑设备的访问，访问任意文件系统中的文件应与访问串行端口、USB摄像头或打印机不同。I/O系统由多个组件组成，一些组件处于用户模式，大多数组件处于内核模式。最重要的部分如下图所示。

用户模式进程使用各种Windows API调用I/O系统，内核端的所有文件和设备操作都由I/O管理器启动。通过创建一个称为I/O请求包（IRP）的内核结构来处理请求（如读或写），填充请求的详细信息，然后将其传递给适当的设备驱动程序。对于实际文件，将转到文件系统驱动程序，如NTFS。如下图所示，该过程与正常的系统调用没有本质区别。

就内核而言，I/O操作总是异步的，意味着驱动程序应该启动操作并尽快返回，以便调用线程可以重新获得控制。但是，原始调用者可以选择同步调用，在这种情况下，I/O管理器代表调用者等待，直到操作完成。从客户的角度来看，这种灵活性非常方便。

下面是不同存储介质的速率对比：

18.11.2 磁盘

18.11.2.1 磁盘结构

磁盘驱动器被寻址为逻辑块（logical block）的大型一维数组，其中逻辑块是最小的传输单元，逻辑块的大小通常为512字节，逻辑块的一维数组按顺序映射到磁盘的扇区，扇区0是最外层圆柱上第一条轨迹的第一扇区。映射依次通过该轨道、该圆柱体中的其余轨道，然后从最外层到最内层通过其余圆柱体，逻辑到物理地址应该很容易，坏扇区除外。通过恒定角速度，每条轨道的扇区数不恒定。

磁盘提供计算机系统的大量辅助存储，可以被视为每台计算机共用的一个I/O设备，有多种尺寸和速度，信息可以用光学或磁性存储。磁带曾被用作早期的辅助存储介质，但存取时间比磁盘慢得多，目前正在使用磁带进行备份。

现代磁盘驱动器被称为逻辑块的大型一维数组，其中逻辑块是最小的传输单元。磁盘I/O操作的实际细节取决于计算机系统、操作系统以及I/O通道和磁盘控制器硬件的性质。信息存储的基本单位是扇区，扇区存储在扁平、圆形的媒体磁盘上，此介质旋转接近一个或多个读/写磁头，磁头可以从磁盘的内部移动到外部。当磁盘驱动器运行时，磁盘以恒定速度旋转，要读或写，磁头必须位于所需磁道和该磁道上所需扇区的开头，轨道选择包括在移动头部系统中移动头部或在固定头部系统中电子选择一个头部。这些特征是软盘、硬盘、CD-ROM和DVD的共同特征。

查看现代硬盘的规格时需要注意的一点是，驱动程序软件所指定和使用的几何图形几乎总是与物理格式不同。在旧磁盘上，每个磁道的扇区数对于所有柱面都是相同的。现代磁盘被划分为多个分区，外部分区上的扇区比内部分区上的多。下图（a）显示了一个有两个区域的小圆盘。外区每条轨道有32个扇区；内部的一条每条轨道有16个扇区。一个真正的磁盘，如WD 3000 HLFS，通常有16个或更多分区，随着从最内层分区到最外层分区的扩展，每个分区的扇区数量增加了大约4%。

（a） 具有两个分区的磁盘的物理几何形状。（b） 此磁盘可能的虚拟几何体。

为了隐藏每个磁道有多少扇区的详细信息，大多数现代磁盘都有一个呈现给操作系统的虚拟几何体。该软件被指示按照每个磁道有x个柱面、y个磁头和z个扇区的方式运行。然后，控制器将（x，y，z）的请求重新映射到实际的圆柱体、封头和扇区。上图（a）中物理磁盘的可能虚拟几何结构如图（b）中所示。在这两种情况下，磁盘都有192个扇区，只有发布的排列与实际的不同。

对于PC，这三个参数的最大值通常为（65535、16和63），因为需要向后兼容原始IBM PC的限制。在这台机器上，16位、4位和6位字段用于指定这些数字，柱面和扇区编号从1开始，磁头编号从0开始。使用这些参数，每个扇区512字节，最大可能磁盘为31.5 GB。为了克服这个限制，所有现代磁盘现在都支持一种称为逻辑块寻址的系统，在这种系统中，磁盘扇区从0开始连续编号，而不考虑磁盘的几何形状。

CPU性能在过去十年中呈指数级增长，大约每18个月翻一番。磁盘性能则不然。随着时间的推移，CPU性能和（硬盘）性能之间的差距变得越来越大，并行处理越来越多地被用于加快CPU性能。多年来，许多人都意识到并行I/O可能也是一个好主意，Patterson等人在其1988年的论文中提出了六种可用于提高磁盘性能和/或可靠性的特定磁盘组织。这些想法很快被业界采纳，并产生了一种新的I/O设备，称为RAID（Redundant Array of Inexpensive Disks，廉价冗余磁盘阵列）。还存在它的反面，就是SLED（Single Large Expensive Disk，单个大型昂贵磁盘）。

RAID级别0到6。备份和奇偶校验驱动器以阴影显示。

磁盘有时会出错，好的扇区可能突然变成坏的扇区，整个驱动器可能会意外损坏。RAID可防止少数扇区出现故障，甚至驱动器出现故障。然而，它们并不能防止写错误，因为首先会留下坏数据，也不能防止在写入损坏原始数据而不替换为新数据时发生崩溃。

对于某些应用程序，即使在磁盘和CPU出现错误的情况下，数据也决不能丢失或损坏。理想情况下，磁盘应该一直工作，没有错误。不幸的是，这是无法实现的。可以实现的是具有以下属性的磁盘子系统：当向其发出写操作时，磁盘要么正确写入数据，要么什么也不做，从而保持现有数据的完整性。这种系统称为稳定存储（stable storage），并用软件实现（Lampon and Sturgis，1979）。目标是不惜一切代价保持磁盘的一致性。

稳定存储使用一对相同的磁盘和相应的块一起工作，形成一个无错误的块。在没有错误的情况下，两个驱动器上的相应块是相同的。任何一个都可以读取以获得相同的结果。为了实现这一目标，定义了以下三种操作：

• 稳定写入。稳定写入包括首先将块写入驱动器1，然后将其读回以验证是否正确写入。如果不是，则会再次执行写入和重新读取，最多可重复n次，直到它们工作为止。在连续n次失败后，该块将重新映射到备用磁盘上，并重复操作，直到成功为止，无论必须尝试多少个备用磁盘。写入驱动器1成功后，会写入并重新读取驱动器2上的相应块，如果需要，可以反复读取，直到最后也成功。在没有CPU崩溃的情况下，当稳定写入完成时，块已正确写入两个驱动器并在两个驱动器上进行验证。
• 读取稳定。稳定读取首先从驱动器1读取块。如果这产生错误的ECC，则再次尝试读取，最多n次。如果所有这些都给出了坏的ECC，则从驱动器2读取相应的块。考虑到成功的稳定写入会留下两个好的块副本，并且我们假设同一块在合理的时间间隔内在两个驱动器上自发损坏的概率可以忽略不计，因此稳定读取总是成功的。
• 崩溃恢复。崩溃后，恢复程序会扫描两个磁盘，并比较相应的块。如果一对块都是好的并且是相同的，那么什么也做不了。如果其中一个出现ECC错误，则坏块将被相应的好块覆盖。如果一对块都是好的但不同的，则驱动器1的块会写入驱动器2。

18.11.2.2 磁盘性能参数

当磁盘驱动器运行时，磁盘以恒定速度旋转。要读或写，磁头必须位于所需磁道和该磁道上所需扇区的开头。轨道选择包括在移动头部系统中移动头部或在固定头部系统中电子选择一个头部，在可移动磁头系统上，磁头在轨道上定位所需的时间称为寻道时间。选择磁道后，磁盘控制器将等待，直到相应的扇区旋转以与磁头对齐，扇区开始到达头部所需的时间称为旋转延迟或旋转延迟。寻道时间（如果有的话）和旋转延迟的总和等于访问时间，即进入读取或写入位置所需的时间。磁头就位后，随着扇区在磁头下方移动，执行读或写操作，这是操作的数据传输部分，转移所需的时间就是转移时间。

寻道时间是将磁盘臂移动到所需轨道所需的时间。事实证明，是一个难以确定的数量。寻道时间由两个关键部分组成：初始启动时间，一旦检修臂达到速度就必须穿过轨道所需的时间，计算公式：

Ts=m∗n+sTs=m∗n+s

其中：TsTs是寻道时间，nn是轨道遍历时间，mm是取决于磁盘驱动器的常数，ss启动时间。

旋转延时（Rotational Latency）是等待磁盘旋转到磁盘头所需扇区的额外时间。

旋转延迟（Rotational Delay）：磁盘（软盘除外）的转速从3600 rpm到15000 rpm不等；在后一速度下，每4毫秒旋转一圈。因此，平均旋转延迟为2毫秒。软盘通常以300至600 rpm的转速旋转。因此，平均延迟将在100到50毫秒之间。

磁盘带宽是传输的总字节数除以第一次请求服务和完成最后一次传输之间的总时间。

传输时间：往返磁盘的传输时间取决于磁盘的以下旋转速度：

T=brNT=brN

其中：TT是传输时间，bb是要传输的字节数，rr是磁道上的字节数，NN是转速，单位为转/秒。因此，总平均访问时间可表示为：

Ta=Ts+12r+brNTa=Ts+12r+brN

18.11.2.3 磁盘调度

满足一系列I/O请求所需的头数量会影响性能，如果所需的磁盘驱动器和控制器可用，则可以立即处理请求。如果设备或控制器繁忙，任何新的服务请求都将被放入该驱动器的待定请求队列中。当一个请求完成时，操作系统会选择下一个要服务的挂起请求。不同类型的调度算法如下。

• 先到先服务调（FCFS）

最简单的调度形式是先进先出（FIFO）调度，它按顺序处理队列中的项目，将按照收到请求的顺序为请求提供服务。此算法虽然是公平的，但不能提供最快的服务，不需要特别的时间来最小化总寻道时间。

这种策略的优点是公平，因为每一个请求都会得到满足，并且请求会按照收到的顺序得到满足。使用FIFO，如果只有少数几个进程需要访问，并且许多请求都是针对集群文件扇区的，那么可以获得良好的性能。

示例：考虑一个磁盘队列，请求对柱面上的块进行I/O。98, 183, 37, 122, 14, 124, 65, 67。

磁头如果最初位于53，将首先从53移动到98，然后再移动到183，然后移动到37、122、14、124、65、67，从而使磁头移动640个圆柱（cylinder）。从122到14，然后再回到124，这说明了这个调度算法的问题。如果cylinder 37和14的请求可以在122和124之前或之后一起处理，则总移动量可以大幅减少，性能可以得到改善。

• 最短寻道时间优先（SSTF）

SSTF首先从当前头部位置选择寻道时间最短的请求，是SJF调度的一种形式，可能会导致某些请求不足。由于寻道时间随头部所经过的cylinder数增加而增加，因此SSTF选择最接近当前cylinder位置的挂起请求，下图显示了236个气缸的缸盖总移动量。示例：考虑一个磁盘队列，请求对柱面上的块进行I/O：98、183、37、122、14、124、65、67。

如果磁头最初位于53，最接近的是cylinder 65，然后是67，然后是37，比98接近67。因此，它服务37，继续服务14、98、122、124，最后服务183，总移动量仅为236个cylinder。

SSTF本质上是SJF的一种形式，可能会导致某些请求的匮乏，是对FCFS的实质性改进，但它不是最优的。

• SCAN

SCAN算法有时称为电梯算法，扫描算法在磁道0处开始扫描，并向编号最高的磁道移动，在磁道通过时为磁道的所有请求提供服务。磁盘臂从磁盘的一端开始，向另一端移动，为请求提供服务，直到它到达磁盘的另一端，此时磁头移动方向相反，服务继续。

下图显示208个cylinder的头部总移动。但请注意，如果请求是均匀密集的，则磁盘另一端的密度最大，等待时间最长。示例：考虑一个磁盘队列，请求对柱面上的块进行I/O：98、183、37、122、14、124、65、67。

如果磁盘磁头最初位于53，并且磁头向0移动，则服务于37，然后服务于14。在cylinder 0处，臂将倒转，并朝着维修65、67、98、122、124和183的磁盘的另一端移动。如果一个请求刚好从头部到达，它将立即得到服务，头部后面的请求将不得不等待，直到手臂到达另一端并反转方向。

它可以始终处理下一个最近的请求，以最小化寻道时间。根据下图的要求，顺序为12、9、16、1、34和36，如图底部的锯齿线所示。按照此顺序，臂运动为1、3、7、15、33和2，总共61个气缸。该算法称为SSF（最短寻道优先），与FCFS相比，它几乎将手臂的总运动量减少了一半。

• 循环扫描（C-SCAN）

C-SCAN是SCAN的变体，旨在提供更均匀的等待时间，其策略将扫描限制在一个方向。与SCAN类似，C-SCAN将磁头从磁盘的末端移动到另一个为请求提供服务的位置，当磁头到达另一端时，它会立即返回到磁盘的开头，而不会在返回时处理任何请求。

C-SCAN将cylinder视为从最终cylinder到第一个cylinder的循环列表，减少了新请求所经历的最大延迟。示例：考虑一个磁盘队列，请求对柱面上的块进行I/O：98、183、37、122、14、124、65、67。

• Look

SCAN和C-SCAN都会在磁盘的整个宽度上移动磁盘臂，开始向一个方向移动头部。当在该方向上没有更多请求时，满足该方向上最近轨迹的请求，磁头正在行驶，反转方向并重复。此算法类似于每条电路上最内侧和最外侧的轨道。实际上，这两种算法都不是以这种方式实现的。手臂在每个方向上只能到达最后的请求。然后它会反转，不会一直到磁盘的末尾。

这些版本的SCAN和CSCAN称为Look和C-Look调度，因为它们在继续向给定方向移动之前会查找请求。示例：考虑一个磁盘队列，请求对柱面上的块进行I/O：98、183、37、122、14、124、65、67。

我们如何在上述几种磁盘调度算法中选择合适的？通用建议如下：

• SSTF很常见，比FCFS提高了性能。
• SCAN和C-SCAN算法更适合于在磁盘上放置重负载的系统，它们的饥饿问题较少。
• SSTF或Look是默认算法的合理选择。
• 调度算法的性能取决于请求的数量和类型。
• 磁盘服务请求可能会受到文件分配方法的影响。
• 磁盘调度算法应作为操作系统的一个单独模块编写，允许在必要时用不同的算法替换。SSTF或LOOK是默认算法的合理选择。

18.11.3 文件

文件是相似记录的集合，除非数据位于文件中，否则无法将其写入辅助存储。文件表示程序和数据，数据可以是数字、字母数字、字母或二进制。许多不同类型的信息可以存储在一个文件中——源程序、目标程序、可执行程序、数字数据、工资记录器、图形图像、录音等。

为了提供存放文件的地方，大多数PC操作系统都有目录的概念，作为将文件分组在一起的一种方式。例如，一个学生可能有一个目录，用于他正在学习的每门课程（用于该课程所需的程序），另一个目录用于他的电子邮件，还有另一个用于他的万维网主页的目录。然后需要系统调用来创建和删除目录。还提供了将现有文件放入目录和从目录中删除文件的调用。目录条目可以是文件或其他目录。该模型还产生了文件系统的层次结构，如下图所示。

文件属性因操作系统而异，常见的文件属性包括：

• 名称：符号文件名是以人类可读形式保存的唯一信息。
• 标识符：唯一标记，通常是一个数字，用于标识文件系统中的文件，是文件的不可读名称。
• 类型：支持不同类型的系统需要此信息。
• 位置：是指向设备和该设备上文件位置的指针。
• 大小：文件的当前大小以及可能的最大允许大小。
• 保护：访问控制信息决定谁可以进行读取、写入、执行等操作。
• 时间、数据和用户标识：必须保存此信息，以备创建、上次修改和上次使用。这些数据有助于保护、安全和使用监控。

文件根据其类型具有特定的定义结构：

• 文本文件：是按行组织的字符序列。
• 对象文件：是一个字节序列，组织成系统链接器可以理解的块。
• 可执行文件：是加载程序可以放入内存并执行的一系列代码段。
• 源文件：子程序和函数的序列，每一个都进一步组织为声明，后面是可执行语句。

（a） 可执行文件；（b） 文档。

文件是一种抽象数据类型。要定义文件，我们需要考虑可以对文件执行的操作。文件的基本操作是：

• 创建文件：需要两个步骤——首先，在文件系统中找到文件的第一个空间；其次，必须在目录中为新文件创建一个条目，目录条目记录文件名和文件系统中的位置。
• 写入文件：系统调用主要用于写入文件。系统调用指定文件名和信息，即要写入文件的信息，给定名称后，系统将在整个目录中搜索该文件，系统必须保留一个指向文件中下次写入位置的写入指针。
• 读取文件：使用文件系统调用读取文件，需要文件名和内存地址，再次搜索目录以查找关联的目录，系统必须维护指向文件中下次读取位置的读取指针。
• 删除文件：系统将搜索要删除文件的目录。如果找到条目，将释放所有可用空间，该可用空间可以被另一个文件重用。
• 截断文件：-户可能希望删除文件的内容，但保留其属性。截断允许所有属性保持不变，文件长度除外，而不是强制用户删除文件然后重新创建。
• 在文件中重新定位：-索目录以查找适当的条目，并将当前文件位置设置为给定值，在文件中重新定位不需要涉及实际的i/o，文件操作也称为文件查找。

除了这6个操作之外，其他两个操作包括在文件末尾附加新信息和重命名现有文件，这些原语可以组合起来执行其他两个操作。大多数文件操作都涉及在整个目录中搜索与文件关联的条目。为了避免这种情况，操作系统会保留一个小表，其中包含有关打开文件的信息（打开表）。当请求文件操作时，将通过该表中的索引指定该文件。因此，不需要搜索。

打开的文件相关联的信息有：

• 文件指针：在不包括偏移量的读写系统调用的一部分的系统上，系统必须将最后的读写位置作为当前文件位置指针进行跟踪。此指针对于在文件上操作的每个进程都是唯一的。
• 文件打开计数：当文件关闭时，操作系统必须重用其打开的文件表条目，否则可能会耗尽表中的空间。因为多个进程可能会打开一个文件，所以系统必须等待最后一个文件关闭，然后才能删除打开的文件表条目。计数器跟踪打开和关闭的副本数，最后一次关闭时为零。
• 文件的磁盘位置：在磁盘上定位文件所需的信息保存在内存中，以避免每次操作都必须从磁盘读取文件。
• 访问权限：每个进程都以访问模式打开一个文件，此信息存储在每个进程表中，操作系统可以允许操作系统拒绝随后的I/O请求。

可以通过多种方式访问文件中的信息。不同的文件访问方法是：

• 顺序访问。它是最简单的访问方法。文件中的信息是按顺序处理的，一条记录接着一条记录。编辑器和编译器以这种方式访问文件，通常对文件执行读写操作。读取操作读取文件的下一部分，并自动前进文件指针，该指针跟踪下一个i/i轨迹。写入操作附加到文件的末尾，这样的文件可以紧邻开头。顺序访问取决于文件的磁带型号。

  

• 直接访问或相对访问。允许随机访问任何文件块，基于文件的磁盘模型，文件由固定长度的逻辑记录组成。它允许程序以任何顺序快速读取和写入记录，允许读取或写入任意块。示例：用户可能需要块13，然后读取块99，然后写入块12。对于搜索具有即时结果的大量信息的记录，直接访问方法是合适的。并非所有操作系统都支持顺序和直接访问，很少有操作系统使用顺序访问，有些操作系统使用直接访问。在直接访问上模拟顺序访问很容易，但反过来效率极低。

索引方法：索引就像一本书末尾的索引，其中包含指向各个块的指针。要在文件中查找记录，我们搜索索引，然后使用指针直接访问文件并查找所需的记录。对于大型文件，索引文件本身可以非常大，以便保存在内存中。一种为索引文件本身创建索引的解决方案。主索引文件将包含指向辅助索引文件的指针，该文件将指向实际数据项。可以使用两种类型的索引：

• 详尽索引：主文件中的每条记录都包含一个条目，索引本身被组织为顺序文件。
• 部分索引：包含记录的条目，其中感兴趣的字段存在可变长度的记录，某些记录将不包含字段。将新记录添加到主文件时，必须更新所有索引文件。

为了跟踪文件，文件系统通常有目录或文件夹，它们本身就是文件。

目录系统的最简单形式是拥有一个包含所有文件的目录。有时它被称为根目录，但因为它是唯一的目录，所以名称并不重要。在早期的个人电脑上，这种系统很常见，部分原因是只有一个用户。有趣的是，世界上第一台超级计算机CDC 6600也只有一个目录存放所有文件，尽管它同时被许多用户使用，此举是为了保持软件设计简单。

下图给出了一个具有一个目录的系统示例，目录包含四个文件，此方案的优点是简单，并且能够快速定位文件，毕竟只有一个地方可以查看。它有时仍用于简单的嵌入式设备，如数码相机和一些便携式音乐播放器。

单级适用于非常简单的专用应用程序（甚至在第一台个人计算机上使用过），但对于拥有数千个文件的现代用户来说，如果所有文件都在一个目录中，则不可能找到任何内容。因此，需要一种方法将相关文件组合在一起——层次结构（即目录树）。使用这种方法，可以有任意多的目录以自然方式对文件进行分组。此外，如果多个用户共享一个公共文件服务器，就像许多公司网络上的情况一样，每个用户都可以为自己的层次结构拥有一个专用根目录。这种方法如下图所示。在这里，根目录中包含的目录A、B和C都属于不同的用户，其中两个用户为他们正在处理的项目创建了子目录。

用户可以创建任意数量的子目录，为用户组织工作提供了强大的结构化工具。因此，几乎所有现代文件系统都是以这种方式组织的。

当文件系统组织为目录树时，需要某种方法来指定文件名。通常使用两种不同的方法。在第一种方法中，每个文件都有一个绝对路径名，由根目录到文件的路径组成。例如，路径/usr/ast/mailbox意味着根目录包含子目录usr，而该子目录又包含子目录ast，其中包含文件mailbox。绝对路径名总是从根目录开始，并且是唯一的。在UNIX中，路径的组件用/分隔，在Windows中，分隔符是\，在MULTICS中，它是>。因此，在这三个系统中，相同的路径名将写入如下：

Windows  \usr\ast\mailbox
UNIX     /usr/ast/mailbox
MULTICS  >usr>ast>mailbox

其中Unix的目录树示例如下：

18.11.3.1 文件系统实现

现在是时候从用户的文件系统视角转向实现者的视角了。用户关心文件的命名方式、允许对其进行哪些操作、目录树的外观以及类似的界面问题。实现者感兴趣的是如何存储文件和目录，如何管理磁盘空间，以及如何使一切高效可靠地工作。下面我们将研究其中的一些领域，以了解问题和权衡。

文件系统软件架构。

文件系统存储在磁盘上。大多数磁盘可以划分为一个或多个分区，每个分区上都有独立的文件系统。磁盘的扇区0称为MBR（主引导记录），用于引导计算机。MBR的末尾包含分区表，此表给出了每个分区的起始地址和结束地址，表中的一个分区被标记为活动分区。当计算机启动时，BIOS读取并执行MBR，MBR程序所做的第一件事是定位活动分区，读取其第一个块（称为引导块），然后执行它。启动块中的程序加载该分区中包含的操作系统。为了一致性，每个分区都从一个引导块开始，即使它不包含可引导的操作系统。此外，将来可能会包含一个。

除了从启动块开始，磁盘分区的布局因文件系统而异。文件系统通常包含下图所示的一些项，第一个是超级块，它包含有关文件系统的所有关键参数，并在计算机启动或首次触摸文件系统时被读入内存，超级块中的典型信息包括用于标识文件系统类型的幻数、文件系统中的块数以及其他关键管理信息。

接下来可能会出现有关文件系统中可用块的信息，例如以位图或指针列表的形式。接下来可能是i节点，一组数据结构，每个文件一个，说明文件的所有信息。之后可能是根目录，其中包含文件系统树的顶部。最后，磁盘的其余部分包含所有其他目录和文件。

文件管理元素。

通用文件组织。

Windows支持多种文件系统，包括在Windows 95、MS-DOS和OS/2上运行的文件分配表（FAT）。但Windows的开发人员也设计了一种新的文件系统，即Windows文件系统（NTFS），旨在满足工作站和服务器的高端需求。高端应用示例：

• 客户端/服务器应用程序，如文件服务器、计算服务器和数据库服务器。
• 资源密集型工程和科学应用。
• 大型公司系统的网络应用程序。

NTFS是一个灵活而强大的文件系统，它建立在一个优雅而简单的文件系统模型上。NTFS最值得注意的功能包括：

• 可恢复性：在新Windows文件系统的要求列表中，最重要的是能够从系统崩溃和磁盘故障中恢复。在发生此类故障时，NTFS能够重建磁盘卷并将其恢复到一致状态。它通过使用事务处理模型对文件系统进行更改来实现这一点，每一个重大变化都被视为一个原子行为，要么完全执行，要么根本不执行，失败时正在处理的每个事务随后都会被退出或完成。此外，NTFS对关键文件系统数据使用冗余存储，因此磁盘扇区故障不会导致描述文件系统结构和状态的数据丢失。
• 安全性：NTFS使用Windows对象模型来加强安全性，打开的文件被实现为具有定义其安全属性的安全描述符的文件对象。
• 大磁盘和大文件：与大多数其他文件系统（包括FAT）相比，NTFS更有效地支持非常大的磁盘和非常大的文件。
• 多个数据流：文件的实际内容被视为字节流。在NTFS中，可以为单个文件定义多个数据流，此功能的实用性示例是，它允许远程Macintosh系统使用Windows来存储和检索文件。在Macintosh上，每个文件都有两个组件：文件数据和包含文件信息的资源分叉。NTFS将这两个组件视为两个数据流。
• 通用索引功能：NTFS将属性集合与每个文件相关联。文件管理系统中的一组文件描述被组织为一个关系数据库，以便可以通过任何属性对文件进行索引。

NTFS使用以下磁盘存储概念：

• 扇区（Sector）：磁盘上最小的物理存储单元。以字节为单位的数据大小是2的幂，几乎总是512字节。
• 群簇（Cluster）：一个或多个连续（在同一轨道上彼此相邻）扇区。扇区中的集群大小是2的幂。
• 卷（Volume）：磁盘上的逻辑分区，由一个或多个群集组成，由文件系统用于分配空间。在任何时候，卷都由文件系统信息、文件集合以及卷上可分配给文件的任何其他未分配空间组成。卷可以是单个磁盘的全部或一部分，也可以跨多个磁盘扩展。如果使用硬件或软件RAID 5，则卷由跨越多个磁盘的条带组成。NTFS的最大卷大小为264264字节。

卷的布局。

NTFS可以在系统崩溃或磁盘故障后将文件系统恢复到一致状态。结合下图，支持可恢复性的关键要素是：

• I/O管理器：包括NTFS驱动程序，用于处理NTFS的基本打开、关闭、读取和写入功能。此外，可以配置软件RAID模块FTDISK以供使用。
• 日志文件服务：维护磁盘写入日志。日志文件用于在系统出现故障时恢复NTFS格式化的卷。
• 缓存管理器：负责缓存文件读写以提高性能。缓存管理器通过使用第11.8节中描述的延迟写入和延迟提交技术来优化磁盘I/O。
• 虚拟内存管理器：NTFS通过将文件引用映射到虚拟内存引用以及读写虚拟内存来访问缓存文件。

Windows NTFS组件。

18.11.3.2 实现文件

在实现文件存储时，最重要的问题可能是跟踪哪个磁盘块与哪个文件对应，不同的操作系统使用不同的方法。下图是记录块的方法：

• 连续分配

最简单的分配方案是将每个文件存储为连续运行的磁盘块。因此，在一个具有1-KB块的磁盘上，一个50-KB的文件将被分配50个连续的块。对于2-KB的块，它将被分配25个连续的块。

我们在下图（a）中看到了连续存储分配的示例，显示了前40个磁盘块，从左侧的块0开始。最初，磁盘是空的，然后，从开头（块0）开始，将一个长度为四个块的文件a写入磁盘，之后，一个六块文件B被写入文件a的末尾之后。

请注意，每个文件都从新块的开始处开始，因此如果文件a实际上是3½个块，那么在最后一个块的末尾会浪费一些空间。在图中，总共显示了七个文件，每个文件都从前一个文件的末尾之后的块开始。着色只是为了更容易区分文件，就存储而言，它没有实际意义。

（a） 连续分配七个文件的磁盘空间。（b） 删除文件D和F后磁盘的状态。

连续文件分配的案例。

连续文件分配的案例（压缩后）。

连续磁盘空间分配有两个显著的优点。首先，它很容易实现，因为跟踪文件块的位置可以简化为记住两个数字：第一个块的磁盘地址和文件中的块数。给定第一个块的数量，任何其他块的数量都可以通过简单的加法得到。

其次，读取性能非常好，因为整个文件可以在一次操作中从磁盘读取，只需要一个寻道（到第一个块）。此后，不再需要寻道或旋转延迟，因此数据以磁盘的全部带宽进入。因此，连续分配易于实现且具有高性能。

不幸的是，连续分配也有一个非常严重的缺点：随着时间的推移，磁盘会变得支离破碎。要了解这是如何发生的，参看上图（b）。这里删除了两个文件D和F。当一个文件被删除时，它的块会被自然释放，从而在磁盘上留下一段空闲块。磁盘不是当场压实以挤出孔洞，因为这将涉及复制孔后的所有块，可能有数百万块，如果磁盘较大，这将需要数小时甚至数天的时间。因此，磁盘最终由文件和孔洞组成。

最初，这个碎片不是问题，因为每个新文件都可以在磁盘末尾写入，紧跟前一个文件。然而，最终磁盘将被填满，因此有必要压缩磁盘（成本高昂），或者重新使用孔中的可用空间。重复使用空间需要维护孔列表，这是可行的。但是，创建新文件时，需要知道其最终大小，以便选择正确大小的孔来放置文件。

想象一下这种设计的后果。用户启动文字处理器以创建文档，程序首先要问的是最终文档的字节数，必须回答此问题，否则程序将无法继续。如果最终证明给出的数字太小，程序必须提前终止，因为磁盘孔已满，没有地方放置文件的其余部分。如果用户试图通过给出一个不切实际的大数字作为最终大小来避免这个问题，例如1GB，那么编辑器可能无法找到如此大的洞，并宣布无法创建文件。当然，用户可以自由地再次启动程序，并说这次是500MB，以此类推，直到找到合适的漏洞为止。不过，这个方案不太可行。

然而，有一种情况下，连续分配是可行的，而且事实上仍在使用：在CD-ROM上。在这里，所有文件大小都是预先知道的，并且在随后使用CD-ROM文件系统时永远不会改变。而DVD的情况有点复杂。原则上，一部90分钟的电影可以编码为一个长度约为4.5 GB的文件，但使用的文件系统UDF（Universal Disk Format，通用磁盘格式）使用30位数字表示文件长度，将文件限制在1 GB以内。因此，DVD影片通常存储为三个或四个1-GB文件，每个文件都是连续的，单个逻辑文件（电影）的这些物理片段称为扩展数据块。

• 链接列表分配

存储文件的第二种方法是将每个文件保存为磁盘块的链接列表，如下图所示。每个块的第一个字用作指向下一个块的指针。块的其余部分用于数据。

与连续分配不同，此方法可以使用每个磁盘块，磁盘碎片不会丢失空间（最后一个块中的内部碎片除外）。此外，目录条目只存储第一个块的磁盘地址就足够了。其余的可以从那里开始找到。

另一方面，虽然顺序读取文件很简单，但随机访问速度非常慢。要到达块n，操作系统必须从开始处启动并读取n− 之前1个街区，一次一个。显然，读取大量内容时会非常缓慢。

此外，块中的数据存储量不再是2的幂，因为指针占用了几个字节。虽然不是致命的，但具有特殊大小的程序效率较低，因为许多程序读写块的大小是2的幂次方。由于每个块的前几个字节被指向下一个块的指针占用，读取完整块大小需要从两个磁盘块获取并连接信息，这会因复制而产生额外的开销。

• 使用内存中的表分配链接列表

通过从每个磁盘块获取指针字并将其放入内存中的表中，可以消除链表分配的两个缺点。下图显示了上图示例的表格。在两个图中，我们都有两个文件。文件A按顺序使用磁盘块4、7、2、10和12，文件B按顺序使用盘块6、3、11和14。使用下图的表格，我们可以从区块4开始，沿着链条一直走到底，从块6开始也可以这样做。两条链条都用一个特殊标记（例如−1）， 但不是有效的块编号。主存储器中的这样一个表称为FAT（File Allocation Table，文件分配表）。

使用主存中的文件分配表分配链接列表。

使用此组织，整个块都可用于数据，随机访问要容易得多。尽管仍必须遵循链来查找文件中的给定偏移量，但链完全在内存中，因此可以在不进行任何磁盘引用的情况下遵循它。与前面的方法一样，目录条目只需保留一个整数（起始块编号）就足够了，而且无论文件有多大，仍然能够定位所有块。

这种方法的主要缺点是，整个表必须始终在内存中才能工作。对于1-TB磁盘和1-KB块大小，该表需要10亿个条目，每个条目对应10亿个磁盘块，每个条目必须至少为3个字节。为了加快查找速度，它们应该是4个字节。因此，该表将始终占用3 GB或2.4 GB的主内存，取决于系统是针对空间还是时间进行了优化，因此不太实用。显然，FAT的想法不能很好地扩展到大型磁盘。它是最初的MS-DOS文件系统，但所有版本的Windows仍然完全支持它。

• I节点

跟踪哪些块属于哪个文件的最后一种方法是将称为I节点（索引节点）的数据结构与每个文件相关联，它列出了文件块的属性和磁盘地址，给定i节点，就可以找到文件的所有块。一个简单的例子如下图所示。

与使用内存中表的链接文件相比，此方案的最大优点是，仅当相应文件打开时，i节点才需要在内存中。如果每个i节点占用n个字节，并且一次最多可以打开k个文件，则保存打开文件的i节点的数组所占用的总内存仅为k*n个字节，只需提前预留这么多空间。

此数组通常远小于上一节中描述的文件表所占用的空间，原因很简单，用于保存所有磁盘块链接列表的表的大小与磁盘本身成比例。如果磁盘有n个块，则表需要n个条目，随着磁盘的增大，此表也会随之线性增长。相反，i-node方案需要内存中的数组，其大小与一次可以打开的最大文件数成正比。磁盘是100 GB、1000 GB还是10000 GB并不重要。

i节点的一个问题是，如果每个节点都有固定数量磁盘地址的空间，那么当文件增长超过此限制时会发生什么情况？一种解决方案是不为数据块保留最后一个磁盘地址，而是为包含更多磁盘块地址的块的地址保留，如上图所示。更高级的方法是两个或多个包含磁盘地址的此类块，甚至是指向其他满有地址的磁盘块的磁盘块。类似地，Windows NTFS文件系统使用了类似的思想，只有更大的i节点也可以包含小文件。

18.11.3.3 实现文件夹

在读取文件之前，必须先将其打开，打开文件时，操作系统使用用户提供的路径名来查找磁盘上的目录项，目录条目提供查找磁盘块所需的信息。根据系统的不同，此信息可能是整个文件的磁盘地址（具有连续分配）、第一个块的编号（两个链表方案）或i节点的编号。在所有情况下，目录系统的主要功能是将文件的ASCII名称映射到查找数据所需的信息上。

一个密切相关的问题是属性应该存储在哪里。每个文件系统都维护各种文件属性，例如每个文件的所有者和创建时间，它们必须存储在某个地方。一种明显的可能性是将它们直接存储在目录条目中，有些系统正是这样做的，该选项如下图（a）所示。在这种简单的设计中，目录由一个固定大小的条目列表组成，每个文件一个，其中包含一个（固定长度）文件名、文件属性的结构，以及一个或多个磁盘地址（最大值），说明磁盘块的位置。

（a） 一个简单的目录，包含固定大小的条目，在目录条目中有磁盘地址和属性。（b） 一种目录，其中的每个条目仅指一个i节点。

树形结构文件夹的案例。

对于使用i-node的系统，存储属性的另一种可能性是在i-node中，而不是在目录条目中。在这种情况下，目录条目可以更短：只需一个文件名和一个i-node编号，如上图（b）所示。

到目前为止，我们假设文件的名称很短，长度固定。在MS-DOS文件中，基本名称为1-8个字符，扩展名可选为1-3个字符。在UNIX版本7中，文件名为1-14个字符，包括任何扩展名。然而，几乎所有现代操作系统都支持更长、可变长度的文件名。如何实现这些目标？

最简单的方法是设置文件名长度限制，通常为255个字符，然后使用下图的一种设计，为每个文件名保留255个字。这种方法很简单，但浪费了大量目录空间，因为很少有文件具有如此长的名称。出于效率原因，最好采用不同的结构。

一种替代方法是放弃所有目录条目大小相同的想法。使用此方法，每个目录条目都包含一个固定部分，通常从条目的长度开始，然后是固定格式的数据，通常包括所有者、创建时间、保护信息和其他属性。这个固定长度的头后面跟着实际的文件名，不管文件名有多长，如图下图（a）所示，格式为大端格式（例如SPARC）。在这个例子中，我们有三个文件，project-budget、personnel和foo。每个文件名都以一个特殊字符（通常为0）结尾，该字符在图中由一个带叉的框表示。为了允许每个目录条目都从单词边界开始，每个文件名都被填入整数个单词，如图中阴影框所示。

处理目录中长文件名的两种方法。（a） 排成一行。（b） 堆成一堆。

18.11.3.4 共享文件

当多个用户一起处理一个项目时，他们通常需要共享文件。因此，共享文件通常很方便同时出现在属于不同用户的不同目录中。下图显示了包含一个共享文件的文件系统，只有C的一个文件现在也存在于B的一个目录中。B的目录和共享文件之间的连接称为链接。文件系统本身现在是一个有向非循环图（DAG），而不是一棵树。将文件系统作为DAG会使维护变得复杂，但生活正是如此。

包含了一个共享文件的文件系统。

共享文件很方便，但也带来了一些问题。首先，如果目录确实包含磁盘地址，那么在链接文件时，必须在B的目录中创建磁盘地址的副本。如果随后B或C追加到文件中，则新块将仅列在执行追加操作的用户的目录中。其他用户将看不到这些更改，从而破坏了共享的目的。这个问题可以通过两种方式解决：

• 第一种解决方案：磁盘块不列在目录中，而是列在与文件本身相关联的一个小数据结构中，然后目录将只指向小数据结构。这是UNIX中使用的方法（其中小数据结构是i节点）。
• 第二种解决方案：B链接到C的一个文件，方法是让系统创建一个新文件，类型为LINK，然后将该文件输入B的目录中，新文件只包含它链接到的文件的路径名。当B从链接文件中读取时，操作系统会看到正在读取的文件的类型为LINK，查找文件名并读取该文件。这种方法称为符号链接，与传统（硬）链接形成对比。

这些方法都有其缺点。在第一种方法中，当B链接到共享文件时，i-node将文件的所有者记录为C。创建链接不会更改所有权（见下图），但会增加i-node中的链接数，因此系统知道当前有多少目录条目指向该文件。

（a） 连接前的情况。（b） 创建链接后。（c） 在原始所有者删除文件后。

如果C随后尝试删除该文件，则系统将面临问题。如果删除文件并清除i-node，B将有一个指向无效i-node的目录条目。如果稍后将i节点重新指定给其他文件，B的链接将指向错误的文件。系统可以从i-node中的计数看出文件仍在使用中，但没有简单的方法可以找到文件的所有目录条目，以便将其删除。指向目录的指针不能存储在索引节点中，因为目录的数量可能不受限制。

唯一要做的是删除C的目录条目，但保留i节点不变，计数设置为1，如上图（C）所示。我们现在有一种情况，B是唯一一个拥有C所拥有文件的目录条目的用户。如果系统进行记帐或有配额，C将继续为该文件计数，直到B决定删除它，如果有，此时计数变为0，文件被删除。

使用符号链接时，不会出现此问题，因为只有真正的所有者才有指向i节点的指针。链接到文件的用户只有路径名，而没有i节点指针。当所有者删除文件时，它将被销毁。当系统无法找到该文件时，后续通过符号链接使用该文件的尝试将失败。删除符号链接根本不会影响文件。

18.11.3.5 日志结构化文件系统

技术的变化给当前的文件系统带来了压力。特别是，CPU的速度越来越快，磁盘越来越大，越来越便宜（但速度并不快），内存的大小呈指数级增长。磁盘寻道时间（固态磁盘除外，固态磁盘没有寻道时间）是一个没有明显改善的参数。

这些因素的组合意味着在许多文件系统中出现了性能瓶颈。伯克利大学的研究试图通过设计一种全新的文件系统LFS（Log-structured
File System，日志结构文件系统）来缓解这个问题。

推动LFS设计的想法是，随着CPU速度的加快和RAM内存的增大，磁盘缓存也在迅速增加。因此，现在可以直接从文件系统缓存满足大部分读取请求，而不需要磁盘访问。从这个观察结果可以看出，在未来，大多数磁盘访问都将是写操作，因此在某些文件系统中用于在需要块之前获取块的预读机制不再能获得太多性能。

更糟糕的是，在大多数文件系统中，写入都是在非常小的块中完成的。小型写入效率很低，因为50微秒的磁盘写入之前通常会有10毫秒的寻道和4毫秒的旋转延迟。使用这些参数，磁盘效率会下降到1%。

要查看所有小写操作的来源，请考虑在UNIX系统上创建一个新文件。要写入此文件，必须写入目录的i节点、目录块、文件的i节点以及文件本身。虽然这些写入可能会延迟，但如果在写入之前发生崩溃，那么这样做会使文件系统面临严重的一致性问题。因此，通常会立即执行i节点写入。

根据这一推理，LFS设计者决定重新实现UNIX文件系统，以实现磁盘的全部带宽，即使面对由大部分小的随机写入组成的工作负载。基本思想是将整个磁盘结构为一个大日志。

定期地，当有特殊需要时，内存中缓冲的所有挂起的写操作都被收集到一个段中，并在日志末尾作为一个连续的段写入磁盘。因此，单个段可能包含混合在一起的i节点、目录块和数据块。每段开头都有一个段摘要，说明段中可以找到什么。如果可以将平均段设置为大约1 MB，则几乎可以利用磁盘的全部带宽。

在这种设计中，i节点仍然存在，甚至具有与UNIX中相同的结构，但它们现在分散在日志中，而不是位于磁盘上的固定位置。然而，在定位i节点时，通常会按常规方式定位块。当然，现在查找i节点要困难得多，因为它的地址不能像在UNIX中那样简单地从i编号计算出来。为了能够找到i节点，将维护一个按i编号索引的i节点映射表。此映射中的条目i指向磁盘上的i节点i。映射表保存在磁盘上，但也会被缓存，因此最常用的部分大部分时间都在内存中。

总结一下我们到目前为止所说的内容，所有写操作最初都在内存中进行缓冲，并且定期将所有缓冲的写操作写入日志末尾的单个段中的磁盘。现在，打开文件包括使用映射表定位文件的i节点。一旦找到i节点，就可以从中找到块的地址。所有块本身都是分段的，位于日志中的某个位置。

如果磁盘无限大，上面的描述就是全部。然而，实际磁盘是有限的，因此日志最终将占据整个磁盘，此时无法向日志写入新的段。幸运的是，许多现有段可能有不再需要的块。例如，如果文件被覆盖，其i节点现在将指向新块，但旧块仍将在以前写入的段中占用空间。

为了解决这个问题，LFS有一个更干净的线程，它花时间循环扫描日志以压缩它。它首先读取日志中第一段的摘要，以查看其中有哪些i节点和文件。然后检查当前的i节点映射表，以查看i节点是否仍然是当前的，文件块是否仍在使用中。否则，该信息将被丢弃。仍在使用的i节点和块进入内存，在下一个段中写出。然后将原始段标记为空闲，以便日志可以将其用于新数据。以这种方式，清洁器沿着日志移动，从后面删除旧段，并将任何实时数据放入内存，以便在下一段中重写。因此，磁盘是一个大的圆形缓冲区，写入线程在前面添加新的段，而清理线程从后面删除旧的段。

这里的记账（bookkeeping）很重要，因为当一个文件块被写回一个新的段时，文件的i节点（在日志中的某个位置）必须被定位、更新并放入内存中，以便在下一段中写出。然后必须更新i节点贴图以指向新副本。尽管如此，仍然可以进行管理，性能结果表明，所有这些复杂性都是值得的。上述论文中给出的测量结果表明，LFS在小写操作方面比UNIX好几个数量级，而在读操作和大写操作方面的性能与UNIX相当或更好。

18.11.3.6 日志文件系统

虽然日志结构文件系统是一个有趣的想法，但它们并没有被广泛使用，部分原因是它们与现有文件系统高度不兼容。然而，它们所固有的一个思想，即面对故障时的健壮性，可以很容易地应用于更传统的文件系统。这里的基本思想是在文件系统执行操作之前保存一个日志，以便如果系统在执行计划的工作之前崩溃，在重新启动系统时，可以查看日志，查看崩溃时发生的情况并完成作业。这种文件系统称为日志文件系统（Journaling File Systems），实际上正在使用中。Microsoft的NTFS文件系统以及Linux ext3和ReiserFS文件系统都使用日志记录，OSX提供日志文件系统作为一个选项。

要了解问题的本质，请考虑一个经常发生的普通操作：删除文件。此操作（在UNIX中）需要三个步骤：

1、从目录中删除文件。

2、将i-node释放到空闲i-node池中。

3、将所有磁盘块返回到可用磁盘块池。

在Windows中，需要类似的步骤。在没有系统崩溃的情况下，采取这些步骤的顺序无关紧要；在发生崩溃的情况下，情况确实如此。假设第一步完成，然后系统崩溃。i节点和文件块将无法从任何文件访问，但也不能用于重新分配，它们只是处于不确定的状态，减少了可用的资源。如果崩溃发生在第二步之后，则仅丢失块。

如果操作顺序发生更改，并且首先释放了i-node，那么在重新启动后，i-node可能会被重新分配，但旧的目录条目将继续指向它，从而指向错误的文件。如果先释放块，则在清除i-node之前发生崩溃意味着有效的目录条目将指向一个i-node，其中列出了当前在空闲存储池中的块，并且很可能很快会被重用，从而导致两个或多个文件随机共享同一块。这些结果都不好。

日志文件系统所做的是首先写入一个日志条目，列出要完成的三个操作。然后将日志条目写入磁盘（为了更好地测量，可能会从磁盘读取，以验证它实际上是否正确写入）。只有在写入日志条目后，才能开始各种操作。操作成功完成后，日志条目将被擦除。如果系统现在崩溃，在恢复时，文件系统可以检查日志以查看是否有任何操作挂起。如果是这样，则可以重新运行所有这些文件（在重复崩溃的情况下多次运行），直到文件被正确删除。

为了使日志记录有效，日志记录的操作必须是幂等的，意味着可以根据需要重复这些操作，而不会造成损害。可以重复执行“更新位图以将i节点k或块n标记为空闲”等操作，直到列回归时没有危险。类似地，搜索目录并删除任何名为foobar的条目也是幂等的。另一方面，将i节点K中新释放的块添加到空闲列表的末尾不是幂等的，因为它们可能已经存在。更昂贵的操作“搜索可用块列表并将块n添加到其中（如果尚未存在）”是幂等的。日志文件系统必须安排其数据结构和可记录操作，以便它们都是幂等的。在这些情况下，可以快速安全地进行崩溃恢复。

为了增加可靠性，文件系统可以引入原子事务的数据库概念。当使用这个概念时，一组操作可以被开始事务和结束事务操作括起来。然后，文件系统知道它必须完成所有括号内的操作，或者不完成任何操作，但不能完成任何其他组合。

NTFS有一个广泛的日志系统，其结构很少因系统崩溃而损坏。自1993年Windows NT首次发布以来，它就一直在开发中。第一个做日志记录的Linux文件系统是ReiserFS，但它的普及受到了阻碍，因为它与当时的标准ext2文件系统不兼容。相反，与ReiserFS相比，ext3是一个不那么雄心勃勃的项目，它在保持与以前的ext2系统兼容的同时也做日志记录。

18.11.3.7 虚拟文件系统

即使对于同一操作系统，在同一台计算机上也经常使用许多不同的文件系统。Windows系统可能有一个主NTFS文件系统，但也有一个旧的FAT-32或FAT-16驱动器或分区，其中包含旧的但仍然需要的数据，有时还需要一个闪存驱动器、旧的CD-ROM或DVD（每个都有自己独特的文件系统）。Windows通过使用不同的驱动器号（如C:、D:等）标识每个文件系统来处理这些不同的文件系统。当进程打开文件时，驱动器号是显式或隐式显示的，因此Windows知道要将请求传递给哪个文件系统。没有尝试将异构文件系统集成到一个统一的整体中。

相比之下，所有现代UNIX系统都在认真尝试将多个文件系统集成到一个结构中。Linux系统可以将ext2作为根文件系统，在/usr上安装ext3分区，在/home上安装ReiserFS文件系统的第二个硬盘，以及在/mnt上临时安装ISO 9660 CD-ROM。从用户的角度来看，存在单个文件系统层次结构。它碰巧包含多个（不兼容）文件系统，这对用户或进程来说是不可见的。

然而，多文件系统的存在对于实现来说是非常明显的，并且自从Sun Microsystems的开创性工作以来，大多数UNIX系统都使用VFS（virtual file system，虚拟文件系统）的概念来尝试将多个文件系统集成到一个有序的结构中。其关键思想是抽象出所有文件系统通用的文件系统部分，并将该代码放在一个单独的层中，该层调用底层的具体文件系统来实际管理数据。总体结构如下图所示。下面的讨论不是针对Linux或FreeBSD或任何其他版本的UNIX，而是介绍了虚拟文件系统在UNIX系统中的工作方式。

虚拟文件系统的位置。

所有与文件相关的系统调用都被定向到虚拟文件系统进行初始处理。这些来自用户进程的调用是标准的POSIX调用，例如open、read、write、lseek等。因此，VFS具有用户进程的“上部”接口，它是众所周知的POSIX接口。

VFS还有一个到具体文件系统的“较低”接口，在上图中标记为VFS接口。该接口由几十个函数调用组成，VFS可以对每个文件系统进行函数调用以完成工作。因此，要创建与VFS一起工作的新文件系统，新文件系统的设计者必须确保它提供了VFS所需的函数调用。此类函数的一个明显示例是从磁盘读取特定块，将其放入文件系统的缓冲区缓存，并返回指向该块的指针。因此，VFS有两个不同的接口：上层接口用于用户进程，下层接口用于具体文件系统。

虽然VFS下的大多数文件系统表示本地磁盘上的分区，但情况并非总是如此。事实上，Sun构建VFS的最初动机是使用NFS（网络文件系统）协议支持远程文件系统。VFS的设计是这样的，只要具体的文件系统提供了VFS所需的功能，VFS就不知道或不关心数据存储在哪里或底层文件系统是什么样的。

在内部，大多数VFS实现本质上是面向对象的，即使它们是用C而不是C++编写的。通常支持几种关键对象类型，包括超级块（描述文件系统）、v节点（描述文件）和目录（描述文件体系目录），每个都有具体文件系统必须支持的关联操作（方法）。此外，VFS有一些内部数据结构供自己使用，包括挂载表和一组文件描述符，用于跟踪用户进程中所有打开的文件。

为了理解VFS是如何工作的，让我们按时间顺序运行一个示例。当系统启动时，根文件系统向VFS注册。此外，当其他文件系统在引导时或操作期间装载时，它们也必须向VFS注册。当一个文件系统注册时，它基本上是提供一个VFS所需函数的地址列表，可以是一个长调用向量（表），也可以是其中的几个，每个VFS对象一个，这是VFS所要求的。因此，一旦文件系统向VFS注册，VFS就知道如何从中读取块，它只需调用文件系统提供的向量中的第四个（或其他）函数。类似地，VFS知道如何执行具体文件系统必须提供的所有其他功能：它只调用文件系统注册时提供地址的函数。

安装文件系统后，可以使用它。例如，如果在/usr上装载了一个文件系统，并且某个进程在解析路径时打开了调用：

open("/usr/include/unistd.h", O_RDONLY)

则VFS会看到一个新的文件系统已装载在/usr上，并通过搜索已装载文件系统的超级块列表来定位其超级块。完成此操作后，它可以找到装载的文件系统的根目录，并查找路径include/unistd.h在那里。然后，VFS创建一个v节点，并调用具体的文件系统来返回文件inode中的所有信息。此信息与其他信息（最重要的是指向函数表的指针）一起复制到v节点（在RAM中）中，以调用v节点上的操作，例如读取、写入、关闭等。

创建v-node后，VFS在文件描述符表中为调用进程创建一个条目，并将其设置为指向新的v-node。最后，VFS将文件描述符返回给调用者，以便它可以使用它来读取、写入和关闭文件。

稍后，当进程使用文件描述符进行读取时，VFS从进程和文件描述符表中找到v节点，并跟随指向函数表的指针，所有这些都是请求文件所在的具体文件系统中的地址。现在将调用处理读取的函数，具体文件系统中的代码将进入并获取请求的块。VFS不知道数据是来自本地磁盘、网络上的远程文件系统、U盘还是其他东西。涉及的数据结构如下图所示。从调用者的进程号和文件描述符开始，依次定位具体文件系统中的v节点、读取函数指针和访问函数。

VFS和具体文件系统用于读取的数据结构和代码的简化视图。

通过这种方式，添加新的文件系统变得相对简单。设计人员首先获得VFS期望的函数调用列表，然后编写文件系统来提供所有函数调用。或者，如果文件系统已经存在，那么它们必须提供包装器函数来完成VFS所需的工作，通常是通过对具体文件系统进行一个或多个本地调用。

18.11.3.8 文件系统管理和优化

使文件系统工作是一回事；让它在现实生活中高效、稳健地工作是完全不同的。在以下各节中，我们将讨论管理磁盘所涉及的一些问题。

• 磁盘空间优化

文件通常存储在磁盘上，因此磁盘空间的管理是文件系统设计者的主要关注点。存储一个n字节文件有两种通用策略：分配n个连续字节的磁盘空间，或者将文件分割成多个（不一定）连续的块。在内存管理系统中，纯分段和分页之间也存在相同的折衷。

正如我们所看到的，将文件存储为连续的字节序列有一个明显的问题，即如果文件增长，可能必须将其移动到磁盘上。内存中的段也存在同样的问题，不同的是，与将文件从一个磁盘位置移动到另一个磁盘的位置相比，在内存中移动段是一个相对较快的操作。因此，几乎所有的文件系统都会将文件切成固定大小的块，这些块不需要相邻。

首先考虑的块大小（Block Size）。

一旦决定将文件存储在固定大小的块中，问题就出现了，块应该有多大。考虑到磁盘的组织方式，扇区、磁道和柱面显然是分配单元的候选对象（尽管它们都依赖于设备，这是负数）。在分页系统中，页面大小也是一个主要的竞争者。

拥有较大的块大小意味着每个文件，甚至是一个1字节的文件，都会占用整个柱面，也意味着小文件会浪费大量磁盘空间。另一方面，较小的块大小意味着大多数文件将跨越多个块，因此需要多次寻道和旋转延迟来读取它们，从而降低性能。因此，如果分配单元太大，我们就会浪费空间；如果太小，会浪费时间。

要做出正确的选择，需要掌握一些有关文件大小分布的信息。Tanenbaum等人（2006年）于1984年和2005年分别在一所大型研究型大学（VU）的计算机科学系和一个托管政治网站（www.electroral-vote.com）的商业Web服务器上研究了文件大小分布。结果下图所示，其中，对于两个文件大小的每一次幂，列出了三个数据集中每个数据集小于或等于它的所有文件的百分比。例如，2005年，VU中59.13%的文件小于等于4 KB，90.84%的文件小于或等于64 KB。中间文件大小为2475字节。有些人可能会觉得这种小尺寸令人惊讶。

小于给定大小（以字节为单位）的文件的百分比。

我们可以从这些数据中得出什么结论？首先，对于块大小为1 KB的文件，只有大约30-50%的文件可以放在一个块中，而对于4-KB的文件块，放在一块中的文件百分比可以达到60-70%。本文中的其他数据显示，对于4-KB的块，93%的磁盘块被10%的最大文件使用。这意味着在每个小文件的末尾浪费一些空间几乎无关紧要，因为磁盘被少量大文件（视频）填满，小文件占用的空间总量几乎无关痛痒。即使将最小的90%文件占用的空间加倍，也几乎看不到。

另一方面，使用小块意味着每个文件将由多个块组成。读取每个块通常需要寻道和旋转延迟（固态磁盘除外），因此读取由许多小块组成的文件会很慢。

例如，考虑一个每个磁道有1 MB的磁盘，旋转时间为8.33毫秒，平均寻道时间为5毫秒。读取k字节块的时间（毫秒）就是寻道时间、旋转延迟时间和传输时间的总和：

5+4.165+(k/1000000)×8.335+4.165+(k/1000000)×8.33

下图的虚线曲线显示了此类磁盘的数据速率与块大小的函数关系。为了计算空间效率，我们需要假设平均文件大小，为了简单起见，我们假设所有文件都是4KB。虽然这个数字略大于VU测量的数据，但学生可能拥有比企业数据中心中更多的小文件，因此总体上来说，这可能是一个更好的猜测。下图的实心曲线显示了作为块大小函数的空间效率。

这两条曲线可以理解如下。一个块的访问时间完全由寻道时间和旋转延迟决定，因此如果访问一个块要花费9毫秒，那么获取的数据越多越好。因此，数据速率几乎与块大小成线性增长（直到传输时间过长，传输时间开始变得重要）。

现在考虑空间效率。对于4-KB文件和1-KB、2-KB或4-KB块，文件分别使用4、2和1个块，没有浪费。对于8-KB的块和4-KB的文件，空间效率下降到50%，而对于16KB的块，空间效率降低到25%。实际上，很少文件是磁盘块大小的精确倍数，因此文件的最后一个块总是浪费一些空间。

然而，曲线表明，性能和空间利用率之间存在固有的冲突。小数据块对性能不利，但对磁盘空间利用率有利。对于这些数据，没有合理的折衷方案。最接近两条曲线交叉处的大小为64KB，但数据速率仅为6.6MB/秒，空间效率约为7%，两者都不是很好。过去，文件系统选择的大小在1-KB到4-KB之间，但现在磁盘超过1TB，最好将块大小增加到64KB，并接受浪费的磁盘空间。磁盘空间几乎不再短缺。

Vogels在康奈尔大学（Cornell University）对文件进行了测量，以确定Windows NT文件的使用情况是否与UNIX文件的使用有明显不同（Vogels，1999）。他注意到NT文件的使用比在UNIX上更复杂。他写道：当我们在记事本文本编辑器中键入几个字符时，将其保存到文件将触发26个系统调用，包括3次失败的打开尝试、1次文件覆盖和4次额外的打开和关闭序列。

然而，Vogels观察到文件的中值大小（按使用情况加权）为1KB，写文件为2.3KB，读写文件为4.2KB。考虑到不同的数据集测量技术和年份，这些结果与VU结果肯定是兼容的。

接下来阐述跟踪空闲块（Keeping Track of Free Blocks）。

一旦选择了块大小，下一个问题是如何跟踪空闲块。有两种方法被广泛使用，如下图所示。第一种方法包括使用磁盘块的链接列表，每个块都包含尽可能多的可用磁盘块编号。对于1-KB块和32位磁盘块编号，可用列表中的每个块都包含255个可用块。（指向下一个块的指针需要一个插槽。）考虑一个1-TB磁盘，它有大约10亿个磁盘块。要将所有这些地址存储为每个块255个，需要大约400万个块。通常，空闲块用于保存空闲列表，因此存储基本上是空闲的。

（a） 将空闲列表存储在链接列表中。（b） 位图。

另一种可用空间管理技术是位图。具有n个块的磁盘需要具有n位的位图。在图中，可用块用1表示，分配块用0表示（反之亦然）。对于我们的示例1-TB磁盘，映射需要10亿位，这需要大约130000个1-KB块来存储。位图需要更少的空间并不奇怪，因为它每个块使用1位，而链接列表模型中使用32位。只有当磁盘接近满时（即只有很少的空闲块），链接列表方案所需的块才会少于位图。

如果空闲块倾向于以长时间连续块的形式出现，则可以修改空闲列表系统，以跟踪块的运行而不是单个块的运行。可以将8、16或32位计数与每个块相关联，给出连续可用块的数量。在最好的情况下，一个基本上是空的磁盘可以用两个数字表示：第一个空闲块的地址后面是空闲块的数量。另一方面，如果磁盘严重碎片化，则跟踪运行比跟踪单个块效率低，因为不仅必须存储地址，还必须存储计数。

这个问题说明了操作系统设计者经常遇到的一个问题。有多种数据结构和算法可用于解决问题，但选择最佳数据结构和方法需要设计者没有并且在系统部署和大量使用之前不会拥有的数据。即使如此，数据也可能不可用。例如，在1984年和1995年测量的VU文件大小、网站数据和康奈尔大学数据只是四个样本。虽然比什么都没有要好得多，但不知道它们是否也能代表家用电脑、公司电脑、政府电脑和其他电脑。通过一些努力，我们可能已经能够从其他类型的计算机上获得一些样本，但即使如此，将这些样本外推到所有被测量的计算机上也是愚蠢的。

回到空闲列表方法，只需要在主内存中保留一块指针。创建文件时，所需的块从指针块中获取。当它用完时，会从磁盘中读入一个新的指针块。类似地，当一个文件被删除时，它的块被释放并添加到主内存中的指针块中。当这个块被填满时，它被写入磁盘。

在某些情况下，此方法会导致不必要的磁盘I/O。考虑下图（a）中的情况，内存中的指针块只能再容纳两个条目。如果释放了一个三块文件，指针块溢出，必须写入磁盘，导致（b）所示的情况。如果现在写入了一个三块文件，则必须再次读取完整的指针块，将我们带回（a）。如果刚刚写入的三块文件是一个临时文件，则在释放该文件时，需要另一次磁盘写入才能将整个指针块写回磁盘。简而言之，当指针块几乎为空时，一系列短期临时文件可能会导致大量磁盘I/O。

避免大多数磁盘I/O的另一种方法是分割整个指针块。因此，当释放三个块时，我们不再从下图（a）转到下图。现在，系统可以处理一系列临时文件，而无需执行任何磁盘I/O。如果内存中的块已满，则会将其写入磁盘，并读入磁盘中的半满块。这里的想法是保持磁盘上的大多数指针块已满（以最小化磁盘使用），但保持内存中的指针块约半满，这样它就可以在空闲列表中没有磁盘I/O的情况下处理文件创建和文件删除。

（a） 指向内存中空闲磁盘块的几乎完整的指针块和磁盘上的三个指针块。（b） 释放三个块文件的结果。（c）处理三个空闲块的替代策略。带阴影的条目表示指向可用磁盘块的指针。

使用位图，也可以只保留内存中的一个块，只有当它完全满或空时才将另一个块放入磁盘。这种方法的另一个好处是，通过从位图的单个块进行所有分配，磁盘块将紧密相连，从而最小化磁盘臂运动。由于位图是固定大小的数据结构，如果对内核进行（部分）分页，则可以将位图放在虚拟内存中，并根据需要分页。

接下来阐述磁盘配额（Disk Quotas）。

为了防止人们占用过多的磁盘空间，多用户操作系统通常提供一种强制执行磁盘配额的机制。其思想是，系统管理员为每个用户分配文件和块的最大分配，操作系统确保用户不会超过其配额。下面描述了一个典型的机制。

当用户打开一个文件时，属性和磁盘地址被定位并放入主内存中打开的文件表中。属性中有一个条目，告诉谁是所有者，文件大小的任何增加都将计入所有者的配额。

第二个表包含当前打开文件的每个用户的配额记录，即使该文件是由其他人打开的，此表如下图所示。它是从磁盘上的配额文件中为当前打开文件的用户提取的，关闭所有文件后，记录将被写回配额文件。

当在打开的文件表中创建新条目时，会在其中输入一个指向所有者配额记录的指针，以便于查找各种限制。每次向文件中添加块时，向所有者收取的块总数都会增加，并对硬限制和软限制进行检查。可以超过软限制，但不能超过硬限制。当达到硬块限制时，尝试附加到文件将导致错误。还存在类似的文件数量检查，以防止用户占用所有i节点。

当用户尝试登录时，系统会检查配额文件，以查看用户是否已超过文件数或磁盘块数的软限制。如果违反了任一限制，将显示警告，剩余警告数将减少一。如果计数为零，则用户多次忽略警告，不允许登录。要获得再次登录的权限，需要与系统管理员进行一些讨论。

此方法具有这样的属性，即用户在登录会话期间可能会超出其软限制，前提是他们在注销之前移除超出的限制。不得超过硬限制。

• 文件系统备份

文件系统的破坏通常比计算机的破坏更大。如果一台电脑被火灾、闪电或一杯咖啡泼到键盘上烧毁，会很烦人，也会花很多钱，但通常情况下，可以用最少的麻烦购买一台替代品。便宜的个人电脑甚至可以在一个小时内通过去电脑商店来更换。

如果计算机的文件系统由于硬件或软件而无法挽回地丢失，恢复所有信息将是困难的、耗时的，而且在许多情况下是不可能的。对于那些程序、文档、税务记录、客户文件、数据库、营销计划或其他数据永远消失的人来说，后果可能是灾难性的。虽然文件系统不能提供任何保护，防止设备和介质的物理破坏，但它可以帮助保护信息，非常简单——进行备份，但这并不像听起来那么简单。

大多数人认为备份文件是不值得花时间和精力的，直到有一天他们的磁盘突然损坏，这时他们中的大多数人都经历了一次致命的转换。然而，公司（通常）非常了解其数据的价值，通常每天至少备份一次，通常备份到磁带。现代磁带可容纳数百GB的容量，每GB成本为几美分。然而，备份并不像听起来那么简单，所以我们将在下面研究一些相关问题。磁带备份通常用于处理以下两个潜在问题之一：

1、从灾难中恢复。

2、从愚蠢中恢复过来。

第一种是在磁盘崩溃、火灾、洪水或其他自然灾害后让计算机重新运行。实际上，这些事情并不经常发生，这就是为什么许多人不愿意为备份而烦恼。

第二个原因是用户经常不小心删除了以后再次需要的文件。这个问题经常发生，当一个文件在Windows中被“删除”时，它根本不会被删除，只是被移动到一个特殊的目录，即回收站，这样它就可以很容易地被提取出来并在以后恢复。备份进一步遵循了这一原则，允许从旧备份磁带恢复几天甚至几周前删除的文件。

备份需要很长时间，并且占用大量空间，因此高效、方便地进行备份非常重要。这些考虑提出了以下问题。

首先，应该备份整个文件系统还是只备份其中的一部分？在许多安装中，可执行（二进制）程序保存在文件系统树的有限部分中。如果可以从制造商网站或安装DVD重新安装这些文件，则无需备份这些文件。此外，大多数系统都有一个临时文件目录，通常也没有理由支持它。在UNIX中，所有特殊文件（I/O设备）都保存在目录/dev中。不仅不需要备份这个目录，而且非常危险，因为如果备份程序试图读取每个目录直到完成，它将永远挂起。简而言之，通常只备份特定目录和其中的所有内容，而不是备份整个文件系统。

第二，备份自上次备份以来未更改的文件是浪费的，于是有了增量转储（incremental dumps）的想法。增量转储的最简单形式是定期进行完整转储（备份），例如每周或每月进行一次，并且每天只转储自上次完全转储以来修改过的文件。更好的方法是只转储自上次转储以来发生更改的文件。虽然此方案将转储时间减至最少，但它使恢复更加复杂，因为首先必须恢复最近的完整转储，然后是按相反顺序的所有增量转储。为了便于恢复，通常使用更复杂的增量转储方案。

第三，由于通常会转储大量数据，因此最好在将数据写入磁带之前对其进行压缩。然而，对于许多压缩算法，备份磁带上的一个坏点可能会破坏解压缩算法，使整个文件甚至整个磁带都无法读取。因此，必须仔细考虑压缩备份流的决定。

第四，很难在活动文件系统上执行备份。如果在转储过程中添加、删除和修改文件和目录，则产生的转储可能不一致。然而，由于进行转储可能需要数小时，因此可能需要让系统在晚上的大部分时间离线以进行备份，这并不总是可以接受的。为此，设计了一些算法，通过复制关键数据结构来快速快照文件系统状态，然后要求将来更改文件和目录以复制块，而不是就地更新块（Hutchinson等人，1999）。通过这种方式，文件系统在快照时被有效地冻结，因此可以在以后空闲时进行备份。

第五，也是最后一点，备份会给组织带来许多非技术性问题。如果系统管理员把所有的备份磁盘或磁带放在办公室里，并且在他走下大厅去喝咖啡的时候让它敞开着，没有人看守，那么世界上最好的在线安全系统可能是无用的。间谍所要做的就是闯进来一秒钟，把一张小小的磁盘或磁带放在口袋里，然后兴高采烈地溜走。此外，如果烧毁计算机的火也烧毁了所有备份磁盘，那么每天备份也没有什么用处。因此，备份磁盘应该放在异地，但这会带来更多的安全风险（因为现在必须保护两个站点）。下面我们将讨论只有文件系统备份涉及的技术问题。

可以使用两种策略将磁盘转储到备份磁盘：物理转储或逻辑转储。

物理转储从磁盘的块0开始，按顺序将所有磁盘块写入输出磁盘，并在复制完最后一个磁盘块后停止。这样一个程序非常简单，它可能100%没有bug，可能是任何其他有用的程序都无法做到的。

尽管如此，还是值得对物理转储发表几点意见。首先，备份未使用的磁盘块没有任何价值。如果转储程序可以访问空闲块数据结构，则可以避免转储未使用的块。但是，跳过未使用的块需要在块（或等效块）前面写入每个块的编号，因为备份中的块k不再是磁盘上的块k。

第二个担忧是转储坏块。几乎不可能制造出没有任何缺陷的大型磁盘，总是存在一些坏块。有时，当完成低级格式化时，会检测到坏块，并将其标记为坏块，然后由每个磁道末端为此类紧急情况保留的备用块替换。在许多情况下，磁盘控制器在操作系统甚至不知道的情况下透明地处理坏块替换。

然而，有时块在格式化后会变差，在这种情况下，操作系统最终会检测到它们。通常，它通过创建一个包含所有坏块的“文件”来解决这个问题，只是为了确保它们不会出现在空闲块池中，也不会被分配。不用说，这个文件完全不可读。

如果所有坏块都被磁盘控制器重新映射，并像刚才描述的那样从操作系统中隐藏，那么物理转储可以正常工作。另一方面，如果它们对操作系统可见，并且保存在一个或多个坏块文件或位图中，那么物理转储程序必须能够访问这些信息，并避免转储这些信息，以防止在尝试备份坏块文件时出现无休止的磁盘读取错误。

Windows系统具有在还原时不需要的分页和休眠文件，因此不应首先备份这些文件。特定系统还可能有其他不应备份的内部文件，因此转储程序需要知道这些文件。

物理转储的主要优点是简单和速度快（基本上可以以磁盘的速度运行）。主要缺点是无法跳过选定的目录，进行增量转储，以及根据请求恢复单个文件。由于这些原因，大多数安装都会进行逻辑转储。

逻辑转储从一个或多个指定目录开始，并递归转储在其中找到的自给定基准日期以来发生更改的所有文件和目录（例如，增量转储的上次备份或完整转储的系统安装）。因此，在逻辑转储中，转储磁盘会获得一系列经过仔细识别的目录和文件，这使得根据请求恢复特定文件或目录变得很容易。

由于逻辑转储是最常见的形式，让我们使用下图中的示例来详细检查一种常见算法。大多数UNIX系统都使用此算法。在图中，我们看到一个包含目录（正方形）和文件（圆形）的文件树。阴影项目自基准日期以来已被修改，因此需要转储。无阴影的不需要转储。

要转储的文件系统。正方形是目录，圆形是文件。自上次转储以来，阴影项目已被修改。每个目录和文件都按其i节点编号进行标记。

由于两个原因，此算法还将位于修改文件或目录路径上的所有目录（即使是未修改的目录）转储到修改后的文件或目录。第一个原因是可以将转储的文件和目录恢复到另一台计算机上的新文件系统。这样，转储和恢复程序可以用于在计算机之间传输整个文件系统。

将未修改的目录转储到修改过的文件上的第二个原因是，可以增量恢复单个文件（可能是为了处理愚蠢的恢复）。假设周日晚上进行了完整文件系统转储，周一晚上进行了增量转储。星期二，目录/usr/jhs/proj/nr3及其下的所有目录和文件将被删除。星期三早上，假设用户希望恢复文件/usr/jhs/proj/nr3/plans/summary。但是，不可能只恢复文件摘要，因为没有放置它的位置。必须首先恢复目录nr3和计划。要获得其所有者、模式、时间等信息，即使这些目录自上次完全转储后未被修改，也必须存在于转储磁盘上。

转储算法维护由i节点编号索引的位图，每个i节点有几个位。随着算法的进行，位将在此映射中设置和清除。该算法分四个阶段运行。阶段1从起始目录（本例中的根目录）开始，并检查其中的所有条目。对于每个修改过的文件，其i节点都标记在位图中。每个目录也被标记（无论是否被修改），然后递归检查。

在第1阶段结束时，所有修改的文件和所有目录都已标记在位图中，如下图（a）所示（通过阴影）。阶段2在概念上再次递归遍历树，取消标记任何目录中或目录下没有修改过的文件或目录。此阶段将留下位图，如（b）所示。请注意，目录10、11、14、27、29和30现在没有标记，因为它们下面没有任何修改过的内容。他们不会被抛弃。相比之下，目录5和6将被转储，即使它们本身没有被修改，因为需要它们来将今天的更改恢复到新机器。为了提高效率，阶段1和阶段2可以合并在一个树行走中。

此时，我们知道必须转储哪些目录和文件，如（b）中标记的。阶段3包括按数字顺序扫描i节点并转储所有标记为转储的目录。如（c）所示。每个目录都以目录的属性（所有者、时间等）为前缀，以便可以恢复它们。最后，在第4阶段，（d）中标记的文件也被转储，再次以其属性作为前缀。这便完成了转储。

逻辑转储算法使用的位图。

从转储磁盘恢复文件系统非常简单。首先，在磁盘上创建一个空文件系统，然后恢复最近的完整转储。由于目录首先出现在转储磁盘上，因此它们都会首先被还原，从而提供文件系统的框架。然后恢复文件本身，然后重复此过程，在完全转储之后进行第一次增量转储，然后进行下一次，依此类推。

虽然逻辑转储很简单，但有一些棘手的问题。首先，由于空闲块列表不是一个文件，因此它不会被转储，因此在恢复所有转储之后，必须从头重新构建它。这样做始终是可能的，因为空闲块集只是包含在所有合并文件中的块集的补充。

另一个问题是链接。如果一个文件链接到两个或多个目录，那么只恢复一次该文件，并且所有指向该文件的目录都会恢复，这一点很重要。

另一个问题是UNIX文件可能包含漏洞。合法的做法是打开一个文件，写入几个字节，然后查找到远处的文件偏移量，再写入几个字节。中间的块不是文件的一部分，不应转储，也不得还原。核心文件在数据段和堆栈之间通常有数百兆字节的空间。如果处理不当，每个恢复的核心文件将用零填充该区域，因此大小与虚拟地址空间相同（例如，232232字节，或者更糟的是，264264字节）。

最后，特殊文件、命名管道等（任何不是真实文件的文件）都不应该转储，无论它们可能出现在哪个目录中（它们不需要局限于/dev）。

• 文件系统一致性

另一个可靠性问题是文件系统一致性。许多文件系统读取块，修改它们，然后将它们写出。如果在写出所有修改的块之前系统崩溃，文件系统可能会处于不一致的状态。如果某些尚未写出的块是i-node块、目录块或包含空闲列表的块，则此问题尤其重要。

为了处理不一致的文件系统，大多数计算机都有一个实用程序来检查文件系统的一致性。例如，UNIX具有fsck，Windows有sfc（和其他）。此实用程序可以在系统启动时运行，特别是在崩溃后。

下面的描述说明了fsck的工作原理。Sfc有些不同，因为它在不同的文件系统上工作，但使用文件系统固有冗余修复它的一般原则仍然有效。所有文件系统检查器都独立于其他文件系统（磁盘分区）来验证每个文件系统。可以进行两种一致性检查：块和文件。为了检查块一致性，程序构建了两个表，每个表包含每个块的计数器，最初设置为0。第一个表中的计数器跟踪每个块在文件中出现的次数；第二个表中的计数器记录每个块出现在空闲列表（或空闲块的位图）中的频率。

然后，程序使用原始设备读取所有i节点，该设备忽略文件结构，只返回从0开始的所有磁盘块。从索引节点开始，可以构建相应文件中使用的所有块编号的列表。读取每个块编号时，第一个表中的计数器递增。然后，程序检查空闲列表或位图以查找所有未使用的块。自由列表中每个块的出现都会导致其在第二个表中的计数器递增。

如果文件系统是一致的，那么每个块在第一个表或第二个表中都会有一个1，如系统（a）所示。然而，由于碰撞，表格可能类似于图（b），其中两个表格中都没有出现方框2。它将被报告为丢失的块。虽然丢失的块不会造成真正的危害，但它们会浪费空间，从而降低磁盘的容量。丢失块的解决方案很简单：文件系统检查器只是将它们添加到空闲列表中。

另一种可能发生的情况如图（c）所示，有一个编号为4的块，在空闲列表中出现了两次。（只有当空闲列表确实是一个列表时，才会出现重复；使用位图是不可能的。）解决方案也很简单：重建空闲列表。

可能发生的最坏情况是，同一数据块存在于两个或多个文件中，如图（d）和块5所示。如果删除其中任何一个文件，块5将被放在空闲列表中，导致同一块同时处于使用和空闲状态。如果两个文件都被删除，则块将被放入空闲列表两次。

文件系统状态。（a） 一致性。（b） 丢失块。（c） 空闲列表中存在重复块。（d） 重复的数据块。

文件系统检查器要采取的适当操作是分配一个空闲块，将块5的内容复制到其中，然后将副本插入其中一个文件。通过这种方式，文件的信息内容保持不变（尽管几乎可以肯定是乱码），但文件系统结构至少保持一致。

应报告错误，以便用户检查损坏情况。除了检查每个块是否都得到了正确的解释之外，文件系统检查器还检查目录系统。它也使用计数器表，但这些计数器是按文件而不是按块计算的。它从根目录开始，递归地下降树，检查文件系统中的每个目录。对于每个目录中的每个i节点，它会为该文件的使用计数增加一个计数器。请记住，由于硬链接，文件可能会出现在两个或多个目录中。符号链接不计数，也不会导致目标文件的计数器递增。

当检查程序全部完成后，它会有一个列表，由i-node编号索引，告诉每个文件包含多少个目录。然后，它将这些数字与存储在i节点本身中的链接计数进行比较。创建文件时，这些计数从1开始，并在每次（硬）链接到文件时递增。在一致的文件系统中，这两种计数将一致。但是，可能会出现两种错误：i节点中的链接计数可能过高，也可能过低。

如果链接计数大于目录条目的数量，那么即使从目录中删除了所有文件，该计数仍将不为零，i-node也不会被删除。此错误并不严重，但如果文件不在任何目录中，则会浪费磁盘空间。应该通过将i节点中的链接计数设置为正确的值来修复此问题。

另一个错误可能是灾难性的。如果两个目录条目链接到一个文件，但i-node表示只有一个，则删除任一目录条目时，i-node计数将变为零。当i节点计数为零时，文件系统会将其标记为未使用，并释放其所有块。此操作将导致其中一个目录现在指向未使用的i-node，其块可能很快会分配给其他文件。同样，解决方案只是将i-node中的链接计数强制为目录条目的实际数量。

出于效率原因，这两种操作（检查块和检查目录）通常是集成在一起的（即，只需要在i节点上进行一次传递）。也可以进行其他检查。例如，目录具有明确的格式，其中包含i节点编号和ASCII名称。如果i节点数大于磁盘上的i节点数，则说明目录已损坏。

此外，每个i-node都有一个模式，其中一些是合法的，但很奇怪，例如0007，它允许所有者及其组根本没有访问权限，但允许外部人员读取、写入和执行文件。至少报告给外部人比所有者更多权利的文件可能会有用。例如，条目超过1000条的目录也是可疑的。位于用户目录中但由超级用户拥有并启用SETUID位的文件是潜在的安全问题，因为此类文件在任何用户执行时都会获得超级用户的权限。只要稍加努力，人们就可以列出一份相当长的技术上合法但仍有可能值得报道的特殊情况的清单。

• 文件系统性能

访问磁盘比访问内存慢得多，读取32位内存字可能需要10纳秒，从硬盘读取可能会以100 MB/秒的速度进行（是每32位字读取速度的四倍），但除此之外，还必须增加5–10毫秒以查找磁道，然后等待所需的扇区到达读取头下方。如果只需要一个字，那么内存访问的速度大约是磁盘访问的一百万倍。由于访问时间的差异，许多文件系统都设计了各种优化以提高性能。下面介绍三种。

第一种提升文件系统性能的方法是缓存。

用于减少磁盘访问的最常见技术是块缓存或缓冲区缓存。在这种情况下，缓存是逻辑上属于磁盘但出于性能原因保留在内存中的块的集合。

可以使用各种算法来管理缓存，但常见的算法是检查所有读取请求，以查看所需的块是否在缓存中。如果是，则无需磁盘访问即可满足读取请求。如果块不在缓存中，则首先将其读入缓存，然后将其复制到需要的位置。缓存可以满足对同一块的后续请求。

高速缓存的操作如下图所示。由于高速缓存中有许多（通常是数千）块，因此需要某种方法来快速确定给定块是否存在。通常的方法是散列设备和磁盘地址，并在散列表中查找结果。具有相同哈希值的所有块都链接在一个链表上，以便可以跟踪冲突链。

缓冲区缓存数据结构。

IO缓冲方案（输入）。

当一个块必须加载到一个完全缓存中时，必须删除一些块（如果它在引入后被修改，则必须重写到磁盘）。这种情况非常类似于分页，所有常用页面替换算法，如FIFO、二次机会和LRU都适用。分页和缓存之间的一个令人愉快的区别是缓存引用相对较少，因此可以使用链接列表将所有块保持在精确的LRU顺序。

在上图中，我们可以看到，除了从哈希表开始的冲突链之外，还有一个按使用顺序遍历所有块的双向列表，最近最少使用的块位于列表的前面，最近使用的块在末尾。当一个块被引用时，可以将其从双向列表中的位置删除并放在末尾。通过这种方式，可以维持精确的LRU顺序。

不幸的是，这里有一个陷阱。既然我们有可能实现精确LRU的情况，事实证明LRU是不可取的。这个问题与崩溃和文件系统一致性有关。如果将关键块（如i节点块）读入缓存并进行修改，但未重写到磁盘，则崩溃将使文件系统处于不一致状态。如果将i-node块放在LRU链的末端，它可能需要很长时间才能到达前端并被重写到磁盘。

此外，某些块（例如i节点块）很少在短间隔内被引用两次。这些考虑导致修改LRU方案，考虑了两个因素：

1、是否很快会再次需要该区块？

2、块对文件系统的一致性至关重要吗？

对于这两个问题，块可以分为类别，例如i节点块、间接块、目录块、完整数据块和部分完整数据块。很快，可能不再需要的块将放在LRU列表的前面，而不是后面，因此它们的缓冲区将被快速重用。可能很快会再次需要的块，例如正在写入的部分已满的块，位于列表的末尾，因此它们将保留很长时间。

第二个问题独立于第一个问题。如果块对文件系统一致性至关重要（基本上，除了数据块以外的所有内容），并且它已经被修改，则应立即将其写入磁盘，而不必考虑它放在LRU列表的哪一端。通过快速写入关键块，我们大大降低了崩溃破坏文件系统的可能性。

即使使用此措施来保持文件系统完整性不变，也不希望在将数据块写出来之前将其保存在缓存中的时间过长。想想使用个人电脑写书的人的困境。即使我们的编写器定期告诉编辑器将正在编辑的文件写入磁盘，也很有可能所有内容都仍在缓存中，而磁盘上什么也没有。如果系统崩溃，文件系统结构将不会损坏，但一整天的工作将丢失。

系统采用两种方法来处理它。UNIX的方法是使用系统调用sync，它将所有修改的块立即强制放到磁盘上。当系统启动时，一个程序（通常称为update）会在后台启动，在一个无休止的循环中发出同步调用，在调用之间休眠30秒。因此，由于崩溃，损失的工作时间不超过30秒。

虽然Windows现在有一个相当于同步的系统调用，称为Flush File Buffers，但过去它没有。相反，它有一种不同的策略，在某些方面比UNIX方法更好（在某些方面更糟）。它所做的是在每个修改过的块写入缓存后立即将其写入磁盘，所有修改过的块立即写回磁盘的缓存称为直写缓存，与非写缓存相比，它们需要更多的磁盘I/O。

当一个程序一次写入一个1-KB的块时，可以看出这两种方法之间的差异。UNIX将收集缓存中的所有字符，并每隔30秒或每当从缓存中删除块时将其写出一次。对于直写缓存，每个写入的字符都有一个磁盘访问权限。当然，大多数程序都进行内部缓冲，因此它们通常不会写入字符，而是在每个写入系统调用上写入一行或更大的单元。

缓存策略的这种差异导致的结果是，仅从UNIX系统中删除磁盘而不进行同步几乎总是会导致数据丢失，并且通常还会导致文件系统损坏。使用直写缓存不会出现问题。之所以选择这些不同的策略，是因为UNIX是在一个所有磁盘都是硬盘且不可移动的环境中开发的，而第一个Windows文件系统是从软盘世界开始的MS-DOS继承而来的。随着硬盘成为标准，UNIX方法以其更好的效率（但更差的可靠性）成为标准，现在在Windows上也用于硬盘。然而，如前所述，NTFS采取了其他措施（例如日志记录）来提高可靠性。

一些操作系统将缓冲区缓存与页面缓存集成在一起。当支持内存映射文件时，尤其有吸引力。如果一个文件映射到内存，那么它的一些页面可能在内存中，因为它们是按需分页的，这样的页面与缓冲区缓存中的文件块几乎没有区别。在这种情况下，可以以相同的方式处理它们，对文件块和页面都使用一个缓存。

第二种提升文件系统性能的方法是块预读取（Block Read Ahead）。

提高感知文件系统性能的第二种技术是，在需要块来提高命中率之前，尝试将块放入缓存。特别是，许多文件是按顺序读取的。当要求文件系统在文件中生成块k时，它会这样做，但当它完成后，它会在缓存中偷偷检查块k+1是否已经存在。如果不是，它会安排块k+1的读取，希望在需要时，它已经到达缓存。至少，它会在路上。

当然，这种预读策略只适用于实际按顺序读取的文件。如果一个文件正在被随机访问，那么预读取并没有帮助。事实上，它会将磁盘带宽读取捆绑在无用的块中，并从缓存中删除可能有用的块（如果这些块脏了，则可能会捆绑更多的磁盘带宽将其写回磁盘），会造成伤害。为了查看预读是否值得，文件系统可以跟踪每个打开的文件的访问模式。例如，与每个文件关联的位可以跟踪文件是处于“顺序访问模式”还是“随机访问模式”。最初，文件被赋予了怀疑的优势，并被置于顺序访问模式。然而，无论何时完成寻道，位都会被清除。如果再次开始顺序读取，则再次设置位。这样，文件系统就可以合理地猜测是否应该提前读取。如果偶尔出错，这不是灾难，只是浪费了一点点磁盘带宽。

第三种提升文件系统性能的方法是减少圆盘臂运动（Reducing Disk-Arm Motion）。

缓存和预读并不是提高文件系统性能的唯一方法。另一项重要的技术是通过将可能被依次接近的块放置在同一个圆柱体中，来减少磁盘臂的运动量。写入输出文件时，文件系统必须按需一次分配一个块。如果自由块记录在位图中，并且整个位图都在主内存中，那么选择一个尽可能接近前一个块的自由块就足够容易了。有了一个空闲列表（其中一部分位于磁盘上），很难将块紧密地分配在一起。

然而，即使有一个空闲列表，也可以进行一些块聚类。诀窍是不按块跟踪磁盘存储，而是按连续块的组跟踪。如果所有扇区都由512字节组成，则系统可以使用1-KB的块（2个扇区），但以2个块（4个扇区）为单位分配磁盘存储。与拥有2 KB的磁盘块，因为缓存仍将使用1 KB的块，磁盘传输仍将为1 KB，但在空闲的系统上顺序读取文件将减少两倍的寻道数，从而大大提高性能。同一主题的变体是考虑旋转定位，分配块时，系统会尝试将连续块放置在同一圆柱体中的文件中。

在使用i节点或类似节点的系统中，另一个性能瓶颈是，即使读取一个短文件也需要两次磁盘访问：一次用于i节点，另一次用于块。通常的i节点布置如下图（a）所示。这里所有的i节点都靠近磁盘的起点，因此inode和它的块之间的平均距离将是柱面数的一半，需要长时间查找。

一个简单的性能改进是将i节点放在磁盘的中间，而不是开始，从而将i节点和第一个块之间的平均寻道减少了两倍。下图（b）所示的另一个想法是将磁盘划分为圆柱体组，每个圆柱体组都有自己的i节点、块和空闲列表。创建新文件时，可以选择任何i-node，但会尝试在与i-node相同的圆柱体组中查找块。如果没有可用的圆柱体组，则使用附近圆柱体组中的圆柱体组。

（a） 位于磁盘开头的I节点。（b） 磁盘分为圆柱体组，每个圆柱体组都有自己的块和i节点。

当然，只有当磁盘具有盘臂运动和旋转时间时，它们才相关。越来越多的计算机配备了固态磁盘（SSD），这些固态磁盘没有任何移动部件。对于这些建立在与闪存卡相同技术上的磁盘，随机访问与顺序访问一样快，传统磁盘的许多问题都消失了。不幸的是，出现了新的问题。例如，SSD在读取、写入和删除时具有特殊的属性。特别是，每个块只能写入有限的次数，因此要非常小心地将磨损均匀地分布在磁盘上。

18.11.3.9 磁盘碎片整理

当操作系统最初安装时，它需要的程序和文件从磁盘的开头开始连续安装，每个程序和文件都直接跟在前一个程序和文件之后。所有可用磁盘空间都位于安装文件之后的单个连续单元中。然而，随着时间的推移，文件会被创建和删除，通常磁盘会严重碎片化，到处都是文件和漏洞。因此，当创建新文件时，用于该文件的块可能会分散在整个磁盘上，从而导致性能低下。

通过移动文件使其连续，并将所有（或至少大部分）可用空间放在磁盘上的一个或多个大的连续区域中，可以恢复性能。Windows有一个程序，即碎片整理，它正是这样做的。Windows用户应该定期运行它，但SSD除外。

碎片整理在分区末尾的相邻区域中有大量可用空间的文件系统上效果更好。此空间允许碎片整理程序选择分区开始处附近的碎片文件，并将其所有块复制到可用空间。这样做可以在分区开始处附近释放一个连续的空间块，原始文件或其他文件可以连续放置在其中。然后可以使用下一块磁盘空间等重复该过程。

无法移动某些文件，包括分页文件、休眠文件和日志记录，因为执行此操作所需的管理工作带来的麻烦比实际需要的多。在某些系统中，这些区域是固定大小的连续区域，因此不必进行碎片整理。他们缺乏移动性的一个问题是，他们碰巧在分区的末尾，用户希望减小分区大小。解决此问题的唯一方法是完全删除它们，调整分区大小，然后在以后重新创建它们。

由于磁盘块的选择方式，Linux文件系统（尤其是ext2和ext3）通常比Windows系统受到的碎片整理更少，因此很少需要手动碎片整理。此外，SSD实际上根本不会受到碎片的影响。事实上，对SSD进行碎片整理会适得其反。不仅性能没有提高，SSD也会磨损，因此对它们进行碎片整理只会缩短它们的寿命。

18.11.3.10 文件系统案例

常见的文件系统案例有MS-DOS文件系统、UNIX V7文件系统、CD-ROM文件系统。

甚至UNIX的早期版本也有一个相当复杂的多用户文件系统，因为它是从MULTICS派生而来的。下面我们将讨论V7文件系统，它是使UNIX出名的PDP-11的文件系统。

文件系统的形式是从根目录开始的树，添加了链接，形成了一个有向非循环图（DAG）。文件名最多可以包含14个字符，并且可以包含除/（因为它是路径中组件之间的分隔符）和NUL（因为它用于填充小于14个字符的名称）之外的任何ASCII字符，NUL的数值为0。

UNIX目录条目包含该目录中每个文件的一个条目。每个条目都非常简单，因为UNIX使用i-node方案。目录条目仅包含两个字段：文件名（14字节）和该文件的i-noder数（2字节），如下图所示。这些参数将每个文件系统的文件数限制为64K。

与i节点类似，UNIX i节点包含一些属性。这些属性包含文件大小、三次（创建、上次访问和上次修改）、所有者、组、保护信息以及指向i节点的目录条目数。由于链接，需要后一个字段。每当建立到i节点的新链接时，i节点中的计数就会增加。删除链接时，计数将递减。当它达到0时，将回收i节点，并将磁盘块放回可用列表中。

为了处理非常大的文件，可以跟踪磁盘块。前10个磁盘地址存储在i节点本身，因此对于小文件，所有必要的信息都在i节点中，当文件打开时，这些信息会从磁盘提取到主内存中。对于较大的文件，i节点中的地址之一是称为单个间接块的磁盘块的地址。此块包含其他磁盘地址。如果仍然不够，则i节点中的另一个地址（称为双间接块）包含包含单个间接块列表的块的地址。每个间接块都指向几百个数据块。如果还不够，也可以使用三重间接块。全图如下所示。

打开文件时，文件系统必须使用提供的文件名并定位其磁盘块。让我们考虑如何查找路径名/usr/ast/mbox。我们将以UNIX为例，但算法对于所有分层目录系统基本相同。首先，文件系统定位根目录。在UNIX中，其i节点位于磁盘上的固定位置。从这个i-node中，它可以找到根目录，可以位于磁盘上的任何位置，也可以是块1。

之后，它读取根目录并在根目录中查找路径的第一个组件usr，以查找文件/usr的i-node编号。根据i节点的编号定位i节点很简单，因为每个节点在磁盘上都有一个固定的位置。从这个i-node，系统找到/usr的目录，并在其中查找下一个组件ast。当它找到ast的条目时，它拥有目录/usr/ast的i-node。从这个i节点，它可以找到目录本身并查找mbox。然后将此文件的i节点读入内存并保存在内存中，直到文件关闭。查找过程如下图所示。

相对路径名的查找方式与绝对路径名相同，只从工作目录开始，而不是从根目录开始。每个目录都有.和..的条目，它们在创建目录时放在那里。条目.具有当前目录的i-node编号，条目..具有父目录的i-node编号。因此，查找../dick/prog的过程。c只需在工作目录中查找..，找到父目录的i-node编号，然后在该目录中搜索dick。处理这些名称不需要特殊的机制，就目录系统而言，它们只是普通的ASCII字符串，与其他名称一样，唯一的技巧是根目录中的..指向自身。

下图是Linux虚拟文件系统上下文：

下图是Linux虚拟文件系统概念：

18.11.4 I/O

除了提供诸如进程、地址空间和文件等抽象概念外，操作系统还控制计算机的所有I/O（输入/输出）设备。它必须向设备发出命令、捕获中断和处理错误，还应该在设备和系统其余部分之间提供一个简单易用的接口。在可能的情况下，所有设备的接口应相同（设备独立性）。I/O代码占整个操作系统的很大一部分。

18.11.4.1 I/O硬件原理

不同的人以不同的方式看待I/O硬件。电气工程师从芯片、电线、电源、电机以及构成硬件的所有其他物理组件的角度来看待它，程序员查看呈现给软件的界面—硬件接受的命令、执行的功能以及可以报告的错误。我们应该关注的是I/O设备的编程，而不是设计、构建或维护它们，所以我们的兴趣在于硬件是如何编程的，而不是它内部的工作方式。然而，许多I/O设备的编程通常与其内部操作密切相关。在接下来的内容中，我们将提供与编程相关的I/O硬件的一般背景知识。

I/O设备可以大致分为两类：块设备（block device）和字符设备（character device）。块设备是将信息存储在固定大小的块中的设备，每个块都有自己的地址，公共块大小从512字节到65536字节不等，所有传输都以一个或多个完整（连续）块为单位。块设备的基本特性是可以独立于所有其他块读取或写入每个块，硬盘、蓝光光盘和USB磁盘是常见的块设备。

如果仔细观察，可以块寻址的设备和不可以块寻址设备之间的边界没有很好地定义。每个人都同意磁盘是一个块寻址设备，因为无论臂当前在哪里，总是可以找到另一个圆柱体，然后等待所需的块在头部下方旋转。现在，考虑一下仍在使用的老式磁带机，有时用于进行磁盘备份（因为磁带很便宜）。磁带包含一系列块，如果磁带驱动器收到读取块N的命令，它总是可以倒带并向前走，直到到达块N为止。此操作类似于磁盘执行查找，只是需要更长的时间。此外，在磁带中间重写一个块也许可能，也许不可能。即使有可能将磁带用作随机访问块设备，也在一定程度上拓展了这一点，但它们通常不是这样使用的。

另一种类型的I/O设备是字符设备。字符设备发送或接受字符流，而不考虑任何块结构。它不可寻址，并且没有任何寻道操作。打印机、网络接口、鼠标（用于指向）、鼠标（用于心理实验室实验）以及大多数其他非磁盘设备都可以被视为字符设备。

这个分类方案并不完美，有些设备不适合。例如，时钟不可块寻址，也不生成或接受字符流，所做的只是以明确的间隔引起中断。内存映射屏幕也不适合该模型，触摸屏也不例外。尽管如此，块和字符设备的模型足够通用，可以用作使某些处理I/O设备的操作系统软件独立的基础。例如，文件系统只处理抽象块设备，而将依赖设备的部分留给较低级别的软件。

I/O设备的速度范围很广，给软件带来了相当大的压力，使其在数据速率上的性能超过许多数量级。下表显示了一些常见设备的数据速率。随着时间的推移，这些设备大多会变得更快。

以下是常见的几种IO组织模型：

设备控制器

I/O单元通常由机械部件和电子部件组成。可以将这两部分分开，以提供更模块化和通用的设计。电子元件称为设备控制器或适配器，在个人计算机上，它通常采用主板上的芯片或可插入（PCIe）扩展插槽的印刷电路卡的形式。机械部件是设备本身。

控制器卡上通常有一个连接器，可以插入通向设备本身的电缆。许多控制器可以处理两个、四个甚至八个相同的设备。如果控制器和设备之间的接口是标准接口，可以是ANSI、IEEE或ISO官方标准，也可以是事实标准，那么公司可以制造适合该接口的控制器或设备。例如，许多公司都生产与SATA、SCSI、USB、Thunderbolt或FireWire（IEEE 1394）接口匹配的磁盘驱动器。

控制器和设备之间的接口通常是非常低级别的接口。例如，一个磁盘可以格式化为2000000个扇区，每个磁道512字节。然而，从驱动器中实际出来的是一个串行位流，从前导码开始，然后是扇区中的4096位，最后是校验和，即ECC（纠错码）。在格式化磁盘时写入前导码，前导码包含柱面和扇区编号、扇区大小、类似数据以及同步信息。

控制器的工作是将串行位流转换为字节块，并执行任何必要的错误纠正，字节块通常首先在控制器内的缓冲区中逐位组装，在校验和经过验证并且块被声明为无错误后，可以将其复制到主内存。

LCD显示器的控制器也可以作为一个同样低电平的位串行设备工作。它从内存中读取包含要显示字符的字节，并生成信号来修改相应像素的背光偏振，以便将其写入屏幕。如果没有显示控制器，操作系统程序员就必须对所有像素的电场进行显式编程。使用控制器，操作系统用一些参数初始化控制器，例如每行的字符或像素数以及每屏的行数，并让控制器负责实际驱动电场。

在很短的时间内，LCD屏幕已经完全取代了旧的CRT（阴极射线管）显示器。CRT显示器将电子束发射到荧光屏上，利用磁场，该系统能够弯曲光束并在屏幕上绘制像素。与LCD屏幕相比，CRT显示器体积庞大、耗电量大且易碎。此外，今天（视网膜）LCD屏幕的分辨率非常好，人眼无法分辨单个像素。今天很难想象，过去的笔记本电脑配备了一个小型CRT屏幕，使其深度超过20厘米，重量约为12公斤。

内存映射I/O

每个控制器都有几个寄存器，用于与CPU通信。通过写入这些寄存器，操作系统可以命令设备发送数据、接收数据、打开或关闭自身，或者执行某些操作。通过读取这些寄存器，操作系统可以了解设备的状态，是否准备接受新命令，等等。

除了控制寄存器外，许多设备还具有操作系统可以读取和写入的数据缓冲区。例如，计算机在屏幕上显示像素的一种常见方式是有一个视频RAM，它基本上只是一个数据缓冲区，可供程序或操作系统写入。

因此，出现了CPU如何与控制寄存器以及设备数据缓冲区通信的问题。有两种选择。在第一种方法中，每个控制寄存器被分配一个I/O端口号，一个8位或16位整数。所有I/O端口的集合构成I/O端口空间，该空间受到保护，因此普通用户程序无法访问它（只有操作系统才能访问）。使用特殊的I/O指令，例如：

IN REG, PORT,

CPU可以读取控制寄存器PORT并将结果存储在CPU寄存器REG中。类似地，使用：

OUT PORT, REG

CPU可以将REG的内容写入控制寄存器。大多数早期的计算机，包括几乎所有的大型机，如IBM360及其所有后续产品，都是这样工作的。在此方案中，内存和I/O的地址空间不同，如下图（a）所示。指令IN R0, 4和MOV R0, 4在这个设计中完全不同。前者读取I/O端口4的内容并将其放入R0，而后者读取内存字4的内容，并将其置于R0。这些示例中的4表示不同且不相关的地址空间。

（a） 分开I/O和内存空间。（b） 内存映射I/O。（c） 混合。

PDP-11引入的第二种方法是将所有控制寄存器映射到内存空间，如上图（b）所示。每个控制寄存器都分配了一个唯一的存储器地址，但没有分配存储器。该系统称为内存映射I/O（Memory-mapped I/O）。在大多数系统中，分配的地址位于或接近地址空间的顶部。上图（c）显示了一种混合方案，该方案具有内存映射I/O数据缓冲区和用于控制寄存器的单独I/O端口。x86使用此体系结构，地址为640K到1M− 除了I/O端口0到64K之外，1是为IBM PC兼容机中的设备数据缓冲区保留的− 1.

这些计划实际上是如何运作的？在所有情况下，当CPU想要从内存或I/O端口读取一个字时，它将所需的地址放在总线的地址线上，然后在总线的控制线上断言一个read信号，第二条信号线用于判断是否需要I/O空间或内存空间。如果是内存空间，内存会响应请求。如果是I/O空间，I/O设备将响应请求。如果只有内存空间（上图（b）），每个内存模块和每个I/O设备都会将地址线与其服务的地址范围进行比较。如果地址在其范围内，它将响应请求。由于从未向内存和I/O设备分配地址，因此没有歧义和冲突。

这两种控制器寻址方案有不同的优缺点。先描述内存映射I/O的优点：

• 首先，如果读写设备控制寄存器需要特殊的I/O指令，那么访问它们需要使用汇编代码，因为无法在C或C++中执行IN或OUT指令，调用这样的过程会增加控制I/O的开销。与此相反，对于内存映射I/O，设备控制寄存器只是内存中的变量，可以用与任何其他变量相同的方式在C中寻址。因此，使用内存映射I/O，I/O设备驱动程序可以完全用C编写。如果没有内存映射I/O的话，就需要一些汇编代码。

• 其次，对于内存映射I/O，不需要特殊的保护机制来阻止用户进程执行I/O。操作系统所要做的就是避免将包含控制寄存器的那部分地址空间放在任何用户的虚拟地址空间中。更好的是，如果每个设备的控制寄存器都位于地址空间的不同页面上，操作系统可以通过简单地将所需页面包含在其页面表中，让用户控制特定设备，而不是其他设备。这样的方案可以将不同的设备驱动程序放置在不同的地址空间中，不仅可以减小内核大小，还可以防止一个驱动程序干扰其他驱动程序。

• 第三，使用内存映射I/O，可以引用内存的每条指令也可以引用控制寄存器。例如，如果有一条指令TEST测试0的内存字，它也可以用于测试0的控制寄存器，可能是设备空闲并可以接受新命令的信号。汇编语言代码可能如下所示：

  LOOP: TEST PORT 4  // check if por t 4 is 0
        BEQ READY    // if it is 0, go to ready
        BRANCH LOOP  // otherwise, continue testing
  READY:
  

  如果不存在内存映射I/O，则必须首先将控制寄存器读入CPU，然后进行测试，便需要两条指令，而不是一条。在上述循环的情况下，必须添加第四条指令，略微降低检测空闲设备的响应速度。

在计算机设计中，实际上一切都涉及权衡，这里也是如此。内存映射I/O也有其缺点：

• 首先，现在大多数计算机都有某种形式的内存字缓存。缓存设备控制寄存器将是灾难性的。考虑上面给出的存在缓存的汇编代码循环。对PORT 4的第一个引用将导致它被缓存。后续引用只会从缓存中获取值，甚至不会询问设备。然后当设备最终准备就绪时，软件将无法发现。相反，循环将永远持续下去。

  为了防止内存映射I/O出现这种情况，硬件必须能够选择性地禁用缓存，例如，以每页为基础。此功能增加了硬件和操作系统的额外复杂性，后者必须管理选择性缓存。

• 其次，如果只有一个地址空间，那么所有内存模块和所有I/O设备都必须检查所有内存引用，以查看要响应的内存引用。如果计算机只有一条总线，如下图（a）所示，让每个人都查看每个地址是很简单的。

  

  然而，现代个人计算机的趋势是拥有专用的高速内存总线，如上图（b）所示。该总线是为优化内存性能而定制的，不会因为I/O设备速度慢而有所妥协。x86系统可以有多条总线（内存、PCIe、SCSI和USB）。

  在内存映射机器上使用单独的内存总线的问题是，I/O设备在内存总线上经过时无法看到内存地址，因此无法对其作出响应。同样，必须采取特殊措施使内存映射I/O在具有多条总线的系统上工作。一种可能是首先将所有内存引用发送到内存。如果内存没有响应，则CPU尝试其他总线。这种设计可以工作，但需要额外的硬件复杂性。

  第二种可能的设计是在内存总线上放置一个监听设备，将所有呈现的地址传递给潜在感兴趣的I/O设备。这里的问题是I/O设备可能无法以内存所能达到的速度处理请求。

  第三种可能的设计，是在内存控制器中过滤地址。在这种情况下，内存控制器芯片包含在引导时预加载的范围寄存器。例如，640K到1M− 1可以标记为非内存范围。属于标记为非内存范围之一的地址被转发到设备而不是内存。此方案的缺点是需要在引导时确定哪些内存地址不是真正的内存地址。因此，每个方案都有支持和反对的理由，所以妥协和权衡是不可避免的。

直接内存访问

无论CPU是否具有内存映射I/O，它都需要寻址设备控制器以与它们交换数据。CPU可以一次从I/O控制器请求一个字节的数据，但这样做会浪费CPU的时间，因此通常使用一种不同的方案，称为DMA（Direct Memory Access，直接内存访问）。为了简化解释，我们假设CPU通过连接CPU、内存和I/O设备的单个系统总线访问所有设备和内存，如下图所示。我们已经知道，现代系统中的实际组织更加复杂，但所有原理都是相同的。如果硬件有DMA控制器，操作系统只能使用DMA，而大多数系统都有。有时，该控制器集成到磁盘控制器和其他控制器中，但这种设计要求每个设备都有一个单独的DMA控制器。更常见的情况是，可以使用单个DMA控制器（例如，在主板上）来调节到多个设备的传输，通常是同时进行的。

无论DMA控制器位于何处，它都可以独立于CPU访问系统总线，如下图所示。它包含几个可由CPU写入和读取的寄存器，这些寄存器包括内存地址寄存器、字节计数寄存器和一个或多个控制寄存器，控制寄存器指定要使用的I/O端口、传输方向（从I/O设备读取或写入I/O设备）、传输单元（每次字节或每次字）以及一次突发传输的字节数。

为了解释DMA的工作原理，让我们先看看不使用DMA时磁盘读取是如何发生的。首先，磁盘控制器从驱动器逐位串行读取块（一个或多个扇区），直到整个块位于控制器的内部缓冲区中。接下来，它计算校验和以验证没有发生读取错误。然后控制器导致中断。当操作系统开始运行时，它可以通过执行循环，一次从控制器的缓冲区读取一个字节或一个字的磁盘块，每次迭代从控制器设备寄存器读取一个字符或字，并将其存储在主内存中。

DMA传输的操作。

使用DMA时，过程不同。首先，CPU通过设置其寄存器来编程DMA控制器，以便它知道要将什么传输到哪里（上图中的步骤1）。它还向磁盘控制器发出命令，告诉它将数据从磁盘读取到其内部缓冲区，并验证校验和。当有效数据在磁盘控制器的缓冲区中时，DMA可以开始。

DMA控制器通过总线向磁盘控制器发出读取请求来启动传输（步骤2）。这个读取请求看起来像任何其他读取请求，磁盘控制器不知道（或不关心）它是来自CPU还是来自DMA控制器。通常，要写入的内存地址位于总线的地址行上，因此当磁盘控制器从其内部缓冲区获取下一个字时，它知道将其写入何处。写入内存是另一个标准总线周期（步骤3）。当写入完成时，磁盘控制器也通过总线向DMA控制器发送确认信号（步骤4）。然后，DMA控制器增加要使用的内存地址，并减少字节计数。如果字节计数仍然大于0，则重复步骤2至4，直到计数达到0。此时，DMA控制器中断CPU，让它知道传输现在已完成。当操作系统启动时，不必将磁盘块复制到内存中，因为磁盘块已经在那里了。

DMA控制器的复杂程度差异很大。如上所述，最简单的方法一次处理一个传输。可以对更复杂的程序进行编程，以同时处理多个传输。此类控制器内部有多组寄存器，每个通道一组。CPU首先加载每组寄存器及其传输的相关参数。每次传输必须使用不同的设备控制器。在上图中的每个字被传输后（步骤2到4），DMA控制器决定下一个要服务的设备。它可能被设置为使用循环算法，或者它可能具有优先方案设计，以支持某些设备而不是其他设备。对不同设备控制器的多个请求可能会同时挂起，前提是有明确的方法区分确认。因此，总线上的不同确认线通常用于每个DMA信道。

许多总线可以在两种模式下运行：逐字模式和块模式。一些DMA控制器也可以在这两种模式中运行。在前一种模式中，DMA控制器请求传输一个字并获得它，如果CPU也需要总线，它必须等待。这种机制称为周期窃取（cycle stealing），因为设备控制器会潜入CPU，偶尔从CPU窃取总线周期，稍微延迟一点。在块模式下，DMA控制器告诉设备获取总线，发出一系列传输，然后释放总线。这种操作形式称为突发模式（burst mode）。它比周期窃取更有效，因为获取总线需要时间，并且可以以一条总线的价格传输多个单词。突发模式的缺点是，如果传输长突发，它会在相当长的一段时间内阻塞CPU和其他设备。

在我们讨论的模型中，有时称为飞行模式（fly-by mode），DMA控制器告诉设备控制器将数据直接传输到主存储器。一些DMA控制器使用的另一种模式是让设备控制器将Word发送到DMA控制器，然后DMA控制器发出第二个总线请求，将Word写入应该写入的位置。该方案要求每传输一个字都有额外的总线周期，但更灵活，因为它还可以执行设备到设备的复制，甚至内存到内存的复制（首先对内存进行读取，然后在不同地址对内存进行写入）。

大多数DMA控制器使用物理内存地址进行传输。使用物理地址需要操作系统将预期内存缓冲区的虚拟地址转换为物理地址，并将此物理地址写入DMA控制器的地址寄存器。少数DMA控制器中使用的另一种方案是将虚拟地址写入DMA控制器。

然后DMA控制器必须使用MMU完成虚拟到物理的转换。只有在MMU是内存的一部分（可能，但很少），而不是CPU的一部分的情况下，虚拟地址才能放在总线上。我们前面提到过，在DMA启动之前，磁盘首先将数据读入其内部缓冲区。

为什么控制器在从磁盘获取字节后不直接将其存储在主内存中。换句话说，它为什么需要内部缓冲区？有两个原因。

首先，通过进行内部缓冲，磁盘控制器可以在开始传输之前验证校验和。如果校验和不正确，则发出错误信号，不进行传输。

第二个原因是，一旦磁盘传输开始，无论控制器是否准备就绪，位都会以恒定的速率从磁盘到达。如果控制器试图将数据直接写入内存，则必须通过系统总线传输每个字。如果总线由于其他设备使用而繁忙（例如，在突发模式下），控制器将不得不等待。如果下一个磁盘字在存储前一个之前到达，则控制器必须将其存储在某个地方。如果总线很忙，控制器可能会存储相当多的字，并有很多管理工作要做。当块被内部缓冲时，直到DMA开始时才需要总线，因此控制器的设计要简单得多，因为DMA传输到内存不是时间关键的。（事实上，一些较旧的控制器确实只需要少量内部缓冲就可以直接进入内存，但当总线非常繁忙时，传输可能会因溢出错误而终止。）

并非所有计算机都使用DMA。反对它的理由是，主CPU通常比DMA控制器快得多，并且可以更快地完成工作（当限制因素不是I/O设备的速度时）。如果没有其他工作要做，让（快速）CPU等待（慢速）DMA控制器完成是毫无意义的。此外，去掉DMA控制器并让CPU完成软件中的所有工作可以节省资源，在低端（嵌入式）计算机上很重要。

重新访问中断

在典型的个人计算机系统中，中断结构如下图所示。在硬件级别，中断的工作方式是：当I/O设备完成给它的工作时，它会导致中断（假设操作系统已启用中断）。它通过在分配给它的总线上断言信号来实现这一点，这个信号由主板上的中断控制器芯片检测到，然后由它决定要做什么。

中断是如何发生的。设备和控制器之间的连接实际上使用总线上的中断线，而不是专用线。

如果没有其他中断挂起，中断控制器会立即处理该中断。然而，如果另一个中断正在进行中，或者另一个设备在总线上的高优先级中断请求行上同时发出了请求，则暂时忽略该设备。在这种情况下，它继续在总线上断言中断信号，直到CPU为其提供服务为止。为了处理中断，控制器将一个数字放在地址线上，指定哪个设备需要关注，并断言一个信号来中断CPU。

中断信号使CPU停止正在做的事情，并开始做其他事情。地址行上的数字用作名为中断向量的表的索引，以获取新的程序计数器。该程序计数器指向相应中断服务程序的开始。通常，陷阱和中断从此时起使用相同的机制，通常共享相同的中断向量。中断向量的位置可以硬连接到机器中，也可以在内存中的任何位置，CPU寄存器（由操作系统加载）指向其原点。

在它开始运行后不久，中断服务程序通过向中断控制器的一个I/O端口写入某个值来确认中断。该确认通知控制器可以自由发出另一个中断。通过让CPU延迟此确认，直到它准备好处理下一个中断，可以避免涉及多个（几乎同时）中断的竞争条件。另外，一些（较旧的）计算机没有集中式中断控制器，因此每个设备控制器都请求自己的中断。

硬件总是在开始维修程序之前保存某些信息。保存的信息和保存位置因CPU而异。至少，必须保存程序计数器，以便重新启动中断的进程。在另一个极端，所有可见寄存器和大量内部寄存器也可以保存。

一个问题是在哪里保存这些信息。一种选择是将其放入操作系统可以根据需要读取的内部寄存器中。这种方法的一个问题是，在读取所有潜在相关信息之前，无法确认中断控制器，以免第二个中断覆盖保存状态的内部寄存器。当中断被禁用时，这种策略会导致长时间的死区，并可能导致中断丢失和数据丢失。

因此，大多数CPU将信息保存在堆栈上。然而，这种方法也有问题。首先：谁的堆栈？如果使用当前堆栈，它很可能是用户进程堆栈。堆栈指针甚至可能不是合法的，当硬件试图在指向的地址写入某些字时，会导致致命错误。此外，它可能指向页面的末尾。在多次内存写入之后，可能会超出页面边界并生成页面错误。在硬件中断处理期间发生页面错误会产生一个更大的问题：在哪里保存状态以处理页面错误？

如果使用内核堆栈，则堆栈指针合法并指向固定页面的可能性要大得多。然而，切换到内核模式可能需要更改MMU上下文，并且可能会使大部分或全部缓存和TLB无效。静态或动态重新加载所有这些内容将增加处理中断的时间，从而浪费CPU时间。

精确和不精确中断

另一个问题是，大多数现代CPU都是高度流水线的，而且常常是超标量的（内部并行）。在较旧的系统中，每条指令执行完毕后，微程序或硬件会检查是否有中断挂起。如果是这样，程序计数器和PSW被推到堆栈上，中断序列开始。在中断处理程序运行后，发生了相反的过程，旧的PSW和程序计数器从堆栈中弹出，前一个过程继续。

该模型隐式假设，如果中断发生在某条指令之后，则该指令之前（包括该指令）的所有指令都已完全执行，并且在执行之后根本没有指令。在较旧的机器上，此假设始终有效。在现代设备上可能不是这样。

如果在管道已满时发生中断，通常情况下会发生什么情况？许多指令处于不同的执行阶段。当中断发生时，程序计数器的值可能无法反映已执行指令和未执行指令之间的正确边界。事实上，许多指令可能已部分执行，不同的指令或多或少都已完成。在这种情况下，程序计数器很可能反映要提取并推入管道的下一条指令的地址，而不是执行单元刚刚处理的指令的地址。

在超标量机器上，情况更糟。指令可以分解为微操作，微操作可能会无序执行，取决于内部资源（如功能单元和寄存器）的可用性。在中断时，一些早就开始的指令可能还没有开始，而另一些最近开始的指令几乎已经完成。在发出中断信号时，可能有许多处于不同完整状态的指令，它们与程序计数器之间的关系较小。

使机器处于定义良好状态的中断称为精确中断（precise interrupt），它有四个属性：

1、PC（程序计数器）保存在已知位置。

2、PC所指的指令之前的所有指令均已完成。

3、除PC指示的指令外，没有其他指令完成。

4、PC指向的指令的执行状态是已知的。

请注意，除电脑指示的指令外，没有禁止启动的指令。只是它们对寄存器或内存所做的任何更改都必须在中断发生之前撤消。允许已执行指向的指令。还允许尚未执行。

必须明确哪种情况适用，通常，如果中断是I/O中断，则指令尚未启动。然而，如果中断真的是一个陷阱或页面错误，那么PC通常会指向导致错误的指令，以便稍后重新启动，下图（a）中的情况说明了一个精确的中断。程序计数器（316）之前的所有指令都已完成，而超出它的指令都没有启动（或回滚以撤消其效果）。

不满足这些要求的中断称为不精确中断（imprecise interrupt），它使操作系统编写者的生活最不愉快，他们现在必须弄清楚发生了什么，还有什么事情要发生。下图（b）显示了一个不精确的中断，其中程序计数器附近的不同指令处于不同的完成阶段，旧指令不一定比新指令更完整。具有不精确中断的机器通常会向堆栈中吐出大量内部状态，以使操作系统能够判断出发生了什么。重启机器所需的代码通常非常复杂。此外，在每次中断时都将大量信息保存到内存中，使中断速度变慢，恢复情况更糟。这导致了一种具有讽刺意味的情况，即由于中断速度较慢，速度非常快的超标量CPU有时不适合实时工作。

一些计算机的设计使得某些中断和陷阱是精确的，而另一些则不是。例如，I/O中断是精确的，但由于致命编程错误导致的陷阱是不精确的，这并不是很糟糕，因为在进程被零除后，不需要尝试重新启动正在运行的进程。有些机器有一个位，可以设置为强制所有中断精确。设置这个位的缺点是，它迫使CPU仔细记录正在做的一切，并维护寄存器的影子副本（shadow copies），以便它可以在任何时刻生成精确的中断。所有这些开销都会对性能产生重大影响。

（a） 精确中断；（b） 不精确中断。

一些超标量计算机，如x86系列，具有精确的中断，以允许旧软件正常工作。为与精确中断向后兼容而付出的代价是CPU内极其复杂的中断逻辑，以确保当中断控制器发出信号表示要引起中断时，所有指令在某一点之前都可以完成，超过该点的指令都不允许对机器状态有任何明显的影响。在这里，付出的代价不是时间，而是芯片面积和设计的复杂性。如果向后兼容不需要精确的中断，则此芯片区域可用于更大的片上缓存，从而使CPU更快。另一方面，不精确的中断使操作系统更加复杂和缓慢，因此很难判断哪种方法真正更好。

18.11.4.2 I/O软件原理

本节将阐述I/O的目标，从操作系统的角度来看它的不同实现方式。

I/O软件的目标

I/O软件设计中的一个关键概念是设备独立性，意味着我们应该能够编写可以访问任何I/O设备的程序，而无需事先指定设备。例如，将文件作为输入读取的程序应该能够读取硬盘、DVD或U盘上的文件，而无需针对每个不同的设备进行修改。类似地，应该能够键入以下命令：

sort <input> output

它可以处理来自任何磁盘或键盘的输入，以及发送到任何磁盘或屏幕的输出。这些设备确实不同，需要非常不同的命令序列来读取或写入，取决于操作系统来解决这些问题。

与设备独立性密切相关的是统一命名的目标。文件或设备的名称应仅为字符串或整数，而不应以任何方式依赖于设备。在UNIX中，所有磁盘都可以以任意方式集成到文件系统层次结构中，因此用户无需知道哪个名称对应于哪个设备。例如，可以将USB记忆棒安装在/usr/ast/backup目录的顶部，以便将文件复制到/usr/ast/backup/monday将文件复制至USB记忆棒。这样，所有文件和设备都以相同的方式寻址：通过路径名。

I/O软件的另一个重要问题是错误处理。一般来说，错误的处理应该尽可能靠近硬件。如果控制器发现一个读取错误，如果可以的话，它应该尝试自己更正错误。如果不能，那么设备驱动程序应该处理它，也许只需再次尝试读取块即可。许多错误都是暂时性的，例如读取头上的灰尘斑点导致的读取错误，如果重复操作，这些错误通常会消失。只有当下层无法处理问题时，才应该告诉上层。在许多情况下，错误恢复可以在较低级别透明地完成，而上层甚至不知道错误。

另一个重要问题是同步（阻塞）与异步（中断驱动）传输的比较。大多数物理I/O都是异步的——CPU开始传输，然后去做其他事情，直到中断到来。如果读系统调用后I/O操作阻塞，则用户程序更容易编写，程序会自动挂起，直到数据在缓冲区中可用为止。操作系统应该让中断驱动的操作看起来对用户程序是阻塞的。然而，一些非常高性能的应用程序需要控制I/O的所有细节，因此一些操作系统为它们提供异步I/O。

I/O软件的另一个问题是缓冲。通常，从设备上下来的数据不能直接存储在最终目的地，例如，当数据包从网络中传入时，操作系统直到将数据包存储在某个位置并对其进行检查之后才知道将其放在何处。此外，一些设备具有严重的实时限制（例如数字音频设备），因此必须提前将数据放入输出缓冲区，以将缓冲区填充速率与清空速率解耦，以避免缓冲区不足。缓冲涉及大量复制，通常对I/O性能有重大影响。我们在这里要提到的最后一个概念是共享设备与专用设备。

一些I/O设备（如磁盘）可以由许多用户同时使用，多个用户同时在同一磁盘上打开文件不会导致任何问题。其他设备（如打印机）必须专用于单个用户，直到该用户完成，然后其他用户可以拥有打印机。让两个或两个以上的用户在同一页面上随机混合写入字符肯定不行。引入专用（非共享）设备也会带来各种问题，例如死锁。同样，操作系统必须能够以避免问题的方式处理共享设备和专用设备。

编程输入/输出

有三种根本不同的I/O执行方式，最简单的I/O形式是让CPU完成所有工作，这种方法称为编程I/O（programmed
I/O）。

通过一个例子来说明编程I/O的工作原理是最简单的。考虑一个用户进程，它希望通过串行接口在打印机上打印八个字符的字符串“ABCDEFGH”，软件首先在用户空间的缓冲区中组装字符串，如下图（a）所示。

然后，用户进程通过系统调用打开打印机来获取打印机进行写入。如果打印机当前正由另一个进程使用，则此调用将失败并返回错误代码，或将阻塞，直到打印机可用为止，具体取决于操作系统和调用的参数。一旦拥有打印机，用户进程将进行系统调用，告诉操作系统在打印机上打印字符串。

然后，操作系统（通常）将带有字符串的缓冲区复制到内核空间中的一个数组，例如p，在那里它更容易访问（因为内核可能必须更改内存映射才能获得用户空间）。然后检查打印机当前是否可用，如果没有，它会一直等待，直到打印机可用。一旦打印机可用，操作系统就会使用内存映射I/O将第一个字符复制到打印机的数据寄存器，此操作将激活打印机。

该字符可能尚未出现，因为某些打印机在打印任何内容之前会缓冲一行或一页。然而，在下图（b）中，我们看到第一个字符已经打印出来，并且系统已经将“b”标记为下一个要打印的字符。

一旦将第一个字符复制到打印机，操作系统就会检查打印机是否准备好接受另一个字符。通常，打印机有第二个寄存器，用于显示其状态，写入数据寄存器的行为导致状态变为未就绪。当打印机控制器处理完当前字符后，它通过在状态寄存器中设置一些位或在其中输入一些值来指示其可用性。

此时，操作系统将等待打印机再次就绪。当发生这种情况时，它会打印下一个字符，如下图（c）所示。此循环一直持续到打印完整个字符串，然后控制权返回到用户进程。

打印字符串的步骤。

下面伪代码简要总结了操作系统执行的操作。首先，将数据复制到内核，然后操作系统进入一个紧密循环，一次输出一个字符。编程I/O的基本行为是，在输出字符后，CPU不断轮询设备，看它是否准备好接受另一个字符。这种行为通常称为轮询（polling）或忙等待（busy waiting）。

copy_from_user(buffer, p,count); /* p is the ker nel buffer */
 
for (i = 0; i < count; i++)      /* loop on every character */
{ 
    while (*printer_status_reg != READY) ; /* loop until ready */
    *printer_data_register = p[i];         /* output one character */
}
 
return_to_user( );

编程I/O很简单，但缺点是在完成所有I/O之前占用CPU的全部时间。如果“打印”字符的时间很短（因为打印机所做的一切都是将新字符复制到内部缓冲区），那么忙等待就可以了。此外，在嵌入式系统中，CPU没有其他事情可做，忙等待也可以。然而，在更复杂的系统中，CPU还有其他工作要做，忙等待效率很低，需要更好的I/O方法。

中断驱动I/O

现在让我们考虑一下在打印机上打印的情况，打印机不缓冲字符，而是在到达时打印每个字符，如果打印机可以打印，例如100个字符/秒，则每个字符需要10毫秒才能打印。这意味着在将每个字符写入打印机的数据寄存器后，CPU将处于空闲循环10毫秒，等待下一个字符的输出。足以进行上下文切换，并在10毫秒内运行其他可能被浪费的进程。

允许CPU在等待打印机就绪时执行其他操作的方法是使用中断。当系统调用打印字符串时，缓冲区被复制到内核空间，如前所示，只要打印机愿意接受字符，就会将第一个字符复制到打印机。此时，CPU调用调度程序，并运行其他一些进程。要求打印字符串的进程被阻止，直到打印完整个字符串。系统调用的工作如下（a）所示。

当打印机打印完字符并准备接受下一个字符时，它会生成一个中断，此中断停止当前进程并保存其状态，然后运行打印机中断服务程序，该代码的粗略版本如下（b）所示。如果没有更多的字符要打印，中断处理程序将采取一些操作取消阻止用户。否则，它输出下一个字符，确认中断，并返回到中断之前运行的进程，该进程从中断处继续。

// 使用中断驱动I/O将字符串写入打印机。
 
// (a) 执行打印系统调用时执行的代码。
copy_from_user(buffer, p, count); 
enable_interrupts(); 
while (*printer_status_reg != READY) ; 
*printer_data_register = p[0]; 
scheduler(); 
    
// (b) 中断打印机的维修程序。
if (count == 0) 
{
    unblock_user( );
} 
else 
{
    *printer_data_register = p[i];
    count = count − 1;
    i = i + 1;
}
acknowledge_interrupt();
return_from_interrupt();

使用DMA的I/O

中断驱动I/O的一个明显缺点是每个字符都会发生中断，中断需要时间，因此此方案浪费了一定的CPU时间。解决方案是使用DMA，让DMA控制器一次将字符输入到打印机，而不会影响CPU。本质上，DMA是编程I/O，只有DMA控制器做所有工作，而不是主CPU。此策略需要特殊硬件（DMA控制器），但在I/O期间释放CPU以执行其他工作。代码概要如下所示。

// 使用DMA打印字符串。
 
// (a) 执行打印系统调用时执行的代码。
copy_from_user(buffer, p, count); 
set_up_DMA_controller(); 
scheduler(); 
 
// (b) 中断服务程序。
acknowledge_interrupt();
unblock_user();
return_from_interrupt();

DMA的最大优势是将中断次数从每个字符减少到每个打印缓冲区一个，如果有许多字符并且中断很慢，会有很大的改进。另一方面，DMA控制器通常比主CPU慢得多。如果DMA控制器无法全速驱动设备，或者CPU在等待DMA中断时通常无事可做，那么中断驱动I/O甚至编程I/O可能更好。然而，在大多数情况下，DMA是值得的。

传统DMA块图。

改进后的DMA配置。

18.11.4.3 I/O软件层级

I/O软件通常分为四层，如下图所示。每一层都有一个定义明确的功能来执行，并有一个与相邻层定义明确的接口。功能和接口因系统而异，因此下面的讨论（从底部开始检查所有层）并不针对一台机器。

I/O软件系统的层。

下面阐述这些层。

• 中断处理器

虽然编程I/O偶尔有用，但对于大多数I/O来说，中断是一个令人不快的事实，无法避免。它们应该隐藏在操作系统的内部深处，以便尽可能少的操作系统了解它们。隐藏它们的最佳方法是让驱动程序启动I/O操作块，直到I/O完成并发生中断。驱动程序可以阻塞自身，例如，通过关闭信号量、等待条件变量、接收消息或类似操作。当中断发生时，中断过程会做任何它必须做的事情来处理中断，然后它可以解锁等待它的驱动程序。

在某些情况下，它只会在一个信号量上完成。在其他情况下，它会对监视器中的条件变量发出信号。在其他情况下，它将向被阻止的驱动程序发送消息。在所有情况下，中断的净影响是先前被阻塞的驱动程序现在能够运行。如果驱动程序结构为内核进程，并且有自己的状态、堆栈和程序计数器，则此模型最有效。

当然，现实并不那么简单。处理中断不仅仅是接受中断，对一些信号量执行一个up，然后执行IRET指令以从中断返回到前一个进程。操作系统需要做更多的工作。现在将概述此项工作，作为硬件中断完成后必须在软件中执行的一系列步骤。需要注意的是，这些细节高度依赖于系统，因此在特定机器上可能不需要下面列出的某些步骤，也可能需要未列出的步骤。此外，在某些机器上，确实发生的步骤可能顺序不同。

1、保存中断硬件尚未保存的所有寄存器（包括PSW）。

2、为中断服务过程设置上下文，可能需要设置TLB、MMU和页表。

3、为中断服务过程设置堆栈。

4、确认中断控制器。如果没有集中式中断控制器，则重新启用中断。

5、将寄存器从保存位置（可能是一些堆栈）复制到进程表。

6、运行中断服务程序，它将从中断设备控制器的寄存器中提取信息。

7、选择下一个要运行的进程。如果中断导致某个被阻塞的高优先级进程准备就绪，则可以选择立即运行。

8、为下一个要运行的进程设置MMU上下文。可能还需要一些TLB设置。

9、加载新进程的寄存器，包括其PSW。

10、开始运行新进程。

可以看出，中断处理远不是微不足道的。它还需要相当多的CPU指令，特别是在存在虚拟内存且必须设置页表或存储MMU状态（例如R和M位）的机器上。在某些机器上，在用户模式和内核模式之间切换时，可能还必须管理TLB和CPU缓存，这需要额外的机器周期。

• 设备驱动

前面我们讨论了设备控制器的功能。我们看到，每个控制器都有一些设备寄存器用于发出命令，或者有一些设备注册表用于读取其状态，或者两者都有。设备寄存器的数量和命令的性质因设备而异。例如，鼠标驱动程序必须接受来自鼠标的信息，告诉它移动了多远以及当前按下了哪些按钮。相反，磁盘驱动器可能必须了解扇区、磁道、圆柱体、磁头、臂运动、电机驱动器、磁头固定时间以及使磁盘正常工作的所有其他机制。显然，这些驱动因素将非常不同。

因此，连接到计算机的每个I/O设备都需要一些特定于设备的代码来控制它。此代码称为设备驱动程序，通常由设备制造商编写，并随设备一起交付。由于每个操作系统都需要自己的驱动程序，设备制造商通常为几种流行的操作系统提供驱动程序。

每个设备驱动程序通常处理一种设备类型，或至多一类密切相关的设备。例如，SCSI磁盘驱动程序通常可以处理多个不同大小和速度的SCSI磁盘，也可以处理SCSI蓝光磁盘。另一方面，鼠标和操纵杆如此不同，通常需要不同的驱动程序。然而，一个设备驱动程序控制多个不相关的设备没有技术限制，在大多数情况下都不是一个好主意。

然而，有时不同的设备基于相同的底层技术。最著名的例子可能是USB，它是一种串行总线技术，并非无缘无故被称为“通用”。USB设备包括磁盘、记忆棒、相机、鼠标、键盘、迷你风扇、无线网卡、机器人、信用卡阅读器、充电剃须刀、碎纸机、条形码扫描仪、迪斯科球和便携式温度计。他们都使用USB，但他们做的事情却大相径庭。

诀窍在于USB驱动程序通常是堆叠的，就像网络中的TCP/IP堆栈一样。在底层，通常在硬件中，我们可以找到USB链路层（串行I/O），它处理诸如向USB数据包发送信号和解码信号流之类的硬件。它被用于处理数据包的高层，以及大多数设备共享的USB通用功能。除此之外，最后，我们找到了更高层的API，例如大容量存储接口、摄像头等。因此，我们仍然有单独的设备驱动程序，即使它们共享协议栈的一部分。

实际上，为了访问设备的硬件，也就是控制器的寄存器，设备驱动程序通常必须是操作系统内核的一部分，至少在当前的体系结构中是这样。实际上，可以构造在用户空间中运行的驱动程序，并通过系统调用读取和写入设备寄存器。这种设计将内核与驱动程序隔离开来，并将驱动程序彼此隔离开来，从而消除了以某种方式干扰内核的系统崩溃错误驱动程序的主要来源。对于构建高度可靠的系统，这无疑是一条路。设备驱动程序作为用户进程运行的系统示例是MINIX 3，然而，由于大多数其他桌面操作系统都希望驱动程序在内核中运行，因此我们将在这里考虑这个模型。

由于每个操作系统的设计者都知道外部编写的代码（驱动程序）将被安装在其中，因此需要有一个允许这种安装的体系结构，意味着要有一个定义良好的模型来描述驱动程序的功能以及它如何与操作系统的其余部分交互。设备驱动程序通常位于操作系统其余部分的下方，如下图所示。

设备驱动程序的逻辑定位。实际上，驱动器和设备控制器之间的所有通信都通过总线进行。

操作系统通常将驱动程序划分为少数类别之一。最常见的类别是块设备（如磁盘），其中包含可以独立寻址的多个数据块，以及字符设备（如键盘和打印机），它们生成或接受字符流。

大多数操作系统定义了所有块驱动程序都必须支持的标准接口和所有字符驱动程序都要支持的第二个标准接口。这些接口由许多过程组成，操作系统的其他部分可以调用这些过程来让驱动程序为其工作。典型的步骤是读取块（块设备）或写入字符串（字符设备）。

在某些系统中，操作系统是一个单一的二进制程序，其中包含它需要编译到其中的所有驱动程序。这种方案多年来一直是UNIX系统的标准，因为它们由计算机中心运行，I/O设备很少更改。如果添加了新设备，系统管理员只需使用新的驱动程序重新编译内核，以构建新的二进制文件。

随着个人计算机及其无数I/O设备的出现，这种模式不再适用。很少有用户能够重新编译或重新链接内核，即使他们有源代码或目标模块，但情况并非总是如此。相反，从MS-DOS开始的操作系统转向了一种模型，在该模型中，驱动程序在执行期间动态加载到系统中。不同的系统以不同的方式处理加载驱动程序。

设备驱动程序具有多个功能。最明显的一种方法是接受来自其上方独立于设备的软件的抽象读写请求，并确保它们得到执行。但它们还必须执行一些其他功能，例如，如果需要，驱动程序必须初始化设备。它可能还需要管理电源要求和记录事件。

许多设备驱动程序具有类似的一般结构。典型的驱动程序首先检查输入参数，看看它们是否有效，如果不是，则返回错误，如果它们有效，可能需要将抽象术语翻译为具体术语。对于磁盘驱动器，可能意味着将线性块编号转换为磁盘几何体的磁头、磁道、扇区和柱面编号。

接下来，驱动程序可能会检查设备当前是否正在使用。如果是，请求将排队等待稍后处理，如果设备处于空闲状态，将检查硬件状态，以查看现在是否可以处理请求。在开始传输之前，可能需要打开设备或启动电机，一旦设备启动并准备就绪，就可以开始实际控制。

控制设备意味着向其发出一系列命令。驱动程序是根据必须执行的操作确定命令序列的位置，在驱动程序知道要发出哪些命令后，它开始将它们写入控制器的设备寄存器。在将每个命令写入控制器后，可能需要检查控制器是否接受该命令并准备接受下一个命令。此序列将继续，直到发出所有命令。一些控制器可以得到一个命令链接列表（内存中），并告诉它们自己读取和处理所有命令，而无需操作系统的进一步帮助。

发出命令后，将应用以下两种情况之一。在许多情况下，设备驱动程序必须等待控制器为其执行某些工作，因此它会阻塞自身，直到中断来解除阻塞。然而，在其他情况下，操作会立即完成，因此驱动无需阻塞。作为后一种情况的示例，滚动屏幕只需要将几个字节写入控制器的寄存器。不需要机械运动，因此整个操作可以在纳秒内完成。

在前一种情况下，被阻塞的驱动程序将被中断唤醒。在后一种情况下，它永远不会睡觉。无论如何，在操作完成后，驱动程序必须检查错误。如果一切正常，驱动程序可能有一些数据要传递给设备独立软件（例如，刚读取的块）。

最后，它返回一些状态信息，以便向调用者报告错误。如果有任何其他请求排队，现在可以选择并启动其中一个请求。如果没有排队，驱动程序将阻塞等待下一个请求。这个简单的模型只是对现实的粗略近似。许多因素使代码更加复杂。首先，I/O设备可能会在驱动程序运行时完成，从而中断驱动程序，中断可能会导致设备驱动程序运行。事实上，它可能会导致当前驱动程序运行，例如，当网络驱动程序正在处理一个传入的数据包时，另一个数据包可能会到达。因此，驱动程序必须是可重入的，意味着运行中的驱动程序必须期望在第一次调用完成之前第二次调用它。

在热插拔系统中，可以在计算机运行时添加或删除设备。因此，当驱动程序忙于读取某个设备时，系统可能会通知它用户突然从系统中删除了该设备。不仅必须在不损坏任何内核数据结构的情况下中止当前的I/O传输，而且对于现在已消失的设备的任何挂起请求也必须从系统及其调用者（如果有坏消息）中优雅地删除。此外，意外添加的新设备可能会导致内核篡改资源（例如中断请求行），将旧设备从驱动程序中删除，并将新设备放在其位置。

驱动程序不允许进行系统调用，但它们通常需要与内核的其余部分进行交互。通常，允许调用某些内核过程。例如，通常会调用分配和取消分配用作缓冲区的内存硬连接页，需要其他有用的调用来管理MMU、定时器、DMA控制器、中断控制器等。

• 独立于设备的I/O软件

虽然一些I/O软件是特定于设备的，但它的其他部分是独立于设备的。驱动程序和独立于设备的软件之间的确切边界取决于系统（和设备），因为出于效率或其他原因，一些可以独立于设备完成的功能实际上可能在驱动程序中完成。下图所示的功能通常在设备独立软件中完成。

设备独立软件的基本功能是执行所有设备通用的I/O功能，并为用户级软件提供统一的接口。我们现在将更详细地讨论上述问题。

先阐述设备驱动程序的统一接口。

操作系统中的一个主要问题是如何使所有I/O设备和驱动程序看起来或多或少相同。如果磁盘、打印机、键盘等都以不同的方式连接，那么每次新设备出现时，都必须为新设备修改操作系统。对于每一个新设备，必须对操作系统进行黑客攻击不是一个好主意。

这个问题的一个方面是设备驱动程序和操作系统其余部分之间的接口。在下图（a）中，我们举例说明了一种情况，即每个设备驱动程序都有一个不同的操作系统接口，意味着系统可调用的驱动功能因驱动而异，也可能意味着驱动程序所需的内核函数也因驱动程序而异。总而言之，意味着连接每个新驱动程序需要大量新的编程工作。

（a） 没有标准的驱动程序接口。（b） 具有标准驱动程序接口。

相反，在上图（b）中，我们展示了一种不同的设计，其中所有驱动程序都具有相同的界面。现在，只要符合驱动程序接口，插入一个新的驱动程序就容易多了，也意味着驱动程序编写者知道对他们的期望是什么。在实践中，并非所有设备都是完全相同的，但通常只有少数设备类型，即使这些设备类型通常也几乎相同。

其工作方式如下。对于每类设备，如磁盘或打印机，操作系统定义了驱动程序必须提供的一组功能。对于磁盘，这些操作自然包括读取和写入，但也包括打开和关闭电源、格式化以及其他磁盘操作。通常，驱动程序持有一个表，其中包含这些函数的指针。加载驱动程序时，操作系统会记录此函数指针表的地址，因此当需要调用其中一个函数时，可以通过此表进行间接调用。此函数指针表定义了驱动程序与操作系统其余部分之间的接口。给定类别的所有设备（磁盘、打印机等）都必须遵守它。

拥有统一接口的另一个方面是如何命名I/O设备。独立于设备的软件负责将符号设备名称映射到正确的驱动程序上。例如，在UNIX中，设备名（如/dev/disk0）唯一地指定了特殊文件的i节点，而此i节点包含用于查找相应驱动程序的主设备号。i节点还包含次要设备编号，该编号作为参数传递给驱动程序，以便指定要读取或写入的单元。所有设备都有主设备号和次设备号，通过使用主设备号选择驱动程序可以访问所有驱动程序。

与命名密切相关的是保护。系统如何阻止用户访问他们无权访问的设备？在UNIX和Windows中，设备在文件系统中显示为命名对象，意味着通常的文件保护规则也适用于I/O设备。然后，系统管理员可以为每个设备设置适当的权限。

接着描述缓冲。

由于各种原因，缓冲也是块和字符设备的一个问题。要查看其中一个，请考虑一个从（ADSL非对称数字用户线路）调制解调器读取数据的过程，许多人在家中使用该调制解调器连接到Internet。处理传入字符的一种可能策略是让用户进程执行读取系统调用并阻塞等待一个字符，每个到达的字符都会导致中断，中断服务过程将字符交给用户进程并解除阻塞。将字符放在某处后，进程读取另一个字符并再次阻塞。该模型如下图（a）所示。

这种业务处理方式的问题是，必须为每个传入字符启动用户进程。允许一个进程在短时间内多次运行很低效，因此这种设计并不好。

改进如下图（b）所示。在方法下，用户进程在用户空间中提供一个n个字符的缓冲区，并读取n个字符。中断服务过程将传入字符放入该缓冲区，直到它完全满为止。只有这样，它才会唤醒用户进程。这个方案比前一个方案效率高得多，但它有一个缺点：如果在字符到达时调出缓冲区，会发生什么情况？缓冲区可以锁定在内存中，但如果许多进程开始任意锁定内存中的页面，可用页面池将缩小，性能将降低。

（a） 无缓冲输入。（b） 在用户空间中缓冲。（c） 在内核中进行缓冲，然后复制到用户空间。（d） 内核中的双缓冲。

另一种方法是在内核内创建一个缓冲区，并让中断处理程序将字符放在那里，如上图（c）所示。当此缓冲区已满时，如果需要，将带用户缓冲区的页面放入，并在一次操作中将缓冲区复制到那里。这个方案效率要高得多。

然而，即使是这种改进的方案也存在一个问题：当带有用户缓冲区的页面从磁盘引入时，到达的字符会发生什么？由于缓冲区已满，因此没有放置它们的位置。解决方法是使用第二个内核缓冲区，在第一个缓冲区填满后，但在清空之前，使用第二个缓冲区，如上图（d）所示。当第二个缓冲区填满时，可以将其复制给用户（假设用户已要求），当第二个缓冲区被复制到用户空间时，第一个缓冲区可以用于新字符。这样，两个缓冲区轮流进行：一个缓冲区被复制到用户空间，另一个缓冲区则在积累新的输入。此方案称为双缓冲（double buffering）。

另一种常见的缓冲形式是循环缓冲（circular buffer），由一个内存区域和两个指针组成，一个指针指向下一个可以放置新数据的自由词，另一个指针指向缓冲区中尚未删除的第一个数据字。在许多情况下，硬件在添加新数据（例如，刚从网络中到达）时向前移动第一个指针，而操作系统在删除和处理数据时向前移动第二个指针，两个指针都会环绕——它们到达顶部时会返回底部。

缓冲对输出也很重要。例如，考虑如何使用上图（b）中的模型在不缓冲的情况下输出到调制解调器，用户进程执行写入系统调用以输出n个字符。此时，系统有两种选择：其一，它可以阻止用户直到所有字符都被写入为止，但可能需要很长时间才能通过慢速电话线完成；其二，它还可以立即释放用户，并在用户进行更多计算时执行I/O，但这会导致更严重的问题：用户进程如何知道输出已经完成，并且可以重用缓冲区？系统可以生成信号或软件中断，但这种编程方式很难实现，并且容易出现竞争情况。一个更好的解决方案是内核将数据复制到内核缓冲区，类似于上图（c），并立即解除对调用者的阻塞。此模式的实际I/O何时完成并不重要，用户可以在缓冲区解除阻塞后立即重新使用它。

缓冲是一种广泛使用的技术，但它也有缺点。如果数据缓冲过多，性能就会受到影响。

接下来描述错误报告。

错误在I/O上下文中比在其他上下文中更常见。当它们发生时，操作系统必须尽可能地处理它们。许多错误是特定于设备的，必须由适当的驱动程序处理，但错误处理框架与设备无关。

一类I/O错误是编程错误。当进程要求一些不可能的东西时，就会出现这些错误，例如写入输入设备（键盘、扫描仪、鼠标等）或读取输出设备（打印机、绘图仪等）。其他错误包括提供无效的缓冲地址或其他参数，以及指定无效的设备（例如，当系统只有两个磁盘时，磁盘3），等等。处理这些错误的操作很简单：只需向调用者报告错误代码。

另一类错误是实际的I/O错误，例如，试图写入已损坏的磁盘块或试图读取已关闭的摄像机。在这些情况下，由驱动程序决定要做什么。如果驱动程序不知道要做什么，它可能会将问题传回设备无关软件。

此软件的功能取决于环境和错误的性质。如果是一个简单的读取错误，并且有一个交互式用户可用，它可能会显示一个对话框，询问用户该怎么做。选项可能包括重试一定次数、忽略错误或终止调用进程。如果没有用户可用，可能唯一可行的方法是让系统调用失败并返回错误代码。

但是，有些错误不能用这种方式处理。例如，关键数据结构（如根目录或可用阻止列表）可能已被破坏。在这种情况下，系统可能必须显示错误消息并终止，能做的事情并不多。

接下来阐述分配和释放专用设备。

某些设备（如打印机）在任何给定时刻只能由单个进程使用。由操作系统检查设备使用请求并接受或拒绝它们，具体取决于所请求的设备是否可用。处理这些请求的一种简单方法是要求进程直接打开设备的特殊文件。如果设备不可用，则打开失败。关闭这样的专用设备，然后释放它。

另一种方法是使用特殊机制来请求和释放专用设备。尝试获取不可用的设备会阻止调用方，而不是失败。阻塞的进程被放入队列。请求的设备迟早会可用，队列中的第一个进程可以获取它并继续执行。

不同的磁盘可能具有不同的扇区大小。由独立于设备的软件来隐藏这一事实，并为更高层提供统一的块大小，例如，将几个扇区视为单个逻辑块。这样，高层只处理抽象设备，这些抽象设备都使用相同的逻辑块大小，与物理扇区大小无关。类似地，一些字符设备每次只传送一个字节的数据（例如鼠标），而其他字符设备则以较大的单位传送数据（例如以太网接口）。这些差异也可能被隐藏。

18.11.4.4 用户空间的I/O软件

尽管大多数I/O软件都在操作系统内，但其中一小部分由与用户程序链接在一起的库组成，甚至包括在内核外运行的整个程序。系统调用，包括I/O系统调用，通常由库过程进行。当C程序包含以下调用时：

count = write(fd, buffer, nbytes);

库过程写入可能与程序链接，并包含在运行时内存中的二进制程序中。在其他系统中，库可以在程序执行期间加载。无论如何，所有这些库过程的集合显然是I/O系统的一部分。

虽然这些过程只不过将其参数放在系统调用的适当位置，但其他I/O过程实际上做了真正的工作。特别是，输入和输出的格式化是由库过程完成的。C语言中的一个示例是printf，它接受格式字符串和可能的一些变量作为输入，构建ASCII字符串，然后调用write输出字符串。作为printf的一个例子，考虑下面的语句：

printf("The square of %3d is %6d\n", i, i*i);

它将一个由14个字符组成的字符串“the square of”后跟值i格式化为3个字符的字符串，然后4个字符的串“”是“”，然后i2i2是6个字符，最后是换行符。

并非所有用户级I/O软件都由库程序组成。另一个重要类别是后台打印系统（spooling system），它是多道程序设计系统中处理专用I/O设备的一种方法。考虑一个典型的后台打印设备：打印机。尽管让任何用户进程打开打印机的字符特殊文件在技术上很容易，但假设有一个进程打开了它，然后几个小时内什么也没做，没有其他进程可以打印任何内容。

下图总结了I/O系统，显示了所有层和每个层的主要功能。从底层开始，层是硬件、中断处理程序、设备驱动程序、独立于设备的软件，最后是用户进程。

图中的箭头显示了控制流程。例如，当用户程序试图从文件中读取块时，会调用操作系统来执行调用。独立于设备的软件会在缓冲区缓存中查找它。如果所需的块不在那里，它会调用设备驱动程序向硬件发出请求，以便从磁盘获取它。然后，该进程被阻塞，直到磁盘操作完成，并且数据在调用方的缓冲区中安全可用。

当磁盘完成时，硬件生成一个中断。运行中断处理程序是为了发现发生了什么，也就是说，现在哪个设备需要关注。然后，它从设备中提取状态并唤醒休眠进程，以完成I/O请求并让用户进程继续。

18.11.5 Windows I/O

18.11.5.1 同步和同步I/O

异步和同步IO的对比图如下：

当调用CreateFile而不将FILE_FLAG_OVERLAPPED指定为dwFlagsAndAttributes参数的一部分时，将仅为同步I/O创建文件对象，是最简单的操作，因此我们将首先处理同步I/O。执行I/O的主要功能是ReadFile和WriteFile，它们与任何文件对象一起工作（不一定指向文件系统文件）：

BOOL ReadFile(HANDLE hFile, LPVOID lpBuffer, DWORD nNumberOfBytesToRead, LPDWORD lpNumberOfBytesRead, LPOVERLAPPED lpOverlapped);
BOOL WriteFile(HANDLE hFile, LPCVOID lpBuffer, DWORD nNumberOfBytesToWrite, LPDWORD lpNumberOfBytesWritten, LPOVERLAPPED lpOverlapped);

Windows I/O系统本质上是异步的，一旦设备驱动程序向其受控硬件（如磁盘驱动器）发出请求，驱动程序就不需要等待操作完成。相反，它将请求标记为“挂起”，并返回给调用方。当I/O正在进行时，线程可以自由执行其他操作。一段时间后，硬件设备完成I/O操作。设备发出硬件中断，使驱动程序提供的回调运行并完成挂起的请求。

使用同步I/O简单易行，许多情况也足够好。然而，如果要处理大量请求，那么为每个请求创建一个线程来启动I/O操作并等待其完成是效率低下的，且扩展性不好。异步I/O提供了一种解决方案，其中线程启动一个请求，然后返回服务下一个请求等，因为I/O操作在CPU执行其他代码的同时并发运行。这个简化模型中唯一的问题是如何通知线程I/O操作完成。

请求异步操作必须从原始的CreateFile调用开始（始终是同步的），必须将FILE_FLAG_OVERLAPPED标志指定为dwFlagsAndAttributes参数的一部分，将以异步模式打开文件/设备。

打开文件进行异步访问的结果之一是不再有文件指针，意味着每个操作都必须以某种方式提供从文件开始的偏移量来执行操作（大小不是问题，因为它是读/写调用的一部分）。这是重叠结构的任务之一，必须作为最后一个参数传递给ReadFile和WriteFile：

typedef struct _OVERLAPPED 
{
    ULONG_PTR Internal;
    ULONG_PTR InternalHigh;
    union 
    {
        struct 
        {
            DWORD Offset;
            DWORD OffsetHigh;
        };
           PVOID Pointer;
    };
    HANDLE hEvent;
} OVERLAPPED, *LPOVERLAPPED;

该结构包含三条不同的信息：

• 内部和内部高是I/O管理器使用的名称，不应写入。
• 偏移量和偏移量高是要设置的偏移量，指示操作在文件中的开始位置。如果需要64位偏移量，则union的指针成员是这些字段的另一种选择，更容易使用。
• hEvent是内核事件对象的句柄，如果非空，则在操作完成时由I/O管理器发出信号。

此外，Windows还支持手动排队APC（Manually Queued APC）。

18.11.5.2 I/O完成端口

I/O完成端口（I/O Completion Port）有自己的主要部分，因为它们不仅用于处理异步I/O。I/O完成端口与文件对象关联（可以是多个），封装了一个请求队列，以及一个一旦完成就可以为这些请求提供服务的线程列表。每当异步操作完成时，等待完成端口的线程之一应该唤醒并处理完成，可能会启动下一个请求。创建示例：

const int Key = 1;
HANDLE hFile = ::CreateFile(..., FILE_FLAG_OVERLAPPED, ...);
HANDLE hOldCP = ::CreateIoCompletionPort(hFile, hNewCP, Key, 0);
assert(hOldCP == hNewCP);

上述代码可以与其他文件对象重复，所有这些对象都与完成端口相关。下图描述了完成端口的简化图，可以看到绑定的线程是什么，以及所有这一切是如何工作的。

I/O完成端口的目的是允许工作线程处理已完成的I/O操作，这里的“工作线程”可以指绑定到完成端口的任何线程。

18.11.5.3 设备和管道

使用设备（Device，即非文件系统文件）与使用文件系统文件本质上没有什么不同。ReadFile和WriteFile函数适用于任何设备，包括异步，但并非所有设备都支持读写操作。特别是对于设备，还有另一个执行I/O操作的功能——DeviceIoControl：

BOOL DeviceIoControl(HANDLE hDevice, DWORD dwIoControlCode, LPVOID lpInBuffer, DWORD nInBufferSize, LPVOID lpOutBuffer, DWORD nOutBufferSize, LPDWORD lpBytesReturned, LPOVERLAPPED lpOverlapped);

符号链接的其他用途是“软件驱动程序”，即不管理任何硬件，但需要做用户模式下无法完成的事情。一个典型的例子是Process Explorer的驱动程序，它必须公开一个符号链接，以便Process Explorer本身（驱动程序的客户端）可以打开设备的句柄，并对设备进行DeviceIoControl调用，根据驱动程序建立并为Process Explorer所知的通信协议请求各种服务。

管道有两种变体——匿名和命名，匿名管道是一种简单的单向通信机制，仅限于本地机器。使用CreatePipe创建匿名管道对：

BOOL CreatePipe(PHANDLE hReadPipe, PHANDLE hWritePipe, LPSECURITY_ATTRIBUTES lpPipeAttributes, DWORD nSize);

CreatePipe为管道两端创建控制句柄，使用匿名管道的一个典型示例是将输入和/或输出重定向到另一个进程，允许一个进程将数据提供给另一个进程，而另一个过程不知道，也不关心，它只使用标准句柄进行输入/输出。

下图是管道的一个应用案例。创建匿名管道，并与EnumDevices进程共享其写端，EnumDevices进程写入的任何内容都可以使用管道的读取端读取。要使其工作，管道的写入和必须附加到EnumDevices进程的标准输出，因此任何标准输出调用都可以通过管道使用。

18.11.6 时钟

由于各种原因，时钟（也称为计时器）对于任何多道程序系统的运行都是必不可少的。它们维护一天中的时间，并防止一个进程独占CPU等。时钟软件可以采用设备驱动程序的形式，即使时钟既不是磁盘之类的块设备，也不是鼠标之类的字符设备。

计算机中常用两种类型的时钟，它们都与人们使用的时钟和手表大不相同。较简单的时钟系在110或220伏电源线上，在50或60赫兹的每个电压周期上都会造成中断。这些钟过去占主导地位，但现在很少了。

另一种时钟由三个部件组成：晶体振荡器、计数器和保持寄存器，如下图所示。当一块石英晶体在张力下正确切割和安装时，它可以产生非常精确的周期信号，通常在几百兆赫到几兆赫的范围内，具体取决于所选的晶体。使用电子学，这个基本信号可以乘以一个小整数，得到高达几吉赫甚至更多的频率。通常在任何计算机中都至少有一个这样的电路，为计算机的各个电路提供同步信号。这个信号被输入计数器，使它倒数到零。当计数器归零时，会导致CPU中断。

可编程时钟。

可编程时钟通常有几种操作模式。在一次触发模式（one-shot mode）下，当时钟启动时，它将保持寄存器的值复制到计数器中，然后在来自晶体的每个脉冲处递减计数器。当计数器归零时，它会导致中断并停止，直到软件再次明确启动。在方波模式（square-wave mode）下，在归零并导致中断后，保持寄存器自动复制到计数器中，整个过程无限期地重复。这些周期性中断称为时钟信号。

可编程时钟的优点是其中断频率可以由软件控制。如果使用500 MHz晶体，则计数器每2毫微秒脉冲一次。使用（无符号）32位寄存器，中断可以编程为以2纳秒到8.6秒的间隔发生。可编程时钟芯片通常包含两个或三个独立的可编程时钟，并且还有许多其他选项（例如，向上计数而不是向下计数，中断禁用等等）。

为了防止在计算机电源关闭时丢失当前时间，大多数计算机都有一个电池供电的备用时钟，采用了数字手表中使用的低功耗电路。电池时钟可以在启动时读取。如果备份时钟不存在，软件可能会询问用户当前的日期和时间。网络系统还可以通过一种标准方式从远程主机获取当前时间。在任何情况下，时间都会转换为自1970年1月1日凌晨12点UTC（世界协调时间，以前称为格林威治标准时间）以来的时钟节拍数，就像UNIX一样，或者从其他基准时刻开始。Windows的时间起点是1980年1月1日。在每个时钟周期，实时时间都会增加一个计数。通常提供实用程序来手动设置系统时钟和备份时钟，并同步两个时钟。

18.11.7 电源管理

第一台通用电子计算机ENIAC有18000个真空管，耗电14万瓦。结果，它增加了一笔不平凡的电费。晶体管发明后，用电量急剧下降，计算机行业对电力需求失去了兴趣。然而，由于几个原因，如今电源管理再次成为人们关注的焦点，而操作系统在其中扮演着重要角色。

让我们从台式电脑开始。台式电脑通常有一个200瓦的电源（通常效率为85%，即损失15%的输入能量用于加热），如果全世界一次性开启1亿台这样的机器，它们总共需要2万兆瓦的电力，这是20个平均规模的核电站的总产量。如果电力需求能削减一半，我们就可以摆脱10座核电站。从环境角度来看，摆脱10座核电站（或同等数量的化石燃料电站）是一个巨大的胜利，值得追求。

电源是一个大问题的另一个地方是电池供电的计算机，包括笔记本、手持设备和Webpad等。问题的核心是电池不能保持足够的电量，以维持很长时间，最多几个小时。此外，尽管电池公司、计算机公司和消费电子公司进行了大量研究，但进展缓慢。对于一个习惯于每18个月业绩翻番的行业（摩尔定律）来说，毫无进展似乎违反了物理定律。因此，让电脑使用更少的能源，从而延长现有电池的使用寿命，是每个人的重要议程。操作系统在此也扮演着重要角色。

在最低层次上，硬件供应商正在努力提高电子产品的能效。使用的技术包括减小晶体管尺寸、采用动态电压缩放、使用低摆幅和绝热总线以及类似技术。有两种降低能耗的一般方法：

• 第一种是操作系统在计算机的某些部分（主要是I/O设备）不使用时关闭它们，因为关闭的设备消耗很少或没有能量。
• 第二种是应用程序使用更少的能源，可能会降低用户体验的质量，以延长电池时间。

后面将介绍以上方法，但首先介绍一下与电源使用有关的硬件设计。

18.11.7.1 硬件问题

电池有两种类型：一次性电池和充电电池。一次性电池（最常见的是AAA、AA和D电池）可用于运行手持设备，但没有足够的能量为大屏幕明亮的笔记本电脑供电。相比之下，可充电电池可以储存足够的能量，为笔记本电脑供电几个小时。镍镉电池过去在这里占主导地位，但它们让位给了镍金属氢化物电池，后者寿命更长，在最终被丢弃时不会对环境造成严重污染。锂离子电池甚至更好，可以在不完全耗尽的情况下重新充电，但其容量也受到严重限制。

大多数计算机供应商采取的节约电池的一般方法是将CPU、内存和I/O设备设计为具有多个状态：打开、休眠、休眠和关闭。要使用设备，它必须处于打开状态。当设备在短时间内不需要时，可以将其置于休眠状态，从而降低能耗。当它预计不需要更长的时间间隔时，它可以休眠，从而进一步降低能耗。这里的折衷是，让设备脱离休眠状态通常比让它脱离休眠状态需要更多的时间和精力。最后，当设备关闭时，它什么也不做，也不耗电。并非所有设备都具有所有这些状态，但当它们都具有这些状态时，则由操作系统在适当的时候管理状态转换。

有些电脑有两个甚至三个电源按钮。其中之一可能会使整个计算机处于睡眠状态，通过键入字符或移动鼠标可以快速将其唤醒。另一种可能会使计算机进入休眠状态，从休眠状态唤醒所需的时间要长得多。在这两种情况下，这些按钮通常什么也不做，只是向操作系统发送一个信号，操作系统在软件中执行其余操作。

电源管理带来了操作系统必须处理的许多问题。其中许多与资源休眠有关，有选择地暂时关闭设备，或者至少在设备空闲时降低其功耗。必须回答的问题包括：哪些设备可以控制？它们是开/关，还是有中间状态？在低功率状态下可以节省多少电力？重启设备是否需要消耗能量？进入低功耗状态时必须保存一些上下文吗？恢复满功率需要多长时间？当然，这些问题的答案因设备而异，因此操作系统必须能够处理各种可能性。

不同的研究人员已经对笔记本电脑进行了研究，以确定电源的去向。Li等人、Lorch和Smith（1998）在笔记本电脑设备上进行了测量，得出了如下图中所示的结果。Weiser等人（1994年）也进行了测量但没有公布数值，只是简单地说，前三个电量消耗依次是显示器、硬盘和CPU。虽然这些数字不太一致，可能是因为所测量的不同品牌的计算机确实有不同的能源需求，但显然显示器、硬盘和CPU是节能的明显目标。在智能手机等设备上，可能还有其他耗电设备，如收音机和GPS。

笔记本电脑各部件的功耗。

18.11.7.2 操作系统问题

操作系统在能源管理中起着关键作用，控制着所有的设备，所以它必须决定关闭什么以及何时关闭。如果它关闭了一个设备，并且很快又需要该设备，那么在重新启动时可能会出现恼人的延迟。另一方面，如果等待时间过长而无法关闭设备，则会无谓地浪费能量。

诀窍是找到算法和启发式，让操作系统能够就什么时候关闭以及什么时候关闭做出良好的决定。问题是“好”是高度主观的。一个用户可能会发现，在不使用计算机30秒后，它需要2秒来响应击键，这是可以接受的。在相同的条件下，另一个用户可能会连续一闪而过。在没有音频输入的情况下，计算机无法区分这些用户。

• 显示器

显示器而是能源预算的大户，要获得清晰明亮的图像，屏幕必须背光，需要大量的能量。许多操作系统试图通过在几分钟内没有活动时关闭显示器来节省能源。通常，用户可以决定关机时间间隔，从而在频繁关闭屏幕和快速耗尽电池电量之间进行权衡（用户可能真的不需要）。关闭显示器是一种睡眠状态，因为当按下任何键或移动定点设备时，几乎可以立即（从视频RAM）重新生成显示器。

Flinn和Satyanarayanan（2004年）提出了一个可能的改进方案。他们建议让显示器由一些区域组成，这些区域可以独立通电或断电。在下图中，用虚线分隔了16个区域。当光标位于窗口2中时，如（a）所示，只有右下角的四个区域必须亮起。其他12个可以是暗的，节省了3/4的屏幕电量。

当用户将光标移动到窗口1时，窗口2的区域可以变暗，窗口1后面的区域可以打开。但是，因为窗口1跨越了9个区域，所以需要更多电源。如果窗口管理器可以感知正在发生的事情，它可以自动将窗口1移动到四个区域，并以一种捕捉到区域的动作，如（b）所示。为了实现从9/16全功率到4/16全功率的降低，窗口管理器必须了解电源管理或能够接受来自其他系统的指令。更复杂的是能够部分照亮未完全填满的窗户（例如，包含短行文字的窗户右侧可以保持黑暗）。

使用区域背光显示。（a） 选择窗口2时，它不会移动。（b） 选择窗口1后，它会移动以减少照亮的区域数。

• 磁盘

对于硬盘，即使没有通道，保持高速旋转也需要大量的能量。许多计算机，尤其是笔记本电脑，在空闲一定时间后会降低磁盘转速。当下次需要时，它会再次旋转。不幸的是，停止的磁盘正在蛰伏（hibernating），而不是休眠（sleeping），因为它需要几秒钟才能再次启动，会导致用户明显的延迟。

此外，重新启动磁盘会消耗大量能量。因此，每个磁盘都有一个特征时间TdTd，即盈亏平衡点，通常在5到15秒之间。假设下一次磁盘访问预计在未来的某个时间t到来。如果t<TdTd，保持磁盘旋转所需的能量会更少，而不是先将其向下旋转，然后再快速将其向上旋转。如果t>TdTd，节省的能量使磁盘值得先向下旋转，然后再向上旋转。如果能够做出良好的预测（例如，基于过去的访问模式），操作系统可以做出良好的关机预测并节省能源。实际上，大多数系统都是保守的，只有在几分钟不活动后才会停止磁盘。

另一种节省磁盘能量的方法是在RAM中拥有大量磁盘缓存。如果所需的块在缓存中，则不必重新启动空闲磁盘来满足读取。类似地，如果对磁盘的写入可以在缓存中缓冲，则停止的磁盘不必重新启动即可处理写入。磁盘可以保持关闭状态，直到缓存填满或发生读取未命中。

避免不必要的磁盘启动的另一种方法是，操作系统通过向正在运行的程序发送消息或信号，使其了解磁盘状态。有些程序具有可跳过或延迟的任意写入。例如，可以设置文字处理器，每隔几分钟将正在编辑的文件写入磁盘。如果此时它会正常写入文件，则文字处理器知道磁盘已关闭，它可以延迟此写入，直到打开为止。

• CPU

管理CPU也可以节省能源。笔记本电脑CPU可以在软件中休眠，从而将功耗降至几乎为零。在这种状态下，它唯一能做的就是在发生中断时唤醒。因此，每当CPU空闲时，无论是等待I/O还是因为没有工作可做，它都会进入休眠状态。

在许多计算机上，CPU电压、时钟周期和电源使用之间存在关系。在软件中，CPU电压通常可以降低，这样既节省了能源，又缩短了时钟周期（近似线性）。由于消耗的功率与电压的平方成正比，将电压减半会使CPU的速度减半，但只有1/4的功率。

此属性可用于具有明确期限的程序，例如必须每隔40毫秒解压缩并显示一帧的多媒体查看器，但如果速度更快，则会变为空闲。假设CPU在全速运行40毫秒时使用x焦耳，而x/4焦耳以半速运行。如果多媒体查看器可以在20毫秒内解压缩并显示帧，则操作系统可以满功率运行20毫秒，然后关闭20毫秒，总能耗为x/2焦耳。或者，它可以半功率运行，只需在截止日期前完成，但只需使用x/4焦耳。下图显示了在一段时间间隔内以全速和全功率运行，以及以半速和四分之一功率运行两倍时间的对比。在这两种情况下，都做了相同的功，但在（b）中，只消耗了一半的能量。

（a） 以全速运行。（b） 电压降低两倍，时钟速度减少两倍，功耗减少四倍。

类似地，如果用户以每秒1个字符的速度键入，但处理字符所需的工作需要100毫秒，那么操作系统最好检测到长空闲时间，并将CPU速度降低10倍。简而言之，慢速运行比快速运行更节能。

有趣的是，CPU内核的缩减并不总是意味着性能的降低。Hruby等人（2013）表明，有时网络堆栈的性能会随着内核速度的降低而提高。其解释是，核心可能太快而不利于自身。例如，假设一个CPU有几个快速内核，其中一个内核代表运行在另一个内核上的生产者负责传输网络数据包。生产商和网络堆栈通过共享内存直接通信，它们都在专用内核上运行。生产者执行了相当多的计算，无法完全跟上网络堆栈的核心。在典型的运行中，网络将传输它必须传输的所有内容，并在一定时间内轮询共享内存，以查看是否真的没有更多数据要传输。最后，它会放弃并进入休眠状态，因为连续轮询对功耗非常不利。不久之后，生产者提供了更多数据，但现在网络堆栈处于快速休眠状态。唤醒堆栈需要时间并降低吞吐量。一个可能的解决方案是永远不要休眠，但这也不具有吸引力，因为这样做会增加功耗，而这恰恰与我们试图实现的相反。一个更具吸引力的解决方案是在较慢的内核上运行网络堆栈，这样它就可以一直处于繁忙状态（因此从不休眠），同时还可以降低功耗。如果小心放慢网络核心的速度，其性能将优于所有核心都快得惊人的配置。

• 内存

内存有两种可能的节能选项。首先，可以刷新缓存，然后关闭缓存。它始终可以从主内存重新加载，而不会丢失信息。重新加载可以动态快速完成，因此关闭缓存将进入休眠状态。

一个更激烈的选择是将主内存的内容写入磁盘，然后关闭主内存本身。这种方法是休眠的，因为几乎所有的电源都可以被切断而占用大量的重新加载时间，特别是在磁盘也关闭的情况下。当内存被切断时，CPU要么也必须被切断，要么必须从ROM中执行。如果CPU被切断，唤醒它的中断必须使它跳转到ROM中的代码，以便在使用之前可以重新加载内存。尽管有这么多开销，如果几秒钟内重新启动比从磁盘重新启动操作系统（通常需要一分钟或更长时间）更可取，那么长时间（如数小时）关闭内存可能是值得的。

• 无线通信

越来越多的便携式计算机可以无线连接到外部世界（如互联网）。所需的无线电发射机和接收机通常是一流的电源插座。特别是，如果无线电接收器始终打开以收听传入的电子邮件，电池可能会很快耗尽。另一方面，如果收音机在空闲1分钟后关闭，则可能会错过传入的信息，这显然是不可取的。

Kravets和Krishnan（1998）提出了一个有效的解决方案，利用移动计算机与具有大内存和磁盘且无电源限制的固定基站通信这一事实。他们建议让移动计算机在即将关闭无线电时向基站发送消息，从那时起，基站在其磁盘上缓冲传入的消息。移动计算机可以明确指示它计划休眠多长时间，或者在它再次打开无线电时简单地通知基站。此时，任何累积的消息都可以发送给它。

收音机关闭时生成的传出消息在移动计算机上进行缓冲。如果缓冲区可能已满，则会打开收音机，并将队列传输到基站。收音机应该什么时候关掉？一种可能性是让用户或应用程序决定。另一种方法是在空闲几秒钟后将其关闭。什么时候应该再次打开？同样，用户或程序可以决定，也可以定期打开它来检查入站流量并传输任何排队消息。当然，它也应该在输出缓冲区接近满时打开。其他各种启发方法也是可能的。

在802.11（“WiFi”）网络中可以找到支持这种电源管理方案的无线技术的示例。在802.11中，移动计算机可以通知接入点它将要休眠，但它会在基站发送下一个信标帧之前唤醒。接入点定期发送这些帧，此时，接入点可以告诉移动计算机它有待处理的数据。如果没有此类数据，移动计算机可以再次休眠，直到下一个信标帧。

• 热量管理

一个稍有不同但仍与能源相关的问题是热量管理（Thermal Management）。现代CPU由于其高速而变得异常热，台式机通常有一个内部电风扇，用于将热空气吹出机箱。由于降低功耗通常不是台式机的驱动问题，因此风扇通常一直处于开启状态。

笔记本电脑的情况有所不同。操作系统必须连续监测温度，当温度接近最大允许温度时，操作系统可以选择。它可以打开风扇，这会产生噪音并消耗电力。或者，它可以通过减少屏幕背光、降低CPU速度、更积极地降低磁盘转速等方式来降低功耗。

用户的一些输入可能有价值，可以作为指导。例如，用户可以事先指定风扇的噪音令人反感，因此该操作系统反而会降低功耗。

• 电量管理

在过去，电池只是提供电流，直到完全耗尽，然后停止，再也没有了。移动设备现在使用智能电池，可以与操作系统通信。根据操作系统的请求，它们可以报告最大电压、电流电压、最大充电、电流充电、最大漏电流率、电流漏电流率等信息。大多数移动设备都有可以运行的程序来查询和显示所有这些参数，还可以指示智能电池在操作系统的控制下更改各种操作参数。

有些笔记本电脑有多个电池。当操作系统检测到一个电池即将用完时，它必须安排一个优雅的切换到下一个电池，而不会在转换过程中造成任何故障。当最后一块电池即将耗尽时，操作系统将向用户发出警告，然后有序关闭，例如确保文件系统未损坏。

• 设备接口

一些操作系统有一种称为ACPI（Advanced Configuration and Power Interface，高级配置和电源接口）的精细电源管理机制。操作系统可以发送任何一致的驱动程序命令，要求它报告其设备的功能及其当前状态。当与即插即用结合时，此功能尤其重要，因为在启动后，操作系统甚至不知道存在哪些设备，更不用说它们的能耗或电源管理属性了。

它还可以向驱动发送命令，指示他们降低功率水平（当然，取决于它之前学到的能力）。另外还有一些传输信号，特别是，当键盘或鼠标等设备在闲置一段时间后检测到活动时，这是系统返回（接近）正常操作的信号。

18.11.7.3 应用程序问题

到目前为止，我们已经研究了操作系统如何减少各种设备的能耗。但还有另一种方法：告诉程序使用更少的能源，即使更差的用户体验（当电池耗尽和灯熄灭时，糟糕的体验比没有体验要好）。通常，当电池电量低于某个阈值时，会传递此信息。然后由程序决定是降低性能以延长电池寿命，还是保持性能和能源耗尽风险。

这里出现的一个问题是，程序如何降低性能以节省能源。Flinn和Satyanarayanan（2004）研究了这个问题，他们提供了四个性能降低如何节省能源的例子。在此研究种，信息以各种形式呈现给用户。当不存在退化时，将提供尽可能好的信息。当出现降级时，呈现给用户的信息的保真度（准确性）比本来的要差。

为了测量能源使用量，Flinn和Satyanarayanan设计了一种称为PowerScope的软件工具，它所做的是提供程序的电源使用配置文件。要使用它，计算机必须通过软件控制的数字万用表连接到外部电源。使用万用表，软件能够读取电源输入的毫安数，从而确定计算机消耗的瞬时功率。PowerScope所做的是定期对程序计数器和电源使用情况进行采样，并将这些数据写入文件。程序终止后，对文件进行分析，以给出每个过程的能量使用情况，这些测量结果构成了他们观察的基础。还采用了硬件节能措施，并形成了衡量性能下降的基线。

测量的第一个节目是视频播放器。在未分级模式下，它以全分辨率和彩色播放30帧/秒。降级的一种形式是放弃颜色信息，以黑白显示视频。另一种形式的降级是降低帧速率，会导致闪烁，并给电影带来显著降低的质量。还有一种退化形式是通过降低空间分辨率或缩小显示图像来减少两个方向上的像素数。这种措施节省了大约30%的能源。

第二个程序是语音识别器。它对麦克风进行采样，以构造波形，这个波形可以在笔记本电脑上分析，也可以通过无线链路发送到固定电脑上进行分析。此举可以节省CPU能量，但会消耗无线电能量。降级是通过使用更小的字和更简单的声学模型来完成的，节省率约为35%。

下一个例子是通过无线电链接获取地图的地图查看器。降级包括将地图裁剪成较小的尺寸，或告诉远程服务器忽略较小的道路，从而减少传输的比特数。这里再次实现了约35%的收益。

第四个实验是将JPEG图像传输到Web浏览器。JPEG标准允许使用各种算法，将图像质量与文件大小进行权衡，平均增益只有9%。总之，实验表明，通过接受一些质量下降，用户可以在给定的电池上运行更长的时间。