前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >什么是缓存置换算法?

什么是缓存置换算法?

作者头像
我是攻城师
发布2019-07-19 18:20:50
1.7K0
发布2019-07-19 18:20:50
举报
文章被收录于专栏:我是攻城师

前言

前面的文章已经介绍了什么是操作系统的虚拟内存,与本文要介绍的缓存置换算法息息相关,如果还没有看的朋友,建议先读一下上篇文章,链接是:什么是操作系统的虚拟内存?

从上篇文章中,我们学习到虚拟内存的page置换算法,就是缓存过期算法的别称,可以说最早的缓存过期算法,其实是先出现操作系统中,这也是为什么,我强调学习一个东西的时候,最好能了解一下它的历史,这样能更好的帮助我们理解。

为什么需要缓存

(1)为了解决不同的存储介质之间的速度不匹配问题,比如CPU和内存,比如内存和磁盘,客户端和服务端。

(2)依据程序访问的局部性原理,近期访问的数据,在将来很有可能会被访问

(3)提升访问效率

缓存为什么需要置换

相信读过上篇文章的朋友应该可以很轻松的回答出来这个问题,操作系统本质上是一个多级缓存系统,从cpu寄存器,cpu一级缓存,cpu二级缓存,cpu三级缓存,主内存,硬盘,我们会发现从右到左,访问效率依次提升,同时设备价格也不断升高,从左到右,访问效率依次降低,同时设备价格也逐渐下降。正是出于这个原因,现代计算机都会在性价比之间做个权衡。因为越高访问效率的存储介质越贵,所以这些介质都是有限的资源,那么如何在有限的资源内处理无限的数据呢?这就提出了置换的概念,举个通俗的例子。去医院排队体验,在有限的房间里面,每次只能进入一个人做某项检查,当这个人检查完了,就离开房间,然后置换另一个人进来,依次类推,完成检查。最理想的情况是置换出未来短期内不会被再次访问的数据,但是我们无法预知未来,所以只能从数据在过去的访问情况中寻找规律进行置换。

常见的置换算法

缓存置换算法常用的策略有三种,分别是:

(1) FIFO:First In First Out,先进先出策略

(2) LFU:Least Frequently Used,最不经常使用策略

(3) LRU:Least Recently Used,最近最少使用策略

这三种淘汰数据的策略和侧重点各不一样,今天我们就来学习相关的知识。

FIFO

FIFO(First in First out)代表先进先出,提起这个概念,相信大家第一时间能够想到队列这种数据结构,在日常生活中,这种场景随处都可见,比如吃饭排队,去银行取钱排队,上地铁排队。这种策略,非常简单易懂,实现简单,而且具有公平性,符合人们思维的习惯。在计算机中这种思想也到处可见,比如在操作系统的调度系统中,IO读取等操作。其核心原则就是:最先进入缓存的数据,应该最早被淘汰。

考虑这样一串数字4, 7, 6, 1, 7, 6, 1, 2, 7, 2。如何在一个固定长度为3的容器中进行FIFO策略的淘汰?如下:

我们观察到前面6,7,4放进去之后,这是1的加入会淘汰原来最早放进去的4,接着7的到来,发现缓存命中所以不做处理,直到2出现,这个时候我们需要淘汰原来的7,就这样按照先进先出的策略淘汰。

LFU

LFU 全称 Least Frequently Used,从名字上我们就能看出来这个算法是基于数据访问频率(次数)来淘汰数据的,也就是说系统会记录一段时间内所有数据的访问次数,当缓存区满的时候,会优先淘汰访问次数最少的数据。其核心思想:如果一个数据在最近一段时间内访问次数很少,则在将来一段时间内被访问的可能性也很小。显然,这是一种合理的算法,因为到目前为止最少使用的页面,很可能也是将来最少访问的页面。缓存的每个数据都有引用计数,所有数据按照引用计数排序,具有相同引用计数的数据按照时间排序。

LRU

LRU 全称 Least Recently Used,基于数据访问历史记录来执行淘汰策略,LRU是首先淘汰最长时间未被使用的页面,这种算法把近期最久没有被访问过的页面作为被替换的页面,与LFU不一样的是,LRU并不关注缓存数据的访问次数,它只关注该条数据的访问时间。核心思想:如果一个数据在最近一段时间内没被访问,则在将来一段时间内被访问的可能性也很小。

FIFO VS LRU VS LFU

FIFO完全是公平的策略,不考虑特定时间段内访问频次和访问时间,适合用在某些公平调度的场景下。

当存在热点数据时,LRU的效率很好,但偶发性的、周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重,此时适合使用LFU来做缓存。此外从实现的复杂度上来分析,LFU 需要维护一个队列记录所有数据的访问记录,每个数据都要维护引用计数,内存消耗和性能消耗都较高,而LRU相对来说,实现比较简单,因为不需要考虑计数的问题,仅仅考虑访问时间,非常适合使用双向链表+HashMap来实现O(1)性能的LRU。

总结

本文主要介绍了缓存置换算法的相关概念,原理和置换策略等相关内容,最后并对比分析了常见置换算法的优缺点。缓存作为一种互联网开发必备的组件,理解其置换算法的原理至关重要,值得每一位同学学习和研究。

历史文章:

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-07-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 我是攻城师 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 为什么需要缓存
  • 缓存为什么需要置换
  • 常见的置换算法
  • FIFO
  • LFU
  • LRU
  • FIFO VS LRU VS LFU
  • 总结
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档