台州网站推广排名,深圳市南山区网站建设,制作网页无法铺平,广州平面设计学徒招聘常见的调度算法 图1 调度算法思维导图
一、LRU算法的典型使用场景
1. 操作系统中的页面置换
什么时候用到页面置换算法呢#xff1f;
当CPU发出指令需要访问某个地址时#xff0c;若该地址在TLB#xff08;Translation Lookaside Buffer#xff0c;快表#xff09;或页…常见的调度算法 图1 调度算法思维导图
一、LRU算法的典型使用场景
1. 操作系统中的页面置换
什么时候用到页面置换算法呢
当CPU发出指令需要访问某个地址时若该地址在TLBTranslation Lookaside Buffer快表或页表中未命中就会发生缺页异常Page Fault。此时操作系统需要从磁盘加载缺失页面到物理内存中。如果物理内存已满就需要选择一个页面置换出去腾出空间。
什么是LRU算法
主要管理虚拟内存和物理内存之间的交换。内存中分成固定大小的页框(4K)把程序(硬盘上)分成4K大小的块用到哪一块加载那一块加载的过程中如果内存已经满了会把最不常用的一块放到swap分区把最新的一块加载进来这个就是著名的LRU算法。
LRU算法在此场景下的作用
选择被置换的物理页面根据页面最近的使用记录优先选择最久未被使用的页面。确保效率通过淘汰冷页面尽量保留活跃的热页面提高系统性能。
2. 缓存机制
除了操作系统LRU算法还广泛应用于各种缓存系统用于管理有限的缓存空间
Redis采用近似LRU算法通过采样实现用于淘汰旧数据。浏览器缓存管理网页资源如图片、脚本时选择最久未访问的资源进行清理。MySQL缓冲池缓存数据块以减少磁盘IO操作通过类似LRU机制维护热端和冷端优化数据访问。Oracle缓冲池还增加不少机制来提高访问效率 触摸计数 Oracle 引入触摸计数来测量对 LRU 列表上的缓冲区进行访问的频率每当数据块被访问时其触摸计数会增加LRU列表的热端和冷端同时存在指向同一 LRU 上的脏缓冲区和非脏缓冲区的指针冷缓冲区是最近未被使用的热缓冲区是被频繁访问并在最近已使用的中部插入机制当缓冲区必须从磁盘读入时, 数据库会将缓冲区插入到 LRU 列表的中部通过这种方式热块可以保留在缓存中以使他们不需要再次从磁盘读取
。。。。。。
3. 文件系统
在文件系统中缓存文件块时也经常使用LRU算法。例如文件读取缓存块满时选择最久未访问的块进行替换。
二、页面置换算法的功能
操作系统中当发生缺页异常时如果内存中没有空闲页框则需要根据某种策略如LRU选择一个页面从物理内存中置换到磁盘以腾出空间加载需要访问的新页面。也就是说选择⼀个物理⻚⾯换出到磁盘然后把需要访问的⻚⾯换⼊到物理⻚。具体流程
如果物理内存中还有空闲页框直接将新页面加载到空闲页框中。如果物理内存已满 根据置换算法如LRU选择一个页面置换到磁盘。如果被置换的页面是脏页即内容被修改过则先将其写回磁盘。将被置换页面对应的页表项状态改为“无效”。加载新的页面到该物理页框中并更新页表项。
三、物理页换入换出操作流程
当操作系统物理内存已满并且访问的页面不在物理内存时缺页中断就需要进行换入换出操作需要通过「⻚⾯置换算法」选择⼀个物理⻚如果该物理⻚有被修改过脏⻚则把它换出到磁盘写回然后把该被置换出去的⻚表项的状态改成「⽆效的」最后把正在访问的⻚⾯装⼊到这个物理⻚中。
在具体操作中LRU算法需要完成以下步骤
选择物理页找到最久未被使用的页面。处理脏页如果被替换的页面是脏页则需将其写回磁盘否则不需读回磁盘直接换出。更新页表将被替换页面的状态标记为无效并将新页面加载到物理内存中。
页表字段页号、物理页、状态位、访问字段、修改位、硬盘地址
四、从数据结构看LRU的实现
我们以数据库缓冲池为例其中LRU有两个功能
获取数据get写入数据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里直接把头去掉headhead.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缓冲池引入了以下机制
热端和冷端 缓冲区分为热端和冷端热端保存频繁访问的数据冷端保存最近未使用的数据。新加载的页面通常插入到LRU链表的中部避免直接进入热端。
触摸计数 通过计数器记录页面访问频率用于辅助LRU决策。频繁访问的页面更可能停留在热端提高命中率。
脏页管理 LRU链表中同时维护脏缓冲区和非脏缓冲区。在需要页面置换时优先选择冷端的非脏页减少写回磁盘的开销。
可以尝试一下力扣146题146. LRU 缓存 - 力扣LeetCode
