num ++是'int num'的原子吗？

Question

一般地,对于int num,num++(或++num),作为读-修改-写操作中,是不是原子.但我经常看到编译器,例如GCC,为它生成以下代码(在这里尝试):

由于第5行对应于num++一条指令,我们可以得出结论,在这种情况下num++ 是原子的吗？

如果是这样,是否意味着如此生成num++可以在并发(多线程)场景中使用而没有任何数据争用的危险(例如,我们不需要制作它,std::atomic<int>并强加相关成本,因为它是无论如何原子)？

UPDATE

请注意,这个问题不是增量是否是原子的(它不是,而且是问题的开头行).它是否可以在特定场景中,即在某些情况下是否可以利用单指令性质来避免lock前缀的开销.而且,作为公认的答案约单处理器的机器,还有部分提到这个答案,在其评论和其他人谈话解释,它可以(尽管不是C或C++).

Answer 1

这绝对是C++定义为导致未定义行为的数据争用的原因,即使一个编译器碰巧产生了在某些目标机器上执行了您所希望的代码.您需要使用std::atomic可靠的结果,但memory_order_relaxed如果您不关心重新排序,则可以使用它.请参阅下面的一些示例代码和asm输出fetch_add.

但首先,汇编语言部分问题:

由于num ++是一个指令(add dword [num], 1),我们可以得出结论,在这种情况下num ++是原子的吗？

内存目标指令(纯存储除外)是在多个内部步骤中发生的读 - 修改 - 写操作.没有修改架构寄存器,但CPU必须在内部保存数据,同时通过其ALU发送数据.即使是最简单的CPU,实际的寄存器文件也只是数据存储的一小部分,锁存器将一级的输出保持为另一级的输入,等等.

来自其他CPU的内存操作可以在加载和存储之间全局可见.即add dword [num], 1在循环中运行的两个线程将踩到彼此的商店.(参见@Margaret的答案,获得一张漂亮的图表).从两个线程中的每个线程增加40k后,计数器可能仅在实际多核x86硬件上增加了大约60k(而不是80k).

"原子",来自希腊语,意思是不可分割的,意味着没有观察者可以看到操作作为单独的步骤.对于所有位同时发生物理/电气瞬间发生只是实现负载或存储的一种方法,但这对于ALU操作来说甚至都不可能.我在x86上对Atomicity的回答中详细介绍了纯负载和纯存储,而这个答案主要集中在read-modify-write.

的lock前缀可以被应用于许多读-修改-写(存储目的地)的指令,以使整个操作原子与系统中的相对于所有可能的观察者(其它内核和DMA设备,而不是挂在CPU针脚示波器).这就是它存在的原因.(另见本问答).

原子lock add dword [num], 1 也是如此.运行该指令的CPU内核将使高速缓存行在其私有L1高速缓存中保持固定状态,从加载时从高速缓存读取数据,直到存储将其结果提交回高速缓存.根据MESI缓存一致性协议(或多核AMD使用的MOESI/MESIF版本)的规则,这可以防止系统中的任何其他缓存在从加载到存储的任何点都拥有缓存行的副本.分别是英特尔CPU).因此,其他核心的操作似乎发生在之前或之后,而不是在此期间.

如果没有lock前缀,另一个核心可以获取缓存行的所有权并在我们加载之后但在我们的商店之前修改它,以便其他商店在我们的加载和存储之间变得全局可见.其他几个答案都是错误的,声称没有lock你会得到相同缓存行的冲突副本.在具有连贯缓存的系统中永远不会发生这种情况.

(如果locked指令对跨越两个缓存行的内存进行操作,则需要做更多的工作才能确保对象的两个部分的更改在传播到所有观察者时保持原子性,因此没有观察者可以看到撕裂.CPU可能必须锁定整个内存总线,直到数据到达内存.不要错位你的原子变量!)

请注意,lock前缀还将指令转换为完整的内存屏障(如MFENCE),停止所有运行时重新排序,从而提供顺序一致性.(请参阅Jeff Preshing的优秀博客文章.他的其他帖子也非常出色,并清楚地解释了很多关于无锁编程的好东西,从x86和其他硬件细节到C++规则.)

在单处理器机器上,或在单线程进程中,单个RMW指令实际上是原子的,没有lock前缀.其他代码访问共享变量的唯一方法是让CPU执行上下文切换,这不能在指令中间发生.因此,plain dec dword [num]可以在单线程程序与其信号处理程序之间或在单核机器上运行的多线程程序之间进行同步.请参阅我对另一个问题的答案的后半部分以及其中的评论,我将在其中更详细地解释这一点.

回到C++:

在num++没有告诉编译器你需要它编译成单个读 - 修改 - 写实现的情况下使用它是完全虚假的:

;; Valid compiler output for num++
mov   eax, [num]
inc   eax
mov   [num], eax

如果您使用num稍后的值,则很可能:编译器会在增量后将其保留在寄存器中.因此,即使您自己检查num++编译方式,更改周围的代码也会影响它.

(如果稍后不需要该值,inc dword [num]则首选;现代x86 CPU将至少与使用三个单独的指令一样有效地运行内存目标RMW指令.有趣的事实:gcc -O3 -m32 -mtune=i586实际上会发出这个,因为(Pentium)P5的超标量管道没有不像P6和后来的微体系结构那样将复杂指令解码为多个简单的微操作.有关更多信息,请参阅Agner Fog的指令表/微架构指南,以及许多有用链接的x86标签wiki(包括Intel的x86 ISA手册,免费提供PDF)).

不要将目标内存模型(x86)与C++内存模型混淆

允许编译时重新排序.使用std :: atomic获得的另一部分是对编译时重新排序的控制,以确保num++只有在执行其他操作后才能全局可见.

经典示例:将一些数据存储到缓冲区中以供另一个线程查看,然后设置一个标志.即使x86确实免费获取加载/发布存储,您仍然必须告诉编译器不要使用重新排序flag.store(1, std::memory_order_release);.

您可能希望此代码与其他线程同步:

// flag is just a plain int global, not std::atomic<int>.
flag--;       // This isn't a real lock, but pretend it's somehow meaningful.
modify_a_data_structure(&foo);    // doesn't look at flag, and the compilers knows this.  (Assume it can see the function def).  Otherwise the usual don't-break-single-threaded-code rules come into play!
flag++;

But it won't. The compiler is free to move the flag++ across the function call (if it inlines the function or knows that it doesn't look at flag). Then it can optimize away the modification entirely, because flag isn't even volatile. (And no, C++ volatile is not a useful substitute for std::atomic. std::atomic does make the compiler assume that values in memory can be modified asynchronously similar to volatile, but there's much more to it than that. Also, volatile std::atomic<int> foo is not the same as std::atomic<int> foo, as discussed with @Richard Hodges.)

Defining data races on non-atomic variables as Undefined Behaviour is what lets the compiler still hoist loads and sink stores out of loops, and many other optimizations for memory that multiple threads might have a reference to. (See this LLVM blog for more about how UB enables compiler optimizations.)

As I mentioned, the x86 lock prefix is a full memory barrier, so using num.fetch_add(1, std::memory_order_relaxed); generates the same code on x86 as num++ (the default is sequential consistency), but it can be much more efficient on other architectures (like ARM). Even on x86, relaxed allows more compile-time reordering.

This is what GCC actually does on x86, for a few functions that operate on a std::atomic global variable.

See the source + assembly language code formatted nicely on the Godbolt compiler explorer. You can select other target architectures, including ARM, MIPS, and PowerPC, to see what kind of assembly language code you get from atomics for those targets.

#include <atomic>
std::atomic<int> num;
void inc_relaxed() {
  num.fetch_add(1, std::memory_order_relaxed);
}

int load_num() { return num; }            // Even seq_cst loads are free on x86
void store_num(int val){ num = val; }
void store_num_release(int val){
  num.store(val, std::memory_order_release);
}
// Can the compiler collapse multiple atomic operations into one? No, it can't.

# g++ 6.2 -O3, targeting x86-64 System V calling convention. (First argument in edi/rdi)
inc_relaxed():
    lock add        DWORD PTR num[rip], 1      #### Even relaxed RMWs need a lock. There's no way to request just a single-instruction RMW with no lock, for synchronizing between a program and signal handler for example. :/ There is atomic_signal_fence for ordering, but nothing for RMW.
    ret
inc_seq_cst():
    lock add        DWORD PTR num[rip], 1
    ret
load_num():
    mov     eax, DWORD PTR num[rip]
    ret
store_num(int):
    mov     DWORD PTR num[rip], edi
    mfence                          ##### seq_cst stores need an mfence
    ret
store_num_release(int):
    mov     DWORD PTR num[rip], edi
    ret                             ##### Release and weaker doesn't.
store_num_relaxed(int):
    mov     DWORD PTR num[rip], edi
    ret

Notice how MFENCE (a full barrier) is needed after a sequential-consistency stores. x86 is strongly ordered in general, but StoreLoad reordering is allowed. Having a store buffer is essential for good performance on a pipelined out-of-order CPU. Jeff Preshing's Memory Reordering Caught in the Act shows the consequences of not using MFENCE, with real code to show reordering happening on real hardware.

Re: discussion in comments on @Richard Hodges' answer about compilers merging std::atomic num++; num-=2; operations into one num--; instruction:

A separate Q&A on this same subject: Why don't compilers merge redundant std::atomic writes?, where my answer restates a lot of what I wrote below.

Current compilers don't actually do this (yet), but not because they aren't allowed to. C++ WG21/P0062R1: When should compilers optimize atomics? discusses the expectation that many programmers have that compilers won't make "surprising" optimizations, and what the standard can do to give programmers control. N4455 discusses many examples of things that can be optimized, including this one. It points out that inlining and constant-propagation can introduce things like fetch_or(0) which may be able to turn into just a load() (but still has acquire and release semantics), even when the original source didn't have any obviously redundant atomic ops.

The real reasons compilers don't do it (yet) are: (1) nobody's written the complicated code that would allow the compiler to do that safely (without ever getting it wrong), and (2) it potentially violates the principle of least surprise. Lock-free code is hard enough to write correctly in the first place. So don't be casual in your use of atomic weapons: they aren't cheap and don't optimize much. It's not always easy easy to avoid redundant atomic operations with std::shared_ptr<T>, though, since there's no non-atomic version of it (although one of the answers here gives an easy way to define a shared_ptr_unsynchronized<T> for gcc).

Getting back to num++; num-=2; compiling as if it were num--: Compilers are allowed to do this, unless num is volatile std::atomic<int>. If a reordering is possible, the as-if rule allows the compiler to decide at compile time that it always happens that way. Nothing guarantees that an observer could see the intermediate values (the num++ result).

I.e. if the ordering where nothing becomes globally visible between these operations is compatible with the ordering requirements of the source (according to the C++ rules for the abstract machine, not the target architecture), the compiler can emit a single lock dec dword [num] instead of lock inc dword [num]/lock sub dword [num], 2.

num++; num-- can't disappear, because it still has a Synchronizes With relationship with other threads that look at num, and it's both an acquire-load and a release-store which disallows reordering of other operations in this thread. For x86, this might be able to compile to an MFENCE, instead of a lock add dword [num], 0 (i.e. num += 0).

As discussed in PR0062, more aggressive merging of non-adjacent atomic ops at compile time can be bad (e.g. a progress counter only gets updated once at the end instead of every iteration), but it can also help performance without downsides (e.g. skipping the atomic inc/dec of ref counts when a copy of a shared_ptr is created and destroyed, if the compiler can prove that another shared_ptr object exists for entire lifespan of the temporary.)

num++; num--当一个线程立即解锁并重新锁定时,即使合并也可能会损害锁定实现的公平性.如果它实际上从未在asm中实际发布,那么即使是硬件仲裁机制也不会让另一个线程有机会在那时获取锁.

使用当前的gcc6.2和clang3.9,lock即使memory_order_relaxed在最明显可优化的情况下,您仍然可以获得单独的ed操作.(Godbolt编译器浏览器,以便您可以看到最新版本是否不同.)

void multiple_ops_relaxed(std::atomic<unsigned int>& num) {
  num.fetch_add( 1, std::memory_order_relaxed);
  num.fetch_add(-1, std::memory_order_relaxed);
  num.fetch_add( 6, std::memory_order_relaxed);
  num.fetch_add(-5, std::memory_order_relaxed);
  //num.fetch_add(-1, std::memory_order_relaxed);
}

multiple_ops_relaxed(std::atomic<unsigned int>&):
    lock add        DWORD PTR [rdi], 1
    lock sub        DWORD PTR [rdi], 1
    lock add        DWORD PTR [rdi], 6
    lock sub        DWORD PTR [rdi], 5
    ret

Answer 2

...现在让我们启用优化:

f():
        rep ret

好吧,让我们给它一个机会:

void f(int& num)
{
  num = 0;
  num++;
  --num;
  num += 6;
  num -=5;
  --num;
}

结果:

f(int&):
        mov     DWORD PTR [rdi], 0
        ret

另一个观察线程(甚至忽略缓存同步延迟)没有机会观察到个别变化.

相比于:

#include <atomic>

void f(std::atomic<int>& num)
{
  num = 0;
  num++;
  --num;
  num += 6;
  num -=5;
  --num;
}

结果是:

f(std::atomic<int>&):
        mov     DWORD PTR [rdi], 0
        mfence
        lock add        DWORD PTR [rdi], 1
        lock sub        DWORD PTR [rdi], 1
        lock add        DWORD PTR [rdi], 6
        lock sub        DWORD PTR [rdi], 5
        lock sub        DWORD PTR [rdi], 1
        ret

现在,每个修改是: -

1. 在另一个线程中可观察到,和
2. 尊重其他线程中发生的类似修改.

原子性不只是在指令级别,它涉及从处理器,缓存到内存和返回的整个流水线.

更多信息

关于优化更新的效果std::atomic.

c ++标准具有'似乎'规则,允许编译器重新排序代码,甚至重写代码,前提是结果具有完全相同的可观察效果(包括副作用),就好像它只是简单地执行了码.

as-if规则是保守的,特别是涉及原子.

考虑:

void incdec(int& num) {
    ++num;
    --num;
}

因为没有互斥锁,原子或任何其他影响线程间排序的结构,我认为编译器可以自由地将此函数重写为NOP,例如:

void incdec(int&) {
    // nada
}

这是因为在c ++内存模型中,不存在另一个线程观察增量结果的可能性.当然,这将是不同的,如果num是volatile(可能影响硬件的行为).但在这种情况下,此函数将是修改此内存的唯一函数(否则程序格式错误).

然而,这是一个不同的球赛:

void incdec(std::atomic<int>& num) {
    ++num;
    --num;
}

num是原子的.必须对正在观看的其他线程观察对它的更改.更改这些线程本身(例如在增量和减量之间将值设置为100)将对num的最终值产生非常深远的影响.

这是一个演示:

#include <thread>
#include <atomic>

int main()
{
    for (int iter = 0 ; iter < 20 ; ++iter)
    {
        std::atomic<int> num = { 0 };
        std::thread t1([&] {
            for (int i = 0 ; i < 10000000 ; ++i)
            {
                ++num;
                --num;
            }
        });
        std::thread t2([&] {
            for (int i = 0 ; i < 10000000 ; ++i)
            {
                num = 100;
            }
        });

        t2.join();
        t1.join();
        std::cout << num << std::endl;
    }
}

样本输出:

99
99
99
99
99
100
99
99
100
100
100
100
99
99
100
99
99
100
100
99

Answer 3

没有太多的复杂性,像add DWORD PTR [rbp-4], 1CISC 一样的指令.

它执行三个操作:从内存加载操作数,递增操作数,将操作数存储回内存.
在这些操作期间,CPU获取并释放总线两次,在任何其他代理之间也可以获取它并且这违反了原子性.

AGENT 1          AGENT 2

load X              
inc C
                 load X
                 inc C
                 store X
store X

X仅增加一次.

Answer 4

add指令不是原子的.它引用内存,两个处理器内核可能具有该内存的不同本地缓存.

IIRC add指令的原子变体叫做lock xadd

Answer 5

由于对应于num ++的第5行是一条指令,我们可以得出结论,在这种情况下num ++是原子的吗？

基于"逆向工程"生成的装配得出结论是危险的.例如,您似乎已经编译了禁用优化的代码,否则编译器会抛弃该变量或直接将1加载到它而不调用operator++.因为生成的程序集可能会根据优化标志,目标CPU等发生显着变化,所以您的结论基于沙子.

另外,你认为一个汇编指令意味着一个操作是原子的也是错误的.add即使在x86架构上,这在多CP​​U系统上也不是原子的.

Answer 6

在单核x86机器上,add指令通常相对于CPU ¹上的其他代码是原子的.中断不能在中间分割单个指令.

需要乱序执行以保持在单个内核中按顺序一次执行一个指令的错觉,因此在同一CPU上运行的任何指令将在添加之前或之后完全发生.

现代x86系统是多核的,因此单处​​理器特殊情况不适用.

如果一个人瞄准小型嵌入式PC并且没有计划将代码移动到其他任何东西,那么可以利用"添加"指令的原子性质.另一方面,操作固有原子的平台变得越来越稀缺.

(这不会帮助你,如果你在C++编写,不过,编译器不必需要一个选项num++编译到存储目的地添加或XADD 没有一个lock前缀.他们可以选择加载num到寄存器和存储使用单独指令的增量结果,如果使用结果,可能会这样做.)

脚注1:lock前缀存在于原始8086上,因为I/O设备与CPU同时运行; 单核系统上的驱动程序需要lock add以原子方式递增设备内存中的值,如果设备也可以修改它,或者关于DMA访问.

Answer 7

即使您的编译器总是将其作为原子操作发出,num同时从任何其他线程访问也会构成根据C++ 11和C++ 14标准的数据竞争,并且该程序将具有未定义的行为.

但它比那更糟糕.首先,如上所述,编译器在递增变量时生成的指令可能取决于优化级别.其次,如果不是原子的,编译器可以重新排序其他存储器访问,例如++numnum

int main()
{
  std::unique_ptr<std::vector<int>> vec;
  int ready = 0;
  std::thread t{[&]
    {
       while (!ready);
       // use "vec" here
    });
  vec.reset(new std::vector<int>());
  ++ready;
  t.join();
}

即使我们乐观地认为++ready是"原子",并且编译器根据需要生成检查循环(正如我所说,它是UB,因此编译器可以自由地删除它,用无限循环替换它等),编译器可能仍然会移动指针赋值,甚至更糟糕的是vector在增量操作之后初始化到一个点,从而导致新线程出现混乱.在实践中,如果优化编译器完全删除了ready变量和检查循环,我不会感到惊讶,因为这不会影响语言规则下的可观察行为(与您的私人希望相反).

事实上,在去年的C++会议上,我从两位编译器开发人员那里听说,他们非常乐意实现优化,这些优化使得天真编写的多线程程序行为不端,只要语言规则允许,即使看到轻微的性能改进也是如此在正确编写的程序中.

最后,甚至如果你不关心可移植性和你的编译器是神奇的不错,你所使用的CPU是非常有可能的超标CISC类型,并且会分解指令转换成微操作,重新排序和/或推测执行它们,仅限于同步原语(如英特尔)LOCK前缀或内存栅栏,以便最大化每秒操作.

总而言之,线程安全编程的自然责任是:

1. 您的职责是编写在语言规则下具有明确定义的行为的代码(特别是语言标准内存模型).
2. 编译器的职责是生成在目标体系结构的内存模型下具有相同明确定义(可观察)行为的机器代码.
3. 您的CPU的职责是执行此代码,以便观察到的行为与其自己的架构的内存模型兼容.

如果您想以自己的方式进行,在某些情况下可能会起作用,但要了解保修无效,并且您将对任何不需要的结果承担全部责任.:-)

PS:正确的书面例子:

int main()
{
  std::unique_ptr<std::vector<int>> vec;
  std::atomic<int> ready{0}; // NOTE the use of the std::atomic template
  std::thread t{[&]
    {
       while (!ready);
       // use "vec" here
    });
  vec.reset(new std::vector<int>());
  ++ready;
  t.join();
}

这是安全的,因为:

1. ready根据语言规则,无法优化检查.
2. 在++ready 之前发生的是看到检查ready不为零,其他操作不能围绕这些操作进行重新排序.这是因为++ready并且检查是顺序一致的,这是C++存储器模型中描述的另一个术语,并且禁止这种特定的重新排序.因此,编译器不能对指令重新排序,并且还必须告诉CPU它必须不会例如vec在增加之后将写入推迟到ready.顺序一致是语言标准中关于原子的最有力保证.较小(且理论上更便宜)的保证可以通过其他方法获得std::atomic<T>,但这些保证仅适用于专家,并且编译器开发人员可能不会对其进行太多优化,因为它们很少使用.

Answer 8

在x86计算机有一个CPU的那一天,使用单个指令确保中断不会分割读/修改/写入,如果内存也不会被用作DMA缓冲区,实际上它是原子的(和C++没有提到标准中的线程,所以没有解决这个问题).

当在客户桌面上很少使用双处理器(例如双插槽Pentium Pro)时,我有效地使用它来避免单核机器上的LOCK前缀并提高性能.

今天,它只会有助于对多线程都设置为同一个CPU的亲和力,让你担心只会通过时间片到期和运行相同的CPU(核心)的其他线程来发挥作用的线程.这是不现实的.

使用现代x86/x64处理器,单条指令可分解为多个微操作,并且内存读写缓冲.因此,在不同CPU上运行的不同线程不仅会将其视为非原子,而且可能会看到有关内存中读取内容的不一致结果以及其他线程在该时间点读取的内容:您需要添加内存栅栏以恢复正常行为.