虽然大多数 Linux 用户都熟悉进程调度器的作用，例如新的 O(1) 调度器，但许多用户不太熟悉 I/O 调度器的作用。I/O 调度器在某些方面与进程调度器类似；例如，两者都在多个用户之间调度某些资源。进程调度器在系统上多个正在执行的进程之间虚拟化处理器时间资源。那么，I/O 调度器调度什么呢？

一个简单的系统甚至不会包含 I/O 调度器。与进程调度器不同，I/O 调度器不是操作系统的强制组件。相反，性能是 I/O 调度器的唯一 raison d'être（存在理由）。

为了理解 I/O 调度器的作用，让我们回顾一些背景信息，然后看看没有 I/O 调度器的系统是如何运行的。硬盘使用大家熟悉的基于几何的柱面、磁头和扇区寻址来寻址其数据。硬盘驱动器由多个盘片组成，每个盘片包含单个磁盘、主轴和读/写头。每个盘片进一步划分为环形磁道，类似于 CD 或唱片。最后，每个磁道由一些整数个扇区组成。

为了在硬盘驱动器中定位特定的数据单元，驱动器的逻辑需要三条信息：柱面、磁头和扇区。柱面指定数据所在的磁道。如果您将盘片彼此叠放（就像在硬盘中一样），给定的磁道会在每个盘片上形成一个柱面。然后，磁头识别出确切的读/写头（以及因此确切的盘片）。现在搜索范围缩小到单个盘片上的单个磁道。最后，扇区值表示磁道上的确切扇区。搜索完成：硬盘知道数据驻留在哪个盘片上的哪个磁道上的哪个扇区。它可以将正确盘片的读/写头定位在正确的磁道上，并读取正确的扇区。

值得庆幸的是，现代硬盘驱动器不强迫计算机以柱面、磁头和扇区的形式与它们通信。相反，现代硬盘驱动器将唯一的块号映射到每个柱面/磁头/扇区三元组上。唯一的数字标识特定的柱面/磁头/扇区值。然后，现代操作系统可以使用此块号（称为逻辑块寻址）来寻址硬盘驱动器，而硬盘驱动器将块号转换为正确的柱面/磁头/扇区值。

关于此块号需要注意的一点是：虽然没有任何保证，但物理映射往往是顺序的。也就是说，逻辑块 n 倾向于在物理上与逻辑块 n+1 相邻。我们稍后讨论为什么这很重要。

现在，让我们考虑典型的 UNIX 系统。各种应用程序（如数据库、电子邮件客户端、Web 服务器和文本编辑器）都会向磁盘发出 I/O 请求，例如读取此块和写入彼块。这些块往往在物理上分布在磁盘的各个位置。电子邮件假脱机可能位于磁盘上与 Web 服务器的 HTML 数据或文本编辑器的配置文件完全不同的区域。实际上，如果文件是碎片化的，即未按顺序块布局，则即使是单个文件也可能散布在整个磁盘上。由于文件被分解为单个块，而硬盘驱动器是通过块而不是更抽象的文件概念来寻址的，因此读取或写入文件数据被分解为许多单个 I/O 请求的流，每个请求都针对不同的块。幸运的是，这些块是顺序的，或者至少在物理上彼此靠近。如果这些块彼此不靠近，则磁盘头必须移动到磁盘上的另一个位置。移动磁盘头称为寻道，它是计算机中最昂贵的操作之一。现代硬盘驱动器上的寻道时间以数十毫秒为单位。这就是碎片整理文件是一件好事的原因之一。

不幸的是，文件是否碎片整理并不重要，因为系统正在为磁盘上的多个文件生成 I/O 请求。电子邮件客户端想要从这里获取一点，而 Web 服务器想要从那里获取一点——但是等等，现在文本编辑器想要读取一个文件。最终结果是磁盘头在磁盘上跳来跳去。在最坏的情况下，对于多个文件的交错 I/O 请求，磁头可能会花费所有时间从一个位置跳到另一个位置——这对整体系统性能不利。

这就是 I/O 调度器的用武之地。I/O 调度器调度挂起的 I/O 请求，以最大限度地减少移动磁盘头所花费的时间。这反过来又最大限度地减少了磁盘寻道时间，并最大限度地提高了硬盘吞吐量。

这种魔力是通过两个主要操作实现的：排序和合并。首先，I/O 调度器将挂起的 I/O 请求列表按块号排序。当发出新的 I/O 请求时，它会按块插入到挂起的请求列表中。这可以防止驱动器头在磁盘上到处寻道以服务 I/O 请求。相反，通过保持列表排序，磁盘头在磁盘上直线移动。如果硬盘驱动器正忙于在磁盘的某个部分服务请求，并且新的请求进入磁盘的同一部分，则可以在移动到磁盘的其他部分之前服务该请求。

当向磁盘的相同或相邻区域发出 I/O 请求时，会发生合并。与其单独发出新请求，不如将其合并到相同或相邻的请求中。这最大限度地减少了未完成请求的数量。

让我们看一个例子。考虑两个应用程序向以下块号发出请求的情况，这些请求以以下顺序到达内核：10、500、12、502、14、504 和 12。没有 I/O 调度器的方法将按给定的顺序服务这些块。那是七次长寻道，在磁盘的两个部分之间来回寻道。真是浪费！但是，如果内核对这些请求进行排序和合并，并按该顺序服务它们，结果将大不相同：10、12、14、500、502 和 504。只有一个远距离寻道，并且总体上少了一个请求。

通过这种方式，I/O 调度器在多个 I/O 请求之间虚拟化磁盘 I/O 资源，以最大限度地提高全局吞吐量。由于 I/O 吞吐量对于系统性能至关重要，并且寻道时间非常慢，因此 I/O 调度器的工作非常重要。

在 2.4 Linux 内核中找到的 I/O 调度器名为 Linus 电梯。I/O 调度器通常被称为电梯算法，因为它们解决的问题类似于保持电梯在大楼中平稳运行的问题。Linus 电梯的功能几乎与上面描述的经典 I/O 调度器完全相同。在大多数情况下，这很棒，因为简单性是一件好事，并且 2.4 内核的 I/O 调度器运行良好。不幸的是，在 I/O 调度器追求最大化全局 I/O 吞吐量的过程中，做出了一些权衡：本地公平性——特别是请求延迟——很容易被忽略。让我们看一个例子。

考虑对逻辑磁盘块（例如 20、30、700 和 25）的请求流。I/O 调度器的排序算法将按以下顺序对请求进行排队和发出（假设磁盘头当前位于磁盘的逻辑开头）：20、25、30 和 700。这是预期之中的，而且确实是正确的。但是，假设在服务块 25 的请求过程中，另一个请求进入磁盘的同一部分。然后又来一个。又一个。完全有可能对块 700 的请求在相对较长的时间内未得到服务。

更糟糕的是，如果请求是读取磁盘块怎么办？读取请求通常是同步的。当应用程序发出读取某些数据的请求时，它通常会阻塞并等待，直到内核返回数据。应用程序必须坐着等待，无所事事，直到对块 700 的请求最终得到服务。另一方面，写入通常不是同步的——它们是异步的。当应用程序发出写入时，内核将数据和元数据复制到内核中，准备一个缓冲区来保存数据，然后返回到应用程序。应用程序实际上并不关心甚至不知道数据何时实际到达磁盘。

然而，对于我们的朋友读取请求来说，情况变得更糟。由于写入是异步的，因此写入往往会流式传输。也就是说，通常会发生大量数据的写回。这意味着许多单独的写入请求被提交到硬盘驱动器的近距离区域。例如，考虑保存一个大文件。应用程序会尽快将其调度的写入请求转储到系统和硬盘驱动器上。

相反，读取请求通常不会流式传输。相反，应用程序以小的、逐个的块提交读取请求，每个块都依赖于上一个块。考虑读取目录中的所有文件。应用程序打开第一个文件，发出读取文件适当块的请求，等待返回的数据，发出读取下一个块的请求，等待并继续这样做，直到读取整个文件。然后关闭文件，打开下一个文件，并重复该过程。每个后续请求都必须等待上一个请求，这意味着如果请求是针对远距离磁盘块的，则此应用程序会出现大量延迟。流式写入请求使依赖读取请求饥饿的现象称为写入饿死读取（请参阅侧边栏“测试 1. 写入饿死读取”）。

while true
do
        dd if=/dev/zero of=file bs=1M
done

time cat 200mb-file > /dev/null

在合理的时间内不服务某些请求的可能性称为饥饿。请求饥饿会导致不公平。在 I/O 调度器的情况下，系统明确决定牺牲公平性来提高全局吞吐量。也就是说，系统试图以牺牲任何特定 I/O 请求为代价来提高系统的整体性能。这是可以接受的，实际上也是期望的——除非长时间的饥饿是不好的。即使在适度的时间内使读取请求饥饿也会导致在其他磁盘活动期间发出读取请求的应用程序出现高应用程序延迟。这种高读取延迟会对系统性能和感觉产生不利影响（请参阅侧边栏“测试 2. 高读取延迟的影响”）。

防止请求（特别是读取请求）的饥饿是新的 2.6 I/O 调度器的目标。

引入 Deadline I/O 调度器是为了解决围绕 2.4 I/O 调度器和传统电梯算法的饥饿问题。正如所讨论的，Linus 电梯在单个队列中维护挂起的 I/O 请求的排序列表。队列头部的 I/O 请求是下一个要服务的请求。Deadline I/O 调度器继续保留此队列，但通过引入两个额外的队列（读取 FIFO 队列和写入 FIFO 队列）使事情更进一步。Deadline I/O 调度器将每个队列中的项目按提交时间排序（实际上，先进先出）。顾名思义，读取 FIFO 队列仅包含读取请求。同样，写入 FIFO 队列仅包含写入请求。每个 FIFO 队列都分配有一个到期值。读取 FIFO 队列的到期时间为 500 毫秒。写入 FIFO 队列的到期时间为 5 秒。

当提交新的 I/O 请求时，它会被插入排序到标准队列中，并放置在其各自的（读取或写入）FIFO 队列的尾部。通常，硬盘驱动器从标准排序队列的头部接收 I/O 请求。这通过最大限度地减少寻道来最大限度地提高全局吞吐量，因为正常队列按块号排序，就像 Linus 电梯一样。

但是，当 FIFO 队列之一的头部的项目比与其队列关联的到期值更旧时，I/O 调度器会停止从标准队列调度 I/O 请求。相反，它会服务 FIFO 队列头部的 I/O 请求，并额外服务几个作为额外的措施。I/O 调度器只需要检查和处理 FIFO 队列头部的请求，因为这些是队列中最旧的请求。

还记得我们的老朋友，对块 700 的请求吗？尽管对远距离块的写入请求泛滥，但在 500 毫秒后，Deadline I/O 调度器将停止服务这些请求，并服务块 700 上的读取。磁盘将寻道到块 700，服务读取请求，然后继续服务其他未完成的请求。

通过这种方式，Deadline I/O 调度器可以对 I/O 请求强制执行软期限。尽管它不保证在到期时间之前服务 I/O 请求，但 I/O 调度器通常会在接近到期时间时服务请求。因此，Deadline I/O 调度器继续提供良好的全局吞吐量，而不会使任何一个请求长时间饥饿。由于读取请求被赋予较短的到期时间，因此写入饿死读取问题被最小化。

这一切都很好，但这并不是一个完美的解决方案。考虑一下我们虚构的对块 700 的请求会发生什么，这可能是对磁盘该区域的许多依赖读取中的第一个。在服务读取请求后，Deadline I/O 调度器继续服务对较早块的写入请求。这很好，直到读取应用程序提交其下一个读取请求（例如，对块 710）。在 500 毫秒内，该请求到期，磁盘寻道到块 710，服务请求，寻道回之前的位置，并继续服务流式写入。然后另一个读取到达。

问题再次源于那些该死的依赖读取。由于读取是以依赖块发出的，因此应用程序仅在上一个读取返回时才发出下一个读取。但是，当应用程序收到读取数据、被调度运行并提交下一个读取时，I/O 调度器已经继续前进并开始服务其他一些请求。这导致每次读取都浪费了一对寻道：寻道到读取，服务它，然后寻道回来。如果只有某种方法可以让 I/O 调度器知道——不，是预料到——很快就会向磁盘的同一部分提交另一个读取。它可以等待预料到下一个读取，而不是来回寻道。节省那些可怕的寻道当然值得等待几毫秒；我们节省了两次寻道。

当然，这正是预读 I/O 调度器所做的。它最初是 Deadline I/O 调度器；它实现了相同的基于期限的调度。但它被赋予了预 anticipatory 机制的附加功能。当提交读取请求时，预读 I/O 调度器会在其期限内像往常一样服务它。但是，与 Deadline I/O 调度器不同，预读 I/O 调度器然后坐着等待，什么也不做，长达六毫秒。应用程序很可能在这六毫秒内向文件系统的同一部分发出另一个读取。如果是这样，则立即服务该请求，并且预读 I/O 调度器会等待更长时间。如果六毫秒过去了而没有读取请求，则预读 I/O 调度器猜错了，并返回到它之前正在执行的操作。

即使适度数量的请求被正确预 anticipatory，也会节省大量时间（每次两次昂贵的寻道）（表 1）。由于大多数读取都是依赖的，因此预 anticipatory 大部分时间都会奏效。为了进一步提高正确预 anticipatory 的几率，预读 I/O 调度器使用启发式方法来更好地猜测要等待哪些进程。为此，调度器维护有关每个进程的 I/O 统计信息，以跟踪其行为。由于这些统计信息和智能启发式方法，预读 I/O 调度器在足够大的时间内正确预 anticipatory 应用程序的操作，这非常值得开销。

通过最大限度地减少不必要的寻道并更快地服务读取请求，在许多工作负载中，预读 I/O 调度器比 Deadline I/O 调度器和 Linus 电梯提供更好的请求延迟和全局吞吐量。毫不奇怪，预读 I/O 调度器是 2.6 内核中的默认 I/O 调度器。理所当然地，它很棒。

Andrea Arcangeli 和 Jens Axboe 是 Linus 电梯的主要作者。Jens Axboe 是 Deadline I/O 调度器的主要作者。Nick Piggin 是预读 I/O 调度器的主要作者。