深入理解OS--硬件高速缓存，缓存一致性，存储设备

存储技术

1.SRAM，DRAM
静态：更快，用作高速缓存存储器。处理器高速缓存采用SRAM。
动态：用作主存及图形系统的帧缓冲区。内存采用DRAM。

2.内存
2.1.内存数据访问示例
在这里插入图片描述
设备控制器存在缓存。设备芯片自身存在缓存。

2.2.采用并行技术的内存访问示例
在这里插入图片描述
多个内存模块聚合为主存

2.3.内存读取流程
在这里插入图片描述

2.4.内存写入流程
在这里插入图片描述
3.磁盘

3.1.磁盘容量
磁盘容量 = 表面数 * 磁道数 * 平均扇区数 * 扇出尺寸

3.2.磁盘操作
在这里插入图片描述
磁盘访问时间 = 寻道时间 + 旋转时间 + 传送时间

3.3.访问磁盘
在这里插入图片描述

4.固态硬盘
先擦除，后写，写固定次数后，会损坏；但速度快于机械结构的磁盘

局部性

时间局部性：最近一段时间引用的数据，在不远将来可能被再次使用
空间局部性：最近被引用内存位置附近的位置，在不远将来可能被使用

存储器层次结构

在这里插入图片描述
1.存储器层次结构中的缓存

2.带缓存下的数据读取，写入
2.1.缓存命中下
执行读取，从缓存读
执行写入，进一步分为写回和通写。
写回指的是先写入缓存，但后续在合适时间再写入内存。
通写指的是写入缓存，同时也写入内存。

2.2.缓存不命中
读不命中，需要寻找一个缓存位置，从下级加载内容到此位置，这样再次读时，将缓存命中。
写不命中，但需要寻找一个缓存位置，将内容加载到缓存。写缓存。

写回策略下，数据在缓存中被修改时，会被标记为脏数据。
当缓存中找不到一个空闲的缓存位置时，需要按一定策略淘汰缓存中某些元素。如果淘汰的元素被标记为脏，需要写回内存。
选择那个缓存位置，淘汰元素如何确定可以引申出很多管理策略。

3.缓存不命中种类可以分为冷不命中，冲突不命中。
冷不命中指的是缓存中相应位置内不含数据信息。
冲突不命中指的是缓存中相应位置含数据信息，但数据信息不是我们要访问的。

当我们频繁操作的数据集合尺寸超过缓存尺寸时，缓存不命中必然会发生。

高速缓存

在这里插入图片描述
1.通用的高速缓存存储器组织结构

存储地址ｍ位，这些比特位一部分用来定位set，一部分用来定位block内偏移。剩余位用于和每个line中tag执行匹配。
每个line中由tag，valid，block构成。valid表示此line是否包含有效数据。

1.1.linux下查询高速缓存行尺寸
CPU Cache 的数据是从内存中读取过来的，它是以一小块一小块读取数据的，而不是按照单个数组元素来读取数据的，在 CPU Cache 中的，这样一小块一小块的数据，称为 Cache Line（缓存块）。

你可以在你的 Linux 系统，用下面这种方式来查看 CPU 的 Cache Line，你可以看我服务器的 L1 Cache Line 大小是 64 字节，也就意味着 L1 Cache 一次载入数据的大小是 64 字节。
在这里插入图片描述
事实上，CPU 读取数据的时候，无论数据是否存放到 Cache 中，CPU 都是先访问 Cache，只有当 Cache 中找不到数据时，才会去访问内存，并把内存中的数据读入到 Cache 中，但是并不是只读一个数据，而是一次性读取一块一块的数据存放到 CPU Cache 中，CPU 再从 CPU Cache 读取数据。

1.2.如何利用高速缓存提升性能
(1).从提高L1 Cache数据缓存命中率角度
程序设计时应该按内存布局顺序执行数据访问，尽量不变跳跃性的执行数据访问。
(2).从提高L1 Cache指令缓存命中率角度
我们先了解 CPU 的分支预测器。对于 if 条件语句，意味着此时至少可以选择跳转到两段不同的指令执行，也就是 if 还是 else 中的指令。那么，如果分支预测可以预测到接下来要执行 if 里的指令，还是 else 指令的话，就可以「提前」把这些指令放在指令缓存中，这样 CPU 可以直接从 Cache 读取到指令，于是执行速度就会很快。

如果我们需要对一个数组中每个元素执行比较操作，当数组中的元素是随机的，分支预测就无法有效工作，而当数组元素都是是顺序的，分支预测器会动态地根据历史命中数据对未来进行预测，这样命中率就会很高。

如果你肯定代码中的 if 中的表达式判断为 true 的概率比较高，我们可以使用显示分支预测工具，比如在 C/C++ 语言中编译器提供了 likely 和 unlikely 这两种宏，如果 if 条件为 ture 的概率大，则可以用 likely 宏把 if 里的表达式包裹起来，反之用 unlikely 宏。

实际上，CPU 自身的动态分支预测已经是比较准的了，所以只有当非常确信 CPU 预测的不准，且能够知道实际的概率情况时，才建议使用这两种宏。总之，对于指令缓存，有规律的条件分支语句能够让 CPU 的分支预测器发挥作用，进一步提高执行的效率；

1.3.如何提升多核 CPU 的缓存命中率？
而现代 CPU 都是多核心的，线程可能在不同 CPU 核心来回切换执行，这对 CPU Cache 不是有利的，虽然 L3 Cache 是多核心之间共享的，但是 L1 和 L2 Cache 都是每个核心独有的，如果一个线程在不同核心来回切换，各个核心的缓存命中率就会受到影响，相反如果线程都在同一个核心上执行，那么其数据的 L1 和 L2 Cache 的缓存命中率可以得到有效提高，缓存命中率高就意味着 CPU 可以减少访问内存的频率。
当有多个同时执行「计算密集型」的线程，为了防止因为切换到不同的核心，而导致缓存命中率下降的问题，我们可以把线程绑定在某一个 CPU 核心上，这样性能可以得到非常可观的提升。
在 Linux 上提供了 sched_setaffinity 方法，来实现将线程绑定到某个 CPU 核心这一功能。
在这里插入图片描述

2.直接映射高速缓存
在这里插入图片描述
当每个set中只包含一行时，我们称高速缓存是直接映射的。

3.组相联高速缓存
在这里插入图片描述

当每个set中包含不止一个line时，我们称这样的高速缓存是组相联的。

4.全相联高速缓存
在这里插入图片描述

当只有一个set时，我们称这样的高速缓存是全相联的。

5.一个真实的高速缓存层次结构的解剖
在这里插入图片描述

5.1.linux上查看
(1).L1 Cache
查看 CPU 里的 L1 Cache 「数据」缓存的容量大小：

$ cat /sys/devices/system/cpu/cpu0/cache/index0/size
32K

查看 L1 Cache 「指令」缓存的容量大小，则是：

$ cat /sys/devices/system/cpu/cpu0/cache/index1/size
32K

(2).L2 Cache
在 Linux 系统，我们可以通过这条命令，查看 CPU 里的 L2 Cache 的容量大小：

$ cat /sys/devices/system/cpu/cpu0/cache/index2/size
256K

(3).L3 Cache
在 Linux 系统，我们可以通过这条命令，查看 CPU 里的 L3 Cache 的容量大小：

$ cat /sys/devices/system/cpu/cpu0/cache/index3/size 
3072K

5.3.CPU数据访问
当 CPU 需要访问内存中某个数据的时候，如果寄存器有这个数据，CPU 就直接从寄存器取数据即可，如果寄存器没有这个数据，CPU 就会查询 L1 高速缓存，如果 L1 没有，则查询 L2 高速缓存，L2 还是没有的话就查询 L3 高速缓存，L3 依然没有的话，才去内存中取数据。

5.4.内存数据加载
程序执行时，会先将内存中的数据加载到共享的 L3 Cache 中，再加载到每个核心独有的 L2 Cache，最后进入到最快的 L1 Cache，之后才会被 CPU 读取。每个存储器只和相邻的一层存储器设备打交道。

5.5.缓存一致性
那缓存一致性的问题具体是怎么发生的呢？我们以一个含有两个核心的 CPU 作为例子看一看。
假设 A 号核心和 B 号核心同时运行两个线程，都操作共同的变量 i（初始值为 0 ）。
在这里插入图片描述
这时如果 A 号核心执行了 i++ 语句的时候，为了考虑性能，使用了我们前面所说的写回策略，先把值为 1 的执行结果写入到 L1/L2 Cache 中，然后把 L1/L2 Cache 中对应的 Block 标记为脏的，这个时候数据其实没有被同步到内存中的，因为写回策略，只有在 A 号核心中的这个 Cache Block 要被替换的时候，数据才会写入到内存里。

如果这时旁边的 B 号核心尝试从内存读取 i 变量的值，则读到的将会是错误的值，因为刚才 A 号核心更新 i 值还没写入到内存中，内存中的值还依然是 0。这个就是所谓的缓存一致性问题，A 号核心和 B 号核心的缓存，在这个时候是不一致，从而会导致执行结果的错误。
在这里插入图片描述
那么，要解决这一问题，就需要一种机制，来同步两个不同核心里面的缓存数据。要实现的这个机制的话，要保证做到下面这 2 点：
(1).第一点，某个 CPU 核心里的 Cache 数据更新时，必须要传播到其他核心的 Cache，这个称为写传播（Write Propagation）；
(2).第二点，某个 CPU 核心里对数据的操作顺序，必须在其他核心看起来顺序是一样的，这个称为事务的串行化（Transaction Serialization）。

第一点写传播很容易就理解，当某个核心在 Cache 更新了数据，就需要同步到其他核心的 Cache 里。而对于第二点事务的串行化，我们举个例子来理解它。

假设我们有一个含有 4 个核心的 CPU，这 4 个核心都操作共同的变量 i（初始值为 0 ）。A 号核心先把 i 值变为 100，而此时同一时间，B 号核心先把 i 值变为 200，这里两个修改，都会「传播」到 C 和 D 号核心。
在这里插入图片描述
那么问题就来了，C 号核心先收到了 A 号核心更新数据的事件，再收到 B 号核心更新数据的事件，因此 C 号核心看到的变量 i 是先变成 100，后变成 200。

而如果 D 号核心收到的事件是反过来的，则 D 号核心看到的是变量 i 先变成 200，再变成 100，虽然是做到了写传播，但是各个 Cache 里面的数据还是不一致的。

所以，我们要保证 C 号核心和 D 号核心都能看到相同顺序的数据变化，比如变量 i 都是先变成 100，再变成 200，这样的过程就是事务的串行化。

要实现事务串行化，要做到 2 点：
(1).CPU 核心对于 Cache 中数据的操作，需要同步给其他 CPU 核心；
(2).要引入「锁」的概念，如果两个 CPU 核心里有相同数据的 Cache，那么对于这个 Cache 数据的更新，只有拿到了「锁」，才能进行对应的数据更新。(加锁，修改，将写传播到所有其他CPU，释放锁)

那接下来我们看看，写传播和事务串行化具体是用什么技术实现的。

5.5.1.总线嗅探
写传播的原则就是当某个 CPU 核心更新了 Cache 中的数据，要把该事件广播通知到其他核心。最常见实现的方式是总线嗅探（Bus Snooping）。

我还是以前面的 i 变量例子来说明总线嗅探的工作机制，当 A 号 CPU 核心修改了 L1 Cache 中 i 变量的值，通过总线把这个事件广播通知给其他所有的核心，然后每个 CPU 核心都会监听总线上的广播事件，并检查是否有相同的数据在自己的 L1 Cache 里面，如果 B 号 CPU 核心的 L1 Cache 中有该数据，那么也需要把该数据更新到自己的 L1 Cache。

可以发现，总线嗅探方法很简单， CPU 需要每时每刻监听总线上的一切活动，但是不管别的核心的 Cache 是否缓存相同的数据，都需要发出一个广播事件，这无疑会加重总线的负载。

另外，总线嗅探只是保证了某个 CPU 核心的 Cache 更新数据这个事件能被其他 CPU 核心知道，但是并不能保证事务串行化。

于是，有一个协议基于总线嗅探机制实现了事务串行化，也用状态机机制降低了总线带宽压力，这个协议就是 MESI 协议，这个协议就做到了 CPU 缓存一致性。

5.5.2.MESI 协议
MESI 协议其实是 4 个状态单词的开头字母缩写，分别是：
(1).Modified，已修改
代表该 Cache Block 上的数据已经被更新过，但是还没有写到内存里。
(2).Exclusive，独占
代表 Cache Block 里的数据是干净的，也就是说，这个时候 Cache Block 里的数据和内存里面的数据是一致性的。
独占状态的时候，数据只存储在一个 CPU 核心的 Cache 里，而其他 CPU 核心的 Cache 没有该数据。这个时候，如果要向独占的 Cache 写数据，就可以直接自由地写入，而不需要通知其他 CPU 核心，因为只有你这有这个数据，就不存在缓存一致性的问题了，于是就可以随便操作该数据。
在「独占」状态下的数据，如果有其他核心从内存读取了相同的数据到各自的 Cache ，那么这个时候，独占状态下的数据就会变成共享状态。
(3).Shared，共享
代表 Cache Block 里的数据是干净的，也就是说，这个时候 Cache Block 里的数据和内存里面的数据是一致性的。
代表着相同的数据在多个 CPU 核心的 Cache 里都有，所以当我们要更新 Cache 里面的数据的时候，不能直接修改，而是要先向所有的其他 CPU 核心广播一个请求，要求先把其他核心的 Cache 中对应的 Cache Line 标记为「无效」状态，然后再更新当前 Cache 里面的数据。
(4).Invalidated，已失效
表示的是这个 Cache Block 里的数据已经失效了，不可以读取该状态的数据。

这四个状态来标记 Cache Line 四个不同的状态。
我们举个具体的例子来看看这四个状态的转换：
(1).当 A 号 CPU 核心从内存读取变量 i 的值，数据被缓存在 A 号 CPU 核心自己的 Cache 里面，此时其他 CPU 核心的 Cache 没有缓存该数据，于是标记 Cache Line 状态为「独占」，此时其 Cache 中的数据与内存是一致的；
(2).然后 B 号 CPU 核心也从内存读取了变量 i 的值，此时会发送消息给其他 CPU 核心，由于 A 号 CPU 核心已经缓存了该数据，所以会把数据返回给 B 号 CPU 核心。在这个时候， A 和 B 核心缓存了相同的数据，Cache Line 的状态就会变成「共享」，并且其 Cache 中的数据与内存也是一致的；
(3).当 A 号 CPU 核心要修改 Cache 中 i 变量的值，发现数据对应的 Cache Line 的状态是共享状态，则要向所有的其他 CPU 核心广播一个请求，要求先把其他核心的 Cache 中对应的 Cache Line 标记为「无效」状态，然后 A 号 CPU 核心才更新 Cache 里面的数据，同时标记 Cache Line 为「已修改」状态，此时 Cache 中的数据就与内存不一致了。
(4).如果 A 号 CPU 核心「继续」修改 Cache 中 i 变量的值，由于此时的 Cache Line 是「已修改」状态，因此不需要给其他 CPU 核心发送消息，直接更新数据即可。
(5).如果 A 号 CPU 核心的 Cache 里的 i 变量对应的 Cache Line 要被「替换」，发现 Cache Line 状态是「已修改」状态，就会在替换前先把数据同步到内存。

所以，可以发现当 Cache Line 状态是「已修改」或者「独占」状态时，修改更新其数据不需要发送广播给其他 CPU 核心，这在一定程度上减少了总线带宽压力。

事实上，整个 MESI 的状态可以用一个有限状态机来表示它的状态流转。还有一点，对于不同状态触发的事件操作，可能是来自本地 CPU 核心发出的广播事件，也可以是来自其他 CPU 核心通过总线发出的广播事件。下图即是 MESI 协议的状态图：
在这里插入图片描述
MESI 协议的四种状态之间的流转过程，我汇总成了下面的表格，你可以更详细的看到每个状态转换的原因：

5.6.伪共享
现在假设有一个双核心的 CPU，这两个 CPU 核心并行运行着两个不同的线程，它们同时从内存中读取两个不同的数据，分别是类型为 long 的变量 A 和 B，这个两个数据的地址在物理内存上是连续的，如果 Cahce Line 的大小是 64 字节，并且变量 A 在 Cahce Line 的开头位置，那么这两个数据是位于同一个 Cache Line 中，又因为 CPU Cache Line 是 CPU 从内存读取数据到 Cache 的单位，所以这两个数据会被同时读入到了两个 CPU 核心中各自 Cache 中。
在这里插入图片描述
我们来思考一个问题，如果这两个不同核心的线程分别修改不同的数据，比如 1 号 CPU 核心的线程只修改了变量 A，或 2 号 CPU 核心的线程的线程只修改了变量 B，会发生什么呢？

5.6.1.分析伪共享的问题
现在我们结合保证多核缓存一致的 MESI 协议，来说明这一整个的过程。
①. 最开始变量 A 和 B 都还不在 Cache 里面，假设 1 号核心绑定了线程 A，2 号核心绑定了线程 B，线程 A 只会读写变量 A，线程 B 只会读写变量 B。
在这里插入图片描述
②. 1 号核心读取变量 A，由于 CPU 从内存读取数据到 Cache 的单位是 Cache Line，也正好变量 A 和变量 B 的数据归属于同一个 Cache Line，所以 A 和 B 的数据都会被加载到 Cache，并将此 Cache Line 标记为「独占」状态。
在这里插入图片描述
③. 接着，2 号核心开始从内存里读取变量 B，同样的也是读取 Cache Line 大小的数据到 Cache 中，此 Cache Line 中的数据也包含了变量 A 和变量 B，此时 1 号和 2 号核心的 Cache Line 状态变为「共享」状态。

④. 1 号核心需要修改变量 A，发现此 Cache Line 的状态是「共享」状态，所以先需要通过总线发送消息给 2 号核心，通知 2 号核心把 Cache 中对应的 Cache Line 标记为「已失效」状态，然后 1 号核心对应的 Cache Line 状态变成「已修改」状态，并且修改变量 A。
在这里插入图片描述
⑤. 之后，2 号核心需要修改变量 B，此时 2 号核心的 Cache 中对应的 Cache Line 是已失效状态，另外由于 1 号核心的 Cache 也有此相同的数据，且状态为「已修改」状态，所以要先把 1 号核心的 Cache 对应的 Cache Line 写回到内存，然后 2 号核心再从内存读取 Cache Line 大小的数据到 Cache 中，最后把变量 B 修改到 2 号核心的 Cache 中，并将状态标记为「已修改」状态。
在这里插入图片描述
所以，可以发现如果 1 号和 2 号 CPU 核心这样持续交替的分别修改变量 A 和 B，就会重复 ④ 和 ⑤ 这两个步骤，Cache 并没有起到缓存的效果，虽然变量 A 和 B 之间其实并没有任何的关系，但是因为同时归属于一个 Cache Line ，这个 Cache Line 中的任意数据被修改后，都会相互影响，从而出现 ④ 和 ⑤ 这两个步骤。

因此，这种因为多个线程同时读写同一个 Cache Line 的不同变量时，而导致 CPU Cache 失效的现象称为伪共享（False Sharing）。

5.6.2.避免伪共享的方法
因此，对于多个线程共享的热点数据，即经常会修改的数据，应该避免这些数据刚好在同一个 Cache Line 中，否则就会出现为伪共享的问题。

接下来，看看在实际项目中是用什么方式来避免伪共享的问题的。

在 Linux 内核中存在 __cacheline_aligned_in_smp 宏定义，是用于解决伪共享的问题。
在这里插入图片描述
从上面的宏定义，我们可以看到：
(1).如果在多核（MP）系统里，该宏定义是 __cacheline_aligned，也就是 Cache Line 的大小；
(2).而如果在单核系统里，该宏定义是空的；

因此，针对在同一个 Cache Line 中的共享的数据，如果在多核之间竞争比较严重，为了防止伪共享现象的发生，可以采用上面的宏定义使得变量在 Cache Line 里是对齐的。

举个例子，有下面这个结构体：
在这里插入图片描述
结构体里的两个成员变量 a 和 b 在物理内存地址上是连续的，于是它们可能会位于同一个 Cache Line 中，如下图：

所以，为了防止前面提到的 Cache 伪共享问题，我们可以使用上面介绍的宏定义，将 b 的地址设置为 Cache Line 对齐地址，如下：
在这里插入图片描述
这样 a 和 b 变量就不会在同一个 Cache Line 中了，如下图：

所以，避免 Cache 伪共享实际上是用空间换时间的思想，浪费一部分 Cache 空间，从而换来性能的提升。

#define ____cacheline_aligned __attribute__((__aligned__(64)))
struct A
{long a;long b ____cacheline_aligned;
};

总结：
所谓的 Cache Line 伪共享问题就是，多个线程同时读写同一个 Cache Line 的不同变量时，而导致 CPU Cache 失效的现象。那么对于多个线程共享的热点数据，即经常会修改的数据，应该避免这些数据刚好在同一个 Cache Line 中，避免的方式一般有 Cache Line 大小字节对齐，以及字节填充等方法。

6.高速缓存参数的性能影响
(1).命中率
命中率越高越好
(2).命中时间
命中时完成访问操作所需的时间
(3).不命中处罚
不命中时，相比命中需要额外付出的时间。