c++的可见性，有序性与原子性

c++的可见性，有序性与原子性

1.可见性

  可见性指的当一个线程修改某个变量时，另一个线程也可以看到该变量的值的变化。但是由于编译器的优化或者cpu寄存器以及cache的硬件结构，有可能某个线程改变了某个变量的值后，另一个线程不能观察到值的变化。举个例子

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
static volatile int a = 0;

pthread_mutex_t mutex ;
void *print_msg(void *arg){
    for(int i=0;i<15;i++){
        printf("output : %d\n",a);
        usleep(100);
    }
    return nullptr;
}
int main(int argc,char** argv){
    pthread_t id1;
    int n = 1000;
    pthread_create(&id1,NULL,print_msg,NULL);
    while(n--){
        a++;
    }
    pthread_join(id1,NULL);
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

  对于上诉代码，理论上线程id1应该可以看到全局变量a的变化，但是当我们使用g++进行编译，使用O2优化等级时，g++编译器会直接把1000赋值给a。
使用g++将上述代码编译为汇编

g++ -O2 -S visible.s visible.cpp
1

得到的汇编文件main函数的片段如下：

main:
.LFB2502:
	.cfi_startproc
	endbr64
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	xorl	%esi, %esi
	leaq	_Z9print_msgPv(%rip), %rdx
	xorl	%ecx, %ecx
	movq	%fs:40, %rax
	movq	%rax, 8(%rsp)
	xorl	%eax, %eax
	movq	%rsp, %rdi
	call	pthread_create@PLT
	movl	$100, %edi
	call	usleep@PLT
	movq	(%rsp), %rdi
	xorl	%esi, %esi
	addl	$1000, _ZL1a(%rip)
	call	pthread_join@PLT
	movq	8(%rsp), %rax
	subq	%fs:40, %rax
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

  其中 addl $1000, _ZL1a(%rip) 就是直接把1000赋值给a变量，那么无论如何,另一个线程执行的print_msg函数只能观察到a = 0然后直接变为a = 1000。
备注：g++使用O0优化等级时，汇编出来的指令会和实际c++代码的逻辑一样，所以上诉问题其实是由于编译器优化带来的。

2.有序性

  为了提高cpu的执行效率，现代cpu会将不存在依赖关系的上下两条或多条指令打乱顺序执行，这种技术被程序乱序执行（out of order execution)。而编译器为了提高程序的执行效率，也会对指令的顺序进行优化调整，这就是我们所说的指令重排。来看下面例子

#include

int a = 0;
int b = 1;

int main(int argc,char** argv){
        a = b+1;
        b = 0;
        return 1;
}
1
2
3
4
5
6
7
8
9
10

使用g++进行汇编，使用O2优化等级。

g++ -O2 -S out-of-order.s out-of-order.cpp 
1

得到的汇编文件main函数的片段如下：

main:
.LFB1812:
	.cfi_startproc
	endbr64
	movl	b(%rip), %eax
	movl	$0, b(%rip)
	addl	$1, %eax
	movl	%eax, a(%rip)
	movl	$1, %eax
	ret
1
2
3
4
5
6
7
8
9
10

汇编对应的逻辑是

1.将b赋值给eax寄存器。
2. 将0赋值给b。
3. 将eax寄存器加1，此时eax寄存器里面的值为2。
4. 将eax寄存器赋值给a。
这个逻辑，与c++代码的逻辑顺序是不一样的，在c++代码中，我们是希望a先被赋值为2，b才被赋值为1，而编译器为了提高程序的执行效率，调整了指令的执行顺序。

3.原子性

  原子性是指，指令的执行是不可分割的，要么指令全部执行成功，要么不执行。原子性也是多线程编程中遇到的最常见的线程安全问题。举一个例子

#include
#include 
#include 
#include 
#include 
#include 
#include 

int a = 0;
void *f1(void *arg)
{
    for(int i = 0 ; i < 1000000;i++){
        a++;
    }
    return nullptr;
}

int main(int argc,char** argv){
        pthread_t id1;
        pthread_t id2;

        pthread_create(&id1,NULL,f1,NULL);
        pthread_create(&id2,NULL,f1,NULL);
        std::this_thread::sleep_for(std::chrono::milliseconds(5000));
        std::cout <<  a  << std::endl;
        return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

  理论上，a应该2000000，但是实际上，不管怎么执行，a都不会为2000000。因为a++这条指令的执行并不具备原子性，a++实际由3个cpu指令组成。

1. cpu在内存中取a的值到寄存器。
2. cpu使算术逻辑运算单元ALU将寄存器上的值加1。
3. cpu把寄存器的值写回内存。
   

  从上图中我们可以看到，两个CPU同时读内存，所以取到的a值都为1，然后加1，写回内存，这时两个CPU写回内存的值都是2，这将会导致a的值比期望值减少1。

4.volatile

  c++中的volatile关键字的用处是

1. 保证该变量的读取是从内存中读取，而不是从寄存器中读取。
2. 保证该变量不会被编译器优化掉。
3. 保证两个用volatile修饰的变量的读或者写，不会被编译器优化导致乱序。

  由于volatile修饰的变量对都是从内存中读取，不会存放到cpu寄存器中，解决了编译优化的问题。但是volatile从内存中读取时，同样会遇到cpu优先从cpu cache中读取和写入，导致不同CPU之间缓存不一致的问题。理论上，CPU应该使用MESI协议来保证不同CPU之间的缓存一致性，实际上，为了保证cpu的效率，AMD 用 MOESI协议，Intel 用 MESIF协议来保证缓存一致性，代价就是无法真正的保证缓存强一致性，需要软件使用memory barrier（内存屏障）或者 lock指令前缀等来保证变量在不同cpu cache中的强一致性。可见，c++的volatile并不能保证可见性。
  由于volatile修饰的变量，只是编译器保证两个volatile变量编译出来的指令的顺序是有序的，编译器无法保证cpu真的不会乱序执行，编译器也无法保证一个volatile修饰的变量和一个普通变量之间的执行顺序，所以volatile不保证有序性。
  至于原子性,volatile从来都不保证变量的运算是原子性的。
备注: volatile在不同编译器下表现出来的特性是不一样的，在微软的MSVC编译器中，MSVC会使用Release / Acquire 语义来保证volatile的可见性和有序性，使volatile修饰的变量具有缓存一致性。但是这不是 C++的标准。

5.java的volatile

  如果你在使用c++的同时也使用java，你就会发现，两种语言对应volatile的解释是不一样的，几乎所有的java文章都会告诉你，java的volatile是具有可见性和有序性，因为这是由java编译器来保证的，而且是java语言本身的标准。java的volatile可以保证变量不会被java编译器优化掉，也保证编译器会把变量存储到内存中，并且编译器不会打乱volatile变量指令上下文的顺序（c++的volatile只保证两个同样使用volatile的变量不会被乱序）。这些与C++中的volatile大同小异，最关键的地方是，以X86架构为例，java编译器会使用lock指令前缀来保证缓存一致性和有序性。
  lock前缀指令可以保证当指令执行时，其它CPU没办法对缓存中的变量进行操作。当lock add之类的指令执行完成后，其它的CPU去读取该变量时，必然能够得到最新的值。这就保证了缓存的一致性，同时lock前缀指令自带类似内存屏障（memory barrier）的效果，即lock所在的指令执行之后，它前面的指令都已经执行，这就有了有序性。
延伸阅读:
  lock前缀指令底层实现上是对cpu cache的总线加锁，这是一个类似与互斥锁的硬件实现，当某个cpu对总线加锁时，其它cpu都无法操作cache，只能等待该cpu解锁，所以对性能会有影响。而新的cpu为了减少lock前缀指令对性能的影响，已经将lock前缀指令从对总线加锁变成了对cache中的缓存加锁，这取决于cpu的硬件实现。
  缓存锁的实现又跟MESI协议有关，几乎所有的cpu，为了提高缓存一致的性能，都有Store Buffer和Invalid Queue，对于一个cpu0来说，cpu0把变量a写回内存这个操作看似会把变量a直接写入内存，实际上cpu0会偷懒，只需要写到cache中就算完成了然后异步从cache写回到内存。为了缓存一致，实际上是cpu0写到Store Buffer中，然后发送Invalid指令通知其它的cpu,其它cpu的cache里面a变量的缓存已经无效了。缓存锁的存在则会强制cpu0必须等待其它cpu返回一个Invalid ack才算指令完成。显而易见的是，当其它cpu返回变量a的Invalid ack时，其它cpu里面的Invalid Queue变量a的Invalid指令前面的Invalid指令都已经执行完成了，而cpu0的Store Buffer中的值也都执行写到其它的cpu了，所以就为lock前缀指令带来了类似内存屏障的效果。

6.c++ atomic

  上面说道，c++的volatile在多线程编程中，只能防止编译器优化带来的影响，不能完成改变硬件带来的影响，那c++中能不能实现变量的读写满足可见性，有序性，原子性。答案是能，使用c++ atomic可以使基本类型的变量满足上诉需求（基本类型指bool,int,float等）。c++ atomic可以屏蔽掉编译器对atomic类的优化，同时，通过c++ 11的memory_order，实现atomic类的有序性和可靠性，通过__atomic_fetch_add等函数实现变量的加法，减法的原子性。对于__atomic_fetch_add的底层实现，目前没有详细的资料。我们可以参考java的atomic类，java有一个概念叫做CAS，即compare and exchange。它与普通的指令不一样的地方在于，CAS从取值到计算再到存储值是线程安全的。CAS需要三个参数，要更新的变量V，V的旧值E，V的新值N,CAS会执行以下三个动作。
4. 取变量V的当前值C。
5. 比较当前值C和CAS参数中的V的旧值E。
6. 如果C和E相等，则更新N的值到V中去，并返回true，否则不更新并返回false。

注意，上诉三个动作是不可分割的，要么都执行成功，要么不执行。即CAS是原子性的。如果再进行分析就会发现，在X86架构上，CAS的本质上就lock cmpxchg 指令，而lock指令前缀，也保证了CAS操作的可见性和有序性。
  依靠CAS，我们可以实现变量的加法或者减法为原子性，伪代码如下：

假设变量为int类型，变量名为a,需要加1。
do{
    int old = a;
    int newValue = old + 1;
}while( !CAS(a,old,newValue) );
1
2
3
4
5

如果取了a的值后，计算后赋值给a时，a的值被其它线程改变，那么CAS就会返回false，从而再计算一次，保证a的计算是原子性的。

7.memory order

  c++没有内存屏障，缓存一致性的关键字，但是c++11及之后的版本，提供了更高级一点的memory order概念来保证变量的可见性与有序性。c++11在atomic类中提供了6个memory order。

1. memory_order_relaxed
2. memory_order_consume
3. memory_order_acquire
4. memory_order_release
5. memory_order_acq_rel
6. memory_order_seq_cst

  可查看英文相关定义
  memory_order_relaxed是最宽松的内存顺序，它保证atomic变量的原子性，保证同一线程的同一个atomic变量操作之间的有序性，但是不保证atomic变量与其它任意变量的有序性。
  memory_order_consume和memory_order_acq_rel用的较少，memory_order_consume保证对本次atomic变量的load操作（读取）有依赖的后续读写不会被重排序到load之前，且其它线程使用memory_order_release内存顺序写入该atomic变量及其有依赖关系的变量具有可见性，即memory_order_consume需要与memory_order_release配合。memory_order_acq_rel是memory_order_release和memory_order_acquire的联合，配合atomic变量的load是memory_order_acquire，配合atomic变量的store是memory_order_release。
  memory_order_acquire配合atomic变量的load操作使用，memory_order_acquire保证load操作之后的其它任何变量的读写都不会被重排序到load操作之前。
  memory_order_release配合atomic变量的store操作使用，memory_order_release保证store操作之前的任何变量的读写都不会被重排序到store操作之后。且store操作之前的任何变量的写入，当执行完store操作之后，对其它使用memory_order_acquire和load的同一atomic变量都具有可见性。如下图所示。

  memory_order_seq_cst是最严格的内存顺序，除了满足memory_order_acq_rel的保证以外，memory_order_seq_cst还保证全局顺序一致性。假设有10个线程和10个atomic变量，一个线程只调用一个atomic变量的store操作，那么memory_order_seq_cst可以保证，所有线程看到的这10个atomic变量的store顺序都是一致的（但是具体顺序是随机的，具体顺序可以是变量1->变量2->变量3->…->变量10，也可以是变量3->变量1->变量2->…->变量10,但是所有线程看到顺序必定是一致的）。

8.总结

  在不熟悉无锁编程的或者需要对复杂变量进行增删查改时，请使用锁来保证变量的线程安全。如果你已经对可见性，有序性，原子性都了然于胸，可以尝试去使用无锁编程来提高程序的性能。c++已经将底层的逻辑暴露给程序员了，你可以按照自己的逻辑去任意的优化程序。