图解操作系统-cpu cache

阳光穿透心脏的1/2处 2024-04-01 10:42 57阅读 0赞

不同物理器件的访问速度不一：速度快的代价高、容量小；代价低且容量大，速度较慢。

为充分发挥各种器件优点，计算机存储数据的物理器件不会只选择一种，而是以CPU为核心，由内而外地组建一整套存储体系结构。它将各种不同的器件组合成一个体系，让各种器件扬长避短，从而形成一种快速、大容量、低成本的内存系统。

写高性能程序，须理解存储体系结构并运用好。

### 1 存储体系结构的核心 ###

成本角度，计算机的存储结构被设计成分层，包括寄存器、缓存、内存、磁盘等。

缓存让内存访问速度接近于寄存器访问速度。

过去几十年，处理器速度增长远超内存速度增长。尤其是在2001～2005年间，处理器的时钟频率在以55%的速度增长，而同期内存速度的增长仅为7%。为了缩小处理器和内存之间的速度差距，缓存被设计了。

距离处理器越近，访问速度越快，造价越高，容量就更小。缓存是处理器、内存间的桥梁，分为多层，包括L1、L2、L3层等。缓存速度介于处理器、内存间：

*  访问处理器内部寄存器的速度在1ns内（一个时钟周期）
 *  访问内存速度通常在50～100ns（上百个时钟周期）
 *  缓存
    
     *  靠近处理器最近的L1层缓存的访问速度在1ns～2ns（3个时钟周期）
     *  外层L2和L3层的访问速度在10ns～20ns（几十个时钟周期）

![0c9fa2b36442446f9d438ab9ad78c112.png][]

根据空间局部性、时间局部性原理，一个处理得当程序，缓存命中率要想达到70～90%不难。因此，存储系统加入缓存，可让整个存储系统的性能接近寄存器，且每字节的成本都接近内存，甚至磁盘。

可见缓存结合寄存器速度快、内存造价低，是整个存储体系的灵魂。

### 2 缓存的物理架构 ###

缓存由SRAM（静态随机存储）组成，本质是一种时序逻辑电路，具体的每个单元（比特）由一个个锁存器构成，锁存器就是让电路具有记忆功能。

SRAM单位造价较高，远高于内存的组成结构“DRAM（动态随机存储）”。因为：

*  实现一个锁存器需六个晶体管
 *  实现一个DRAM仅需一个晶体管和一个电容

但DRAM因为结构简单，单位面积可以存放更多数据，所以更适合做内存。为了兼顾这两者的优缺点，于是它们中间需要加入缓存。

DRAM因有电容，不是单纯逻辑电路，所以不能用CMOS工艺，而SRAM可以。所以缓存能集成到芯片内部，而内存和芯片分开制造。

#### 缓存怎样集成到芯片 ####

过去单核时代，处理器和各级缓存都只有一个，因此缓存集成方式单一，即把处理器和缓存直连。2004年，Intel取消4GHz奔腾处理器研发，即处理器以提升主频榨取性能时代结束，多核处理器成为主流。

多核芯片，缓存集成方式：

*  集中式缓存：一个缓存和所有处理器直接相连，多核共享这个缓存
 *  分布式缓存：一个处理器仅和一个缓存相连，一个处理器对应一个缓存
 *  混合式缓存：在L3采用集中式缓存，在L1和L2采用分布式缓存

![a41a1cc934d24e9dbb26626889234e5e.png][]

多核处理器大多采用混合式：

*  L3，所有处理器核共享
 *  L1、L2，每个处理器核特有

### 3 缓存的工作原理 ###

#### 3.1 cache line ####

缓存进行管理的一个最小存储单元，也叫缓存块。从内存向缓存加载数据也是按缓存块进行加载的，一个缓存块和一个内存中相同容量的数据块（下称内存块）对应。

管理缓存块的角度看缓存块的组织形式：

![a8a98ddb01d344e790d88b062df8a946.png][]

小方框代表一个缓存块。整个缓存由组（set）构成，每组由路（way）构成。所以

整个缓存容量 = 组数 \* 路数 \* 缓存块大小

为简化寻址方式，内存地址确定的数据块总被放在一个固定组，但可放在组内任意路，即对特定地址数据的访问，它若要载入缓存，则它放在上图中的行数固定，但具体放到哪列不固定。

根据组、路数不同：

#### 缓存映射方式分类 ####

*  直接相连映射：缓存只有一个路，一个内存块只能放置在特定的组上
    
    当多个内存块映射到同一组，会冲突，因为只有一列，就需将旧缓存块换出，新缓存块放入，这会导致缓存块被频繁替换
 *  全相连映射：缓存只有一个组，所有的内存块都放在这一个组的不同路上
    
    大程度避免冲突，不过，当查询某缓存块时，需逐个遍历每路，且电路实现较难。折中办法就是，采用组组相连映射
 *  组组相连映射：缓存同时由多个组和多个路
    
    与直接相连映射相比，产生冲突可能性更小，与全相连映射相比，查询效率更高，实现更简单

缓存组数一直是2n。虽这样利于查询和定位，但若一个程序刚好以2\{n\}间隔寻址，就会导致地址更多的被映射到同组，而另外一些组就会被映射很少。因此，也有些缓存的组数设计成一个质数，这样即便程序以2^\{n\}间隔寻址，落到同组可能性大大减小，缓存各组的利用率相对均衡。

一个内存块怎样映射到一个缓存块？

#### 缓存块的内部结构 ####

![baf116d001674b408532664bc523d090.png][]

*  V（valid），这缓存块是否有效或是否正在被使用
 *  M（modified），这缓存块是否被写，即“脏”位
 *  B，缓存块的bit个数

假设要寻址一个32位地址，缓存块64字节，缓存组织方式4路组相连，缓存8K。

缓存共32组（8 \* 1024 / 64 / 4=32）。则对任一32位地址Addr ，它映射到缓存的组号（set index）为 Addr对组数32取模，组号同时也等于Addr的第6~10位（ (Addr >> 6) & 0x1F ），Addr低6位很好理解，它是缓存块的内部偏移（ 2 6 2^\{6\} 26为64字节）。

确定需要被映射到哪组后，需在该组的路中查询。查询方式也简单，直接将每个缓存块tag的bit位和地址Addr的高21位逐一匹配：

*  相等，说明该内存块已载入缓存
 *  若无匹配的tag，说明缓存缺失，需将内存块放到该组的一个空闲缓存块上
 *  若所有路的缓存块都正被使用，就需要选择一个缓存块，将其移出缓存，把新的内存块载入

上面这个过程涉及到缓存块状态转换，而状态转换又涉及到有效位V、脏位M、标签tag。

缓存状态转换：

![80a04305abc241f9b09242dc83de8e2f.png][]

当同组的缓存块都被用完，需选择一个缓存块被换出，那选谁换出呢？和缓存块替换策略有关。

### 4 缓存块替换策略 ###

目标：被替换出的数据块应该是将来最晚会被访问的块。但对将来事情无法预测，因为处理器不知程序将来访问哪个地址。因此，现在的缓存替换策略都采用最近最少使用算法（Least Recently Used ，LRU）或类LRU算法。

如程序要顺序访问 B1 、B2、B3、B4、B5地址块，这几个缓存块都映射到缓存的同一组，同时假设缓存采用4路组组相连映射，则当访问B5时，B1就需被替换出来。最简单的利用位矩阵实现。

先定义一个行、列都与缓存路数相同的矩阵。当访问某路对应缓存块，先将该路对应的所有行置为1，然后再将该路对应的所有列置为0。最终结果体现为，缓存块访问时间的先后顺序，由矩阵行中1的个数决定，最近最常访问缓存块对应行1的个数最多。

假设现在一个四路相连的缓存组包含数据块 B1、B2、B3、B4, 数据块的访问顺序为 B2、B3、B1、B4，则LRU矩阵在每次访问后的变化：

![7b692021ec3647f0aec4d732d73885d1.png][]

最终B2对应行的1的个数最少，所以B2将会被优先替换。

### 5 缓存对程序性能的影响 ###

CPU将未来最可能被用到的内存数据加载进缓存。若下次访问内存时：

*  数据已在缓存中，即缓存命中，它获取目标数据的速度很快
 *  若数据不在缓存，即缓存缺失，此时要启动内存数据传输，而内存访问速度相比缓存差很多。所以要避免这种情况

哪些情况易缓存缺失及程序性能影响。

#### 5.1 缓存缺失 ####

缓存性能主要取决于缓存命中率，缓存缺失（cache miss）越少，缓存性能越好。

引起缓存缺失的类型：

##### ① 强制缺失 #####

第一次将数据块读入缓存所产生缺失，也称冷缺失（cold miss），因为当发生缓存缺失时，缓存是空的（冷的）。

因为第一次将数据读入缓存时，缓存不会有数据，这种缺失无法避免。

##### ② 冲突缺失 #####

由于缓存的相连度有限导致的缺失。

##### ③ 容量缺失 #####

由于缓存大小有限导致的缺失。可认为是除了强制缺失、冲突缺失外的缺失。当程序运行的某段时间内，访问地址范围超过缓存大小过多，这样缓存容量就会成为缓存性能瓶颈。

注意和冲突缺失区别：

*  冲突缺失指同组内的缺失
 *  容量缺失描述范围是整个缓存

第②类冲突缺失因为相连度有限。第一步可通过getconf查看缓存信息：

# getconf -a |grep CACHE
    LEVEL1_ICACHE_SIZE                 32768
    LEVEL1_ICACHE_ASSOC                8
    LEVEL1_ICACHE_LINESIZE             64
    LEVEL1_DCACHE_SIZE                 32768
    LEVEL1_DCACHE_ASSOC                8
    LEVEL1_DCACHE_LINESIZE             64
    LEVEL2_CACHE_SIZE                  262144
    LEVEL2_CACHE_ASSOC                 4
    LEVEL2_CACHE_LINESIZE              64
    LEVEL3_CACHE_SIZE                  3145728
    LEVEL3_CACHE_ASSOC                 12
    LEVEL3_CACHE_LINESIZE              64
    LEVEL4_CACHE_SIZE                  0
    LEVEL4_CACHE_ASSOC                 0
    LEVEL4_CACHE_LINESIZE              0

这缓存信息中，L1Cache（LEVEL1\_ICACHE和LEVEL1\_DCACHE分别表示指令缓存、数据缓存）的cache line 大小为64字节，路数为8路，32K，可计算出缓存组数为64组（ 32 K ÷ 8 ÷ 64 = 64 32K\\div8\\div64=64 32K÷8÷64=64）。

第二步，我们使用一个程序来测试缓存的影响：

// cache.c
    #include <stdio.h>
    #include <stdlib.h>
     
    #define M  64
    #define N  10000000
    int main( )
    {
        
       printf("%ld",sizeof(long long));
       long long (*a)[N] = (long long(*)[N])calloc(M * N, sizeof(long long));
     
       for(int i = 0; i < 100000000; i++) {
        
           for(int j = 0; j < 4096; j+=512) {
        
               a[5][j]++;
           }
       }
       return 0;
    }

上面代码中定义了一个二维数组，数组中元素的类型为long long ，元素大小为8字节。所以一个cache line 可以存放  64 ÷ 8 64\\div8 64÷8= 8 8 8个元素。一组是8路，所以一组可以存放 8 × 8 8\\times8 8×8= 64 64 64个元素。一路包含64个cache line，因为前面计算出缓存的组数为64，所以一路可以存放 8 × 64 8\\times64 8×64= 512 512 512个元素。

代码中：

*  第一层循环，执行次数
 *  第二层循环，以512 为间隔访问元素，即每次访问都会落在同一个组内的不同cache line ，因为一组有8路，所以我们迭代到  512 × 8 512\\times8 512×8= 4096 4096 4096的位置。这样可以使同一组刚好可以容纳二层循环需要的地址空间。

运行结果：

# gcc cache.c
    # time ./a.out
    8
    real 0m2.670s
    user 0m2.671s
    sys 0m0.001s

第三步，第二层循环的迭代次数扩大一倍：

# gcc cache.c
    # time ./a.out
    8
    real 0m16.693s
    user 0m16.700s
    sys 0m0.001s

虽然运算量增加了一倍，但运行时间增加6倍，性能劣化三倍。劣化根本原因，当i > 4096，即访问4096后的元素，同组的cache line已全部使用，须替换，且之后的每次访问都会冲突，导致缓存块频繁替换，性能劣化严重。

### 6 程序局部性 ###

分为：

*  时间局部性
    
    被访问过一次的内存位置，很可能不远将来会被再次访问
 *  空间局部性
    
    如果一个内存位置被引用过，那么它邻近位置在不远的将来也有很大概率会被访问。

若程序有很好的局部性，那么在程序运行期间，缓存缺失就很少发生。

利用局部性原理，设计了缓存，把可能会被访问到的少量数据放在缓存中，大大加速CPU访存速度。

虚拟内存的页缓存也同理，未来最有可能会被访问到的页面会被保留在物理内存。所以多级存储结构里，当访问者和被访问者之间的速度不匹配，就是缓存能够发挥作用的场景。同理还有CDN。

修改案例，验证程序局部性对缓存命中率的影响。

#include <stdio.h>
    #include <stdlib.h>
     
    #define M  10000
    #define N  10000
    int main( )
    {
        
       printf("%ld",sizeof(long long));
       long long (*a)[N] = (long long(*)[N])calloc(M * N, sizeof(long long));
       
       for(int i = 0; i < M; i++) {
        
           for(int j = 0; j < N; j++) {
        
               a[i][j]++;
           }
       }
       return 0;
    }

*  修改迭代次数，方便测试
 *  将之前间隔访问数组中的部分元素修改为顺序访问整个数组，访问方式按二维数组的行逐次访问

测试结果：

# gcc -O0 cache.c
    # time ./a.out
    8
    real 0m1.245s
    user 0m0.797s
    sys 0m0.449s

按列访问时，即将内层循环条件提到外：

for(int j = 0; j < N; j++) {
        
        for(int i = 0; i < M; i++) {
        
            a[i][j]++;
        }
    }

运行结果：

# gcc -O0 cache.c
    # time ./a.out
    8
    real 0m2.527s
    user 0m1.980s
    sys 0m0.548s

性能也2倍劣化，主因当按行访问时地址连续，下次访问的元素和当前大概率在同一cache line（一个元素8字节，而一个cache line容纳8个元素），但按列访问时，由于地址跨度大，下次访问的元素基本不可能还在同一cache line，增加cache line被替换的次数，导致性能劣化。

这次编译项都添加-O0选项，告诉编译器不要进行优化，因为编译器聪明，能识别出这种循环外提的优化，所以要先关掉优化。

因缓存使用不当而引起的性能下降的问题：

### 7 伪共享 ###

伪共享（false-sharing），当两个线程同时各自修改两个相邻的变量，由于缓存是按缓存块来组织，当一个线程对一个缓存块执行写操作，须使其他线程含有对应数据的缓存块无效。

这样两个线程都会同时使对方的缓存块无效，导致性能下降。

#### 7.1 案例 ####

#include <stdio.h>
    #include <pthread.h>
     
    struct S{
        
       long long a;
       long long b;
    } s;
     
    void *thread1(void *args)
    {
        
        for(int i = 0;i < 100000000; i++){
        
            s.a++;
        }
        return NULL;
    }
     
    void *thread2(void *args)
    {
        
        for(int i = 0;i < 100000000; i++){
        
            s.b++;
        }
        return NULL;
    }
     
    int main(int argc, char *argv[]) {
        
        pthread_t t1, t2;
        s.a = 0;
        s.b = 0;
        pthread_create(&t1, NULL, thread1, NULL);
        pthread_create(&t2, NULL, thread2, NULL);
        pthread_join(t1, NULL);
        pthread_join(t2, NULL);
        printf("a = %lld, b = %lld\n", s.a, s.b);
        return 0;
    }

创建两个线程，分别修改结构体S中的a 、b 变量。a 、b均为long long 类型，都占8字节，所以a 、b 在同一个cache line中，因此会发生为伪共享。

运行结果：

# gcc -Wall false_sharing.c -lpthread
    # time ./a.out
    a = 100000000, b = 100000000
     
    real 0m0.790s
    user 0m1.481s
    sys 0m0.008s

#### 7.2 解决伪共享 ####

a 、b不要放在同一个cache line，这样两个线程分别操作不同cache line，不会相互影响。

对结构体S修改：

struct S{
        
       long long a;
       long long nop_0;
       long long nop_1;
       long long nop_2;
       long long nop_3;
       long long nop_4;
       long long nop_5;
       long long nop_6;
       long long nop_7;
       long long b;
    } s;

因为a、b中间插入8个long long变量，中间隔64字节，所以a、b肯定会被映射到不同缓存块，程序执行结果：

# gcc -Wall false_sharing.c -lpthread
    # time ./a.out
    a = 100000000, b = 100000000
     
    real 0m0.347s
    user 0m0.693s
    sys 0m0.001s

性能有一倍的提升。

伪共享是一种缓存缺失问题，并发场景中常见。Java并发库里经常会看到为了解决伪共享而进行的数据填充。

### 8 总结 ###

缓存是整个存储体系结构的灵魂，它让内存访问的速度接近于寄存器的访问速度。缓存对程序员是透明的，程序员不必使用特定的API接口来操作缓存工作，它是自动工作的。但如果我们的代码写得不好的话，我们就会感受到缓存不能起作用时的性能下降了。

缓存的映射方式包括了直接相连、全相连、组组相连三种。直接相连映射会导致缓存块被频繁替换；而全相连映射可以很大程度上避免冲突，但查询效率低；组组相连映射，与直接相连映射相比，产生冲突的可能性更小，与全相连映射相比，查询效率更高，实现也更简单。

如果要访问的数据不在缓存中，这就是缓存缺失。当发生缓存缺失时，就需要往缓存中加载目标地址的数据。如果缓存空间不足了，就需要对缓存块进行替换，替换的策略多采用LRU策略。

缓存缺失对性能影响非常大。缓存缺失主要包括强制缺失，冲突缺失和容量缺失。为了避免缓存缺失我们一定要注意程序的局部性，虽然编译器会帮我们做很多事情，但编译器还是有很多情况是无法优化的。

伪共享是一类非常典型的缓存缺失问题。它是由于多个线程都反复使对方的缓存块无效，带来的性能下降。为了解决这一类问题，我们可以考虑让多个线程所共同访问的对象，在物理上隔离开，保证它们不会落在同一个缓存块里。

[0c9fa2b36442446f9d438ab9ad78c112.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/98f20df6933b48efa7ed1ca9b6ccc306.png
[a41a1cc934d24e9dbb26626889234e5e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/6550204354c84f4eb94cff52e1be8659.png
[a8a98ddb01d344e790d88b062df8a946.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/dbe0f7c06afb408893c3434e229cf422.png
[baf116d001674b408532664bc523d090.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/28d53a4f65c946d0b0a89ff8d493df6c.png
[80a04305abc241f9b09242dc83de8e2f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/82ce28bca6c44b10aa03760fdfa8f6fe.png
[7b692021ec3647f0aec4d732d73885d1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/170f2ee78f794a9d9e6d8ba964703b61.png