温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

操作系统页面更换与Redis内存淘汰的示例分析

发布时间:2021-12-20 10:43:58 来源:亿速云 阅读:123 作者:小新 栏目:大数据

小编给大家分享一下操作系统页面更换与Redis内存淘汰的示例分析,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!

操作系统为什么需要页面更换呢,因为物理内存不够,不可能同时加载所需的所有数据页,因此只能加载正在或最近要使用的内存页。页面更换的目标是,尽量替换掉不再使用或者一段时间内不再使用的内存页,要不然会很容易触发缺页中断,该操作代价较大,涉及到从磁盘加载,因此页面更换可不是随便的事情。

为了达到降低随后发生缺页中断的次数或者概率,人们设计出了各种各样的页面替换算法,这些算法大致可分为公平算法和非公平算法。

  • 公平算法:随机算法、FIFO算法、时钟算法。

  • 非公平算法:NRU算法、LRU算法、工作集算法。

随机算法

这种就是简单的随机选择进行页替换,无需多言,简单粗暴。

 

FIFO算法

这种就是先来后到,可以使用链表记录页分配的先后顺序,淘汰时按照顺序淘汰即可,也是非常的简单粗暴。

 

时钟算法

内存使用中的页按照时钟的逻辑形状,淘汰页时按照时钟顺序检查,如果页未访问到(每个页对应一个访问标识,未访问到时设置为0),则直接替换;如果访问过则设置访问位为0,方便下次淘汰。时钟逻辑图如下:

操作系统页面更换与Redis内存淘汰的示例分析

 

NRU算法

最近未使用算法,将最近一段时间没有访问过的页面进行替换,作出这种选择是基于程序访问的时空局域性。依据时空局域性,一个最近没有访问过的页面,在随后的时间内也不太可能被访问,而NRU的实现就是利用页面的访问和修改位来实现的。

时空局限性在很多程序设计思想中有体现,比如rocketmq中page cache缓存最近读写的消息数据等。

 

LRU算法

LRU是对NRU算法的改进,其考虑的是最近使用的频率而不是最近是否使用过。LRU算法的实现必须以某种方式记录每个页面被访问的次数,简单的办法就是在页表的记录项里面增加一个计数域,一个页面被访问一次,则这个计数器的值加1;或者使用链表结构,每访问一次就将该页移动到链表头。

 

工作集算法

考虑到LRU算法实现,其需要对每个页面保持某种记录,并在每次页面访问时或周期性对这些记录更新,造成时间空间成本高。工作集概念来源于程序访问的时空局域性,在一段时间内,程序访问的页面将局限在一组页面集合上。

例如,最近K次访问均发生在某m个页面上,那么m就是参数为k时的工作集。用w(k, t)表示时间t时k次访问所涉及的页面数量。显然随着k的增长,w(k, t)的值将随之增长,在k增长至某个数值后,w(k, t)值增长将及其缓慢甚至接近停滞,并维持一段时间。

操作系统页面更换与Redis内存淘汰的示例分析

工作集算法就是操作系统局限性的一种体现,一段时间内,CPU操作的数据大都集中在少量数据上,因此可以应用工作集算法来进行页的替换操作。

 

Redis中的内存淘汰

以上分析了操作系统中的页面更换算法,更广义来讲,页面更换就是内存淘汰,操作系统的页面更换算法可能不能直接让开发者感同身受,毕竟这是OS层面的东东。下面就以实际开发中常用到的Redis为例,来分析下Redis内存淘汰策略,对比加深对内存淘汰的理解。

Redis的内存淘汰策略是指在Redis的用于缓存的内存不足时,怎么处理需要新写入且需要申请额外空间的数据。目前Redis的内存淘汰策略有如下几种:

  • noeviction:当内存不足以容纳新写入数据时,新写入操作会报错。

  • allkeys-lru:当内存不足以容纳新写入数据时,在键空间中,移除最近最少使用的key。

  • allkeys-random:当内存不足以容纳新写入数据时,在键空间中,随机移除某个key。

  • volatile-lru:当内存不足以容纳新写入数据时,在设置了过期时间的键空间中,移除最近最少使用的key。

  • volatile-random:当内存不足以容纳新写入数据时,在设置了过期时间的键空间中,随机移除某个key。

  • volatile-ttl:当内存不足以容纳新写入数据时,在设置了过期时间的键空间中,有更早过期时间的key优先移除。

对于LRU(Least Recent Used),淘汰掉最不经常使用的,LRU可以通过hashMap + 双向链表来实现,如果Redis也基于hashMap + 双向链表实现,显然要对目前的数据结构做较大改动,为了追求空间的利用率,Redis采用权衡的实现方案:Redis会基于server.maxmemory_samples配置选取固定数目的key,然后比较它们的lru访问时间,然后淘汰最近最久没有访问的key,maxmemory_samples的值越大,Redis的近似LRU算法就越接近于严格LRU算法,但是相应消耗也变高,对性能有一定影响,样本值默认为5

从Redis的内存淘汰实现方案来看,虽然遵循了LRU思想但不完全照搬,根据实际应用场景进行trade-off。

以上是“操作系统页面更换与Redis内存淘汰的示例分析”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI