Windyland 内核崩坏

原子操作的一些介绍

原子操作

又称为Atomic Operations, 是高并发编程里的不同于加锁的一项技术,常见于无锁算法。

原博客见 windyland.me ,这里会做一些更多的解释。

相比加锁的优势

常见的锁比如Mutex 和Spinlock,(还有类似于Mutex的Futex)。

Mutex加锁的特点是其他需要锁的进程遇到已经上锁的情况会暂停正在执行的指令,等到锁解除才会唤醒。这时候后内核的调度程序会把这部分代码从CPU的Cache 中Swap出去,做一次Context Switch。

如果短时间内Spinlock没有结束,Spinlock还会更是由于OS的任务调度造成持续不断的Context Switch。

一次Context Switch 开销是非常可观的,此操作会要求保存当前的CPU的寄存器,这个意义上像是做了一对setjmp,和longjmp。而且很大可能上让当前的L1 Cache几乎无效,需要从L2、L3或者内存上重新抓取,降低了CPU缓存命中率。其他的例子,比如内核的任务调度部分就会执行很多的Context Switch 的指令。

相比之下,原子操作就没有相关的劣势。具体来说原子操作会暂时屏蔽中断,并且保证当前执行的代码不会被Context Switch。

原子操作的模型

大体分为7种:

  • NonAtomic, 无原子保证的。此模型,是C/C++的标准模型,对不同线程同时读取、写入同一地址的行为(竞争)不做任何保证,或者说是Undefined Behavior。比如读取未初始化的局部int*变量所指向的内存也是Undefined Behavior。
  • Unordered, 无序保证的。此模型,是Java等一些语言的标准模型,对不同线程的竞争做了一些保证,不再是Undefined behavior, 而且一定程度的支持了部分的原子操作。
  • Monotinic, 顺序保证的。此模型对应了C/C++标准里的 memory_order_relexed。此模型不对内存同步做任何保证,只保证相关的原子操作之间是顺序执行的。
  • Acquire, 获取保证。此模型对应了C/C++标准里的 memory_order_acquire, 或者 memory_order_consume。此模型保证了获取一个锁,这个锁是用于正常的读取、写入(Load 和Store)指令访问其他的地址。请注意一个Acquire必有下文的一个Release与之对应。
  • Release, 释放保证。此模型对应了C/C++标准里的 memory_order_release。 此模型保证了释放一个锁,这个锁是用于正常的读取、写入(Load 和Store)指令访问其他的地址。请注意一个Release必有一个上文的Acquire与之对应。
  • AcquireRelease, 获取释放保证。此模型对应了C/C++标准里的 memory_order_acq_rel。简单认为是做了同时满足Acquire和Release的保证的。
  • SequentiallyConsistent, 顺序一致保证。此模型对应了C/C++标准里的 memory_order_seq_cst, Java 的volatile修饰词,gcc 的__sync_*的编译器内建函数。此模型做了AcquireRelease保证,而且另外也保证所有SequentiallyConsistent的操作也是顺序执行的。这个也是传说中最强的原子操作,同时是开销最大的原子操作。还有也是写代码最省力的。

详细可以参见LLVM Atomic Instructions and Concurrency Guide,和memory order

实际使用

好消息是C++11 标准和 C11 标准已经加入了上述完整的原子操作的支持

坏消息是完全支持C11 标准的编译器还没出世,完整支持C++11 标准的编译器虽然已经大规模上市了(clang++ 3.3 或以上, gcc 4.8.1 或以上, vs 2013基本完成),但是实际使用还有一段时间。

如果你还无法在工程中开启-std=c11 或者-std=c++11:

一些测试

我写了一段小程序,可以跑在Linux 和Mac OS X, Mingw64上。

如果是Mingw64+GCC 4.8+环境,比如MSYS2,也是可以正常编译运行的。

原理很简单,就是同时跑几个线程,每个线程都在一个相当长时间的循环中不断的访问同一个地址,造成race。测试的有Mutex、Spinlock还有Atomic。

此程序需要一个支持C++11 的编译器,比如gcc 4.8 或者更新,clang 3.3 以上,通常ubuntu 14.04 以上和Xcode 4.6.x 以上都满足这个要求。

当然用纯C写也是可以,但是我懒啊。。。。

然后执行下面代码就可以了

git clone https://github.com/Chilledheart/ch_utils
cd ch_utils
make

比如我的机子,4核超线程的i7:

jobs:  1 total time:  614932094 ns average time:  6149 ns (Mutex)
jobs:  1 total time:    5132226 ns average time:    51 ns (SpinLock)
jobs:  1 total time:    4172785 ns average time:    41 ns (Atomic)
jobs:  2 total time:  746401303 ns average time:  7464 ns (Mutex)
jobs:  2 total time:   15983439 ns average time:   159 ns (SpinLock)
jobs:  2 total time:    9356120 ns average time:    93 ns (Atomic)
jobs:  4 total time:   42609222 ns average time:   426 ns (SpinLock)
jobs:  4 total time:   13734551 ns average time:   137 ns (Atomic)
jobs:  8 total time:  107958834 ns average time:  1079 ns (SpinLock)
jobs:  8 total time:   30681228 ns average time:   306 ns (Atomic)
jobs: 16 total time:  213277915 ns average time:  2132 ns (SpinLock)
jobs: 16 total time:   52189737 ns average time:   521 ns (Atomic)