原子计数、缓存行、争用与总线锁

原子计数、缓存争用与性能问题

操作系统会在什么时候进行线程切换

想必熟背八股的朋友们都知道，操作系统进行线程切换时无非是两种情况：线程时间片用尽和线程主动让出执行权。

线程主动让出执行权时包括等待锁、等待IO操作或者是单纯的sleep，这里我们主要讨论的不是这个问题。

而操作系统是如何知道线程的时间片用尽的呢？实际上，操作系统是根据时钟中断来确认时间片是否用尽的。时钟中断的触发频率通常为100-1000Hz，这在Linux系统中由编译时决定，可以使用zcat /proc/config.gz | grep CONFIG_HZ来查看时钟中断的频率。

比如我的WSL，获取到的结果为

qy@localhost ~/test_c$ zcat /proc/config.gz |grep CONFIG_HZ
# CONFIG_HZ_PERIODIC is not set
CONFIG_HZ_100=y
# CONFIG_HZ_250 is not set
# CONFIG_HZ_300 is not set
# CONFIG_HZ_1000 is not set
CONFIG_HZ=100

这代表我的电脑的时钟中断频率为100Hz，也即每秒钟会有100次时钟中断。操作系统会每秒会进行100次的时钟处理，这其中包括更新系统时间、检查线程时间片是否用尽，如果用尽则调度线程、更新一些系统计数（如load average）等等操作。

CPU会在什么时候处理中断

中断分为硬中断(Hardware interrupt)和软中断(Software interrupt)，顾名思义，硬中断是由计算机的外围硬件引发的中断，而软中断则是由软件自身引发的中断。而时钟中断则属于一种硬中断。

硬中断

由于硬中断并非由CPU内部产生，其到达的时机不固定，CPU不能同时处理指令和中断，所以CPU会将硬中断暂存，每当执行一条指令前，CPU会检查中断寄存器，如果发现有中断则会执行中断处理程序。

这里我们可以看到CPU的指令执行本身是原子的，一条指令过程中并不会被硬中断打断，也就意味着不会被操作系统调度。

软中断

软中断即为程序通过指令触发的中断，除了通过int指令手动调用中断外，其他指令也可能会引起软中断，比如内存访问引起的缺页中断，除法指令引起的除0中断等，这些中断都在指令执行中发生，而具体如何处理取决于操作系统和程序设计。

多核下的竞争冒险

我们来看一段在x86上的C代码，如无特殊说明，这些代码都采用gcc -O2编译。

多核读写同一个变量

#include<stdio.h>
#include<stdint.h>
#include<pthread.h>
// TOTAL 这个数字在我的i7-7700HQ上大部分时间能跑完示例，如果你的CPU性能太好可以酌情加一些
#define TOTAL (100000000)
__attribute__((aligned(4))) static uint32_t counter = 0;

void *add_addl(void *ctx) {
    for (int i = 0; i < TOTAL; i++) {
        // 一条汇编指令，没有锁，也没有原子计数
        asm("addl $0x1, %0":"+m"(counter));
        asm(""); // 空指令
    }
    return NULL;
}

int main() {
    pthread_t t1;
    pthread_t t2;
    pthread_create(&t1, NULL, add_addl, NULL);
    pthread_create(&t2, NULL, add_addl, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("end thread t1 and t2\n");
    printf("counter = %u\n", counter);
    return 0;
}

在执行的最后，其会有什么结果呢？刚刚我们知道，CPU在执行单条指令时不会被操作系统中断，那么结果会是counter = 200000000吗？不幸的是，在大多数CPU下，其结果不会是这个数字，和所有常见的竞争冒险类似，它的结果也是比200000000小的。但如果addl指令是不会被操作系统中断的，那么还有什么会是导致竞争冒险的原因呢？

显然，是多核CPU的导致了这个问题。我们知道，多核CPU是不共享L1、L2缓存的，这样就会导致虽然每个核心上计数器都是原子的，但是由于缓存的不一致，导致最终加起来的总数不一致。不过在单核CPU下，或者是使用某些方式将线程限制在仅在一个核心中运行时，则不会有这种问题。

那么，是因为使用了过期的缓存行吗？将上面的的代码略作修改，修改为下面的代码。

多核读写同一缓存行的不同变量

#include<stdio.h>
#include<stdint.h>
#include<pthread.h>
// TOTAL 这个数字在我的i7-7700HQ上大部分时间能跑完示例，如果你的CPU性能太好可以酌情加一些
#define TOTAL (100000000)
// aligned(64)保证其必然在同一个缓存行内，虽然不写大概率也会在同一个缓存行内
__attribute__((aligned(64))) static uint32_t counter[2] = {0};

void *add_addl_1(void *ctx) {
    for (int i = 0; i < TOTAL; i++) {
        // 和上面一样，但是这是在同一个缓存行内的两个counter
        asm("addl $0x1, %0":"+m"(counter[0]));
        asm("");
    }
    return NULL;
}

void *add_addl_2(void *ctx) {
    for (int i = 0; i < TOTAL; i++) {
        // 同一个缓存行内的另一个计数器
        asm("addl $0x1, %0":"+m"(counter[1]));
        asm("");
    }
    return NULL;
}

int main() {
    pthread_t t1;
    pthread_t t2;
    pthread_create(&t1, NULL, add_addl_1, NULL);
    pthread_create(&t2, NULL, add_addl_2, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("end thread t1 and t2\n");
    printf("counter[0] = %u\n", counter[0]);
    printf("counter[1] = %u\n", counter[1]);
    return 0;
}

运行这段代码，我们会惊讶的发现，其运行结果为两者都是100000000，这可以证明CPU并非是使用了过期的缓存行数据。这里我们就要清楚缓存刷新原理与CPU指令执行的局限性。

即使CPU的单个指令看似是原子的，但是CPU实际上仍然不能直接操作主存，addl指令在实现内部仍然是读内存-增加-写回内存三步走，这也就可以解释为什么单指令多核多线程的不一致了。

缓存争用与总线锁

MESI 协议

如今CPU的缓存刷新方式是使用MESI协议，MESI 协议是 4 个状态单词的开头字母缩写，用于标记缓存行的四种不同状态，其含义分别为：

• Modified，已修改：数据已被该核心修改，但还未写回主存（共享区域）。
• Exclusive，独占：其他核心的缓存中没有该数据，CPU可以随意对该缓存行进行读写。
• Shared，共享：其他核心的缓存行中也有该数据，但所有核心均未对该缓存行的数据进行修改。
• Invalid，已失效：其他核心写入了该数据，这个缓存行的内容已经被修改过了。

现在让我们来看看MESI协议下，上面两种情况是CPU是如何工作的呢？

假设我们的counter的起始地址总是 0x1000，这样可以简化我们的部分讨论，并且和实际情况相差不大。

• 多核读写同一个变量

  由于CPU0和CPU1都需要使用0x1000的数据，我们几乎可以断定在0x1000所在的缓存行中几乎不可能有Exclusive状态的时间。

  1. CPU1等待0x1000缓存行为Shared，读取，寄存器中为0

  2. CPU2等待0x1000缓存行为Shared，读取，寄存器中为0

     注意到此时CPU1和CPU2同时读取了同一个变量，目前其内部的寄存器值也相同

  3. CPU1为该寄存器+1，CPU2也为该寄存器+1

  4. CPU1将增加后的数值1写回0x1000，此时CPU1的缓存行为Modified，CPU2的缓存行为Invalid，内存中值为1

  5. CPU2等待缓存行刷新为Shared，并将增加后的数值1写回0x1000，此时CPU2的缓存行为Modified，CPU1的缓存行为Invalid，内存值仍然为1

  由此可见即使CPU只会写Shared的缓存行，仍然会出现竞争冒险问题，因为多核CPU的读写通常是不会被串行化的，这也就导致了在指令执行过程中数据变为旧数据的情况。

• 多核读写同一缓存行内的不同变量

  1. CPU1等待0x1000缓存行为Shared，读取，寄存器中为0

  2. CPU2等待0x1004缓存行为Shared，读取，寄存器中为0

     注意到此时CPU1和CPU2同时读取了不同的变量，但它们都在同一个缓存行

  3. CPU1为该寄存器+1，CPU2也为该寄存器+1

  4. CPU1将增加后的数值1写回0x1000，此时CPU1的缓存行为Modified，CPU2的缓存行为Invalid，内存中值为1

  5. CPU2等待缓存行刷新为Shared，并将增加后的数值1写回0x1004，此时CPU2的缓存行为Modified，CPU1的缓存行为Invalid，内存值为1，其不会使用老值。

MOESI/MESIF 协议

可以看到，MESI协议下，每当数据脏时，都需要重新写回主存才能够让其他核心获得新数据，然而可以想到的是，CPU内部核心之间传递缓存行的速率会高于CPU与主存之间的通信效率。这也就诞生了MOESI和MESIF两个协议。

与MESI协议类似，但它们各增加了一个状态，增加的状态是对MESI协议的补充。协议的字母顺序仅仅是为了方便发音，其顺序并无含义。

• Owned，拥有：MESI协议下，当数据写入缓存时，其他核心的该缓存都会变为Invalid，这样就导致所有使用该数据的核心一个需要写回主存，而剩下的则需要从主存拿回数据。Owned可以保持其他核心的Shared状态，但Owned的核心可以写入该缓存，并在写入后在CPU内部广播该写入，其他核心无需从主存中再次获取，加快了缓存更新的速度。 AMD、ARM主要使用该技术。
• Forward，转发：与Owned类似，也是可以让缓存之间通信，而不通过主存的方式。但是F状态的是干净的缓存，该缓存由CPU内的L3缓存提供。这样当多个核心读取同一个内存地址时可以不用频繁访问主存。Intel主要使用该技术。

这里的优化对接下来的原理几乎没什么影响。

缓存争用带来的性能问题

上面的例子可以看到，CPU会频繁的争用同一个内存地址，这样在读取和写入时都会引起CPU等待缓存刷新，而这种等待会导致CPU无法执行其他任务，因为指令还未完成，操作系统也无法有效利用这些等待时间，是实打实的多占用了CPU时间。然而这种问题也是可以轻易规避的。显然，只要我们的变量不在同一缓存行，那么问题就迎刃而解。现代CPU的缓存大小通常为64字节，所以只要让变量间隔64字节，那么两个变量就不会映射在同一个缓存行，通常也不会被组相联映射在同一个缓存行里。

让我们先来实际测试一下CPU缓存征用带来的性能下降。我们对 多核读写同一缓存行的不同变量 这里的代码再稍作修改，改为下面的代码。

#include<stdio.h>
#include<stdint.h>
#include<pthread.h>
// TOTAL 这个数字在我的i7-7700HQ上大部分时间能跑完示例，如果你的CPU性能太好可以酌情加一些
#define TOTAL (100000000)
// aligned(64)保证其必然在同一个缓存行内，虽然不写大概率也会在同一个缓存行内，64/4=16，所以我们申请17个int32，分别增加第一个和最后一个
__attribute__((aligned(64))) static uint32_t counter[17] = {0};

void *add_addl_1(void *ctx) {
    for (int i = 0; i < TOTAL; i++) {
        // 和上面一样，但是这是在同一个缓存行内的两个counter
        asm("addl $0x1, %0":"+m"(counter[0]));
        asm("");
    }
    return NULL;
}

void *add_addl_2(void *ctx) {
    for (int i = 0; i < TOTAL; i++) {
        // 同一个缓存行内的另一个计数器
        asm("addl $0x1, %0":"+m"(counter[16]));
        asm("");
    }
    return NULL;
}

int main() {
    pthread_t t1;
    pthread_t t2;
    pthread_create(&t1, NULL, add_addl_1, NULL);
    pthread_create(&t2, NULL, add_addl_2, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("end thread t1 and t2\n");
    printf("counter[0]  = %u\n", counter[0]);
    printf("counter[16] = %u\n", counter[16]);
    return 0;
}

我们让两个线程分别使用两个缓存行，这样就可以尽量保证在每个CPU核心中，它们对缓存行都是独占状态，让我们来看看两个程序运行时间的差异。

# 无缓存行争用版本
end thread t1 and t2
counter[0]  = 100000000
counter[16] = 100000000

real    0m0.181s
user    0m0.336s
sys     0m0.000s

# ============================================
#有缓存行争用版本
end thread t1 and t2
counter[0] = 100000000
counter[1] = 100000000

real    0m0.290s
user    0m0.551s
sys     0m0.010s

我们可以看到缓存行争用在极端情况下带来了60%的额外性能消耗。

总线锁

一些熟悉X86汇编的朋友们可能注意到，我在所有的操作里都没有使用lock这一个X86指令前缀，前面我说的是X86无锁的情况下，如果带上了lock前缀，那么就可以保证是原子操作。然而同样的操作，由于需要提供额外的顺序保障，会有更多的性能消耗。

锁与原子操作

互斥器 (mutex)

CAS原子操作

FAA原子操作

LL/SC原子操作

强弱内存模型架构

更高效的多线程

由此可见，多线程中想要效率更高，除了减少锁的使用，还应该尽量避免将写入较多的多线程的数据放入同一个缓存行中。对于高负载线程，应尽量每个线程绑定一个CPU核心执行，这样可以避免线程颠簸，对于多核CPU而言可能还好，但对于服务器上的多个CPU而言，线程颠簸的代价相对就大得多，因为这意味着要完全从内存中转移线程常用的数据，CPU中的缓存将彻底失效。