​ 每个块设备或者块设备的分区，都对应有自身的请求队列，而每个请求队列都可以选择一个I/O调度器来协调所递交的request。I/O调度器的基本目的是将请求按照它们对应在块设备上的扇区号进行排列，以减少磁头的移动，提高效率。每个设备的请求队列里的请求将按顺序被响应。实际上，除了这个队列，每个调度器自身都维护有不同数量的队列，用来对递交上来的request进行处理，而排在队列最前面的request将适时被移动到请求队列中等待响应。

调度算法

CFQ

​ CFQ（Completely Fair Queuing）算法，顾名思义，绝对公平算法。它试图为竞争块设备使用权的所有进程分配一个请求队列和一个时间片，在调度器分配给进程的时间片内，进程可以将其读写请求发送给底层块设备，当进程的时间片消耗完，进程的请求队列将被挂起，等待调度。

​ 每个进程的时间片和每个进程的队列长度取决于进程的IO优先级，每个进程都会有一个IO优先级，CFQ调度器将会将其作为考虑的因素之一，来确定该进程的请求队列何时可以获取块设备的使用权。IO优先级从高到低可以分为三大类:RT(real time),BE(best try),IDLE(idle),其中RT和BE又可以再划分为8个子优先级。实际上，我们已经知道CFQ调度器的公平是针对于进程而言的，而只有同步请求(read或syn write)才是针对进程而存在的，他们会放入进程自身的请求队列，而所有同优先级的异步请求，无论来自于哪个进程，都会被放入公共的队列，异步请求的队列总共有8(RT)+8(BE)+1(IDLE)=17个。

​ 从Linux 2.6.18起，CFQ作为默认的IO调度算法。

​ 对于通用的服务器来说，CFQ是较好的选择。

Deadline

​ Deadline使用了两种不同的数据结构来管理请求：排序队列是基于红黑树的，根据请求的块号排序；FIFO队列使用双向链表，按照请求到达的顺序排列。

​ Deadline把请求按照读写方向分成两类。同时维持4个队列：两个排序队列以及两个FIFO队列，根据读写方向把请求放置到对应的排序队列和 FIFO队列中。

​ 在分派请求的过程中，Deadline首先选择一个排序队列(读或者写)，按照扇区号由小到大的顺序分派16(可以通过fifo_batch修改)请求。请求的分派过程类似于磁盘的C—SCAN调度策略。当该排序队列已经没有请求可以分派，Deadline选择另一个方向的排序队列进行分派。选择队列时的方向默认为读，只有写请求队列被忽略2次(Writes_starved)后，算法才会选择写请求队列。Deadline把读和写分开处理，且读请求的优先级高于写请求，是因为读请求一般是同步的，可以阻塞进程的运行，而写请求大多是系统在空闲时才发的(例如脏页的回写)，适当的延迟对系统整体性能影响不大。

1）读写请求分离，读请求具有高优先调度权，除非写请求即将被饿死的时候，才会去调度处理写请求。这种处理可以保证读请求的延迟时间最小化。

2）对请求的顺序批量处理。对那些地址临近的顺序化请求，deadline给予了高优先级处理权。例如一个写请求得到调度后，其临近的request会在紧接着的调度过程中被处理掉。这种顺序批量处理的方法可以最大程度的减少磁盘抖动。

3）保证每个请求的延迟时间。每个请求都赋予了一个最大延迟时间，如果达到延迟时间的上限，那么这个请求就会被提前处理掉，此时，会破坏磁盘访问的顺序化特征，回影响性能，但是，保证了每个请求的最大延迟时间。

不足之处

CFQ

​ 由于缺乏Linux电梯框架提供的信息，CFQ无法正确地将请求映射到进程导致不公平。此外，文件系统排序要求限制了CFQ的重新排序选项，从而导致优先级倒置。为了克服这两个缺点，我们引入了AFQ（实际公平队列调度程序），以根据优先级在进程间公平地分配I/O。

Deadline

​ 由于在文件系统排序要求存在时无法重新排序块I/O，所以Block-Deadline在试图限制尾部延迟时表现得很差。

改进

AFQ

​ AFQ采用两级调度策略。读取在块级处理，写入在系统调用级别处理。这种设计允许读取命中高速缓存，同时保护写入不受日志纠缠的影响。

​ 命中高速缓存：

​ 块级可以应用程序->缓存->文件系统->块级队列，就可以实现对于缓存的读取。直接系统调用是应用程序->块级队列，无法读取缓存。

​ 写入不受日志纠缠：

​ 如果用块级调用的话，日志会以为p3(p1、p2的回写代理）把DataPage弄脏了，事实上是p1、p2弄脏的。

Deadline

​ Split-Deadline使用缓冲区脏钩子监视一个缓存文件的脏污程度，从而估算fsync的成本。如果存在可能通过导致过多I / O而影响其他进程的fsync挂起，则不会直接调度。相反，调度程序要求内核启动文件脏数据的异步写回，并等待，直到脏数据量下降到一定程度，以便发出的fsync不会影响其他截止日期。异步写回不会生成文件系统同步点，也没有截止日期，因此不会强制其他操作等待。

所谓同步，就是调用后直到返回结果，程序才继续往下运行。

异步，就是调用后立刻执行之后的代码。调用的结果以事件/委托在不确定的一段时间以后才返回。