来源：https://zhuanlan.zhihu.com/p/...网上随便查一下。各大互联网公司的笔试面试特别喜欢考一道算法题，就是LRU缓存机制。来看看最近公司喜欢研究的LRU缓存机制，超火！今天给大家分享一篇关于Cache硬核的技术文章。基本上所有关于Cache的知识点都可以在这篇文章中看到。关于Cache内容的图很多，我不想自己画，所以图都来自《Computer Architecture : A Quantitative Approach》。这是一本神奇的系统架构书，推荐大家阅读。本文主要内容如下，基本涉及Cache的概念、工作原理以及保持一致性的介绍内容。为什么是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[我][j]；可以看出，由于大量循环的存在，我们访问的数据实际上是位于同一个内存中。换句话说，从专业上讲，我们访问的数据具有局部性。我们只需要将这些数据放入一个小而快的存储中，以便可以快速访问相关数据。综上所述，Cache是一种小型存储单元，旨在为CPU提供高速存储访问并发挥数据局部性的优势。1.2实际系统中的Cache让我们展示一下实际系统中的Cache。如上图所示，整个系统的存储架构包括CPU寄存器、L1/L2/L3CACHE、DRAM和硬盘。访问数据时，先找寄存器，如果寄存器中没有L1Cache，L1Cache中没有L2Cache，以此类推，最后找到硬盘。同时，我们可以看到速度和存储容量之间的权衡。容量越小，访问速度越快！其中，需要明确一个概念。CPU和Cache是??按字传输的，而从Cache到主存的传输是按块的，一个块大约64Byte。现有SOC中Cache的一般构成如下。1.3缓存分类缓存根据不同的标准可以分为几类。按数据类型分：I-Cache和D-Cache。其中I-Cache负责放置指令，D-Cache负责模式数据。两者最大的区别在于D-Cache中的数据是可以回写的，而I-Cache是??只读的。按大小划分：分为smallCache和largeCache。无路组（后面会介绍该组）<4KB的称为smallCache，多用于L1Cache，大于4KB的称为largeCache。多用于L2等Cache。按位置分：InnerCache和OuterCache。一般InnerCache属于CPU微架构，比如上图中的L1L2CACHE。不属于CPU微架构的称为外部Cache。按照数据关系分为：Inclusive/exclusiveCache：下级Cache包含上级数据称为inclusiveCache。不包含独占缓存。比如L3Cache中有L2Cache中的数据，那么L2Cache就称为exclusiveCache。Cache的工作原理要弄清楚Cache的工作原理，需要回答四个问题：如何放置数据，如何查询数据，如何替换数据。如果发生写操作，Cache如何处理2.1如何放置数据也很容易解决。我们举个简单的栗子来说明问题。假设我们的主存有32个block，我们的Cache一共有8条Cacheline（一条Cacheline保存一行数据）。假设我们要将主存中的块12放入Cache中。那么应该放在Cache的什么位置呢？三种方法：完全关联。可以放在Cache的任何地方。直接映射。只允许放在Cache的某一行。例如，12mod8组连接（设置关联）。它可以放在Cache的某些行中。比如2路组相连，一共有4组，所以可以放在0和1的其中一个位置。可见全关联和直接映射是Cachesetassociative的两种极端情况。不同的放置方式主要有两个作用：1.组关联组数越多，比较电路越大，但Cache利用率越高，Cachemiss发生概率小。2.组连接数变小，经常更换Cache，但比较电路比较小。这也很好理解。Cache中可以放置内存中块的地方很多，找起来自然很麻烦。2.2如何在Cache中查找数据其实查找数据就是一个比较的过程，如下图所示。我们的地址都是Byte。但是，主缓存之间交换数据的单位是块（block，现代缓存的一个块一般在64Byte左右）。所以地址是最后几位的块偏移量。由于我们使用的是groupconnection，所以还有几个bits代表它存放在哪个group中。group中有一些数据，我们需要比较Tags。如果组中有Tags，说明我们访问的数据在缓存中，可以愉快的使用。例如，以2路组连接为例，如下图所示。T代表标签。直接对比Tag，就可以知道命中与否。如果命中，就根据索引（组号）取出对应的块即可。如图所示使用索引来选择哪个组位于连接的组中。然后并行比较Tags，判断最后是否在Cache中。上图是2-waygroupconnection，也就是两个group并联比较。如果它不在缓存中怎么办？这涉及另一个问题。不在缓存中如何替换Cache？2.3如何替换Cache中的数据Cache中的数据如何替换？这个比较简单明了。随机更换。如果发生缓存未命中，将随机替换一个块。最近最少使用。LRU。最近使用的块最后被替换。先进先出（FIFO），先入先出。其实第一个用的不多，LRU和FIFO可以根据实际情况选择。Cache中的数据什么时候会被替换？还有几种策略。在此缓存中未被替换。如果Cache未命中，则访问地址直接转发到主存，取到的数据不会写入Cache。读取MISS时将被替换。如果读取时Cache中不存在数据，则从主存中读取数据，然后写入Cache中。写MISS时代入。如果写入时Cache中没有该数据，则将数据加载到Cache中再写入。2.4发生写操作怎么办Cache毕竟是临时缓存。如果发生写操作，Cache和主存中的数据就会不一致。如何保证写数据操作是正确的？也有三种策略。Writethrough：直接将数据写回Cache，同时写回主存。对写入速度影响很大。回写：先将数据写回Cache，当Cache中的数据被替换时再写回主存。直写队列：直写和回写的结合。先写回一个队列，再慢慢写到主存。如果多次写入相同的数据，直接写入这个队列。避免频繁写入主存。缓存一致性缓存一致性是Cache中遇到的一个问题。为什么需要缓存来处理一致性？主要是在多核系统中，如果0核读取主存中的数据，写入数据。Core1也读取主从数据。此时core1并不知道数据已经改变，也就是说core1Cache中的数据已经过时了，就会出错。Cache一致性的保证是让多核访问无错。缓存一致性有两种主要策略。策略一：基于监控的一致性策略这种策略是所有缓存都监控每个缓存的写操作。如果缓存中的数据被写入，有两种处理方式。写更新协议：当一个缓存被写入时，所有的缓存都会被更新。写失效协议：当一个缓存被写入时，其他缓存中的数据块就会失效。由于监控成本高，策略1只能用于非常简单的系统。策略二：基于目录的一致性策略这种策略是在主存中维护一张表。记录每个数据块写入了哪个Cache，从而更新相应的状态。一般来说，这种策略用得比较多。又分为以下几种常用策略。SI：对于一个数据块来说，有两种状态：共享和无效。如果是share状态，直接通知其他Cache使对应的block失效。MSI：对于一个数据块，有共享、无效、修改三种状态。其中，修改状态表表示数据只属于这个Cache，已经被修改。当此数据从缓存中逐出时更新主内存。这样做的好处是可以避免大量的主从写。同时，如果数据在无效时写入，需要保证所有其他缓存中数据的标志位不为M，由其负责先写回主存。MESI：一个数据，有4种状态。已修改、无效、共享、独占。独占状态用于标识数据不依赖于其他缓存。想写的时候，直接把Cache状态改成M就行了。我们专注于MESI。图中黑线：CPU访问。红线：总线访问，其他Cache访问。当前状态为I状态时，如果发生处理器读操作prrd。如果其他Cache中有此数据，如果其他Cache中有M状态，则先将M状态写回主存，再读取。不然直接读。最终状态变为S，如果其他缓存中没有该数据，则直接变为E状态。当前状态为S状态。如果发生处理器读操作，它仍然处于S状态。如果发生了处理器写入，则跳转到M状态。如果其他缓存有写操作，则跳转到I状态。当前状态E状态是处理器读取操作或E。发生处理器对M的写入。如果其他缓存有读操作，则变为S状态。当前状态M状态有读操作，仍处于M状态。如果发生写操作，则仍处于M状态。如果其他缓存有读操作，则将数据写回主存，变为S状态。总结Cache在计算机体系结构中有着非常重要的地位。这篇文章讲的是Cache的主要内容，具体细节可以根据某个点进一步研究。近期热点文章推荐：1.1000+Java面试题及答案（2022最新版）2.厉害了！Java协程来了。..3.SpringBoot2.x教程，太全面了！4.不要用爆破爆满画面，试试装饰者模式，这才是优雅的方式！！5.《Java开发手册（嵩山版）》最新发布，赶快下载吧！感觉不错，别忘了点赞+转发！
