免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 6528 | 回复: 3

2.4.18预读算法详解 [复制链接]

论坛徽章:
0
发表于 2008-09-02 15:15 |显示全部楼层
琢磨ULK2时的一些个人理解。参考了WFG的这篇文章:
http://os.51cto.com/art/200711/60574.htm
如果觉得有必要,以后会写写其他版本预读算法的实现分析及改进逻辑。

一 为什么需要预读

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所需求的所有页都会在新的预读窗口内,因而其后不会有同步预读发生。也就是说,不会有“一次异步预读加上一次同步预读”的情形出现。

论坛徽章:
0
发表于 2008-09-02 15:49 |显示全部楼层
这两天刚好看ULK的这部分,多谢分享

论坛徽章:
0
发表于 2008-09-09 16:08 |显示全部楼层
不错,把格式整理一下就更好。

论坛徽章:
0
发表于 2008-09-14 02:36 |显示全部楼层
和tcp的滑动窗口有些相像,不错。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会 限时8.5折

【架构革新 高效可控】2020年6月4日~6日第十一届中国数据库技术大会将在北京隆重召开。

大会设置2大主会场,20+技术专场,将邀请超百位行业专家,重点围绕数据架构、AI与大数据、传统企业数据库实践和国产开源数据库等内容展开分享和探讨,为广大数据领域从业人士提供一场年度盛会和交流平台。

http://dtcc.it168.com


大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP