Oracle筑基篇-调度算法-LRU的引入

devtools/2024/12/24 20:34:18/

常见的调度算法

图1 调度算法思维导图

一、LRU算法的典型使用场景

1. 操作系统中的页面置换

什么时候用到页面置换算法呢?

当CPU发出指令需要访问某个地址时,若该地址在TLB(Translation Lookaside Buffer,快表)或页表中未命中,就会发生缺页异常(Page Fault)。此时,操作系统需要从磁盘加载缺失页面到物理内存中。如果物理内存已满,就需要选择一个页面置换出去腾出空间。

什么是LRU算法?

主要管理虚拟内存和物理内存之间的交换。内存中分成固定大小的页框(4K),把程序(硬盘上)分成4K大小的块,用到哪一块,加载那一块,加载的过程中,如果内存已经满了,会把最不常用的一块放到swap分区,把最新的一块加载进来,这个就是著名的LRU算法。

LRU算法在此场景下的作用?

  • 选择被置换的物理页面:根据页面最近的使用记录,优先选择最久未被使用的页面。
  • 确保效率:通过淘汰冷页面,尽量保留活跃的热页面,提高系统性能。
2. 缓存机制

除了操作系统LRU算法还广泛应用于各种缓存系统,用于管理有限的缓存空间:

  • Redis:采用近似LRU算法(通过采样实现),用于淘汰旧数据。
  • 浏览器缓存:管理网页资源(如图片、脚本)时,选择最久未访问的资源进行清理。
  • MySQL缓冲池:缓存数据块以减少磁盘IO操作,通过类似LRU机制维护热端和冷端,优化数据访问。
  • Oracle缓冲池还增加不少机制来提高访问效率:
    1. 触摸计数, Oracle 引入触摸计数来测量对 LRU 列表上的缓冲区进行访问的频率每当数据块被访问时,其触摸计数会增加;
    2. LRU列表的热端和冷端,同时存在指向同一 LRU 上的脏缓冲区和非脏缓冲区的指针,冷缓冲区是最近未被使用的,热缓冲区是被频繁访问并在最近已使用的;
    3. 中部插入机制,当缓冲区必须从磁盘读入时, 数据库会将缓冲区插入到 LRU 列表的中部,通过这种方式,热块可以保留在缓存中,以使他们不需要再次从磁盘读取;

。。。。。。

3. 文件系统

在文件系统中,缓存文件块时也经常使用LRU算法。例如,文件读取缓存块满时,选择最久未访问的块进行替换。

二、页面置换算法的功能

操作系统中当发生缺页异常时,如果内存中没有空闲页框,则需要根据某种策略(如LRU)选择一个页面从物理内存中置换到磁盘,以腾出空间加载需要访问的新页面。也就是说选择⼀个物理⻚⾯换出到磁盘,然后把需要访问的⻚⾯换⼊到物理⻚。具体流程:

  • 如果物理内存中还有空闲页框,直接将新页面加载到空闲页框中。
  • 如果物理内存已满:
    1. 根据置换算法(如LRU)选择一个页面置换到磁盘。
    2. 如果被置换的页面是脏页(即内容被修改过),则先将其写回磁盘。
    3. 将被置换页面对应的页表项状态改为“无效”。
    4. 加载新的页面到该物理页框中,并更新页表项。

三、物理页换入换出操作流程

操作系统物理内存已满并且访问的页面不在物理内存时(缺页中断),就需要进行换入换出操作,需要通过「⻚⾯置换算法」选择⼀个物理⻚,如果该物理⻚有被修改过(脏⻚),则把它换出到磁盘(写回),然后把该被置换出去的⻚表项的状态改成「⽆效的」,最后把正在访问的⻚⾯装⼊到这个物理⻚中。

在具体操作中,LRU算法需要完成以下步骤:

  1. 选择物理页:找到最久未被使用的页面。
  2. 处理脏页:如果被替换的页面是脏页,则需将其写回磁盘,否则不需读回磁盘直接换出。
  3. 更新页表:将被替换页面的状态标记为无效,并将新页面加载到物理内存中。

页表字段:页号、物理页、状态位、访问字段、修改位、硬盘地址

四、从数据结构看LRU的实现

我们以数据库缓冲池为例,其中LRU有两个功能

  1. 获取数据get
  2. 写入数据put

假设buffer cache大小为6

1. 数组实现

我们依次读入buffer的数据分别是2、6、3、7、8、9、1、10,这时候数组已经满了,如果需要新调入一个数据块,这时候我们怎么找出数组中哪一项时最不常用的?实现方式很多,最常用的可以在每一个块上记录一个Timestamp,此时,3号块8s没被访问,时间最长。

但是问题又来了,查找最不常用的内存块需要遍历整个buffer cache,时间复杂度时O(n),好一点的数组查找算法如二分查找也要 O(log n) ,哈希查找理想情况下是O(1),但最坏情况下所有元素都映射到一个桶里可能是O(n),也就是我们常说的存在哈希冲突,换链表试一下。

数组实现优劣:

  • 优点:简单易实现。
  • 缺点:查找最久未使用的页面需要遍历整个数组,时间复杂度为 O(n)。
2. 单向链表实现

使用尾插法维护一个单向链表,每次把新来的数据插入在链表尾部,头部就永远是最不常用的块,比如依次访问2、6、3、7、4、8六个块,

这时候缓存满了

  • 当访问的块不在buffer里,直接把头去掉head=head.next,把新访问的数据块插入到链表尾部;put()写入数据是O(1),删除最不常用的数据也是O(1).
  • 当访问的块在buffer里,比如要再次访问块3的时候,需要把最后访问的放到链表尾部,也就是3放到链表尾部,这个时候缓冲区块的物理位置是不会改变的,变动指针方向即可。

直接在尾部直接画线图有点难看,使用伪尾部节点构造一个空指针,算不占buffer空间

所以上面的图相当于

在这个过程需要在链表查找到块三,在链表上get()查找还是一个O(n)的操作,和链表长度成正比,再继续看看下一个结构-哈希表+单向链表。

链表实现优劣:

  • 使用链表维护页面访问顺序,最近访问的页面在链表尾,最久未使用的页面在链表头,查找最久未使用的页面时间复杂度降至O(1)。
  • 每次访问页面,需要将页面移动到链表尾部,查找命中的缓存块时间复杂度为O(n)。
3. 哈希表 + 单向链表

数组说到get()查找一个元素O(1)操作可以是哈希查找,用哈希表实现且后面跟一个链表。

如图所示:

还没完,我们还是要再次访问数据块3,

通过哈希表查找操作get(3)已经可以O(1)实现了

将最常访问的放在链表尾部,找到块3之后将三号块指向tail,断开8号块指向tail的指针指向3号块。

6->3->7的指针也需要断开,跳过3号块,将6号块指向7号块,怎么通过3号块直接找到它的前驱呢?双向链表,我们继续看

哈希表+单向链表实现优劣:

  • 哈希表存储页面号到链表节点的映射,快速定位页面。
  • 单向链表维护访问顺序,结合哈希表后,查找命中的缓存块的时间复杂度降至 O(1),但是更改操作还是O(n)
4. 哈希表 + 双向链表(最优实现)

最后我们得到了哈希表+双向链表的结构实现LRU

哈希表用来实现get()查找操作是O(1),链表用来实现排序和put()新增操作是O(1)。

Java里有这样的结构:LinkedHashMap

哈希表+双向链表实现优劣:

  • 双向链表:实现页面访问顺序的快速更新,支持节点的插入、删除操作。
  • 哈希表:快速定位页面。
  • 复杂度:查找、插入和删除均为 O(1)。

五、实际应用中的优化(以Oracle缓冲池为例)

LRU数据库中并不是上面get(),put()两个功能,这么简单的实现,还会结合具体场景进行优化。例如,Oracle缓冲池引入了以下机制:

  1. 热端和冷端
    • 缓冲区分为热端和冷端,热端保存频繁访问的数据,冷端保存最近未使用的数据。
    • 新加载的页面通常插入到LRU链表的中部,避免直接进入热端。
  1. 触摸计数
    • 通过计数器记录页面访问频率,用于辅助LRU决策。
    • 频繁访问的页面更可能停留在热端,提高命中率。
  1. 脏页管理
    • LRU链表中同时维护脏缓冲区和非脏缓冲区。
    • 在需要页面置换时,优先选择冷端的非脏页,减少写回磁盘的开销。

可以尝试一下力扣146题:146. LRU 缓存 - 力扣(LeetCode)


http://www.ppmy.cn/devtools/145071.html

相关文章

Matplotlib DAY1 (完)

Matplotlib 是支持 Python 语言的开源绘图库,因为其支持丰富的绘图类型、简单的绘图方式以及完善的接口文档,深受 Python 工程师、科研学者、数据工程师等各类人士的喜欢。本次实验课程中,我们将学会使用 Matplotlib 绘图的方法和技巧。 知识…

【蓝碳】基于GEE云计算、多源遥感、高光谱遥感技术、InVEST模型、PLUS模型的蓝碳储量估算;红树林植被指数计算及提取

蓝碳和红树林研究的重要性主要体现在以下几个方面: 1.全球碳循环的关键角色:蓝碳生态系统,包括红树林、盐沼和海草床,虽然覆盖面积不到海床的0.5%,但其碳储量却高达海洋碳储量的50%以上,甚至可能高达71%。红…

java全栈day18--Web后端实战(java操作数据库2)

前言:在上节入门程序当中我们见到了JDBC所提供的API,本节来详细说明一下。 一、JDBC--API详解 1.1DriverManager(驱动管理器) 回顾:作用获取连接,调用它里面的getConnection。即如下 作用 1.注册驱动解…

单节点calico性能优化

在单节点上部署calicov3273后,发现资源占用 修改calico以下配置是资源消耗降低 1、因为是单节点,没有跨节点pod网段组网需要,禁用overlay方式网络(ipip,vxlan),使用route方式网络 配置calico-node的环境变量 CALICO_IPV4POOL_I…

16×16LED点阵字符滚动显示-基于译码器与移位寄存器(设计报告+仿真+单片机源程序)

资料下载地址:​1616LED点阵字符滚动显示-基于译码器与移位寄存器(设计报告仿真单片机源程序)​ 1、功能介绍 设计1616点阵LED显示器的驱动电路,并编写程序实现在1616点阵LED显示器上的字符滚动显示。1616点阵LED显示器可由4块88点阵LED显示器构成。可采…

Scala图书管理系统

项目创建并实现基础UI package org.appimport scala.io.StdInobject Main {def main(args: Array[String]): Unit {var running truewhile (running) {println("欢迎来到我的图书管理系统,请选择")println("1.查看所有图书")println("2…

MongoDB 介绍及 Java 实现基本操作

MongoDB 介绍及 Java 实现基本操作 一、MongoDB 简介二、Java 操作 MongoDB 的基本步骤1. 环境准备2. 基本操作示例 三、代码解析1. 连接 MongoDB:通过 MongoClients.create(uri) 创建客户端连接,uri 指定 MongoDB 服务地址。2. 获取数据库和集合&#x…

ASP.NET Core 与 Blazor:现代 Web 开发技术的全新视角

在当代 Web 技术快速演进的浪潮中,开发者们总是在寻找能够提高效率、简化开发流程的工具和框架。微软推出的 ASP.NET Core 和 Blazor,为开发者提供了多样化的选择,不仅适应了现代 Web 应用的发展需求,同时也为技术人员打开了更多可…