`

数据库存取缓冲区的LRU与MRU算法

 
阅读更多
1.Cache Hit and Cache Miss
当使用者第一次向数据库发出查询数据的请求的时候,数据库会先在缓冲区中查找该数据,如果要访问的数据恰好已经在缓冲区中(我们称之为Cache Hit)那么就直接用缓冲区中读取该数据.
反之如果缓冲区中没有使用者要查询的数据那么这种情况称之为Cache Miss,在这种情况下数据库就会先从磁盘上读取使用者要的数据放入缓冲区,使用者再从缓冲区读取该数据.
很显然从感觉上来说Cache Hit会比Cache Miss时存取速度快.

2.LRU(最近最少使用算法) and MRU(最近最常使用算法)
所谓的LRU(Least recently used)算法的基本概念是当内存的剩余的可用空间不够时,缓冲区尽可能的先保留使用者最常使用的数据,换句话说就是优先清除”较不常使用的数据”,并释放其空间.之所以”较不常使用的数据”要用引号是因为这里判断所谓的较不常使用的标准是人为的、不严格的.所谓的MRU(Most recently used)算法的意义正好和LRU算法相反.
下面我们通过Oracle 9i Cache中对LRU和MRU的使用来看一下两者在缓冲区工作机制中的作用和区别
     在Oracle 9i中有LRU List的概念我们可以把LRU List想象成是一连串的缓冲区集合,两端分别是LRU端和MRU端, 当数据库从磁盘上读取数据放入缓冲区时,系统必须先确定缓冲区中有free buffers,这个时候Oracle 9i会扫描LRU List,扫描的基本原则是
1.     从LRU端到MRU端;
2.     当扫描到free buffer或已扫描的缓冲区数目超过临界值时,就会停止扫描动作;
      如果在扫描过程顺利的在LRU List中找到了free buffer,那么Oracle 9i就把从磁盘读出的数据写到free buffer中然后把free buffer加到LRU List的MRU端.
      那如果扫描过程没有在LRU List中找到free buffer怎么办?当然是从LRU List的LRU端开始清除缓冲区,如此一来就可以腾出新的空间了.
      下图就是一个例子
          使用者查询数据A,初始的时候LRU List中没有数据A,于是Oracle 9i到磁盘读取A,然后放到LRU List的MRU端,使用者再从LRU List中读取数据A,同理对于B,C…当LRU List满了以后,如果使用者查询N,此时N不在LRU List中而且LRU List中已经没有free buffer了,此时Oracle 9i就开始从LRU端淘汰A以腾出空间存放N.


  图 1
我们再来看另外一种情况
    在State 3之后,恰好使用者持续的查询A—这将会导致A一直被放置在靠近MRU端的缓冲区,结果将如图State m’所示,你会发现图2的State m’与图1的State m缓冲区存放的数据完全一样但是存放位置不一样.此时LRU List满了,如果再放N的时候LRU List`淘汰的是B,因为A的查询率高于B,所以LRU List让A在缓冲区中呆上较长的时间而先淘汰掉”较不常用的”的B.

图 2

参考:http://blog.csdn.net/lmdcszh/article/details/39717207
分享到:
评论

相关推荐

    用C++实现LRU页面置换算法

    使用LRU算法实现页面置换算法。LRU算法基于一种假设,长期不使用的数据,在未来的使用性也不大。因此,当数据占用内存达到一定的阙值时,我们要移除最近最少使用的数据。LRU算法中,使用了一种有趣的数据结构,叫做...

    LRU页面置换算法

    LRU页面置换算法 LRU 页面置换算法是一种常用的页面置换算法,主要用于操作系统中虚拟内存管理。该算法的核心思想是将最久未使用的页面从内存中置换出去,以腾出内存空间用于其他应用程序。 LRU 页面置换算法的...

    数据库缓冲区实验

    在这个“数据库缓冲区实验”中,我们重点研究了如何有效地管理内存中的数据块,特别是应用了LRU(最近最少使用)算法来决定何时将数据从内存换出到磁盘。 首先,我们需要理解数据库缓冲区的基本原理。数据库中的大...

    LRU算法 lru算法

    LRU(Least Recently Used)算法是一种常用的页面替换策略,它基于“最近最少使用”的原则来决定何时替换内存中的页面。在计算机系统中,由于物理内存有限,当程序需要的内存超过实际可用内存时,操作系统会将部分...

    c语言实现的LRU算法

    在实际应用中,LRU算法广泛应用于数据库系统、操作系统、Web服务器的缓存管理等领域,以提高数据访问效率。通过理解这个C语言实现的LRU算法,你可以深入学习到如何结合数据结构和算法来解决实际问题。

    LRU.rar_LRU_LRU2 算法_MRU_lru2

    LRU(最近最少使用算法) and MRU(最近最常使用算法)所谓的LRU(Least recently used)算法的基本概念是:当内存的剩余的可用空间不够时,缓冲区尽可能的先保留使用者最常使用的数据,换句话说就是优先清除”较不常使用的...

    FIFO、OPT、LRU页面置换算法实验代码和截图

    FIFO、OPT、LRU页面置换算法实验代码和截图 在操作系统中,页面置换算法是指操作系统在内存不足时,如何将某些页面从内存中移除,以腾出空间供其他页面使用的算法。常见的页面置换算法有FIFO、OPT、LRU等。 FIFO...

    LRU算法

    LRU算法LRU算法LRU算法LRU算法LRU算法LRU算法

    闪存数据库缓冲区置换算法综述.docx

    【闪存数据库缓冲区置换算法综述】 随着闪存技术的快速发展和容量的持续扩大,闪存数据库管理系统面临着新的机遇和挑战。闪存与传统磁盘的读写机制不同,导致其性能表现各异,因此对闪存缓冲区的管理成为了一个关键...

    编写程序实现虚拟存储管理中OPT,FIFO,LRU页面置换算法

    根据给定文件的信息,我们可以详细地探讨一下在虚拟存储管理中如何实现三种主要的页面置换算法:Optimal (OPT), First-In First-Out (FIFO), 和 Least Recently Used (LRU)。此外,我们还会简要提及Clock置换算法,...

    LRU页面淘汰算法模拟程序(源码)C++

    LRU页面淘汰算法模拟程序(源码)C++ 产生一个进程的大小,构建页表并对页表进行初始化,随后生成访问的指令地址流(是一系列需要访问的指令的地址)。不失一般性,可以适当地(人工指定或随机数产生器)生成这个序列...

    操作系统LRU页面置换算法

    操作系统中的LRU(Least Recently Used)页面置换算法是内存管理的一种关键策略,它在处理物理内存有限而程序需要访问的页面数量超过内存容量时发挥作用。LRU算法的基本思想是:最近最少使用的页面最有可能在未来一...

    模拟LRU页面置换算法c语言程序

    LRU(Least Recently Used)页面置换算法是一种常用的内存管理策略,用于处理进程中的虚拟内存页面调入调出问题。在操作系统中,当物理内存不足以容纳所有活动页面时,LRU算法会选择最近最少使用的页面进行淘汰,以...

    一个数据库缓冲区实现文档

    数据库缓冲区实现文档 在数据库管理系统中,缓冲区管理是一个至关重要的组件,它负责缓存数据页以提高数据访问效率。本文档将详细介绍一个简单的数据库缓冲区实现,涉及的主要概念包括缓冲区和帧的大小、存储结构、...

    对FIFO/LRU两种算法的对比

    本文主要针对两种常见的页面置换算法——先进先出(FIFO)与最近最少使用(LRU)进行深入对比分析。这两种算法广泛应用于操作系统的虚拟内存管理中,对于提高系统效率、减少缺页中断次数具有重要意义。 #### 二、基础...

    LRU 页面置换算法 最近最久未使用 源代码 c/c++

    ### LRU页面置换算法详解与C/C++实现 在计算机科学中,页面置换算法是操作系统内存管理中的一个重要组成部分,主要用于解决虚拟内存环境下的页面调度问题。其中,“最近最少使用”(Least Recently Used,简称LRU)...

    lru算法实验报告

    在实际应用中,LRU 算法常用于缓存管理和数据库系统,以优化数据的访问效率。例如,当内存不足以存放所有数据时,LRU 可以帮助决定哪些数据应该被暂时移除,以便为更重要的数据腾出空间。由于 LRU 的高效性和直观性...

    LRU.rar_LRU_lru算法

    在计算机操作系统中,LRU算法常用于虚拟内存管理,确保频繁访问的数据能够快速存取。 LRU算法的核心思想是:如果一个数据最近被访问过,那么它在未来的短时间内被再次访问的可能性比较高。因此,当需要从内存中移除...

    操作系统LRU页面置换算法 C语言程序

    7. **性能分析**:为了评估LRU算法的效果,可以计算缺页率(缺页次数/总访问次数),并与其他页面置换算法(如FIFO,LFU等)进行比较。 C语言的实现将涉及到指针操作、动态内存分配以及循环结构等核心概念。在编写...

Global site tag (gtag.js) - Google Analytics