常见的I/O调度算法
写在草稿纸上，之前的工作早晚会被埋没了。
之前看了一下SSD的I/O调度算法，发现里面大有文章。
看的还是Stan Park的论文：https://dblp.org/rec/html/conf/fast/ParkS12
该论文有15页。该论文的中心内容为作者自行研发的一套SSD I/O调度器，为了体现出其性能的优越性，作者将其与一些常见的Linux I/O调度器进行了性能比较，包括应用程序综合性能和读写公平程度两大方面。毕竟，这个I/O调度器的目的是为了解决由SSD基本结构造成的读写不公平性。（读写操作共用相同队列，但是写入时间要远远长于读取时间，按照最短任务，最先执行Shortest Job First, SJF的理论来看，让大量耗时较短的读取操作等待耗时较长的写入操作完成，会对性能有相当大的负面影响；当然也不能一味地优先读取，这样对写入也不公平，让一定时间内的读取任务优先执行即可）
-
NOOP 仿佛是No Operation的缩写。（= =）正如其名字一样，一个队列，先来先走，不做任何操作。在实际情况下根据算法实现者的考虑，可能会对任务按照地址进行一定的顺序重排，这样能够减少一定的I/O时间（最明显的是机械硬盘，连续读取省去了磁头机械臂移动带来的额外等待耗时），但整体思路就是按先来后到发送I/O请求。
-
CFQ Linux下经常使用的一个I/O调度器，全名为
Completely Fair Queueing，即完全公平队列。采用类似模拟的方法计算任务的发送顺序，给每个任务建立一个单独的请求队列，然后分配相同的时间片给每个队列用以执行请求。由于公平性问题在网络（不是社交网络，理解成设备之间通信的网络比较好）上也有需求，可以借鉴一下CFQ在网络上的解决方法：由于网络层传输数据是按照包来的，显然在包头定义完长度之后整个包的大小就确定了，包的传输中断的话会被对方主机认为包损坏，因而在网络层包不可拆。所以采用这么一个办法：用计算机模拟包的预计传输时间，每次发送预计完成最早的包，在宏观上就有着近似的效果。但是由于我没有深入研究Linux上的具体实现方法，在磁盘I/O上的具体规则如何有待考证。 -
WFQ
Weighted Fair Queueing，加权公平队列，是CFQ的一种改版，可以为不同优先级的队列分配对应合适的时间片长度。 -
Deadline https://blog.csdn.net/hs794502825/article/details/24664259 照着链接看了一下源码，没看完，说的太具体了，讲的是在Linux系统中的实现，而不是算法本身的思路。
-
Anticipation 翻译为中文是预测。该算法主要针对在HDD上运行、需要连续读取数据的应用。如上文NOOP中略微提到过的请求重排序一样，该算法会在单次I/O请求结束后较短的时间内，强制空闲I/O设备，等待可能出现的连续地址的请求。这样对于某些加载-处理类型的任务较为友好。解决的问题是“假空闲”：一个任务的I/O请求执行完毕后，可能还没有发送下一请求；此时系统认为该程序程序暂时不需要I/O，开始处理其他程序的I/O请求。而可能恰恰在1-2ms后，该任务发出了下一I/O请求，可是却需要等到其他任务的请求执行完成后才能得到处理。（个人举例是MD5校验码的计算：MD5计算可以使用当前已计算的部分，即已经获得的部分内容的MD5码，追加需要计算部分的数据进行计算。这样做的目的是节约内存，不然一次加载整个文件的话，有的设备内存会吃不消。则程序的运行流程可视为：读取数据-合并至已有的部分数据MD5-读取数据-继续合并MD5，直至整个文件加载完成，完成整个文件的MD5计算）似乎Anticipation的等待时间典型值为6ms。但是由于该方法使用场景过于狭窄（尤其是现在多任务系统，而且不会都是连续读取型请求，所以强制空闲反而可能降低整体I/O效率），所以现在的Linux内核基本上都是不用这个的，仅作为替选方案存在于<=4.x版本的Linux内核中。
- Deficit Round Robin
毛。。咳咳，俄罗斯友人的一项传统游戏，一把左轮，一发子弹，一人一枪，看谁先中。这里的Round Robin有着类似的规则，所有程序轮流使用相同时间的稀缺资源（如磁盘或网络I/O），直到任务执行完成。而这里的
Deficit一词直译为赤字，引申为赊欠，表示在一个Round Robin轮回中没有使用完的时间可以加到下一轮回。没有用完分配时间的原因是，原子性的任务耗时若是小于可用的剩余时间，将不能执行，因而有很大概率会剩下零散的时间片。若是忽略每个程序可能剩下的不等资源片，又会在整体上表现出资源分配的不公平性。因而，采取占用一点资源的方式，记录下每个任务所剩下的未使用资源，在下一个周期补上，能够有效地弥补其公平性。A：你们玩吧，今天我不参加了BC等：行，我们先玩，明天多给他来两枪与上面的冷笑话相反的是，在系统中程序是不会嫌资源多的。