关键词：
Linux 内核包含4个IO调度器，分别是 Noop IO scheduler、Anticipatory IO scheduler、Deadline IO scheduler 与 CFQ IO scheduler。
anticipatory, 预期的；提早发生的；期待着的
通常磁盘的读写影响是由磁头到柱面移动造成了延迟，解决这种延迟内核主要采用两种策略：缓存和IO调度算法来进行弥补.
本文做一简单介绍.
调度算法概念
- 当向设备写入数据块或是从设备读出数据块时,请求都被安置在一个队列中等待完成.
- 每个块设备都有它自己的队列.
- I/O调度程序负责维护这些队列的顺序,以更有效地利用介质.I/O调度程序将无序的I/O操作变为有序的I/O操作.
- 内核必须首先确定队列中一共有多少个请求,然后才开始进行调度.
IO调度器（IO Scheduler）
IO调度器（IO Scheduler）是操作系统用来决定块设备上IO操作提交顺序的方法。存在的目的有两个，一是提高IO吞吐量，二是降低IO响应时间。然而IO吞吐量和IO响应时间往往是矛盾的，为了尽量平衡这两者，IO调度器提供了多种调度算法来适应不同的IO请求场景。其中，对数据库这种随机读写的场景最有利的算法是DEANLINE。
IO调度器在内核栈中所处位置如下：
块设备最悲剧的地方就是磁盘转动，这个过程会很耗时间。
每个块设备或者块设备的分区，都对应有自身的请求队列(request_queue),而每个请求队列都可以选择一个I/O调度器来协调所递交的request。I/O调度器的基本目的是将请求按照它们对应在块设备上的扇区号进行排列，以减少磁头的移动，提高效率。每个设备的请求队列里的请求将按顺序被响应。实际上，除了这个队列，每个调度器自身都维护有不同数量的队列，用来对递交上来的request进行处理，而排在队列最前面的request将适时被移动到请求队列中等待响应。
IO scheduler 的作用主要是为了减少磁盘转动的需求。主要通过2中方式实现：
1.合并
2.排序
每个设备都会自己对应请求队列，所有的请求在被处理之前都会在请求队列上。 在新来一个请求的时候如果发现这个请求和前面的某个请求请求的位置是相邻的，那么就可以合并为一个请求。如果不能找到合并的，就会按照磁盘的转动方向进行排序。通常IO scheduler 的作用就是为了在进行合并和排序的同时，也不会太影响单个请求的处理时间。
1、NOOP
FIFO
- noop是什么?
noop是一种输入输出调度算法 . NOOP, No Operation. 什么都不做，请求来一个处理一个。这种方式事实起来简单，也更有效。问题就是disk seek 太多，对于传统磁盘，这是不能接受的。 但对于SSD 磁盘就可以，因为SSD 磁盘不需要转动。 - noop的别称
又称为电梯调度算法. - noop原理是怎样的?
将输入输出请求放到一个FIFO队列中，然后按次序执行队列中的输入输出请求:
当来一个新请求时:
- 如果能合并就合并
- 如果不能合并，就会尝试排序。 如果队列上的请求都已经很老了，这个新的请求就不能插队，只能放到最后面。否则就插到合适的位置
- 如果既不能合并，有没有合适的位置插入，就放到请求队列的最后。
- 适用场景
4.1 在不希望修改输入输出请求先后顺序的场景下；
4.2 在输入输出之下具有更加智能调度算法的设备，如NAS存储设备；
4.3 上层应用程序已经精心优化过的输入输出请求；
4.4 非旋转磁头式的磁盘设备，如SSD磁盘
2、CFQ(Completely Fair Queuing, 完全公平排队)
CFQ（Completely Fair Queuing）算法，顾名思义，绝对公平算法。它试图为竞争块设备使用权的所有进程分配一个请求队列和一个时间片，在调度器分配给进程的时间片内，进程可以将其读写请求发送给底层块设备，当进程的时间片消耗完，进程的请求队列将被挂起，等待调度。
每个进程的时间片和每个进程的队列长度取决于进程的IO优先级，每个进程都会有一个IO优先级，CFQ调度器将会将其作为考虑的因素之一，来确定该进程的请求队列何时可以获取块设备的使用权。
IO优先级从高到低可以分为三大类:
RT(real time)
BE(best try)
IDLE(idle)
其中RT和BE又可以再划分为8个子优先级。可以通过ionice 去查看和修改。 优先级越高，被处理的越早，用于这个进程的时间片也越多，一次处理的请求数也会越多。
实际上，我们已经知道CFQ调度器的公平是针对于进程而言的，而只有同步请求(read或syn write)才是针对进程而存在的，他们会放入进程自身的请求队列，而所有同优先级的异步请求，无论来自于哪个进程，都会被放入公共的队列，异步请求的队列总共有8(RT)+8(BE)+1(IDLE)=17个。
从Linux 2.6.18起，CFQ作为默认的IO调度算法。对于通用的服务器来说，CFQ是较好的选择。具体使用哪种调度算法还是要根据具体的业务场景去做足benchmark来选择，不能仅靠别人的文字来决定。
3、DEADLINE
DEADLINE在CFQ的基础上，解决了IO请求饿死的极端情况。
除了CFQ本身具有的IO排序队列之外，DEADLINE额外分别为读IO和写IO提供了FIFO队列。
读FIFO队列的最大等待时间为500ms，写FIFO队列的最大等待时间为5s（当然这些参数都是可以手动设置的）。
FIFO队列内的IO请求优先级要比CFQ队列中的高，，而读FIFO队列的优先级又比写FIFO队列的优先级高。优先级可以表示如下：
FIFO(Read) > FIFO(Write) > CFQ
deadline 算法保证对于既定的 IO 请求以最小的延迟时间，从这一点理解，对于 DSS 应用应该会是很适合的。
deadline 实际上是对Elevator 的一种改进:
1 避免有些请求太长时间不能被处理。
2 区分对待读操作和写操作。
deadline IO 维护3个队列。第一个队列和Elevator 一样， 尽量按照物理位置排序。 第二个队列和第三个队列都是按照时间排序，不同的是一个是读操作一个是写操作。
deadline IO 之所以区分读和写是因为设计者认为如果应用程序发了一个读请求，一般就会阻塞到那里，一直等到的结果返回。 而写请求则不是通常是应用请求写到内存即可，由后台进程再写回磁盘。应用程序一般不等写完成就继续往下走。 所以读请求应该比写请求有更高的优先级。
在这种设计下，每个新增请求都会先放到第一个队列，算法和Elevator的方式一样，同时也会增加到读或者写队列的尾端。这样首先处理一些第一队列的请求，同时检测第二/三队列前几个请求是否等了太长时间，如果已经超过一个阀值，就会去处理一下。 这个阀值对于读请求时 5ms， 对于写请求时5s.
个人认为对于记录数据库变更日志的分区，例如oracle 的online log， mysql 的binlog 等等，最好不要使用这种分区。 因为这类写请求通常是调用fsync 的。 如果写完不成，也会很影响应用性能的。
4、ANTICIPATORY
CFQ和DEADLINE考虑的焦点在于满足零散IO请求上。对于连续的IO请求，比如顺序读，并没有做优化。
为了满足随机IO和顺序IO混合的场景，Linux还支持ANTICIPATORY调度算法。ANTICIPATORY的在DEADLINE的基础上，为每个读IO都设置了6ms的等待时间窗口。如果在这6ms内OS收到了相邻位置的读IO请求，就可以立即满足。
小结
IO调度器算法的选择，既取决于硬件特征，也取决于应用场景。
在传统的SAS盘上，CFQ、DEADLINE、ANTICIPATORY都是不错的选择；对于专属的数据库服务器，DEADLINE的吞吐量和响应时间都表现良好。然而在新兴的固态硬盘比如SSD、Fusion IO上，最简单的NOOP反而可能是最好的算法，因为其他三个算法的优化是基于缩短寻道时间的，而固态硬盘没有所谓的寻道时间且IO响应时间非常短。
番外篇
SUSE Linux Enterprise Server 11 SP1 provides a number of I/O scheduler alternatives to optimize for different I/O usage patterns. You can use the elevator= option at boot time to set the scheduler for I/O devices or you can assign a specific I/O scheduler to individual block devices.
Completely Fair Queuing (CFQ) scheduler
The Completely Fair Queuing (CFQ) scheduler is the default I/O scheduler for SUSE Linux Enterprise Server 11 SP1. The CFQ scheduler maintains a scalable per-process I/O queue and attempts to distribute the available I/O bandwidth equally among all I/O requests. The effort balancing of I/O requests has some CPU costs.
Deadline scheduler
The Deadline scheduler is one alternative to the CFQ scheduler. The deadline scheduler uses a deadline algorithm to minimize I/O latency by attempting to guarantee a start time for an I/O request. The scheduler attempts to be fair among multiple I/O requests and to avoid process starvation. This scheduler wills aggressively re-order requests to improve I/O performance.
NOOP scheduler
The NOOP scheduler is another alternative, that can help minimize the costs of CPU utilization of managing the I/O queues. The NOOP scheduler is a simple FIFO queue that uses the minimal amount of CPU/instructions per I/O operation to accomplish the basic merging and sorting functionality to complete the I/O operations.
I/O scheduler test results
In this test, twenty-three of the spinning hard disks attached to System B are replaced by fifty-two 73 GB SAS SSD devices for main database space.
Table 1 compares the database performance with the 3 different I/O schedulers using all of the workloads. We see that the in the mixed read/write workloads (2 and 4) the NOOP scheduler has a negative impact on performance and so should not be used for these workloads. The Deadline I/O scheduler shows a performance benefit when run against the smaller workloads on lesser performing storage while having no impact on the larger workloads with better performing storage.
Note
Values shown in the following table are the Performance metric result.
I/O scheduler conclusions
For the workloads used in this test, the Deadline scheduler was a better choice overall than the default CFQ scheduler. It yielded a higher throughput in the smaller workloads and performed equally to the CFQ scheduler in the larger workloads. While these particular workloads performed best with the deadline scheduler, not all workloads benefit equally from the same scheduler. If optimal performance is an requirement, it is worthwhile to investigate the benefits of each I/O scheduler for your workloads.
参考资料
https://www.bilibili.com/read/cv4365546
htmlhttps://www.ibm.com/support/knowledgecenter/en/linuxonibm/performance/tuneforsybase/ioschedulers.htm
Kotlin 开发者社区
国内第一Kotlin 开发者社区公众号，主要分享、交流 Kotlin 编程语言、Spring Boot、Android、React.js/Node.js、函数式编程、编程思想等相关主题。
越是喧嚣的世界，越需要宁静的思考。
《linux内核设计与实现》学习笔记——i/o调度算法
I/O调度子系统用于调度来自多个进程对块设备的I/O请求。电梯调度首先，如果队列中已存在一个对相邻磁盘扇区操作的请求，那么新请求将和这个已经存在的请求合并为一个请求。2.如果队列中存在一个驻留时间过长的请求，那... 查看详情
进程调度
Linux进程调度：在linux2.5内核系列中，开始采用O(1)调度程序，但是其缺少交互进程。在2.6内核系统开发初期，引入新的进程调度算法-反转楼梯最后期限调度算法（RotatingStaircaseDeadlinescheduler）（RSDL）。该算法吸取了队列理论，将... 查看详情
linux磁盘io调度算法(代码片段)
A、CFQ（完全公平排队I/O调度程序）最新的内核版本和发行版中，都选择CFQ做为默认的I/O调度器，对于通用的服务器是最好的选择。CFQ对于多媒体应用（video，audio）和桌面系统是最好的选择。CFQ赋予I/O请求一个优先级，而I/O优先... 查看详情
io调度算法
...I/O调度程序将无序的I/O操作变为有序的I/O操作. 4)内核必 查看详情
linux-linux内核-进程调度
文章目录Linux内核-进程调度一、进程调度的原理（1）多任务分类（2）进程分类（3）优先级二、进程状态（1）三状态模型（2）进程的切换（3）状态字段定义（4）psaux中的stat... 查看详情
1.4.cfs调度算法(代码片段)
...的组织，可以认为是资源面的组织方式，调度系统需要对内核进程（线程）进行调度，对于内核进程的组织也可以分为单个的内核进程和内核进程组的区别，无论是单个的内核进程还是内核进程组，只要是参与调度的运行实体，... 查看详情
linux-linux内核-进程调度
文章目录Linux内核-进程调度一、进程调度的原理（1）多任务分类（2）进程分类（3）优先级二、进程状态（1）三状态模型（2）进程的切换（3）状态字段定义（4）psaux中的stat... 查看详情
调度算法
参考：OS中常用的调度算法总结调度算法的介绍及优缺点linux进程（任务）调度算法进程类型：IO消耗型（交互）处理器消耗型（计算）进程两种不同的优先级：nice值，普通进程实时优先级，实时进程调度器，目的是允许不同类... 查看详情
linux进程管理之进程调度与切换
...关调度相关的结构保存在task_struct中，如下：active_mm是为内核线程而引入的，因为内核线程没有自己的地址空间，为了让内核线程与普通进程具有统一的上下文切换方式，当内核线程进行上下文切换时，让切换进来的线程的active_... 查看详情
centos-内核核心组成
linux内核，相当于linux大脑，高可靠和高稳定都是针对内核来说完整linux核心组成部分 1. 内存管理 合理有效的管理整个系统的物理内存，同时快速响应内核各子系统对内存分配的请求 2. 进程管理 ... 查看详情
lvs调度算法
内核中的连接调度算法IPVS在内核中的负载均衡调度是以连接为粒度的。在HTTP协议（非持久中），每个对象从WEB服务器上获取都需要建立一个TCP连接，同一用户的不同请求会被调度到不同服务器上，所以这种细粒度的调度在一定... 查看详情
linux进程的调度
...使一个Linux调度程序可以有多个不同的调度策略。1）关闭内核抢占，初始化部分变量。获取当前CPU的ID号，并赋值给局部变量CPU，使rq指向CPU对应的运行队列。标识当前CPU发生任务切换，通知R 查看详情
lvs理论2--算法
在内核中的连接调度算法上，IPVS已实现了以下十种调度算法1.轮叫调度2.加权轮叫调度3.最小连接调度4.加权最小连接调度5.基于局部性的最小链接6.带复制的基于局部性最少链接7.目标地址三列调度8.源地址散列调度9.最短预期延... 查看详情
深入理解linux内核之主调度器（下）
4.进程上下文切换接前文：深入理解Linux内核之主调度器（上）前面选择了一个合适进程作为下一个进程，接下来做重要的上下文切换动作，来保存上一个进程的“上下文”恢复下一个进程的“上下文”，... 查看详情
rt-thread内核线程调度算法（基于位图的线程调度算法）(代码片段)
在实时操作系统中，对时间的要求度很高，所以在线程调度算法RT-Thread采用的是位图调度算法，时间复杂度为O(1)。本篇采用最大优先级为32的情况进行讲解，256与之类似。/*Maximumprioritylevel,32*/rt_uint32_trt_thread_ready_priority_group;... 查看详情
linux内核线程kernelthread详解--linux进程的管理与调度(代码片段)
内核线程为什么需要内核线程Linux内核可以看作一个服务进程(管理软硬件资源，响应用户进程的种种合理以及不合理的请求)。内核需要多个执行流并行，为了防止可能的阻塞，支持多线程是必要的。内核线程就是内核的分身，... 查看详情
课程学习总结报告(代码片段)
Linux内核主要由以下几个功能：进程管理、文件系统、IO体系结构和设备驱动程序、内存管理等。一.进程管理在Linux中，进程是系统资源分配的基本单位，也是使用CPU运行的基本调度单位。它实现了对进程的控制和调度。进程管... 查看详情
linux进程调度
...力调度进程，尽力使进程在它的限定时间到来前运行，但内核不保证总能满足这些进程的要求，相反，硬实时系统保证在一定的条件下，可以满足任何调度的要求。SCHED_NORMAL使用完全公平调度算法（CFS），之前的算法直接将nice... 查看详情