高速缓存

计算机程序运行时遵循局部性原理：

• 时间局部性：程序中的某条指令被执行，不久后该条指令可能再次被执行；某数据被访问，不久后该数据可能再次被访问（保留一段时间，等到之后被访问）
  • 指令循环执行
  • 局部变量集中存储，被频繁访问
• 空间局部性：程序访问了某个存储单元，它附近的存储单元也可能被访问（将邻近单元内容调入，等待之后被访问）
  • 指令顺序执行
  • 数组

引入高速缓存

典型的存储器层次结构如下图

CPU设计的目的是实现高速计算，存储器设计的目的是实现大容量存储，两种器件需要分离。为了获得存取时间和存储容量的折中(tradeoff)，弥补CPU与内存的性能差异，把CPU性能的提升利用起来，在CPU内部引入了高速缓存。从CPU Cache被加入到现有的CPU开始，内存中的指令、数据会被加载到L1-L3中，而不是CPU问内存去拿，其中L1-L3指由SRAM(static RAM)组成的物理芯片。

运行程序的主要事件花在了将对应的数据从内存中读取出来，加载到CPU Cache中，读取的单位称作Cache Line(缓存块)，大小通常是​.

高速缓存采用纯硬件设计，原因包括：（参考AI）

高速缓存（Cache）是计算机体系结构中的一个重要组成部分，它位于CPU和主内存之间，用于减少处理器访问内存所需的时间。高速缓存采用纯硬件设计的主要原因有以下几点：

• 速度需求：为了匹配CPU的高速度，Cache需要极快的响应时间。纯硬件设计可以提供更低的访问延迟，因为它是通过电路直接实现的，而不需要操作系统的介入。

• 传输效率：硬件设计可以支持并行处理，这意味着Cache可以同时处理多个数据请求，从而提高数据传输的效率；硬件Cache能够直接在CPU和内存之间进行数据的快速传递，而不需要经过操作系统或其他软件层。这样可以避免软件层的开销，提高数据传输的效率。

• 预测和预取：硬件Cache能够实现复杂的预测算法和预取策略，如旁路预测和指令预取，这些算法可以提前将可能需要的数据加载到Cache中，从而进一步提高性能。

• 一致性：在多处理器系统中，保持内存的一致性是一个复杂的问题。硬件Cache通过使用一致性协议（如MESI协议）来确保不同CPU核心看到的内存视图是一致的。

• 专用性：硬件设计可以根据Cache的特定需求进行优化，如缓存行的设计、关联度、替换策略等，这些优化可以显著提高Cache的命中率。

• 集成性：随着工艺技术的发展，将Cache集成到CPU芯片内部成为可能，这样可以进一步减少访问延迟，并提高整体的系统性能。

• 稳定性：硬件设计一旦完成并验证，通常非常稳定，不易受到软件错误的影响。减少了开发人员编写和管理缓存逻辑的需求。这样可以避免由于软件实现的错误而导致的缓存管理问题。

Cache的工作原理

• 块(Block)：Cache与主存交换数据的大小；
• 行(Line)：Cache中存放一个数据的大小，标记包含一个有效位，表示行内数据是否有效，上电时所有行均无效

现代CPU进行数据读取的过程中，无论数据是否已经存储在Cache中，CPU始终会首先访问 Cache，只有当CPU找不到数据时，才会访问内存，并且读取到Cache中。

• 命中率：CPU访问单元所在的主存块在Cache中的概率

• 命中时间：从Cache中获得数据的时间

• 主存访问时间：从主存获得数据的时间

平均访问时间

Cache的映射方法

Cache Line与主存地址的映射。由于Cache全硬件执行，CPU不可见，即不存在Cache地址

直接映射(Direct)

直接映射(Direct)：每个主存块映射到Cache的固定行（模运算）；

全相联映射(Full Associate)

全相联映射(Full Associate)：每个主存块映射到Cache的任意行；

组相联映射(Set Associate)

组相联映射(Set Associate)：每个主存块映射到Cache固定组的任意行；实现组间直接映射（分组减少并行查找），组内全相联映射。

映射方法比较

方法	优点	缺点
直接映射	唯一映射、确定性获取，缓存获取快	空间利用不充分，命中率低
全相联映射	空间利用充分，命中率高	命中判断开销大，缓存获取慢
组相联映射	折中（空间利用充分，组内判断开销可控）

Cache的替换算法

FIFO(First In First Out), LRU(Least Recently Used), LFU(Least Frequently Used), Random

Cache的写入策略

我们现在用的Intel CPU，通常是多核的，每个核有独立属于自己的L1、L2 Cache，还有多个核共用的L3 Cache、主内存。写入Cache的性能比写入主内存快，那么应该将数据写入Cache还是直接写入主存？如何保证多核Cache数据的一致性。

写直达(Write-Through)

如果数据在Cache中，先写到Cache中，再写到主内存中；如果不在Cache中，就直接更新主内存。这种策略速度很慢，无论数据是否在Cache中，都需要把数据写入主存。

写回(Write-Back)

如果要写入的数据在Cache中，就只更新Cache里面的数据。同时标记Cache 里的这个 Block 是脏的（Cache中的数据与主存不一致）如果要写入的数据所对应的CacheBlock 里，放的是其它内存地址的数据，就要判断CacheBlock 里面的数据有没有被标记成脏的。如果是脏的话，要先把这个CacheBlock 里面的数据，写入到主内存里面，然后再把当前要写入的数据写入到Cache里，同时把CacheBlock 标记成脏的。如果 Block 里面的数据没有被标记成脏的，那么我们直接把数据写入到Cache里面，然后再把CacheBlock 标记成脏的。

写回策略要求加载内存数据到Cache时，若Cache Block有脏标记，需先写回主内存，再加载新数据覆盖Cache。此策略下，若多次操作都能命中缓存，因选择性写存，多数时间无需读写主内存，性能远超写直达。标记脏数据旨在实现此优化。

多核Cache之间的一致性

使用多核CPU可以提高CPU吞吐率，但是也带来了缓存一致性的问题。多个CPU核共享L3 Cache，它们L2 Cache中数据可能不同，导致缓存一致性问题

• 写传播：在一个CPU核心里，我们的Cache数据更新，要能够传播到其它对应节点的Cache Line中
• 事务的串行化：在一个CPU核心里数据的读取和写入，在其它节点看起来顺序是一样的。这类似于多个不同的连接访问数据库时，也必须要保证事务的串行化。

总线嗅探

为了解决多个CPU之间的数据传播问题，需要用到总线嗅探，本质上就是把所有读写请求通过总线广播给所有的CPU核心，然后让各个核心去嗅探这些请求，根据本地情况响应。基于总线嗅探机制，最常用的是MESI协议。

MESI协议

MESI是一种写失效协议，只有一个CPU核心负责写数据，其它的核心只是同步读取到这个写入。在这个CPU核心写入Cache之后，会广播一个“失效”请求告诉其它的CPU核心，其它的CPU核心自己是否有“失效”版本的Cache Block，然后也标记成“失效”的。

相对于写失效协议，还有写广播协议，即一个写入请求广播到所有的CPU核心，同时更新到各个核心的Cache，这需要更大的带宽（写失效只需要告知失效的缓存，写广播还需要传输对应的数据）

MESI协议对应了Cache Line的四种状态标记

• Modified：已修改的脏数据，Cache Block已经更新，但是没有写存；
• Exclusive：独占，对应的Cache Line只加载到了当前CPU核对应的Cache中，其它核并没有加载数据到自己的Cache里，此时可以自由地写入数据而不需要告知其它核；
• Shared：共享，在独占状态下，如果收到了来自于总线的读取对应缓存的请求，就会变成共享状态。这时想更新数据，就不能自由修改，而需要向其它CPU核心广播一个请求(RFO, Reuquest For Ownership)，将其它CPU核心的Cache变成无效状态，然后更新当前Cache中的数据；
• Invalidated：Cache Block中的数据已失效；

Java关键字volatile的解释

来源：https://dzone.com/articles/java-volatile-keyword-0

实验过程

实验程序如下：

public class VolatileTest
{
    private static volatile int COUNTER = 0;

    public static void main(String[] args)
    {
        new ChangeListener().start();
        new ChangeMaker().start();
    }

    /**
     * 监听 COUNTER, 如果 COUNTER 变化, 输出 COUNTER 的值,
     * 直到 COUNTER达到 5.
     */
    static class ChangeListener extends Thread
    {
        @Override
        public void run()
        {
            int threadValue = COUNTER;
            while (threadValue < 5)
            {
                if (threadValue != COUNTER)
                {
                    System.out.println("Got Change for COUNTER : " + COUNTER);
                    threadValue = COUNTER;
                }
            }
        }
    }

    /**
     * 每隔 500ms COUNTER 自增 1,
     * 直到 COUNTER 达到 5.
     */
    static class ChangeMaker extends Thread
    {
        @Override
        public void run()
        {
            int threadValue = COUNTER;
            while (COUNTER < 5)
            {
                System.out.println("Incrementing COUNTER to : " + (threadValue + 1));
                COUNTER = ++threadValue;
                try
                {
                    Thread.sleep(500);
                }
                catch (InterruptedException e)
                {
                    e.printStackTrace();
                }
            }
        }
    }
}

程序中定义了一个volatile修饰的int变量COUNTER。然后，定义了两个单独的线程，分别为ChangeListener和ChangeMaker

• ChangeListener：监听COUNTER，如果发生变化，输出COUNTER的值，直到COUNTER达到；
• ChangeMaker：每隔 COUNTER自增，直到COUNTER达到

在main函数中，分别启动这两个线程，观察程序输出结果：

Incrementing COUNTER to : 1
Got Change for COUNTER : 1
Incrementing COUNTER to : 2
Got Change for COUNTER : 2
Incrementing COUNTER to : 3
Got Change for COUNTER : 3
Incrementing COUNTER to : 4
Got Change for COUNTER : 4
Incrementing COUNTER to : 5
Got Change for COUNTER : 5

Process finished with exit code 0

去掉修饰COUNTER的volatile，输出结果：

Incrementing COUNTER to : 1
Incrementing COUNTER to : 2
Incrementing COUNTER to : 3
Incrementing COUNTER to : 4
Incrementing COUNTER to : 5

此时让ChangeListener在循环中等待5ms，输出结果：

Incrementing COUNTER to : 1
Got Change for COUNTER : 1
Incrementing COUNTER to : 2
Got Change for COUNTER : 2
Incrementing COUNTER to : 3
Got Change for COUNTER : 3
Incrementing COUNTER to : 4
Got Change for COUNTER : 4
Incrementing COUNTER to : 5
Got Change for COUNTER : 5

Process finished with exit code 0

解释

volatile关键字会确保我们对变量的读写都同步到主内存里，而不是从Cache里面读取。

• 使用volatile关键字时，两个线程的输出结果相同；

• 去掉volatile关键字后，ChangeListener是一个忙等待的循环，他不断地从线程的Cache中获取COUNTER的值，于是，这个线程就没有时间从主内存里面同步更新后的COUNTER，就会已知卡在COUNTER=0的循环中；

• 让循环等待，让线程有机会把最新的数据从主内存同步到Cache中，于是ChangeListener就能监听到ChangeMaker对COUNTER变量的修改。

参考资料

• 浅析CPU高速缓存(cache)

• https://time.geekbang.org/column/article/107477,109331,109874

• 【Linux】Linux Page Cache页面缓存的原理