起源：https://zhuanlan.zhihu.com/p/...

能够轻易到网上查一查，各大互联网公司口试面试特地喜爱考一道算法题，即 LRU缓存机制，又棘手查了一下LRU缓存机制最近有哪些企业喜爱考查，超级大热门！

明天给大家分享一篇对于 Cache 的硬核的技术文，基本上对于Cache的所有知识点都能够在这篇文章里看到。

对于 Cache 这方面内容图比拟多，不想本人画了，所以图都来自《Computer Architecture : A Quantitative Approach》。

这是一本体系架构方面的神书，举荐大家看一下。

本文次要内容如下，根本波及了Cache的概念，工作原理，以及放弃一致性的入门内容。

为什么须要 Cache

1.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。

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的数据被替换时再写回主存。

  • 通写队列：通写与回写的联合。先写回一个队列，而后缓缓往主存储写。如果屡次写同一个数据，间接写这个队列。防止频繁写主存。

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态。

总结

Cache 在计算机体系架构中有十分重要的位置，本文讲了 Cache中最次要的内容，具体细节能够再依据某个点深入研究。

近期热文举荐：

1.1,000+ 道 Java面试题及答案整顿(2022最新版)

2.劲爆！Java 协程要来了。。。

3.Spring Boot 2.x 教程，太全了！

4.别再写满屏的爆爆爆炸类了，试试装璜器模式，这才是优雅的形式！！

5.《Java开发手册（嵩山版）》最新公布，速速下载！

感觉不错，别忘了顺手点赞+转发哦！