ITPub博客

首页 > Linux操作系统 > Linux操作系统 > LRU链与脏LRU链

LRU链与脏LRU链

原创 Linux操作系统 作者:1004050304 时间:2013-09-17 00:40:28 0 删除 编辑
最近在学习ORACLE体系结构,学习中很多地方都用到了LRU这个东西,LRU主要在内存中使用。任何缓存的大小都是有限制的,就如buffer cache用来缓存数据文件,数据文件的大小远远超过buffer cache。当缓存被占满的时候,如果新的数据要求进入缓存,就只有从缓存中原来的数据中选择出一个牺牲者了,用新进入缓存的数据覆盖这个牺牲者。
一般最先想到的就是将最没用的去掉,换上新进来的,那么如何找到那个最没用的呢?在ORACLE里就是通过LRU(最近最少)这个东西来解决的。
其意义是将最后被访问的时间距现在最远的内存块作为牺牲者。比如说,现在有三个内存块,分别是A、B、C,A被访问过10次,最后一次访问是在10:20,B被访问过15次,最后一次访问是在10:18,C也被访问10次,最后一次是在10:22。当需要选择牺牲者时,B访问次数最多,肯定不是它,A、C访问次数一样,但C最后访问要比A晚,牺牲者就是A。
ORACLE在buffer cache中创建了一个LRU链表,将buffer cache中所有内存块,按照访问次数,访问时间排序串在链表中。链表的两头分别叫做热端与冷端,如下图:
当你访问某个块时,如果这个块不在buffer cache中,ORACLE要将它读进buffer cache,而buffer cache里面已经存放满了。此时ORACLE将从冷端开始选择牺牲者。
如上图,假设新块为V,新块将会被读入U,覆盖原来的内容。但是块V不会被放在冷端头,因为冷端头的块,很快会被当作牺牲者被覆盖掉。这不符合“最近最少”的宗旨。块V是最后时间距当前时刻最近的,它不应该作为下一个牺牲者。
ORACLE是这样处理的:将LRU链从中间分为两半,一半记录热端块、一半记录冷端块。而刚刚被访问的V块:如下图:
如果再有新的块进来,比如X块被读入,它将覆盖T,并且会被移动到块V的前面。
如果按照这样的方式继续下去,最右边冷端头处的块,一定是最后一次访问时间距现在最远的块,那么,访问次数多的块是不会被选做牺牲者,在ORACLE一般以2次为准,块被访问2次以上了,它就有机会进入热端。
ORACLE为内存中的每个块都添加了一个记录访问次数的标志,假设图中每个块的访问次数如下:
如果现在又有新块要被读入,ORACLE开始从冷端头寻找牺牲者,第一个块S,它的访问次数为2,那么它不能被覆盖,只要访问次数大于等于2的块,ORACLE会认为它可能会被经常访问到,ORACLE要把它移动到热端,它会选择R做为本次的牺牲者:
块S会被从冷端移到到热端,并且它的访问次数会被清零。此时,块R就是牺牲者了,因为它的访问次数不到2次。
新块Y覆盖了块R,并被移到了冷端块开始处,它的访问次数是1。如果再被访问一次就是2了。
虽然Y的访问次数达到了两次,但它不会马上被移到热端,它仍然留在原来的位置,随着不断有新块加入,被插入到它的前面,它会不断的被向后推移。

如上图,又加入了很多的新块,Y又被推到了冷端头,当再有新块进入时,Y不会是牺牲者,它会被移动到热端S的前面,Y后面的Z,它的访问次数没有达到2,它将会是牺牲者。
以上就是ORACLE中LRU的原理。

脏块与脏LRU链:
ORACLE中修改块的规则只是在内存中(buffer cache)修改,并不是直接修改磁盘中的块。如果要修改的块不在内存中,ORACLE会先将它读入内存中(buffer cache),再在内存中(buffer cache)进行修改。当内存中(buffer cache)的块被修改后,ORACLE会把它标记为“脏”块。脏块含有脏数据,脏数据就是用户修改过的数据。ORACLE会定期的将脏块写到磁盘中。有一个专门的后台进程就是专门负责写脏块到磁盘的,它就是DBWN。我们也把DBWN写脏块到磁盘这个过程叫做刷新脏块,刷新过后,脏块就不脏了,又变成了干净块。比如:有一个块A,如果buffer cache中此块的数据和磁盘上块中数据不一致,那么,这个块就是脏块。否则,就是是干净块。当修改完成后,因为ORACLE只修改buffer cache,因此,块中数据和磁盘肯定不一致,这时块就是脏块。当块被刷新后,块被写到磁盘,那么,磁盘中块数据和buffer cache中块的数据又是一致的,此时,块就又变成了干净块。
脏块在被写回磁盘前,也就是在它还是脏块时,它是不能被覆盖的,因为,脏块含有用户修改过的数据,而这些数据还没被写到磁盘,如果此时覆盖了脏块,用户的修改结果将会丢失。

如上图所示,其中V、L、O、P、Q是脏块。当新的块要进入时,ORACLE从冷端头开始选择牺牲块,Q、P和O都不能做牺牲块,因为它们是脏块,N是这一次的牺牲块,新进入的块将会覆盖N,然后将N插入到Y之前。然后,一一次有块进入时,ORACLE又从冷端搜索,它还要检查一次Q、P、O,发现不能被覆盖,M将是牺牲块;每一次都要检查一次Q、P、O,这太浪费时间了,ORACLE有准备了一个脏LRU链,专门保存脏块。当块变脏时,块不会马上被移到脏LRU中,只有当ORACLE从冷端头开始搜索时,才会将发现的脏块移到到脏LRU链中。这样做的目的就是下次搜索时,不用再检查这些脏块。

假如现在有新块Z要进入buffer cache:
如上图:O、P、Q将被移到脏LRU链中。

冷端头变成了N,N的访问次数小于2,它就是本次的牺牲者了。这样当下一次再需要从冷端头搜索时,就不用再检查O、P、Q这三个脏块了。当脏LRU链的长度,也就是脏LRU链中的脏块达到一定数目时,DBWN会开始刷新脏块。
通过LRU链与脏LRU链的原理,可以发现ORACLE把很多工作,都留到了在LRU的冷端搜索牺牲者时。当块的访问次数增加的超过2时,块在LRU链的位置不变;当块变脏时,块的LRU链位置也不变。只有当从LRU的冷端搜索牺牲者时,才会将发现的脏块移到脏LRU链,将访问次数超过2的,插入到热端,这就是ORACLE改进了的LRU算法。ORACLE这样做的目的,是为了让我们平时的查询、修改所需完成的操作昼的少。对于用户的查询、修改操作,LRU算法几乎没有任何的影响,额外所做的工作只是改变了几个标志位而已,查询时增加访问次数标志位,修改块时设置脏块标志位。LRU算法大部分的工作都是在搜索牺牲者时完成的。因此,有时搜索牺牲者这个过程有可能会出现等待,等待事件是free buffer waits。

访问次数大于2的块太多,或者脏块太多,反正这些块都是不能覆盖的,ORACLE不得不移到它们到它们该去的位置。当碰到的这样的块超过LRU中总块数的40%时,也就是说搜索了一小半LRU链,还是没有发现可以覆盖的牺牲者,ORACLE就不在找了,它会唤醒DBWN刷新脏块。在DBWN刷新间的等待,就会被记入到free buffer waits事件中。另外,在资料视图中有一个资料free buffer inspected,它记录了ORACLE在所有次的搜索牺牲者的过程中,共计碰到了多少个不可覆盖的块。
在搜索牺牲者过程中发现脏块,ORACLE将其移到脏LRU链,但是脏LRU链中脏块数目达到限制,DBWN被唤醒开始刷新脏块,ORACLE必须等待刷新脏块完毕,才能再继续搜索牺牲者,这期间的等待事件,也会被记入free buffer inspected。
总之,free buffer waits事件发生的主要原因就是在LRU中搜索牺牲者的时间过长。如果这个等待事件频繁出现,说明buffer cache中脏块太多了,通常是DBWN写刷新慢造成的。我们应该将DBWN更频繁的被唤醒去刷新脏块,好让它们变干净、可以被选为牺牲者。我们不应该让脏块从脏LRU链中被刷新,因为这时通常会出现free buffer inspected。脏LRU链并不是为了将脏块集中到一起,让DBWN去刷新的,上面已经说了,将脏块移动到脏LRU链中,是为了减少下一次搜索牺牲者所需要搜索的块。ORACLE中另有一个链表,专门用来记录脏块,好让DBWN定期刷新,这个链表是检查点队列





























26762723_1341024807Qwh2[1].jpg

26762723_1341025032Dah3.jpg

26762723_1341025071h3ZC.jpg

26762723_13410249140MZ0.jpg

26762723_13410249671QF2.jpg

1111.jpg

2222.jpg

3333.jpg

4444.jpg

5555.jpg

6666.jpg

7777.jpg

8888.jpg

9999.jpg

1010.jpg

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/25285600/viewspace-772802/,如需转载,请注明出处,否则将追究法律责任。

上一篇: SQL解析执行过程
请登录后发表评论 登录
全部评论

注册时间:2013-09-04

  • 博文量
    6
  • 访问量
    6916