2.4.18预读算法详解

琢磨ULK2时的一些个人理解。参考了WFG的这篇文章：

如果觉得有必要，以后会写写其他版本预读算法的实现分析及改进逻辑。

一 为什么需要预读

1 I/O合并 2 延迟隐藏
参见上述链接。

二 预读算法初步设计

设read系统调用的内核实现函数为do_generic_read。如果不考虑预读，直观上讲，其实现用伪码表示，应该是如下形式：


do_genric_read（）
{
    for(read系统调用需读取的所有页){
        if（页不在pagecache）{
            分配page加入pagecache；
            锁住page；
            启动对page的I/O传送；
         }
        等待当前页I/O传送完成；
        copy当前页数据到用户空间；
    }
}

在上述表示中，我们将核心流程进行简化：只在读取新页时启动I/O；如果page已经在pagecache里时，说明它要么包含有效数据，要么在page新加入到pagecache时，已经启动I/O。在不考虑I/O错误时，这种简化是可行的。

如果考虑预读，有两种形式的预读：同步预读与异步预读。
每个read系统调用需要读取的所有页面是连续的，它们应被一次性同步预读。称为“同步”，是因为read需同步等待这些页面I/O完成。当read与前 一个read在文件内的位置是顺序的，说明它正在顺序读取文件，此时应进行异步预读：启动对read“最后一个页面之后”的一组连续页面的预读，为下一个 顺序read提前准备数据，从而形成流水线预读。称为“异步”，是因为后续read的I/O启动与数据处理是异步进行的。

特别友情提醒：本文以后出现的“read”都是指read系统调用。

检测顺序读还有一个特例。当文件被打开后的第一次读，并且读的是文件首部时，我们善意推定，后续的read会是顺序的，因此需进行异步预读。如果不满足上述顺序性条件，就判定为随机读。任何一个随机读都将终止当前的顺序序列，从而终止预读行为。

利用这两种预读，尽最大可能隐藏I/O延迟。其实现用伪码表示，变成如下形式：

do_genric_read（）
{
    generic_read_ahead（read需读取的所有页）/* 启动同步预读 */
    if（顺序读）
        /* 启动异步预读*/
        generic_read_ahead（read最后一页之后的一组连续页面）；
     /* 等待同步预读完成 */
    for(read需读取的所有页){
        等待当前页I/O传送完成；
        copy当前页数据到用户空间；
    }
}

注意：do_genric_read并不需要等待异步预读I/O传送完成。

generic_read_ahead（预读的所有页）
{
    for(预读的所有页){
      if(页不在pagecache){
      分配page加入pagecache；
      锁住page；
      启动对page数据的I/O传送；
     }
  }
}

注意：generic_read_ahead只是启动页I/O传送，但并不等待I/O完成。
异步预读的“一组连续页面”在读文件开始时可设置一个初值，如“read需读取的所有页”的2倍。在顺序读时，其额度可不断加大（例如加倍），直至某一个上限，后面还会讲到这一点。

上述实现的特点是：
1 同步预读的页面肯定会被用到，不会浪费；异步预读的页面不一定被用到，如果后续读不是顺序的，就可能部分或全部被浪费掉。
2 同步预读是为当前read服务的，因此有较小的预读组；而异步预读是为顺序读形成流水线服务的，应该有较大的预读组。
3 我们一开始就启动所有可能的预读，这是一种有“确定预读时机”的方案。

三 上述实现中的问题

我们使用预读，是希望程序在处理一批数据时，硬盘能在后台把下一批数据给CPU事先准备好，以便CPU和硬盘能流水线作业。流水线预读的所达到的理想状态 是：当read向“同步预读”的页面发出请求时，页面已经由前一个read的“异步预读”读入内存，因此read无须等待I/O传送。

考虑这样的情形：

假设read“同步预读”的第一页被锁。如果它是由前一个read（或更之前的read）的“异步预读”启动I/O传送的， 说明I/O传送尚未完成。显然，对比理想状态，I/O传送速度要慢于进程运行速度。这可能是I/O系统负担太重，也可能是进程处理太快。无论哪种情形，此 时再启动其他预读I/O（它与前一个read发出的I/O请求不太可能合并），不但于事无补，很可能加重I/O负担，使得I/O传送速度更慢。但在实现 中，read的同步预读是无条件地启动所有页的I/O传送（如果它不是被前一个read异步预读启动的话），因此可能导致系统性能问题。

再考虑这样的情形：

假设read是顺序的，其“异步预读”的第一页未锁，说明I/O传送已经完成。如果此页是由“前一个read”异步预读启动I/O，为达到流水线预读的理 想状态，此时启动下一轮预读是可行的。但如果此页是由“前一个read之前的read”启动I/O，显然，I/O传送速度要快于进程运行（可能是进程计算 量太大），预读的页面数量相对很充足了，此时，启动其他预读I/O，会使得预读页面过早过多占据pagecache空间，而且一旦后续读并非顺序读，会导 致I/O处理时间与pagecache空间的浪费。但在实现中，只要read为顺序读，其“异步预读”也是无条件的，同样会导致系统性能问题。

四 提出新的设计

结合上面的分析，要使预读发挥最大的效益，必须对要预读的页考虑两个因素：其I/O传送是否已经由前一个read或更前的read启动；它是否仍处于I /O传送中。前者需要记录“预读历史”，后者需要跟踪页面加锁状态。记录“预读历史”后，还能明确知道新的预读究竟从何处开始。read需根据两个因素的 组合特性，决定是否启动预读I/O。我们考虑在预读中记录预读历史，然后将“确定预读时机”转化为“动态预读时机”：在处理每个页的读操作时，执行“与此 页状态相关”的预读：由这个预读根据页加锁状态及预读历史，动态决定是否启动预读I/O。其基本原则是：当页是由“以前的预读”启动I/O并且加锁时，不 要启动新的预读；当页是由“最近一次”预读启动I/O，并且页未锁时，应该启动新的预读。需要强调的是：“以前的预读”不但包括“最近一次预读”，但还包 括更早的预读。

我们还应注意到一点，当预读与页绑定在一起时，我们无法象原实现一样，独立启动针对顺序读的异步预读，而预读函数无法自己判断顺序读。所以，应当给预读函数传递一个表示顺序读的标志。伪码如下：

do_genric_read（）
{
    int reada_ok=0;        /* 表示是否顺序读的标志 */
    if（顺序读）reada_ok=1;
    for(read需读取的所有页){
        if（页不在pagecache）{
          分配page加入pagecache；
          锁住page；
          启动对page的I/O传送；
       }
       generic_read_ahead（page,reada_ok，file）；/*与此页状态相关的预读，page指当前页 */
       等待当前页I/O传送完成；
       copy当前页数据到用户空间；
   }
}

generic_read_ahead（page,reada_ok,file）
{
    根据reada_ok标志，page加锁状态及预读历史，确定是否启动预读I/O；
}

五 详细分析generic_read_ahead的设计

从直观上看，我们希望上述实现在循环读取页的过程中，某一次读取会触发同步预读，另一次读取会触发异步预读，其他读取不会触发预读。这样，就与原实现在语义上等价。（真实的情形不一定是这样，后面会看到例子）

1 记录预读历史

先考虑如何记录预读历史。我们称最近一次预读的页面集合为一个预读组，显然，记录预读组是必须的，我们将预读组记录在file对象中。按照前面的分析，当 顺序读命中预读组时，如果页未锁，正是推进下一次预读的最佳时机：需要启动新一轮预读I/O，在紧跟预读组尾部的位置设置新的预读组，以包含新的预读页 面。如果页被锁，则不推进预读。因此，每一个后续的顺序读都可能产生一个新的预读组，那么，是否需要记录所有这些预读组呢？我们注意到一点，触发建立新预 读组的读操作，其读取的页包含在前一个预读组中，因此，后续的顺序读可能仍访问前一个预读组，但不可能访问前一个预读组之前的页。因此，对顺序读，只需记 录最近两个预读组即可。我们将最近两个预读组合并成预读窗口，作为总的预读历史记录在file对象中。当然，如果前面的reads只预读过一次，仅有一个 预读组时，则预读窗口即为预读组。显然，当预读往前推进，设置新的预读组时，预读窗口也在同步推进。需要强调的是，因为需要区分最近一次预读和以前的预 读，所以预读窗口不能完全替代预读组。预读组和预读窗口的设置，与每次预读的大小息息相关，我们将表示“下一个预读的大小”的字段f_ramax也记录在 file对象中。

2 启动预读时机

有了预读组与预读窗口的定义，关于预读启动时机的基本原则可初步描述为：当读取的页被锁并命中预读窗口时，不要启动新的预读；当读取的页未锁并命中预读组 时，应该启动新的预读。在这个原则的约束下，在read循环读取页面时，究竟何时启动一个预读，使它能对应“同步预读”？当读是顺序时，也即 reada_ok为1时，何时启动另一个预读，使它能对应“异步预读”？

考虑这样的情形。在read读取的页面中，前一部分页面在预读窗口中，正等待I/O传送完成。考察在预读窗口外的第一页，因为它没有被前面的预读启动I /O，很可能不在pagecache中，直到本次读取页面的操作，将页加入pagecache并启动I/O，此时页面被锁，需要等待I/O操作完成。而其 后需读取的页面，当然也很可能都不在pagechache中。因此，此时是启动“同步预读”的最佳时机。需要注意的是，当页在预读窗口外，而页未锁时，说 明页早已在pagecache中（例如被其他进程装入内存），此时，无须启动同步预读，因为不用等待I/O操作完成，“启动同步预读”的时间不会被隐藏。

启动了同步预读后，会设置新的预读组，包含其后需读取的所有页面。在read继续往前读取页面时，发现某页未锁（此页必然在预读组中），如果read是顺序读，此时，应触发新的预读，即“异步预读”。当然，如果read不是顺序读，就不应触发异步预读。

因此，预读启动时机的基本原则可总结为：
a 当页被锁并且不在预读窗口中时，启动同步预读。
b 当读是顺序的（reada_ok为1），页未锁，且页在预读组中时，启动异步预读。
c 当读不是顺序时，禁止异步预读。
d 其他情形下，不能启动预读。

需要提到的是，为了在等待同步预读完成的过程中，异步预读能尽快启动并完成，使得顺序读之间达到最大程度的流水，异步预读需要激活低级I/O设备 驱动程序，确保新页被尽快读取。但需要注意的是，过于频繁激活低级I/O设备驱动程序，会影响I/O请求的合并，对系统性能是不利的。

3 预读过程

现在来讨论预读组与预读窗口的设置与推进过程。当read第一次打开文件来读时，预读组和预读窗口初始化为空，表示“下一个预读的大小”的f_ramax 初值为0。我们注意到一点，read是第一次读取文件，预读窗口为空，它读取的页面很可能不在pagecache里，因此在加入到pagecache并启 动I/O前会加锁。为了支持后面将触发的同步预读，设置f _ramax为read需读取的页数。一旦同步预读被触发，会启动后续f_ramax页的的I/O传送，并设置预读组包括所有预读页面，预读窗口与预读组 保持一致。

然后，使f_ramax加倍，为以后的顺序读作准备。因为对顺序读，我们需要考虑合适的预读粒度：预读粒度太小的话，达不到应有的性能提升效果；预读太 多，又有可能载入太多程序不需要的页面，启动大量无效I/O，造成资源浪费。为此，采用一个2倍的扩张过程：f_ramax 在每次预读后加倍，下一个顺序读就会预读加倍的页面。当读是顺序的，这一扩张过程将不断重复，f_ramax将逐次倍增，直到达到系统设定的块设备的上限 值。

当某个read是顺序的，在循环读取页面之前，判断f_ramax是否小于需读取的页面数，若是，将f_ramax设置为后者。这里的逻辑是：只要能预 读，不管是同步还是异步的，就应该至少先预读read所需求的所有页面。假设读取某页时，触发预读，启动后续f_ramax页的的I/O传送，其中包括需 读取的所有页面。我们设置预读组包括所有预读页面，预读窗口为最近两个预读组，并使f_ramax加倍。

当某个read是随机的。因为预读是为顺序读服务的，对一个随机读保留预读历史是毫无意义的。我们清除预读历史：将预读组和预读窗口置为 空，f_ramax初值清0。此时，文件状态与打开文件第一次来读的状态是类似的。我们同样设置f_ramax为需读取的页数，为后面的预读作准备。

4 放松顺序性标准

顺序性要求当前read与前一个read在文件内的位置是顺序的，其严格定义应该是两个位置紧密相连。有了预读窗口，我们或许可以放松一下顺序性标准：只 要read读取的第一页命中预读窗口（前一个read设置），就认为read是顺序的。这样会使得预读算法更加激进，预读效果可能更好。

六 同步预读与异步预读相互配合的实际情形

为了加深对预读算法的理解，我们结合实际的情景描述同步预读与异步预读。

1 随机读

一个read如果是随机的，会禁止异步预读。一般而言，在它读取所有页面的过程中，只会触发一次同步预读操作。在极端情形下，例如read读取的所有页面都已经被“其他进程”装入内存，因而都未锁时，一次预读都不会触发。不过，这种情形也无须预读了。

2 顺序读

当本次read是顺序的，需要启动异步预读。

顺序读的几种组合情形
a 没有预读
读预读窗口内的页时，页都被锁，没有同步预读。读预读窗口之外的页时，页都未锁，没有异步预读。结果，一次预读都未发生。这应该是一种非常极端的巧合情形。

b 一次异步预读
假设read所需读取的页未超过预读窗口的范围。
首先读在预读窗口中但不在预读组中的页，不管是否加锁，不会进行预读。接着读到预读组里的页，其中已锁的页不会引发同步预读，此时发现某页未锁，引发异步 预读：启动相关页的I/O数据传送，包含read需要的所有页，并设置新的预读窗口及预读组。在新的预读组中不包含read所需要的页面，read读“后 续页”时不管页是否加锁，都不会引发预读。

c 两次异步预读
假设read所需读取的页超过了预读窗口的范围。

第一次异步预读的情形同上，但在新的预读组中包含了read所需要的所有页面。于是开始与第一次异步预读类似的情形：先读到在新的预读窗口中但不在新预读 组中的页，不会触发预读。再往后读到新的预读组中的页，其中加锁的页不会引发同步预读。此时，发现某一页未锁，于是再次触发新的异步预读，并再次设置新的 预读窗口及预读组。 此时，新的预读组中不可能包含read所需要的页面。因此，read后续的读操作不会再次引发新的预读。

d 一次同步预读
假设read所需读取的页超过了预读窗口的范围。
读预读组中的页时，页都被锁。读到预读窗口外页时，其中未锁的页不会引发异步预读。此时，发现某页锁住，因此进行同步预读：启动相关页的I/O数据传送， 包含read需要的所有页，并设置新的预读窗口及预读组。接着读到新的预读窗口（与预读组一致）中的页，所有的页都加锁，因而不会有任何预读操作。

e 一次同步预读加上一次异步预读
假设read所需要的页超过了预读窗口的范围。
第一次同步预读的情形同上。在读到新的预读窗口（与预读组一致）中的页时，发现某一页未锁，于是再次进行新的异步预读，并再次设置新的预读窗口及预读组。此时，新的预读组中不可能包含read所需要的页面，read后续的读操作不会再次引发新的预读。


因此，一个read如果为顺序读，在其读取所有页面的过程中，至多引发两次预读。还要注意到，经过一次异步预读后，read所需求的所有页都会在新的预读窗口内，因而其后不会有同步预读发生。也就是说，不会有“一次异步预读加上一次同步预读”的情形出现。