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

常见的调度算法

图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. 1. 触摸计数， Oracle 引入触摸计数来测量对 LRU 列表上的缓冲区进行访问的频率，每当数据块被访问时，其触摸计数会增加；
   2. LRU列表的热端和冷端，同时存在指向同一 LRU 上的脏缓冲区和非脏缓冲区的指针，冷缓冲区是最近未被使用的，热缓冲区是被频繁访问并在最近已使用的；
   3. 中部插入机制，当缓冲区必须从磁盘读入时, 数据库会将缓冲区插入到 LRU 列表的中部，通过这种方式，热块可以保留在缓存中，以使他们不需要再次从磁盘读取；

。。。。。。

3. 文件系统

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

二、页面置换算法的功能

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

• 如果物理内存中还有空闲页框，直接将新页面加载到空闲页框中。
• 如果物理内存已满：

1. 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）