无锁数据结构（基础篇）：内存模型
（点击上方公众号，可快速关注）
来源： 伯乐在线 - 乔永琪
英文出处：khizmax
如果转载，请发送「转载」二字查看说明
假设在无锁数据结构（基础篇）：原子性、原子性原语中大家已窥探了处理器的内部结构。为了并行代码的正确执行，我们需提示处理器对内部执行的读写优化做一些限制。这些提示就是内存栅障，在某种程度，对内存访问进行管理。管理“权重”可能不同，每种架构都能提供一组完整的栅障供开发者使用。运用这些内存栅障，你可以建立不同的内存模型，执行这组保障就可以为我们程序所用。
本文我们会讨论C++11内存模型。
简要的历史回顾
最初，开发者并没有发布一个公开的处理器内存模型规范。然而依据一组规则，弱序列化的处理器便可很好的与内存进行工作。个人认为那会开发人员肯定希望在未来的某一天引入一些新的策略（为什么在架构开发中需遵循某些规范？）。然而厄运不断，千兆周就足以让开发者毛躁。开发者引入多核，最终导致多线程暴增。
最初惊慌的是操作系统开发人员，因为他们不得不维护多核CPU，然而那会并不存在弱的有序架构规则。此后其它的标准委员会才陆续参与进来，随着程序越来越并行，语言内存模型的标准化就应运而生，为多线程并发执行提供某种保障，不过现在我们有了处理器内存模型规则。最终，几乎所有的现代处理器架构都有开放的内存模型规范。
一直以来C++就以高级语言的方式编写底层代码的特性而著称，在C++内存模型的开发中自然也是不能破坏这个特性，必然赋予程序员最大的灵活性。在分析JAVA等语言的内存模型，及典型同步原语的内部结构和无锁算法案例之后，开发人员引入了三种内存模型：
序列一致性模型
获取/释放语义模型
宽松的内存序列化模型（relaxed）
所有这些内存模型定义在一个C++列表中– std::memory_order，包含以下六个常量：
memory_order_seq_cst 指向序列一致性模型
memory_order_acquire, memory_order_release, memory_order_acq_rel, memory_order_consume 指向基于获取/释放语义的模型
memory_order_relaxed 指向宽松的内存序列化模型
开始审视这些模型之前，应先确定程序中采用何种内存模型，再一次审视原子性运算。该运算原子性的文章中已有介绍，此运算与C++11中定义的运算并没什么两样。因为都基于这样一个准则：memory_order作为原子运算的参数。其原因有二：
语义：事实上，我们说的序列化（内存栅障）是指程序执行的原子运算。位于读/写方法中的栅障，其神奇之处就在于跟代码没有关联，其实是栅障等价存在的指令。另外，读/写中的栅障位置取决于架构本身。
实际应用中：英特Itanium是一种特殊的、与众不同的架构，该架构的序列化内存方式，适用于读写指令和RMW运算。而旧的Itanium版本则是一种可选的指令标签：获取、释放或者宽松（relaxed）。但架构中不存在单独的获取/释放语义指令，仅有一个重量级的内存栅障指令。
下面是真实的原子性运算，std::atomic<T> 类的每种规范至少应包含以下方法：
void store(T, memory_order = memory_order_seq_cst);
T load(memory_order = memory_order_seq_cst) const;
T exchange(T, memory_order = memory_order_seq_cst);
bool compare_exchange_weak(T&, T, memory_order = memory_order_seq_cst);
bool compare_exchange_strong(T&, T, memory_order = memory_order_seq_cst);
独立的内存栅障
当然，在C++11同样也为大家提供了两个独立的内存栅障方法：
void atomic_thread_fence(memory_order);
void atomic_signal_fence(memory_order);
atomic_thread_fence亦可采用独立读写栅障的方式运行，而后者被告知已过时。尽管memory_order序列化方法atomic_signal_fence不提供读栅障（load/load）或者写栅障（Strore/Store）,不过atomic_signal_fence可以用于信号处理器（signal handler）；作为一个规则，该方法不产生任何代码，仅是一个编译器栅障。（译者注：称之为栅栏似乎更为妥当）。
正如你看到的，缺省状态的C++11内存模型为序列一致模型，这正是我们要讨论的，不过在这之前我们先简要聊聊编译器栅障。
编译器栅障
谁会重排我们写的代码呢？处理器可以重排代码，另外还有编译器。而许多启发式开发和优化开发方法，都是基于单线程执行这样的假设。因此，要让编译器明白你的代码是多线程的，那是相当困难的。因此它需要提示–栅障。诸如此类的栅障告知编译器“别把栅障前面的代码和栅障后面的代码混在一起，反之亦然”，编译器栅障不会产生任何代码。
MS Visual С++的编译器栅障是一个伪方法：_ReadWriteBarrier()。（过去我一直记不住它的名字：和读写内存栅障相关—重量级内存栅障）而对GCC和Clang而言，它是一个smart __asm__ __volatile__ ( “” ::: «memory» )结构。
同样值得注意的是，assembly __asm__ __volatile__ ( … ) insertions也是一种GCC和Clang栅障。编译器没有权利遗弃或者重排栅障前后的代码。C++ memory_order常量,在某种程度上,支持编译器对处理器施加影响。作为编译器栅障，限制了代码的重排（比如优化）。因此，无需再设置特定的编译器栅障，当然，前提是编译器完全支持这一新标准。
序列化一致性模型
假设，我们实现了一个无锁栈，编译后并正在进行测试。我们拿到一个核心文件，会问哪里出错呢？开始查找寻找错误根源，脑袋飞快地在思索无锁栈中一行行代码实现（没有一个调试器能帮到我们），试图模拟多线程，并回答下列问题：
“线程1执行第k行的同时，线程2执行第N行，此时会有什么致命问题导致程序失败呢？”或许，你会发现错误根源并处理掉这些错误，但无锁栈依旧报错，这是为何？
（译者注：所谓核心文件，又叫核心转储，操作系统在进程收到某些信号而终止运行时，将此时进程地址空间的内容以及有关进程状态的其他信息写入该文件，此信息用来调试）
事实上，我们试图寻找错误根源，在脑海中比较多线程并发执行下的程序不同行，其实就是序列化一致性。它是一种严格的内存模型，确保处理器按照程序本身既定的顺序执行程序指令，例如，下面的代码：
// Thread 1
atomic<int> a, b ;
a.store( 5 );
int vb = b.load();
// Thread 2
atomic<int> x,y ;
int vx = x.load() ;
y.store( 42 ) ;
任何一种执行情形都是序列化一致性模型允许的，除了对调换a.store / b.load或者x.load / y.store。注意，我并没有显式地给加载存储设置memory_order参数，而是依赖缺省的参数值。
相同的规范扩展到编译器：memory_order_seq_cst下面的运算不得迁移到此栅障上面，与此同时，在seq_cst-barrier上面的运算不得迁移到此栅障下面。
序列化一致性模型接近人脑思维，但它有个相当致命的缺陷，对现代处理器限制过多。这会产生极度重量级的内存栅障，很大程度上制约了处理器的启发式执行，这也是新的C++标准为何有以下折中的原因：
有序化一致性模型由于其严格的特性，加之容易理解，因而被作为原子运算的缺省模型
同时C++引入一个弱内存栅障，以应对现代架构的更多可能
基于获取/释放语义的模型作为序列化一致性模型的一个很好补充。
获取/释放语义
正如你看到的标题那样，在某种程度上，该语义与资源的获取释放有关。确实如此，资源的获取就是将其从内存读入寄存器，释放就是将其从寄存器写回内存中。
load memory, register ;
membar #LoadLoad | #LoadStore ; // acquire-барьер
// Operation within acquire/release-sections
...
membar #LoadStore | #StoreStore ; // release-barrier
store regiser, memory ;
正如你看到的，我们没有用到#StoreLoad这样重量级栅障应用。获取栅障、释放栅障就是半个栅障。获取不会将前面的存储运算与后续的加载、存储进行重排，而释放不会将前面加载与后续的加载进行重排，同样，不会将前面的存储与后续的加载进行重排。所有的这些适用于编译器和处理器，获取、释放作为该区间所有代码的栅障。而获取栅障前面的某些运算（可以被处理器或编译器重排）可以渗入到获取/释放模块中。同样释放栅障后续的运算可以转入上方进入获取/释放区间。但获取/释放里面的运算不会越出这个界。
我猜自旋锁（spin lock）是获取/释放语义应用最简单的例子。
无锁和自旋锁
或许你会感到奇怪，在无锁算法系列文章中列举一个锁算法的例子似乎不妥，容我解释一下。
我不是一个纯无锁粉，不过，纯无锁（特别是无等待）算法确实令我很开心。设法实现它我甚至会更开心。作为一个务实主义者：任何有效的事情就是好的。倘若使用锁带来益处，我也觉得挺好的。自旋锁可以带来比综合互斥量（mutex）更多的收益，比如对一个小段程序进行保护–少量汇编指令。同样，针对不同优化，自旋锁是一种用之不竭的资源。
基于获取/释放的最简易自旋锁实现大致如此：（而C++专家认为应该用某个特定的atomic_flag来实现自旋锁，但我更倾向于将自旋锁建立在原子变量上，甚至不是boolean类型。从本文角度看，这样看起来会更清晰。）
class spin_lock
{
atomic<unsigned int> m_spin ;
public:
spin_lock(): m_spin(0) {}
~spin_lock() { assert( m_spin.load(memory_order_relaxed) == 0);}
void lock()
{
unsigned int nCur;
do { nCur = 0; }
while ( !m_spin.compare_exchange_weak( nCur, 1, memory_order_acquire ));
}
void unlock()
{
m_spin.store( 0, memory_order_release );
}
};
本代码中困惑我的是，倘若CAS未成功执行，compare_exchange方法，第一参数接收一个引用，并修改它。因此不得不采用一个带非空体的do-while。
在lock方法中采用获取-语义，在unlock方法中采用释放语义（顺便说一句，获取/释放语义来自同步原语，标准开发者细心地分析各种不同的同步原语实现，进而衍生出获取/释放模型）。正如早前提到的，本例中的栅障不允许lock和unlock之间的代码溢出，这正是我们需要的。
原子性m_spin变量确保m_spin=1时，没有人可以获得该锁，这也是我们所需要的！
大家看到算法中用到了compare_exchange_weak，但它是什么呢？
Weak and Strong CAS
正如你所记得那样，处理器结构通常会选择两种类型中的一种，或者实现原子性CAS原语，或者实现LL/SC对（(load-linked/store-conditional）。LL/SC对可以实现原子性CAS，但由于很多原因它并不具有原子性。其中一个原因就是，LL/SC中正在执行的代码可以被操作系统中断。例如，此刻OS决定将当前线程压出；重新恢复之后，store-conditional不再响应。而CAS会返回false，错误的原因不是数据本身，而是外部事件-线程被中断。
正是因为如此，促使开发人员在标准中添入两个compare_exchange原语-弱的和强的。也因此这两原语分别被命名为compare_exchange_weak和compare_exchange_strong。即使当前的变量值等于预期值，这个弱的版本也可能失败，比如返回false。可见任何weak CAS都能破坏CAS语义，并返回false，而它本应返回true。而Strong CAS会严格遵循CAS语义。当然，这是值得的。
何种情形下使用Weak CAS，何种情形下使用Strong CAS呢？我做了如下变通：倘若CAS在循环中（这是一种基本的CAS应用模式），循环中不存在成千上万的运算（比如循环体是轻量级和简单的），我会使用compare_exchange_weak。否则，采用强类型的compare_exchange_strong。
针对获取/释放语义的内存序列
正如上文所述，获取/释放语义下的memory_order定义：
memory_order_acquire
memory_order_consume
memory_order_release
memory_order_acq_rel
针对读（加载），可选memory_order_acquire和 memory_order_consume。针对写（存储），仅能选memory_order_release。Memory_order_acq_rel是唯一可以用来做RMW运算，比如compare_exchange, exchange, fetch_xxx。事实上，原子性RMW原语拥有获取语义memory_order_acquire, 释放语义memory_order_release 或者 memory_order_acq_rel.
这些常量决定了RMW运算语义，因为RMW原语可以并发执行原子性读写。RMW运算语义上被认为拥有获取-加载，或者释放-存储，或者两者皆有。
只在算法中定义RMW运算语义是可行的，在某种程度上与自旋锁相似的部分，在无锁算法中显得很特别。首先，获取资源，做一些运算，比如计算新值；最后，释放掉新的资源值。倘若资源获取由RMW运算（通常为CAS）执行，诸如此类的运算很有可能拥有获取语义。倘若某个新值由RMW原语来执行，此类型很有可能拥有释放语义。用“很有可能”描述不是没有目的，对算法的具体细节进行分析是必须的，这样才能明白什么样的语义匹配什么样的RMW运算。
倘若RMW原语分开执行，获取/释放模式是做不到的，不过有三种可能的语义变体：
memory_order_seq_cst 是算法的核心， RMW运算中，代码的重排，加载和存储的上下迁移都会报错。
memory_order_acq_rel 和memory_order_seq_cst有些相似, 但RMW运算位于获取/释放内部。
memory_order_relaxed RMW运算可以上下迁移，不会引发错误。(比如：运算就在获取/释放区间)
以上这些细枝末节都应很好地被理解，然后再试着采用一些基本的原则，在RMW原语上采用这样的，或那样的语义。完了之后，必须针对每个算法做出细致地分析。
消费语义（COnsume-Semantic）
这是一个独立的，更弱类型的获取语义，一个读消费语义。此语义作为一个“内存的礼物”被引入DECAlpha处理器中。Alpha架构与其它现代架构有很大的不同，它会破坏数据依赖。下面的代码就是一个例子：
struct foo {
int x;
int y;
} ;
atomic<foo *> pFoo ;
foo * p = pFoo.load( memory_order_relaxed );
int x = p->x;
重排p->x读取和p获取（别问我这怎么可能呢！这就是Alpha的特点之一，我没有用过Alpha，所以也不能确定这对与不对）。为了阻止此种重排，引入了消费语义，用于struct指针的原子读，以及struct字段读取。下面的例子中pFoo指针便是如此：
foo * p = pFoo.load( memory_order_consume );
int x = p->x;
消费语义介于读取的宽松语义和获取语义之间，现今大多数架构都基于读取的宽松语义。
再谈CAS
我已经介绍了两个CAS原子性接口-weak和Strong，但不止两个CAS变体，其它CAS，多了一个memory_order参数：
bool compare_exchange_weak(T&, T, memory_order successOrder, memory_order failedOrder );
bool compare_exchange_strong(T&, T, memory_order successOrder, memory_order failedOrder );
不过failedOrder是什么样的参数呢？
记住CAS是RMW原语，即便失败，也会执行原子性读。CAS失败，failedOrder参数会决定本次读运算语义。普通读相应的相同值也是支持的，在实际应用中，“针对失败语义”是极其少有的，当然，这取决于算法。
宽松语义
最后，来说说第三种原子性模型，宽松语义适用于所有的原子性原语-加载、存储、所有RMW-几乎没有任何限制。因此，它允许处理器最大程度上的指令重排，这是它最大的优势。为何是几乎呢？
首先，该标准需要保证宽松运算的原子性。这意味着即使是宽松运算也应该是原子性的，不存在部分效应（partial effects)。
其次，启发式写在原子性宽松写中是被禁止的。
这些要求会严格地应用于一些弱序列化架构的原子性宽松运算中。比如，原子性变量的宽松加载在Intel Itanium中由load.acq实现（acquire-read, 切勿把Itanium acquire和C++ acquire混为一体）。
Itanium之安魂曲
我在文中多次提到英特尔Itanium，搞得我好像就是Intel架构粉；其实该架构在慢慢逝去，当然我不是英特尔的粉丝。Itanium VLIW 架构不同于其它架构地方，是其命令系统的构建规则。内存序列化由加载、存储、RMW指令的前缀完成。而在现代架构体系中你不会找到这些的，这些获取和释放术语，让我想到，C++11或许就是从Itanium拷贝过来的。
过去，我们一直在用Itanium或者它的子架构，直到AMD引入AMD64—将x86扩展到64位。那时Intel正慢悠悠地开发一款64位计算架构。这个架构潜藏着一些细枝末节，透过它，你会了解到台式机Itanium原本是为我们准备的。另外，针对Itanium架构的微软Windows操作系统端口和Visual C++编译器也间接地证明这一点（还有人看到其它运行在Itanium上的Windows操作系统吗？）。显然AMD打乱了Intel的计划，而Intel必须迎头赶上，将64位整合进x86。最后，Itanium停留在服务器片段中，因拿不到合适的开发资源，而慢慢消失了。
不过，Itanium的一组VLIW指令却是很有趣，并已取得突破性进展。现代处理器执行的这些指令（加载执行块，重排运算）曾经被植入Itanium 的编译器中。但该编译器不能处理任务，也不能产生完备的优化代码。结果，Itanium性能数次跌入谷底，因此Itanium 是我们不可以实现的未来。
但有谁知道呢，或许现在写梦之安魂曲为时尚早？
熟悉C++11标准的人肯定会问：“关系（relations）在何处决定原子性运算语义：happened before, synchronized with ，还是其它？”我会说“在标准里”。
Anthony Williams在其书《C++ Concurrency in Action》第五章对此有详尽的描述，你可以找到很多详尽的例子。
标准开发者有一项重要的任务，对C++内存模型规则做一些变动。该规则不是用来描述内存栅障的位置，而是用来保障线程之间通信的。
结果，一个简洁明了的C++内存模型规范就此产生了。
不幸的是，在实际应用中，此关系使用起来太过困难；不论是在复杂或是简易的无锁算法中，大量的变量需要考虑，才能保证memory_order的正确性。
这就是为何缺省模型为序列化一致性模型，它无需针对原子性运算设置任何特殊的memory_order参数。前面已经提到，该模型处于一种减速状态，应用弱模型—比如获取/释放 或者宽松—均需要算法验证。
补充说明：读了一些文章发现最后的论述不够准确。事实上，序列一致性模型本身不保证任何事情，即使有它的帮助，你也能把代码写的一团糟。因此不论何种内存模型，无锁算法验证都是必须的。只不过在弱模型中，特别有必要。
无锁算法验证
我知道的第一个验证方式，是Dmitriy Vyukov写的 relacy 库。不幸的是，该方式需要建立一个特殊模型。第一步，简化的无锁模型应该以relacy library方式来构建；而且该模型应该经过调试（为何是简化的呢？在建模的时候，通常你要深思熟虑摒弃掉跟算法无关的东西）；只有这样，你才能写出一个算法产品。该方式特别适合从事无锁算法和无锁数据结构开发的软件工程师，事实上也确实如此。
但通常很难做到两步，或许是人惰性的天性，他们即可马上就需出东西。
我猜relacy的作者也意识到这个缺陷（不是嘲讽，在这个小领域也算是一个突破性的项目）。作者将一个验证方法作为标准库的一部分，这也意味着你无须做任何额外的模型。这个看起来有些像STL中的safe iterators概念。
最近一个新工具ThreadSanitizer由Dmitriy和他谷歌的同事一起开发的，这个工具可以用来检测程序中存在的数据竞争；因此在原子性运算的重排中非常有用。更重要的是，该工具不是构建进了STL，而是更底层的编译器中（比如Clang3.2、GCC4.8）。
ThreadSanitizer的使用方式特别简单，编译某个程序时仅仅需要特定的按键，运行单元测试，接着就可以看到丰富的日志分析结构。因此，我也将本工具应用于我的libcds库中，确保libsds没有问题。
“我不是很明白”—批判标准
我斗胆批判C++标准，只是不明白为何标准将该语义设置为原子性运算的参数。不过，逻辑上应该使用模板，这么做才对嘛：
template <typename T>
class atomic {
template <memory_order Order = memory_order_seq_cst>
T load() const ;
template <memory_order Order = memory_order_seq_cst>
void store( T val ) ;
template <memory_order SuccessOrder = memory_order_seq_cst>
bool compare_exchange_weak( T& expected, T desired ) ;
// and so forth, and so on
};
我来谈谈为何我的想法更正确呢。
前面不止一次提到，原子性运算语义不仅作用于处理器，也作用于编译器。语义是编译器的优化（半）栅障。除此之外，编译器应该监控原子性运算是否被赋予恰当语义（比如，释放语义应用于读运算）。那该语义在编译期就应该确定下来，但在下面的代码中，我很难想象编译器如何做到这一点：
从形式上看，该代码并不违反C++11标准，不过编译器唯一能做的也就只有下面这些了：
extern std::memory_order currentOrder ;
std::Atomic<unsigned int> atomicInt ;
atomicInt.store( 42, currentOrder ) ;
要么报错，但为何允许原子性运算接口抛出错误？
要么应用序列化一致性语义，总之是“不会太糟”。但变量currentOrder会被忽略掉，程序会遇到很多我们原本想避免的问题。
要么产生一个针对所有currentOrder可能值的switch/case语句。但这样，我们会得到很多低效的代码，而非一两个汇编指令。恰当语义问题还未解决，你可以调用释放读或者获取写。
然而模板方式却没有此缺陷，在模板函数中，memory_order列表中定义编译期常量。的确，原子性运算调用确实有些繁琐。
std::Atomic<int> atomicInt ;
atomicInt.store<std::memory_order_release>( 42 ) ;
// or even like that:
atomicInt.template store<std::memory_order_release>( 42 ) ;
但这些繁琐可以借由模板方式抵消，在编译期运算语义就可以明白无误地显示出来。而C++采用非模板的方式唯一的解释就是为了兼容C语言。除了std::atomic类，C++11标准还引入了诸如 atomic_load, atomic_store等C原子性函数。
当C++11还在计划中时，我已用模板的方式实现了原子性原语。因此，我必须做出决定，是否遵从标准，基于C++11原子性运算接口构建另一个版本的libcds。
自此基础篇完结！
第一部分：无锁数据结构（1）：简介
觉得本文有帮助？请分享给更多人
关注「算法爱好者」，修炼编程内功