一文吃透Cache处理一致性及工作原理
可以随便到网上查一查，各大互联网公司笔试面试特别喜欢考一道算法题，即 lru缓存机制，又顺手查了一下lru缓存机制最近有哪些企业喜欢考察，超级大热门！
今天给大家分享一篇关于 cache 的硬核的技术文，基本上关于cache的所有知识点都可以在这篇文章里看到。
关于 cache 这方面内容图比较多，不想自己画了，所以图都来自《computer architecture ： a quantitative approach》。
这是一本体系架构方面的神书，推荐大家看一下。
本文主要内容如下，基本涉及了cache的概念，工作原理，以及保持一致性的入门内容。
1、为什么需要 cache1.1 为什么需要 cache
我们首先从一张图来开始讲为什么需要 cache.
上图是 cpu 性能和 memory 存储器访问性能的发展。
我们可以看到，随着工艺和设计的演进，cpu 计算性能其实发生了翻天覆地的变化，但是dram存储性能的发展没有那么快。
所以造成了一个问题，存储限制了计算的发展。
容量与速度不可兼得。
如何解决这个问题呢？可以从计算访问数据的规律入手。
我们随便贴段代码：
for （j = 0; j 《 100; j = j + 1）
for（ i = 0; i 《 5000; i = i + 1）
x［i］［j］ = 2 * x［i］［j］;
可以看到，由于大量循环的存在，我们访问的数据其实在内存中的位置是相近的。
换句专业点的话说，我们访问的数据有局部性。
我们只需要将这些数据放入一个小而快的存储中，这样就可以快速访问相关数据了。
总结起来，cache是为了给cpu提供高速存储访问，利用数据局部性而设计的小存储单元。
1.2 实际系统中的 cache
我们展示一下实际系统中的 cache 。
如上图所示，整个系统的存储架构包括了 cpu 的寄存器，l1/l2/l3 cache，dram 和硬盘。
数据访问时先找寄存器，寄存器里没有找 l1 cache， l1 cache 里没有找 l2 cache 依次类推，最后找到硬盘中。
同时，我们可以看到，速度与存储容量的折衷关系。容量越小，访问速度越快！
其中，一个概念需要搞清楚。
cpu 和 cache 是 word 传输的，而 cache 到主存是以块传输的，一块大约 64byte 。
现有 soc 中的 cache 一般组成如下。
1.3 cache 的分类
cache按照不同标准分类可以分为若干类。
按照数据类型划分：i-cache与d-cache。其中i-cache负责放置指令，d-cache负责方式数据。两者最大的不同是d-cache里的数据可以写回，i-cache是只读的。
按照大小划分：分为small cache和large cache。没路组（后文组相连介绍）《4kb叫small cache， 多用于l1 cache， 大于4kb叫large cache。多用于l2及其他cache.
按照位置划分：inner cache和outer cache。一般独属于cpu微架构的叫inner cache， 例如上图的l1 l2 cache。不属于cpu微架构的叫outer cache.
按照数据关系划分：inclusive/exclusive cache： 下级cache包含上级的数据叫inclusive cache。不包含叫exclusive cache。举个例子，l3 cache里有l2 cache的数据，则l2 cache叫exclusive cache。
2、cache的工作原理要讲清楚 cache 的工作原理，需要回答 4 个问题：
数据如何放置
数据如何查询
数据如何被替换
如果发生了写操作，cache如何处理
2.1 数据如何放置
这个问题也好解决。我们举个简单的栗子来说明问题。
假设我们主存中有 32 个块，而我们的 cache 一共有 8 个 cache 行（ 一个 cache 行放一行数据）。
假设我们要把主存中的块 12 放到 cache 里。
那么应该放到 cache 里什么位置呢？
三种方法：
全相连（fully associative）。可以放在cache的任何位置。
直接映射（direct mapped）。只允许放在cache的某一行。比如12 mod 8
组相连（set associative）。可以放在cache的某几行。例如2路组相连，一共有4组，所以可以放在0，1位置中的一个。
可以看到，全相连和直接映射是cache组相连的两种极端情况。
不同的放置方式主要影响有两点：
1、组相连组数越大，比较电路就越大，但cache利用率更高，cache miss发生的概率小。2、组相连数目变小，cache经常发生替换，但是比较电路比较小。
这也好理解，内存中的块在cache中可放置的位置多，自然找起来就麻烦。
2.2 如何在cache中找数据
其实找数据就是一个比对过程，如下图所示。
我们地址都以 byte 为单位的。
但主存于cache之间的数据交换单位都是块（block，现代cache一般一个block大约64byte）。所以地址对最后几位是block offset。
由于我们采用了组相连，则还有几个比特代表的是存储到了哪个组。
组内放着若干数据，我们需要比较tag， 如果组内有tag出现，则说明我们访问的数据在缓存中，可以开心的使用了。
比如举个 2 路组相连的例子，如下图所示。
t表示tag。直接比较tag，就能得知是不是命中了。如果命中了，则根据index（组号）将对应的块取出来即可。
如上图所示。用index选出位于组相连的哪个组。然后并行的比较tag， 判断最后是不是在cache中。上图是2路组相连，也就是说两组并行比较。
那如果不在缓存中呢？这就涉及到另一个问题。
不在缓存中如何替换 cache ？
2.3 如何替换cache中的数据
cache中的数据如何被替换的？这个就比较简单直接。
随机替换。如果发生cache miss里随机替换掉一块。
least recently used. lru。最近使用的块最后替换。
first in， first out （fifo）， 先进先出。
实际上第一个不怎么使用，lru 和 fifo 根据实际情况选择即可。
cache 在什么时候数据会被替换内？也有几种策略。
不在本 cache 替换。如果cache miss了，直接转发访问地址到主存，取到的数据不会写到cache.
在读miss时替换。如果读的时候cache里没有该数据，则从主存读取该数据后写入cache。
在写miss时替换。如果写的时候cache里没有该数据，则将本数据调入cache再写。
2.4 如果发生了写操作怎么办
cache毕竟是个临时缓存。
如果发生了写操作，会造成cache和主存中的数据不一致。如何保证写数据操作正确呢？
也有三种策略。
通写：直接把数据写回cache的同时写回主存。极其影响写速度。
回写：先把数据写回cache， 然后当cache的数据被替换时再写回主存。
通写队列：通写与回写的结合。先写回一个队列，然后慢慢往主存储写。如果多次写同一个数据，直接写这个队列。避免频繁写主存。
3、cache一致性cache 一致性是 cache 中遇到的比较坑的一个问题。
什么原因需要 cache 处理一致性呢？
主要是多核系统中，假如core 0读了主存储的数据，写了数据。core 1也读了主从的数据。这个时候core 1并不知道数据已经被改动了，也就是说，core 1 cache中的数据过时了，会产生错误。
cache一致性的保证就是让多核访问不出错。
cache一致性主要有两种策略。
策略一：基于监听的一致性策略
这种策略是所有cache均监听各cache的写操作，如果一个cache中的数据被写了，有两种处理办法。
写更新协议：某个cache发生写了，就索性把所有cache都给更新了。
写失效协议：某个cache发生写了，就把其他cache中的该数据块置为无效。
策略 1 由于监听起来成本比较大，所以只应用于极简单的系统中。
策略二：基于目录的一致性策略
这种策略是在主存处维护一张表。记录各数据块都被写到了哪些cache， 从而更新相应的状态。一般来讲这种策略采用的比较多。又分为下面几个常用的策略。
si： 对于一个数据块来讲，有share和invalid两种状态。如果是share状态，直接通知其他cache， 将对应的块置为无效。
msi：对于一个数据块来讲，有share和invalid，modified三种状态。其中modified状态表表示该数据只属于这个cache， 被修改过了。当这个数据被逐出cache时更新主存。这么做的好处是避免了大量的主从写入。同时，如果是invalid时写该数据，就要保证其他所有cache里该数据的标志位不为m，负责要先写回主存储。
mesi：对于一个数据来讲，有4个状态。modified， invalid， shared， exclusive。其中exclusive状态用于标识该数据与其他cache不依赖。要写的时候直接将该cache状态改成m即可。
我们着重讲讲 mesi。图中黑线：cpu的访问。红线：总线的访问，其他cache的访问。
当前状态时i状态时，如果发生处理器读操作 prrd。
如果其他cache里有这份数据，如果其他cache里是m态，先 把m态写回主存再读。否则直接读。最终状态变为s。
其他cache里没这个数据，直接变到e状态。
当前状态为s态。
如果发生了处理器读操作，仍然在s态。
如果发生了处理器写操作，则跳转到m状态。
如果其他cache发生了写操作，跳到i态。
当前状态e态
发生了处理器读操作还是e。
发生了处理器写操作变成m。
如果其他cache发生了读操作，变到s状态。
当前状态m态
发生了读操作依旧是m态。
发生了写操作依旧是m态。
如果其他cache发生了读操作，则将数据写回主存储，变换到s态。
4、总结cache 在计算机体系架构中有非常重要的地位，本文讲了 cache中最主要的内容，具体细节可以再根据某个点深入研究。
作者：桔里猫
来源：https://zhuanlan.zhihu.com/p/386919471
版权说明：此文章只做学术分享，版权归原作者所有，若有侵权，请联系修改或删除
以太坊和智能合约在金融合约领域中的应用介绍
三星官方终于确认，Galaxy Fold将会在九月开售
蓄电池容量这一重要的参数的运用与解析
汽车电子中的PCB系统是如何来设计的
灵途科技解析液位检测传感器的应用及优势
一文吃透Cache处理一致性及工作原理
深开鸿亮相虎嗅2023工业AI大会，以开鸿安全数字底座助力工业场景价值最大化
DC/DC电源下方铺铜是否有益
中国成功研发出世界首台拟态计算机 效能提升数百倍
传感器技术在医疗领域中的应用
AD974414位、210 MSPS TxDAC®数模转换器介绍
智能手表的优点和缺点是什么
数字孪生技术将为制造企业成功实现数字化转型提供更多可行性
电力公司正在使用机器学习构建绿色的智能电网
双控开关控制一个灯怎么接线
FF现场总线技术特点、网络结构及在SECCO项目中的应用
边缘计算有什么应用？工业网关能用吗？
FPGA电源设计部分电路原理图解析
什么叫屏蔽线 屏蔽线有什么用 屏蔽线的正确端接方法
高智能全项目多通道食品安全综合检测仪的介绍
今天给大家分享一篇关于 cache 的硬核的技术文，基本上关于cache的所有知识点都可以在这篇文章里看到。
关于 cache 这方面内容图比较多，不想自己画了，所以图都来自《computer architecture ： a quantitative approach》。
这是一本体系架构方面的神书，推荐大家看一下。
本文主要内容如下，基本涉及了cache的概念，工作原理，以及保持一致性的入门内容。
1、为什么需要 cache1.1 为什么需要 cache
我们首先从一张图来开始讲为什么需要 cache.
上图是 cpu 性能和 memory 存储器访问性能的发展。
我们可以看到，随着工艺和设计的演进，cpu 计算性能其实发生了翻天覆地的变化，但是dram存储性能的发展没有那么快。
所以造成了一个问题，存储限制了计算的发展。
容量与速度不可兼得。
如何解决这个问题呢？可以从计算访问数据的规律入手。
我们随便贴段代码：
for （j = 0; j 《 100; j = j + 1）
for（ i = 0; i 《 5000; i = i + 1）
x［i］［j］ = 2 * x［i］［j］;
可以看到，由于大量循环的存在，我们访问的数据其实在内存中的位置是相近的。
换句专业点的话说，我们访问的数据有局部性。
我们只需要将这些数据放入一个小而快的存储中，这样就可以快速访问相关数据了。
总结起来，cache是为了给cpu提供高速存储访问，利用数据局部性而设计的小存储单元。
1.2 实际系统中的 cache
我们展示一下实际系统中的 cache 。
如上图所示，整个系统的存储架构包括了 cpu 的寄存器，l1/l2/l3 cache，dram 和硬盘。
数据访问时先找寄存器，寄存器里没有找 l1 cache， l1 cache 里没有找 l2 cache 依次类推，最后找到硬盘中。
同时，我们可以看到，速度与存储容量的折衷关系。容量越小，访问速度越快！
其中，一个概念需要搞清楚。
cpu 和 cache 是 word 传输的，而 cache 到主存是以块传输的，一块大约 64byte 。
现有 soc 中的 cache 一般组成如下。
1.3 cache 的分类
cache按照不同标准分类可以分为若干类。
按照数据类型划分：i-cache与d-cache。其中i-cache负责放置指令，d-cache负责方式数据。两者最大的不同是d-cache里的数据可以写回，i-cache是只读的。
按照大小划分：分为small cache和large cache。没路组（后文组相连介绍）《4kb叫small cache， 多用于l1 cache， 大于4kb叫large cache。多用于l2及其他cache.
按照位置划分：inner cache和outer cache。一般独属于cpu微架构的叫inner cache， 例如上图的l1 l2 cache。不属于cpu微架构的叫outer cache.
按照数据关系划分：inclusive/exclusive cache： 下级cache包含上级的数据叫inclusive cache。不包含叫exclusive cache。举个例子，l3 cache里有l2 cache的数据，则l2 cache叫exclusive cache。
2、cache的工作原理要讲清楚 cache 的工作原理，需要回答 4 个问题：
数据如何放置
数据如何查询
数据如何被替换
如果发生了写操作，cache如何处理
2.1 数据如何放置
这个问题也好解决。我们举个简单的栗子来说明问题。
假设我们主存中有 32 个块，而我们的 cache 一共有 8 个 cache 行（ 一个 cache 行放一行数据）。
假设我们要把主存中的块 12 放到 cache 里。
那么应该放到 cache 里什么位置呢？
三种方法：
全相连（fully associative）。可以放在cache的任何位置。
直接映射（direct mapped）。只允许放在cache的某一行。比如12 mod 8
组相连（set associative）。可以放在cache的某几行。例如2路组相连，一共有4组，所以可以放在0，1位置中的一个。
可以看到，全相连和直接映射是cache组相连的两种极端情况。
不同的放置方式主要影响有两点：
1、组相连组数越大，比较电路就越大，但cache利用率更高，cache miss发生的概率小。2、组相连数目变小，cache经常发生替换，但是比较电路比较小。
这也好理解，内存中的块在cache中可放置的位置多，自然找起来就麻烦。
2.2 如何在cache中找数据
其实找数据就是一个比对过程，如下图所示。
我们地址都以 byte 为单位的。
但主存于cache之间的数据交换单位都是块（block，现代cache一般一个block大约64byte）。所以地址对最后几位是block offset。
由于我们采用了组相连，则还有几个比特代表的是存储到了哪个组。
组内放着若干数据，我们需要比较tag， 如果组内有tag出现，则说明我们访问的数据在缓存中，可以开心的使用了。
比如举个 2 路组相连的例子，如下图所示。
t表示tag。直接比较tag，就能得知是不是命中了。如果命中了，则根据index（组号）将对应的块取出来即可。
如上图所示。用index选出位于组相连的哪个组。然后并行的比较tag， 判断最后是不是在cache中。上图是2路组相连，也就是说两组并行比较。
那如果不在缓存中呢？这就涉及到另一个问题。
不在缓存中如何替换 cache ？
2.3 如何替换cache中的数据
cache中的数据如何被替换的？这个就比较简单直接。
随机替换。如果发生cache miss里随机替换掉一块。
least recently used. lru。最近使用的块最后替换。
first in， first out （fifo）， 先进先出。
实际上第一个不怎么使用，lru 和 fifo 根据实际情况选择即可。
cache 在什么时候数据会被替换内？也有几种策略。
不在本 cache 替换。如果cache miss了，直接转发访问地址到主存，取到的数据不会写到cache.
在读miss时替换。如果读的时候cache里没有该数据，则从主存读取该数据后写入cache。
在写miss时替换。如果写的时候cache里没有该数据，则将本数据调入cache再写。
2.4 如果发生了写操作怎么办
cache毕竟是个临时缓存。
如果发生了写操作，会造成cache和主存中的数据不一致。如何保证写数据操作正确呢？
也有三种策略。
通写：直接把数据写回cache的同时写回主存。极其影响写速度。
回写：先把数据写回cache， 然后当cache的数据被替换时再写回主存。
通写队列：通写与回写的结合。先写回一个队列，然后慢慢往主存储写。如果多次写同一个数据，直接写这个队列。避免频繁写主存。
3、cache一致性cache 一致性是 cache 中遇到的比较坑的一个问题。
什么原因需要 cache 处理一致性呢？
主要是多核系统中，假如core 0读了主存储的数据，写了数据。core 1也读了主从的数据。这个时候core 1并不知道数据已经被改动了，也就是说，core 1 cache中的数据过时了，会产生错误。
cache一致性的保证就是让多核访问不出错。
cache一致性主要有两种策略。
策略一：基于监听的一致性策略
这种策略是所有cache均监听各cache的写操作，如果一个cache中的数据被写了，有两种处理办法。
写更新协议：某个cache发生写了，就索性把所有cache都给更新了。
写失效协议：某个cache发生写了，就把其他cache中的该数据块置为无效。
策略 1 由于监听起来成本比较大，所以只应用于极简单的系统中。
策略二：基于目录的一致性策略
这种策略是在主存处维护一张表。记录各数据块都被写到了哪些cache， 从而更新相应的状态。一般来讲这种策略采用的比较多。又分为下面几个常用的策略。
si： 对于一个数据块来讲，有share和invalid两种状态。如果是share状态，直接通知其他cache， 将对应的块置为无效。
msi：对于一个数据块来讲，有share和invalid，modified三种状态。其中modified状态表表示该数据只属于这个cache， 被修改过了。当这个数据被逐出cache时更新主存。这么做的好处是避免了大量的主从写入。同时，如果是invalid时写该数据，就要保证其他所有cache里该数据的标志位不为m，负责要先写回主存储。
mesi：对于一个数据来讲，有4个状态。modified， invalid， shared， exclusive。其中exclusive状态用于标识该数据与其他cache不依赖。要写的时候直接将该cache状态改成m即可。
我们着重讲讲 mesi。图中黑线：cpu的访问。红线：总线的访问，其他cache的访问。
当前状态时i状态时，如果发生处理器读操作 prrd。
如果其他cache里有这份数据，如果其他cache里是m态，先 把m态写回主存再读。否则直接读。最终状态变为s。
其他cache里没这个数据，直接变到e状态。
当前状态为s态。
如果发生了处理器读操作，仍然在s态。
如果发生了处理器写操作，则跳转到m状态。
如果其他cache发生了写操作，跳到i态。
当前状态e态
发生了处理器读操作还是e。
发生了处理器写操作变成m。
如果其他cache发生了读操作，变到s状态。
当前状态m态
发生了读操作依旧是m态。
发生了写操作依旧是m态。
如果其他cache发生了读操作，则将数据写回主存储，变换到s态。
4、总结cache 在计算机体系架构中有非常重要的地位，本文讲了 cache中最主要的内容，具体细节可以再根据某个点深入研究。
作者：桔里猫
来源：https://zhuanlan.zhihu.com/p/386919471
版权说明：此文章只做学术分享，版权归原作者所有，若有侵权，请联系修改或删除
以太坊和智能合约在金融合约领域中的应用介绍
三星官方终于确认，Galaxy Fold将会在九月开售
蓄电池容量这一重要的参数的运用与解析
汽车电子中的PCB系统是如何来设计的
灵途科技解析液位检测传感器的应用及优势
一文吃透Cache处理一致性及工作原理
深开鸿亮相虎嗅2023工业AI大会，以开鸿安全数字底座助力工业场景价值最大化
DC/DC电源下方铺铜是否有益
中国成功研发出世界首台拟态计算机 效能提升数百倍
传感器技术在医疗领域中的应用
AD974414位、210 MSPS TxDAC®数模转换器介绍
智能手表的优点和缺点是什么
数字孪生技术将为制造企业成功实现数字化转型提供更多可行性
电力公司正在使用机器学习构建绿色的智能电网
双控开关控制一个灯怎么接线
FF现场总线技术特点、网络结构及在SECCO项目中的应用
边缘计算有什么应用？工业网关能用吗？
FPGA电源设计部分电路原理图解析
什么叫屏蔽线 屏蔽线有什么用 屏蔽线的正确端接方法
高智能全项目多通道食品安全综合检测仪的介绍