内存模型 - 简书

大家好，我是dandyhuang。
内存模型（Memory Model）是编程中比较深入的一个问题，它与编程语言有关、与编译器有关、与并发有关、与处理器也有关。但是一旦发生与内存模型相关的问题，总是出现在并发的场景下，多数情况下，我们搞不清楚内存模型和并发有什么关系，似乎紧密相关，又似乎找不到必然的联系。你可以查阅鸟哥翻译的三篇文章硬件内存模型和编程语言内存模型和go内存模型中的背景知识。Memory Model 其实是一个概念，表示在多线程场景下，如何保证数据同步的正确性。 为什么多线程读取共享内存变量的时候会有数据同步正确性问题呢，这里主要涉及到CPU缓存一致性问题和CPU乱序执行的问题

1.1 CPU Cache 的产生背景

计算机中的所有运算操作都是由CPU的寄存器来完成的，CPU指令的执行过程需要涉及数据的读取和写入，这些数据只能来自于计算机主存（通常指RAM）。

CPU的处理速度和内存的访问速度差距巨大，直连内存的访问方式使得CPU资源没有得到充分合理的利用，于是产生了在CPU与主存之间增加高速缓存CPU Cache的设计。

1.2 CPU Cache 模型

CPU Cache模型，缓存分为三级L1/L2/L3，由于指令和数据的行为和热点分布差异很大，因此将L1按照用途划分为L1i（instruction）和L1d（data）.

在多核CPU的结构中，L1和L2是CPU私有的，L3则是所有CPU共享的。

1.3 什么是 Cache Line

Cache line 是 Cache 和 RAM 交换数据的最小单位，通常为 64 Byte。当 CPU 把内存的数据载入 Cache 时，会把临近的共 64 Byte 的数据一同放入同一个Cache line，因为空间局部性：临近的数据在将来被访问的可能性大。

由于CPU Cache缓存数据最小的单位是一个Cache Line（64节），如果两个Core读取了同一个Cache Line，并对Cache Line中的数据频繁读写，就会有Flase Sharing的问题。

1.4 Flase Sharing 问题

false sharing.png

上图中 thread1 位于 core1 ，而 thread2 位于 core2 ，二者均想更新彼此独立的两个变量，但是由于两个变量位于不同核心中的同一个 L1 缓存行中，此时可知的是两个缓存行的状态应该都是 Shared ，而对于同一个缓存行的操作，不同的 core 间必须通过发送 RFO 消息来争夺所有权 (ownership) ，如果 core1 抢到了， thread1 因此去更新该缓存行，把状态变成 Modified ，那就会导致 core2 中对应的缓存行失效变成 Invalid ，当 thread2 取得所有权之后再去更新该缓存行时必须先让 core1 把对应的缓存行刷回 L3 缓存/主存，然后它再从 L3 缓存/主存中加载该缓存行进 L1 之后才能进行修改。然而，这个过程又会导致 core1 对应的缓存行失效变成 Invalid ，这个过程将会一直循环发生，从而导致 L1 高速缓存并未起到应有的作用，反而会降低性能；轮番夺取所有权不但带来大量的 RFO 消息，而且如果某个线程需要读此行数据时，L1 和 L2 缓存上都是失效数据，只有 L3 缓存上是同步好的数据，而从前面的内容可以知道，L3 的读取速度相比 L1/L2 要慢了数十倍，性能下降很大；更坏的情况是跨槽读取，L3 都不能命中，只能从主存上加载，那就更慢了。

CPU 缓存的最小的处理单位永远是缓存行 (Cache Line)，所以当某个核心发送 RFO 消息请求把其他核心对应的缓存行设置成Invalid 从而使得 var1 缓存失效的同时，也会导致同在一个缓存行里的 var2 失效，反之亦然。

Cache Line缓存测试

func main() {

    arr := make([][]int, 64*1024)
    for i := 0; i < len(arr); i++ {
        arr[i] = make([]int, 1024)
    }
    now := time.Now()
    for i := 0; i < len(arr); i++ {
        for j := 0; j < 1024; j++ {
            arr[i][j]++
        }
    }
    timeSpan := time.Since(now).Microseconds()
    fmt.Println("横向遍历耗时：", timeSpan)
    now = time.Now()
    for j := 0; j < 1024; j++ {
        for i := 0; i < len(arr); i++ {
            arr[i][j]++
        }
    }
    timeSpan = time.Since(now).Microseconds()
    fmt.Println("纵向遍历耗时：", timeSpan)
}

横向遍历耗时： 485995  //因为横向写数据的时候，会一直命中CPU缓存，所以比纵向更快一些
纵向遍历耗时： 1705150

1.5 CPU 缓存一致性协议

在MESI（还有MSI、MESIF等等）协议中，每个Cache line（Cache Line的概念后面会补充介绍）有4个状态，可用2个bit表示，它们分别是：

失效（Invalid）缓存段，要么已经不在缓存中，要么它的内容已经过时。为了达到缓存的目的，这种状态的段将会被忽略。一旦缓存段被标记为失效，那效果就等同于它从来没被加载到缓存中。
共享（Shared）缓存段，它是和主内存内容保持一致的一份拷贝，在这种状态下的缓存段只能被读取，不能被写入。多组缓存可以同时拥有针对同一内存地址的共享缓存段，这就是名称的由来。
独占（Exclusive）缓存段，和 S 状态一样，也是和主内存内容保持一致的一份拷贝。区别在于，如果一个处理器持有了某个 E 状态的缓存段，那其他处理器就不能同时持有它，所以叫“独占”。这意味着，如果其他处理器原本也持有同一缓存段，那么它会马上变成“失效”状态。
已修改（Modified）缓存段，属于脏段，它们已经被所属的处理器修改了。如果一个段处于已修改状态，那么它在其他处理器缓存中的拷贝马上会变成失效状态，这个规律和 E 状态一样。此外，已修改缓存段如果被丢弃或标记为失效，那么先要把它的内容回写到内存中——这和回写模式下常规的脏段处理方式一样。

在MESI协议中，每个Cache的Cache控制器不仅知道自己的读写操作，而且也监听(snoop)其它Cache的读写操作。每个Cache line所处的状态根据本核和其它核的读写操作在4个状态间进行迁移。

更多可以看《大话处理器》Cache一致性协议之MESI 这篇文章介绍。

1.5.1 为什么有 MESI 协议还会有缓存一致性问题

由上面的MESI协议，我们可以知道如果满足下面两个条件，你就可以得到完全的顺序一致性：

缓存一收到总线事件，就可以在当前指令周期中迅速做出响应.
处理器如实地按程序的顺序，把内存操作指令送到缓存，并且等前一条执行完后才能发送下一条。

当然，实际上现代处理器一般都无法满足以上条件，主要原因有：

缓存不会及时响应总线事件。如果总线上发来一条消息，要使某个缓存段失效，但是如果此时缓存正在处理其他事情（比如和 CPU 传输数据），那这个消息可能无法在当前的指令周期中得到处理，而会进入所谓的“失效队列（invalidation queue）”，这个消息等在队列中直到缓存有空为止。
处理器一般不会严格按照程序的顺序向缓存发送内存操作指令。当然，有乱序执行（Out-of-Order execution）功能的处理器肯定是这样的。顺序执行（in-order execution）的处理器有时候也无法完全保证内存操作的顺序（比如想要的内存不在缓存中时，CPU 就不能为了载入缓存而停止工作）。
写操作尤其特殊，因为它分为两阶段操作：在写之前我们先要得到缓存段的独占权。如果我们当前没有独占权，我们先要和其他处理器协商，这也需要一些时间。同理，在这种场景下让处理器闲着无所事事是一种资源浪费。实际上，写操作首先发起获得独占权的请求，然后就进入所谓的由“写缓冲（store buffer）”组成的队列（有些地方使用“写缓冲”指代整个队列，我这里使用它指代队列的一条入口）。写操作在队列中等待，直到缓存准备好处理它，此时写缓冲就被“清空（drained）”了，缓冲区被回收用于处理新的写操作。
这些特性意味着，默认情况下，读操作有可能会读到过时的数据（如果对应失效请求还等在队列中没执行），写操作真正完成的时间有可能比它们在代码中的位置晚，一旦牵涉到乱序执行，一切都变得模棱两可。

可以看缓存一致性（Cache Coherency）入门这篇文章了解更多。

1.6 如何解决False Sharding问题

要提高性能，就要避免让CPU频繁同步cacheline。这不单和原子指令本身的性能有关，还会影响到程序的整体性能。最有效的解决方法很直白：尽量避免共享。

一个依赖全局多生产者多消费者队列(MPMC)的程序难有很好的多核扩展性，因为这个队列的极限吞吐取决于同步cache的延时，而不是核心的个数。最好是用多个SPMC或多个MPSC队列，甚至多个SPSC队列代替，在源头就规避掉竞争。
另一个例子是计数器，如果所有线程都频繁修改一个计数器，性能就会很差，原因同样在于不同的核心在不停地同步同一个cacheline。如果这个计数器只是用作打打日志之类的，那我们完全可以让每个线程修改thread-local变量，在需要时再合并所有线程中的值，性能可能有几十倍的差别。

对一些热点数据，如果想避免cache line被其他Core设置为失效，可以通过Pading的方式把每个项凑齐cache line的长度，即可实现隔离，虽然这不可避免的会浪费一些内存。

我们可以看到golang的源码里面 p struct的也用了CacheLinePad的方式来避免了False Sharding的问题

type p struct {

    上面省略
    .....
        
    runSafePointFn uint32 // if 1, run sched.safePointFn at next safe point

    pad cpu.CacheLinePad
}

CacheLinePad 是cpu包下面定义的一个64字节的数组

const CacheLinePadSize = 64
// CacheLinePad is used to pad structs to avoid false sharing.
type CacheLinePad struct{ _ [CacheLinePadSize]byte }

这样能保证p的数据不管怎么拼接都不会跟其他数据在同一个cache line中。因为目前主流的CPU Cache的Cache Line大小都是64Bytes

同样的，brpc源码中，我们也可以看到pading方式的处理

# define BAIDU_CACHELINE_ALIGNMENT __attribute__((aligned(64)))
class BAIDU_CACHELINE_ALIGNMENT Stream {
};

2.2 重排序

2.2.1 重排序执行验证 Demo

func main() {
    count := 0
    for {
        x, y, a, b := 0, 0, 0, 0
        count++
        var wg sync.WaitGroup
        wg.Add(2)
        go func() {
            a = 1
            x = b
            println("thread1 done ", count)
            wg.Done()
        }()
        go func() {
            b = 1
            y = a
            println("thread2 done ", count)
            wg.Done()

        }()
        wg.Wait()
        if x == 0 && y == 0 {
            println("执行次数 ：", count)
            break
        }
    }
}
...
thread2 done  11061
thread1 done  11061
执行次数 ： 11061 // 执行了11061次以后出现了 x=0、y=0的情况

上面demo中我在线程1和线程2中，先分别让a = 1、b = 1，再让x = b、y = a，如果CPU是按顺序执行这些指令的话，无论线程一和线程二中的如何而组合先后执行，永远也不会得到 x = 0、 y = 0的情况。

在执行程序时为了提高性能，编译器和处理器常常会对指令做重排序。重排序分三种类型：

编译器优化的重排序。编译器在不改变单线程程序语义的前提下，可以重新安排语句的执行顺序。
指令级并行的重排序。现代处理器采用了指令级并行技术（Instruction-Level Parallelism， ILP）来将多条指令重叠执行。如果不存在数据依赖性，处理器可以改变语句对应机器指令的执行顺序。
内存系统的重排序。由于处理器使用缓存和读 / 写缓冲区，这使得加载和存储操作看上去可能是在乱序执行。

从源代码到最终实际执行的指令序列，会分别经历下面三种重排序

unorder.png

上述的 1 属于编译器重排序，2 和 3 属于处理器重排序。这些重排序都可能会导致多线程程序出现内存可见性问题。

2.3.1 分支预测

分支预测(Branch predictor):当处理一个分支指令时,有可能会产生跳转,从而打断流水线指令的处理,因为处理器无法确定该指令的下一条指令,直到分支指令执行完毕。流水线越长,处理器等待时间便越长,分支预测技术就是为了解决这一问题而出现的。因此,分支预测是处理器在程序分支指令执行前预测其结果的一种机制。

采用分支预测，处理器猜测进入哪个分支，并且基于预测结果来取指、译码。如果猜测正确，就能节省时间，如果猜测错误，大不了从头再来，刷新流水线，在新的地址处取指、译码。

分支预测有很多方式，详见Wikipedia

2.3.1.1 分支预测 Demo

func main() {
    data := make([]int, 32678)
    for i := 0; i < len(data); i++ {
        data[i] = rand.Intn(256)
    }
    sort.Sort(sort.IntSlice(data))// Sort和非Sort
    now := time.Now()
    count := 0
    for i := 0; i < len(data); i++ {
        if data[i] > 128 {
            count += data[i]
        }
    }
    end := time.Since(now)
    fmt.Println("time : ", end.Microseconds(), "ms count = ", count)
}
sort ：time :  112 ms count =  3101495
非Sort：time :  290 ms count =  3101495

2.4.1 如何解决重排指令

2.4.1.1 内存屏障（Memory barrier、Memory fence）

内存屏障（Memory barrier），也称内存栅栏，内存栅障，屏障指令等，是一类同步屏障指令，它使得 CPU 或编译器在对内存进行操作的时候, 严格按照一定的顺序来执行, 也就是说在memory barrier 之前的指令和memory barrier之后的指令不会由于系统优化等原因而导致乱序。

CPU和编译器提供了memory fence，让用户可以声明访存指令间的可见性(visibility)关系，Java 的 synchronized 原语，以及boost和C++11对memory fence做了抽象，总结为如下几种memory order.

memory order	作用
memory_order_relaxed	没有fencing作用
memory_order_consume	后面依赖此原子变量的访存指令勿重排至此条指令之前
memory_order_acquire	后面访存指令勿重排至此条指令之前
memory_order_release	前面访存指令勿重排至此条指令之后。当此条指令的结果对其他线程可见后，之前的所有指令都可见
memory_order_acq_rel	acquire + release语意
memory_order_seq_cst	acq_rel语意外加所有使用seq_cst的指令有严格地全序关系

2.4.1.2 如

// Thread 1
p.init();
ready = true;
// Thread2
if (ready) {
    p.bar();
}

有了memory order，上面的例子可以这么更正：

// Thread1
p.init();
// 前面访存指令勿重排至此条指令之后
ready.store(true, std::memory_order_release);
// Thread2
// 后面访存指令勿重排至此条指令之前
if (ready.load(std::memory_order_acquire)) {
    p.bar();
}

线程2中的acquire和线程1的release配对，确保线程2在看到ready==true时能看到线程1 release之前所有的访存操作。

注意，memory fence不等于可见性，即使线程2恰好在线程1在把ready设置为true后读取了ready也不意味着它能看到true，因为同步cache是有延时的。memory fence保证的是可见性的顺序：“假如我看到了a的最新值，那么我一定也得看到b的最新值”。

3.1 可见性问题

Happens Before 是Memory Model中一个通用的概念。主要是用来保证内存操作的可见性。如果要保证E1的内存写操作能够被E2读到，那么需要满足：

E1 Happens Before E2；
其他所有针对此内存的写操作，要么Happens Before E1，要么Happens After E2。也就是说不能存在其他的一个写操作E3，这个E3 Happens Concurrently E1/E2。

让我们再回头来看下官方文档 The Go Memory Model，里面讲到， golang 中有数个地方实现了 Happens Before 语义，分别是 init函数、goruntine 的创建、goruntine 的销毁、channel 通讯、锁、sync、sync/atomic.

Init 函数

如果包P1中导入了包P2，则P2中的init函数Happens Before所有P1中的操作
main函数Happens After所有的init函数

Goroutine

Goroutine 的创建 Happens Before 所有此 Goroutine 中的操作
Goroutine 的销毁 Happens After 所有此 Goroutine 中的操作

Channel

channel底层实现主要是由ringbuf、sendqueue、recequeue、mutex组成。
内部实现主要是使用锁来保证一致性，但这把锁并不是标准库里的锁，而是在 runtime 中自己实现的一把更加简单、高效的锁。

Lock

Go里面有Mutex和RWMutex两种锁，RWMutex是在Mutex基础上实现的。所以这里主要说下Mutex。

Mutex是一个公平锁，有正常模式和饥饿模式两种状态。看下mutex结构体

type Mutex struct {
    // 第0位:表示是否加锁，第1位:表示有 goroutine被唤醒，尝试获取锁； 第2位:是否为饥饿状态。
    state int32
    // semaphore，锁的信号量。
    // 一般通过runtime_SemacquireMutex来获取、runtime_Semrelease来释放
    sema  uint32 
}

在看下Mutex加锁是怎么实现的

func (m *Mutex) Lock() {
    // 先CAS判断是否加锁成功，成就返回
    if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
        return
    }
    // lockSlow 里面主要是尝试自旋、正常模式、饥饿模式切换
    m.lockSlow()
}

sync.Mutex底层都是使用Atomic来读写锁的状态。所以我们可以理解为，Mutex都是基于Atomic来实现Happens Before语义。我们下面来看下Atomic是如何实现的。

Atomic

Golang中的Atomic主要保证了三件事，原子性、可见性、有序性。

我们先看下Go的源码里面Atomic 的API，主要包括Swap、CAS、Add、Load、Store、Pointer几类，在IA64 CPU上对应的汇编指令如下：

Swap : 主要是XCHGQ指令
CAS : 主要是 LOCK CMPXCHGQ指令
Add : 主要是 LOCK XADDQ指令
Load : 主要是 MOVQ（Load64）指令
Store : 主要是 XCHGQ指令
Pointer : 主要当做64位int，调用上述相关方法。

关于LOCK prefix和XCHG指令在英特尔开发人员手册 section 8.2.5中，我们找到了如下的解释：

For the Intel486 and Pentium processors, the LOCK# signal is always asserted on the bus during a LOCK operation, even if the area of memory being locked is cached in the processor.

For the P6 and more recent processor families, if the area of memory being locked during a LOCK operation is cached in the processor that is performing the LOCK operation as write-back memory and is completely contained in a cache line, the processor may not assert the LOCK# signal on the bus. Instead, it will modify the memory loca�tion internally and allow it’s cache coherency mechanism to ensure that the operation is carried out atomically. This operation is called “cache locking.” The cache coherency mechanism automatically prevents two or more proces�sors that have cached the same area of memory from simultaneously modifying data in that area.

The I/O instructions, locking instructions, the LOCK prefix, and serializing instructions force stronger orderingon the processor.

Synchronization mechanisms in multiple-processor systems may depend upon a strong memory-ordering model. Here, a program can use a locking instruction such as the XCHG instruction or the LOCK prefix to ensure that a read-modify-write operation on memory is carried out atomically. Locking operations typically operate like I/O operations in that they wait for all previous instructions to complete and for all buffered writes to drain to memory (see Section 8.1.2, “Bus Locking”).

从描述中，我们了解到：LOCK prefix和XCHG 指令前缀提供了强一致性的内(缓)存读写保证，可以保证 LOCK 之后的指令在带 LOCK 前缀的指令执行之后才会执行。同时，我们在手册中还了解到，现代的 CPU 中的 LOCK 操作并不是简单锁 CPU 和主存之间的通讯总线， Intel 在 cache 层实现了这个 LOCK 操作，此因此我们也无需为 LOCK 的执行效率担忧。

PS：Java中的volatile关键字也是基于 Lock prefix 实现的。

从上面可以看到Swap、CAS、Add、Store 都是基于LOCK prefix和XCHG指令实现的，他能保证缓存读写的强一致性。

我们单独来看下Load指令，在IA32、IA64、Arm的CPU架构下就是对应MOV指令。我们写个简单demo验证下。测试代码如下：

var numB uint32

func main() {
   numB = 8
   fmt.Println(normalLoad())
   fmt.Println(atomicLoad())
}

func normalLoad() uint32 {
   a := numB
   return a
}

func atomicLoad() uint32 {
   a := atomic.LoadUint32(&numB)
   return a
}

我们go build -gcflags "-N -l" atomic.go 编译以后再objdump -d atomic导出对应的汇编代码。我们看到normalLoad()和atomicLoad() 对应的汇编代码是一样的，也印证了，我们上面说的atomic.Load方法在IA64 就是简单的MOV指令。

tomicload.png

再回来看，我们知道Golang的Atomic方法保证了三件事，原子性、可见性、有序性。

可见性和有序性Store方法保证了，Load方法使用MOV指令只要能保证原子性就行了。我们知道golang里面是内存对齐的，所以能保证MOV指令是原子的。

更多可以参考探索 Golang 一致性原语

3.2 Golang Happen Before 语义继承图

                +----------+ +-----------+   +---------+
                | sync.Map | | sync.Once |   | channel |
                ++---------+++---------+-+   +----+----+
                 |          |          |          |
                 |          |          |          |
+------------+   | +-----------------+ |          |
|            |   | |       +v--------+ |          |
|  WaitGroup +---+ | RwLock|  Mutex  | |   +------v-------+
+------------+   | +-------+---------+ |   | runtime lock |
                 |                     |   +------+-------+
                 |                     |          |
                 |                     |          |
                 |                     |          |
         +------+v---------------------v   +------v-------+
         | LOAD | other atomic action  |   |runtime atomic|
         +------+--------------+-------+   +------+-------+
                               |                  |
                               |                  |
                  +------------v------------------v+
                  |           LOCK prefix          |
                  +--------------------------------+

感兴趣的go

大家可以添加我的wx一起交流
我是dandyhuang_，码字不易，有不清楚的可以加w一起交流。

reference

Golang Memory Model

atomic_instructions