FIOS，即 Flash IO Scheduler，出自 FAST'2012的一篇论文 FIOS: a fair, efficient flash I/O scheduler，致力于解决在 NAND Flash 上存在的公平性问题。我们知道 Linux 已有一个着重公平性的 IO 调度器：CFQ，并且已经发展的非常成熟，那为何又出来一个 FIOS 呢，且听我一一道来。

---

SSD 面临的调度问题

要突出一个东西的好，就要有对比。SSD 面临的调度问题就是 CFQ 在 NAND Flash 上的缺点，到目前应用于 SSD 的调度器通常是 NOOP 或 DeadLine，如果使用 CFQ，反而会造成性能更差。问题如下：

1. 读写性能差异带来 IO 瓶颈
2. 读可能被写阻塞，导致读写不公平
3. 严格的读优先可能导致同步写的不公平
4. 目前的公平调度器针对 flash 读/写性能的差异不能很好的处理
5. 过渡的 IO 预期将会导致很长的空闲时间，会显著降低 flash 性能
6. CFQ 没有将 SSD 的并发特性使用起来

要分析以上问题，我们就要基于下面的已知条件：SSD 的读写不平衡。不同于机械硬盘，大量的时间开销在于寻道，SSD 不存在寻道操作，因此写入的速度远远慢于读取的速度。CFQ 不会严格筛选出读请求，那么必然存在写请求阻塞读请求的情况，导致同步的读请求迟迟得不到处理。此外 CFQ 还存在一个 IO 预期的操作，相对于机械硬盘而言，这个预期的时间是比较合理的，通常是 8 ms，而对于 SSD 而言，由于单个请求的处理速度比机械硬盘快得多，那么相对过长的预期将是一种浪费。FIOS 针对 SSD 的特性提出了一种新的设计思路，总结为下面 4 个设计点：

• 公平时间片管理
• 读写干扰管理
• 并行发送请求
• 更加有限的 IO 预期

---

公平时间片管理

与 CFQ 一样，FIOS 也采用时间片的调度，不同之处在于，FIOS 将时间片打散，引入一个新的概念：epoch。epoch 是一组时间片的集合，IO调度器在每个epoch上实现公平性，我们后面会详细介绍调度过程。一个任务的时间片可以在一个 epoch 内的几个非连续时间段使用，一旦一个任务消耗完了当前 epoch 内属于它的时间片，就必须等待下一个 epoch 刷新其时间片。下图是一个 epoch 的示意图。

在 CFQ 中，一轮调度中所有任务的时间片按照以时间片为单位依次排列，时间片消耗光后再刷新所有时间片开启一轮新的调度；而在 FIOS 中，一轮 epoch 调度中，只要任务还有时间片，就有可能在 epoch 的任意位置被调度，这样能够很好的减少空转的等待时间。

一轮 epoch 结束并且开始新的 epoch 的条件为：

• 当前 epoch 中所有任务都没有可用时间片；或
• 当前 epoch 中还有可用时间片的任务没有新的 IO 请求

---

读写干扰管理

为了减少写请求对读请求造成的阻塞，FIOS 简单的采取了读取优先策略。

• 当读/写请求在 IO 调度队列中排队时，读取优先策略将优先发出读请求，并阻止所有写请求，直到完成完整的读取
• 只有写入已经发出后，读请求到达时，才会被写请求阻塞
• 优先读取策略会导致额外的写请求排队时间，但是由于读请求更快，所以相对而言写请求的额外排队时间较小
• 读取优先策略仍受制于基于 epoch 的时间片管理的控制，因此可以防止写入的饥饿

下图举例：假设每个进程的时间片为 3，P1-R 表示进程 1 的读请求，P2-W 表示进程 2 的写请求。当读/写请求在 IO 调度队列中排队时，读取优先策略将优先发出读请求，并阻止所有写请求，直到完成完整的读取。

只有写入已经发出后，读请求到达时，才会被写请求阻塞。

读取优先策略仍受制于基于epoch的时间片管理的控制，因此可以防止写入的饥饿。

---

并行发送请求——IO 开销计算

由于 SSD 设备内部存在并行，如果连续下发了数个请求，请求实际被并行执行，而在调度器中被计算成了串行的时间开销，会造成一定程度的不准确——即：任务的请求没有用那么多时间，却被计算成了那么多时间，导致这一轮调度能够被执行的请求数减少，导致了调度的不公平。FIOS 使用两种方法来核准 IO 开销。

线性核准

• 大前提：假设 IO 请求的时间开销和数据大小之间是线性关系
• 首先校准不同数据大小的读/写请求的开销时间，并根据校准结果的类型（读/写）和大小，计算出 IO 请求的时间开销
• 其中只校准了四种情况：4KB 读、128KB 读、4KB 写、128KB 写

方法一不可用时，将采用备用方法进行 IO 成本核算。

平均法核准

大前提：假设在设备上一组未完成的 IO 请求保持不变（不发出新的请求或完成未完成的请求）期间，所有未完成的 IO 请求均等地共享此时段的设备使用开销。IO 开销计算公式：

举例来说，例如下面在某个时间段 T 内，下发了 P 个请求，并且等待到它们执行完成并回调，则每个请求的时间开销都是 cost = T / P。

---

更加有限的 IO 预期

IO 预期最开始在磁盘上的使用目的是为了提高性能；在 SSD 中主要的作用是保证公平性。我们考虑两个问题：

• 何时进行预期？
• 预期多长时间？

何时进行预期

当一个请求刚刚完成时，始终考虑预期。将拥有刚刚完成的请求的任务称为预期任务。

1. 当预期任务快速处理刚刚完成的 I/O 请求并发出另一请求时，欺骗性空闲可能会打破公平的时间片管理。这种情况下采用如下的处理方法：

   • 如果预期任务没有非零剩余时间片，则 epoch 正常结束
   • 如果预期任务具有非零剩余时间片，则在 epoch 切换之前进行预测
2. 欺骗性空闲可能会破坏优先读策略，当发出读取请求的任务很少时，可能存在请求队列中没有读请求的情况。为了保证优先读取策略，在完成读取请求后，需要一个 IO 预期。因为立即发出写入请求可能会阻止后面的读取。

预期多长时间

机械硬盘中的 IO 预期大致设置为磁盘 IO 操作的时间，即 6-8ms。但是 SSD 中大不相同，SSD 上的 IO 预期不会改善性能，使用 IO 预期的目的是维持公平性，因为 flash IO 服务时间远小于磁盘 IO 操作时间，这会加剧 flash 上 IO 预期引起的设备空闲成本。

FIOS 根据可容忍性能损失的可配置阈值设置 I/O 预期的界限，以保持公平性。用阈值 α 表示用于预计公平性的最大时间比例，确保最大设备空闲时间不超过设备总时间的 α 比例。IO 预期的时间为：

其中 Tserve 是通过计算该任务过去的指数加权移动平均值得到的，每个任务都有一个 Tservice；FIOS 设置的 α 默认值为 0.5。最后要说明这里的 IO 预期的时间成本需要计算到预期任务的时间片中。

更多细节请阅读 FIOS 论文原文。

（完）

---

参考文献

[1] Park S, Shen K. FIOS: a fair, efficient flash I/O scheduler[C]//FAST. 2012: 13.