在现代计算机体系中，机械硬盘仍然作为大部分情况下的存储设备使用，而机械硬盘的访问相对内存差了多个数量级，主要原因在于机械臂转动的寻道时间太长，机械操作没法跟上电子信号的传递，所以OS不可能对每次I/O请求都直接作寻道处理，而是需要额外的工作。
在Linux中，这部分工作主要由I/O调度器完成。
既然时间消耗主要花费在寻道上，那么减少寻道时间就成为I/O调度算法的核心，这主要是通过对I/O请求实施合并和排序完成的。I/O调度器的主要工作是管理像磁盘这种块设备的请求队列，并分配I/O资源给请求。目标是提升全局吞吐量，注意，这意味着I/O请求并不是按照FIFO来处理，而是存在不公平的现象，原理类似于公平锁和非公平锁。
I/O调度器通过合并和排序完成调度任务。
合并是指将两个或多个请求结合成一个新的请求，例如当新来的请求和当前请求队列中的某个请求需要访问的是相同或相邻扇区时，那么就可以把两个请求合并为对同一或多个相邻扇区的请求，这样只需要一次寻道即可。通过合并的做法，多个I/O请求被压缩为一次I/O，最后发送给磁盘的只需要一条寻址命令，就能完成多次寻址同样的效果。显然，合并请求能减少系统开销和磁盘寻址次数。
解决了对相邻扇区的访问，那么对于非相邻扇区呢？我们知道机械臂的转动是朝着扇区增长的方向的，类似于电梯，那么如果我们把I/O请求按照扇区增长排列，一次旋转就可以访问更多的扇区，就可以缩短所有请求的实际寻道时间。这便是I/O调度器的另一项任务：排序。
1、Linus电梯
上面说到排序操作导致的结果和电梯类似，所以早期Linux的I/O调度算法被称为电梯算法，在2.4内核中，被称作Linus电梯。
Linus电梯实现了向前合并和向后合并，对应扇区的增长和减少，而排序操作则如同上面所说的，通过将新请求插入到已有请求队列中合适的位置去实现。那么这里就有一个问题了，如果一个请求比较倒霉，老是被插队怎么办？Linus电梯解决这个问题的办法是当一段时间后检测到队列中有长期没有被处理的请求，那么就暂时中止插入，将新请求直接放到队列尾部，寄希望于顺序处理当前队列中现有的请求来保证响应。但这种做法的缺点在于，I/O调度器并没有真正去处理饥饿的请求，而是采取了一种间接的方式，所以很有可能饥饿的请求仍然饥饿，并没有解决实质的问题。
2、DeadLine
为了解决Linus电梯的饥饿问题，DeadLine在全局吞吐量和延迟方面取了权衡。在DeadLine算法中，每个I/O请求都有一个超时时间，默认读请求是500ms，写请求是5s。
DeadLine除了和Linus电梯一样维护了一个拥有合并和排序功能的请求队列以外，额外维护了两个队列，分别是读请求队列和写请求队列，它们都是带有超时的FIFO队列。当新来一个I/O请求时，会被同时插入普通队列和读/写队列，然后处理普通队列中的请求。当调度器发现读/写请求队列中的请求超时的时候，会优先处理这些请求，保证尽可能不产生请求饥饿。当然，这里会牺牲一定的全局吞吐量。
3、Anticipatory
DeadLine解决了饥饿问题，但是降低了全局吞吐量，当系统大量存在顺序请求时，可能导致请求无法被很好地排序，引发频繁寻道。
Anticipatory是基于预测的I/O算法，大体上它和DeadLine很类似，也维护了三个请求队列。区别在于，当它处理完一个I/O请求以后并不会直接返回处理下一个请求，而是会等待片刻，默认为6ms。如果这时候有新来的针对当前扇区相邻扇区的请求，那么会直接处理它，当等待时间结束后，调度器才返回处理下一个队列请求。
试想一下，如果系统有频繁的针对邻近扇区的I/O请求，那么这种预测算法必然大幅提高整体的吞吐量，毕竟节约了那么多寻道时间。Anticipatory也是当前Linux内核默认的I/O调度器。
更新：在Linux Kernel 2.6.28 的Anticipatory/CFS算法中，对于块设备增加了QUEUE_FLAG_NONROT的标志位，标记随机访问设备以消除等待时间的开销。感谢 @fbcon 的提醒：）
4、CFQ(Complete Fair Queuing)
CFQ把I/O请求按照进程分别放入进程对应的队列中，所以A进程和B进程发出的I/O请求会在两个队列中。而各个队列内部仍然采用合并和排序的方法，区别仅在于，每一个提交I/O请求的进程都有自己的I/O队列。
CFQ的“公平”是针对进程而言的，它以时间片算法为前提，轮转调度队列，默认从当前队列中取4个请求处理，然后处理下一个队列的4个请求。这样就可以确保每个进程享有的I/O资源是均衡的。
5、Noop
Noop做的事情非常简单，它不会对I/O请求排序也不会进行任何其它优化（除了合并）。Noop除了对请求合并以外，不再进行任何处理，直接以类似FIFO的顺序提交I/O请求。
那么为什么我们需要这种调度器呢？因为Noop面向的不是普通的块设备，而是随机访问设备（例如SSD），对于这种设备，不存在传统的寻道时间，那么就没有必要去做那些多余的为了减少寻道时间而采取的事情了。
从上面的算法中我们可以看到，对于不同的场景，选择不同的I/O调度器是十分有必要的。例如对于数据库这种随机访问特别明显的场景，如果使用默认的Anticipatory，就会牺牲大量不必要的等待时间，这时候使用DeadLine通常是更好的选择。对于SSD这种设备，采用Noop或者DeadLine也通常能获得比默认调度器更好的性能。
