Race Condition(竞态条件) 和 Memory Barrier(内存屏障)

  • CPU乱序执行
  • 我们熟悉的X86架构CPU
  • Memory Barrier
  • 缓存一致性
  • Race Condition
  • Go Memory Model、C++ Memory Model、Rust Memory Model

CPU乱序执行

说起乱序执行,就得不得不提另外作为其实现基础的两个技术,现代CPU架构中为了增强单核运行性能,开发了超标量和流水化管线技术。

超标量superscalar

拥有这个技术的CPU单颗核心就有多个执行单元,例如算术逻辑单元、位移单元、乘法器,在单个时钟周期内就可以同时执行多条指令,而非超标量CPU单核仅能支持1条指令,在相同时钟频率/主频下,前者的CPU流量就会远大于后者。

流水化管线

如果前述的执行单元同一时间只能执行某条指令的拆分工作的话,那么就会出现若该指令拆分出的步骤越串行化,那么效率越低情况,最理想的情况下,该CPU指令拆分步骤能让所有执行单元工作。所以为了改善其中的最好最坏情况,研发了流水化管线技术,同个时钟周期内,一条流水管线的各个执行单元可以执行分属于不同指令的拆分工作。形成如下的工作模式:

这张图中有7个流水线层级,可以看到它能最大同时处理5条相同指令,当然了,受制于实际乱序执行和预测执行结果,可能实际运行情况并非能达到最理想的运型模式。可以看到在T+1、+2、+3、+4、+6、+7时钟周期内,流水管线上的工作是不饱和的,为了提高执行效率,我们得把这些空闲的执行单元安排上工作。那么到底安排哪些工作呢?这就是我们终于要谈到的乱序执行。

乱序执行

如果分支和时延比较长的指令存在,那么不可避免的会造成流水管线中添加Nop操作/冒泡,那么理论上这些NOP可以被用来做其他事情。除了指令转发解决资源冲突并合理规划指令,分支预测解决取指令/译码优化以外,还有一种解决执行阶段空闲的方法就是乱序执行。

顾名思义,乱序执行指的是打乱顺序来执行。如果没有乱序执行,我们的指令执行顺序应该是按照机器码顺序来执行的。而引入乱序执行后,流水管线会将指令译码完成的操作一并加入到一个保留站ReservationStation中,加入到RS中的子操作并不会立即执行,它会等待,直到运行的所依赖的数据就绪后,才交由各个执行单元来操作,完成这个子操作后就将结果先放回一个叫做重排序缓冲区ReorderingBuffer中,这个区域既不属于CPU高速缓存Lx,也不属于内存,等最终所有加入到RS中子操作完成并重新排序后,再写入寄存器。

编译器如何实现“乱序执行”

除了前面所述的基于硬件/CPU自身实现动态指令调度的派发逻辑之外,另外一种方案则是基于编译器。

硬件方案虽然是透明的,对开发者友好的,但是往往由于实际复杂的调度逻辑,无形之中使CPU内更多的晶体管电路处于活跃状态,产生功耗。编译器方案更上层一些,并且直面编程语言,可以获得更多关于运行分支的信息,直接在编译层面优化并产生对CPU友好的指令流。不过像CPU高速缓存未命中的问题引发的NOP就只能靠CPU自身硬件实现乱序执行来优化了

现代的CPU架构大多数是支持乱序执行的,除非为追求低功耗低体积设计目标的CPU。

X86架构

我们可以看到x86架构的CPU内部存在micro-opreations这类被拆分的子/微操作,又称作μop。通过寄存器重命名技术将RISC架构下的很多设计引入进来。一些新款的X86架构CPU在其中开辟了一块缓冲区专门用作μop的存储,避免一次又一次地转换相同的x86指令

由于现实世界中大多数程序的并发度并不高(客户端程序),这个事实情况可能会削弱超标量CPU利用指令并行的加速方法,每个时钟周期几乎永远不会超过2-3条指令,再加上负载延迟和高速缓存未命中、分支和指令之间的依赖关系组合,峰值性能几乎是达不到的

如果正在执行中的程序没有其他独立的指令,那么也可以用来去执行其他正在运行的程序或同一程序中的其他线程,同步多线程SMT正是利用了这种类型的操作来实现更高并行性。SMT处理器在系统的其余部分看起来就像多个独立的处理器一样,就像真正的多处理器系统一样

当然SMT也会带来一定的负面作用,因为所有线程共享一个核心和一组缓存,平衡线程之间的进度也会变得非常麻烦,否则如果单个线程使其他线程所需要的功能单元工作饱和的话,即使其他线程只需要很少的功能的单元,也需要被暂停

Memory Barrier

由于乱序执行的存在,导致可能CPU或者编译器在对内存进行操作的时候,如果后续代码中出现依赖前面内存读写结果的情况,可能会导致发生异常。MemoryBarrier内存屏障指令就是用来做这个工作的,它可以强制内存屏障指令前的操作都要写入内存,内存屏障之后的读操作都是可以获得屏障前写操作的情况。即发生在屏障前的Load/Store指令一定会比屏障后的操作先发生,x86架构就算不加屏障也可以保证Store指令的顺序性,而这个操作也可以用来实现下面缓存一致性

缓存一致性

Memory Wall问题: 一般情况下,从内存中加载数据几乎占了所有CPU指令的1/4,而由于大多数超标量处理器每个时钟周期只能发出一个或者最多两个Load指令,这就导致CPU到内存的访问可能会出现指令停顿,难以提升CPU指令的并发度。

现代CPU使用高速缓存来解决MemoryWall问题,高速缓存是位于处理器芯片上的小型但快速的内存,主要用来保留小块主内存的副本,当处理器要求一块特定的主内存时,如果数据在缓存中,缓存则可以比主内存更快的提供它

理论上来说最好的办法就是在缓存中保留最近使用的数据,但是如果采用这种设计的话,那么每次快速访问都需要检查每条缓存行是否匹配,这对于具有数百行的高速缓存来说速度会很慢。所以实际上高速缓存通常仅允许来自存储器中任意地址占据1一个或最多几个位置,这样在访问的时候仅需要几个比对就可以。

这样就引发了缓存一致性的问题,因为每个处理器核心都有自己的高速缓存,并且都可以从主存中加载相同地址的数据,如果某个处理器核心决定对此地址的数据进行修改,那么在写回主存之前的这段时间,不同核心看到缓存中的数据时不一致。缓存一致性就是要解决这个问题,有两个要求:写传播和序列化。前者要求在任何高速缓存中的数据更改必须传播到对等高速缓存中的其他副本,后者要求所有处理器核心必须以相同的顺序看到对单个内存位置中的读写操作,即写入同一位置必须被排序,这也反映除了缓存一致性和顺序一致性这两种一致性模型的差异之处,前者要求单个存储位置,可以对不同位置进行写操作,后者要求所有存储位置。

Race Condition

前面说了这么多CPU底层的实现,那么对于平时的编程来说,我们是接触不到这么低的层面来解决问题。一致性模型也有非常多种,那么对于我们平时来说,处理器一致性虽然并不是严格的顺序一致性,但是只要编程语言实现正确的同步机制和一致性模型,那么处理器一致性也基本等同于顺序一致性。换句话说编程语言实现的内存/一致性模型无法满足处理器一致性,那么编码就需要考虑前面缓存一致性的问题。(一致性强弱:严格>顺序>处理器>缓存)。这也是为什么有的语言有volatile关键字,而有的语言没有(C/C++ 拿这个关键字用来保证编译器对代码volatile内存读写操作不会发生重排序,并不能完全保证是内存屏障,所以还是需要更强的同步原语或者手动屏障),没有volatile的语言往往实现了更为严格的一致性模型。

我们在某些多线程访问情况下对某个共享变量存在至少一个线程是写入操作时如果没有任何同步措施就会出现data race的情况,像下面这种情况

var data int
go func() { data++ }()
if data == 0 {
    fmt.Printf("the value is %v.\n" data)
}

在这种情况下data这个共享资源在没有任何同步措施的情况下,就会导致data race的情况。解决办法也很简单,使用一个互斥锁Mutex

var data int
var s sync.Mutex
go func() {
    s.Lock()
    defer s.Unlock()
    data++
}()
s.Lock()
if data == 0 {
    fmt.Printf("the value is %v.\n",
    data)
}
s.Unlock()

虽然我们程序员依然不清楚最后输出结果如何,但对于CPU来说,从Cache写回/WriteBack/WriteThrough内存的视角来看就不会存在不满足处理器一致性的问题,所以即不会存在data race

Go Memory Model 、C++ Memory Model、Rust Memory Model

Go Memory Model   https://golang.org/ref/mem

保证了能够在一个goroutine中读取在另一个goroutine修改同一变量的值(这里变量的大小是不超过1个机器字的,64bit,比如指针、int64等,超过的就不会保证,这是因为原子操作)。不过对于同时在不同goroutine中修改同一变量的同步机制就需要程序员自己去写了,推荐的方式使用channel或者sync、sync/atomic包中的同步原语

C++ Memory Model      https://people.cs.pitt.edu/~xianeizhang/notes/cpp11_mem.html

这里说的是C++11,如果之前更早版本的话,那么需要看具体CPU架构和编译器版本,非常繁琐,而C++11 之后提出了统一的内存模型用以应对不同平台下编写多线程程序

在使用C++11原子类型时,共享变量将默认具有内存排序,即编译器会在背后插入内存屏障指令来保证达成顺序一致性,这种一致性可以保证所有线程都会有统一的内存操作顺序

在多线程编程中,为避免竞争情况,应该在来自不同线程的访问之间强制执行排序,尽量不要依赖CPU提供的有限保证,毕竟ARM、MIPS、X86等架构差异性很大。使用编程语言提供的原子互斥锁或者其他的高级互斥锁,除非迫不得已,尽量在编码层面少用内存屏障

参考资料

https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-745.html

https://medium.com/fcamels-notes/從-double-checked-locking-了解-memory-barrier-的作用-bb151a359c1b

https://people.cs.pitt.edu/~xianeizhang/notes/cpp11_mem.html