用来决定块设备上 IO 操作提交顺序的方法，主要是用于提高吞吐量、降低响应时间。然而两者是相互矛盾的，为了尽量平衡这两者，Linux 内核提供了多种调度算法来适应不同的 IO 请求场景。

这里简单介绍下 Linux 中的 IO 调度器。

Linux IO 调度算法 #

Linux 2.6 引入了新的 IO 调度子系统，其总体目标是希望让磁头可以沿着一个方向移动，移动到底了再往反方向走，这恰恰类似于现实生活中的电梯模型，所以对应的调度算法也就叫做电梯算法。

内核中的电梯算法包括了：AS(Anticipatory)、CFQ(Complete Fairness Queueing)、Deadline、NOOP(No Operation)，可以在启动的时候通过内核参数指定，默认使用的是 CFQ 。

可以通过如下方式查看或者设置 IO 的调度算法。

----- 查看当前系统支持的IO调度算法
# dmesg | grep -i scheduler
io scheduler noop registered
io scheduler anticipatory registered
io scheduler deadline registered
io scheduler cfq registered (default)

----- 查看当前系统的IO调度方法
$ cat /sys/block/BLOCK-DEVICE/queue/scheduler
noop anticipatory deadline [cfq]

----- 临时修改IO调度方法
$ echo "noop" > /sys/block/BLOCK-DEVICE/queue/scheduler

----- 永久修改参数
# vim /boot/grub/menu.lst
kernel /boot/vmlinuz-2.6.32-504.el6 ro root=LABEL=/ elevator=deadline quiet

NOOP #

全称为 No Operation，实际上就是实现了最简单的 FIFO 队列，所有 IO 请求基本会按照先进先出的规则操作，不过对于一些相邻的还是做了 IO 请求合并，而非完全按照 FIFO 规则。

----- 有如下的IO请求序列
100, 500, 101, 10, 56, 1000
----- 经过NOOP算法处理之后会按照如下顺序处理
100(101), 500, 10, 56, 1000

这一算法是 2.4 之前版本的唯一调度算法，计算比较简单，从而减少了 CPU 的使用，不过容易造成 IO 请求饿死。

其应用环境主要有以下两种：一是物理设备中包含了自己的 IO 调度程序，比如 SCSI 的 TCQ；二是寻道时间可以忽略不计的设备，比如 SSD 等。

CFQ #

CFQ (Complete Fair Queuing) 完全公平的排队。

该算法会按照 IO 请求的地址进行排序，而非按照 FIFO 的顺序进行响应。该算法为每个进程/线程单独创建一个队列来管理该进程所产生的请求，各队列之间的调度使用时间片来调度，以此来保证每个进程都能被很好的分配到 IO 带宽。

这是一种 QoS 的 IO 调度算法，为每一个进程分配一个时间窗口，在该时间窗口内，允许进程发出 IO 请求。通过时间窗口在不同进程间的移动，保证了对于所有进程而言都有公平的发出 IO 请求的机会；同时 CFQ 也实现了进程的优先级控制，可保证高优先级进程可以获得更长的时间窗口。

----- 有如下的IO请求序列
100，500，101，10，56，1000
----- 经过CFQ算法处理之后会按照如下顺序处理
100，101，500，1000，10，56

在传统机械磁盘上，寻道会消耗绝大多数的 IO 响应时间，所以 CFQ 尽量减小磁盘的寻道时间。

CFQ 适用于系统中存在多任务 IO 请求的情况，通过在多进程中轮换，保证了系统 IO 请求整体的低延迟。但是，对于只有少数进程存在大量密集的 IO 请求的情况，会出现明显的 IO 性能下降。

通过 CFQ 算法可以有效提高 SATA 盘的整体吞吐量，但是对于先来的 IO 请求并不一定能被满足，也可能会出现饿死的情况，对于通用的服务器也是比较好的选择。

CFQ 是 Deadline 和 AS 调度器的折中，对于多媒体应用和桌面系统是最好的选择。

配置参数 #

CFQ 调度器主要提供如下参数。

$ ls /sys/block/BLOCK-DEVICE/queue/iosched/

slice_idle
	如果一个进程在自己的时间窗口里，经过 slice_idle 时间都没有发送 IO 请求，则调度选择下一个程序。
quantum
	该参数控制在一个时间窗口内可以发送的 IO 请求的最大数目。
low_latency
	对于 IO 请求延时非常重要的任务，可以打开低延迟模式来降低 IO 请求的延时。

DEADLINE #

在 CFQ 的基础上，解决了 IO 请求可能会被饿死的极端情况，除了 CFQ 本身具有的 IO 排序队列之外，还分别为读 IO 和写 IO 提供了 FIFO 队列，读 FIFO 队列的最大等待时间为 500ms，写 FIFO 队列的最大等待时间为 5s。

也就是说针对 IO 请求的延时而设计，每个 IO 请求都被附加一个最后执行期限。该算法维护两类队列，一是按照扇区排序的读写请求队列；二是按照过期时间排序的读写请求队列。

如果当前没有 IO 请求过期，则会按照扇区顺序执行 IO 请求；如果发现过期的 IO 请求，则会处理按照过期时间排序的队列，直到所有过期请求都被发送为止；在处理请求时，该算法会优先考虑读请求。

FIFO 队列内的 IO 请求优先级要比 CFQ 队列中的高，而读 FIFO 队列的优先级又比写 FIFO 队列的优先级高，也就是说 FIFO(Read) > FIFO(Write) > CFQ 。

参数配置 #

当系统中存在的 IO 请求进程数量比较少时，与 CFQ 算法相比，DEADLINE 算法可以提供较高的 IO 吞吐率，主要提供如下参数。

$ ls /sys/block/BLOCK-DEVICE/queue/iosched/

writes_starved
	该参数控制当读写队列均不为空时，发送多少个读请求后，允许发射写请求。
read_expire
	参数控制读请求的过期时间，单位毫秒。
write_expire
	参数控制写请求的过期时间，单位毫秒。

该算法适用于数据库环境，如 MySQL、PostgreSQL、ES 等。

Anticipatory #

CFQ 和 DEADLINE 主要聚焦于一些零散的 IO 请求上，而对于连续的 IO 请求，比如顺序读写，并没有做优化。

该算法在 DEADLINE 的基础上，为每个读 IO 都设置了 6ms 的等待时间窗口，如果在这 6ms 内 OS 收到了相邻位置的读 IO 请求，就可以立即处理。

参考 #

内核中与存储相关的内核栈可以参考 Linux Storage Stack Diagram ，一个很不错的图。