无锁数据结构设计 之 详解C++内存顺序(Memory Order)


内存顺序概述

内存顺序,这是一个很大很大很大的坑,在介绍atomic原子类型的时候,就已经提及过,但是由于本身概念理解起来非常困难,所以没有细讲。现在就让我们仔细看看这是什么一个神奇的东西吧。

先通过一系列简单的代码片段,看一看内存顺序是如何定义的:

可见,memory_order一般情况下是加在有内存操作的函数(如store、load等)后面,比如上面程序中的 std::memory_order_release ,特别的由于函数compare_exchange_weak在失败、成功之后存在两种不同的内存操作策略,因此它可以传入两个memory_order分别指示成功(success)和失败(failure)后不同的操作策略:

 

内存顺序原理

好了,废话不多说,为了让读者理解内存顺序,我们将分别解释内存顺序、操作可见性等概念

内存顺序,顾名思义,是由于内存操作重排带来的不确定性。

CPU中的缓存机制曾经大幅提高了内存访问速度,这个机制将内存中经常访问的区域拷贝到了缓存中以加快速度。这种策略使得内存的读写的目标不一定是内存中的值,而是有可能仅仅是该值在缓存中的一个副本。

在单核处理器下,并不会出现任何问题,毕竟所有线程的缓存是共用的,也就是说不存在缓存同步的问题。在多核的情况下,问题就会比较复杂了,每一个核都有自己独立的L1缓存,若两个核共享内存,就需要解决缓存同步的问题。内存重排就是处理器(编译器)设计者为了平衡缓存同步的时间开销,和程序不稳定性之后得到的一个较好的解决方式。

不仅仅缓存会导致内存操作的重排,编译器也可能为了优化速度重排操作,当然,这些重排也是建立在不影响单线程程序正确性的情况下。不过,编译器的优化非常好处理,在解决好处理器优化后,编译器优化自然而然可以解决,因此我们这里就不深入讨论。

【注:在 之前的文章 中,我曾介绍过内存顺序可以用多人写作的版本控制来理解,单独线程的本地修改对于自身来说是一定有序的,但是这些修改要传递到远程的代码库中,则是一个可能发生顺序交换的不确定事件。  】

以上面的程序为例子:函数 write_x_then_y 依次写了变量x和y,而函数 read_y_then_x 在确认变量y已经被写之后读入x。从常理上来说,此时 z++ 是一定会被执行的。但是从运行结果上来看,assert可能被触发!

假设编译器没有优化汇编层面x和y的写入次序。实际上,是由于缓存机制,导致不同变量在其他线程看来更新的顺序是不同的。这就是内存顺序所刻画的问题。其中,本程序中,x的赋值操作可能不会被其他线程所看到,这就是所谓的不可见

从可见性方面重新叙述内存顺序的问题——一个线程的内存操作对于其他线程来说是不可见的。一种可能的情况是:

  • 线程A:写x,写y
  • 线程B:发现x先于y被赋值
  • 线程C:发现y先于x被赋值

联想之前说的缓存机制,确实会是这样的。

所以内存顺序memory_order是什么呢,memory_order是编译器指定常规的非原子内存访问如何围绕原子操作排序。

初步理解内存顺序

下面是我对于内存顺序的理解,由于在x8-64的机器上,内存顺序的问题本身不容易触发,所以下面的所有解释都没有经过验证,但是是我通过阅读网络上各种“不靠谱”的文献之后,经过自己筛选总结出的一套可信的解释。

memory_order_acquire & memory_order_release

在各种资料中,这两个内存顺序标记都是组合使用的,一个比较直观的理解是:线程A的release标记写操作W_A和线程B的acquire标记读操作R_B组合,可以达到:

  1. 线程A中的所有W_A之前的写操作,相对于W_A对齐,也就是说W_A操作完成后,线程A所有写操作完成
  2. 线程B中的所有R_B之后的读操作,相对于R_B对齐,也就是说R_A操作开始时,线程B的所有读操作尚未开始
  3. 线程A的W_A在线程B的R_B之前读入

综合上面三条性质,我们发现,acquire-release操作成功将线程A和线程B分割开来。

memory_order_relaxed

不进行内存顺序限制,即对于某一条语句,倘若运用了memory_order_relaxed标记,则其储存顺序对于其他线程不可见。那么什么时候使用这个标记呢?

既然acquire-release通过标记线程A的最后一个写操作,和线程B的第一个读操作,实现了线程的顺序要求,那么除了这两个操作之外的其他操作,实际上是可以直接用memory_order_relaxed的

无锁数据结构设计 之 通过atomic实现自旋锁

这是mhy12345的无锁数据结构教程的第二篇,通过atomic<bool>实现自旋锁。对,你没有听错,用无锁数据结构实现一个锁 >_<

自旋锁,顾名思义,通过自旋来实现线程加锁的工具。一个最简单的demo如下

看起来这是一个很机智的做法。程序进入时将一个共享bool变量赋值为true,而在另一个程序准备进入时,检查到该bool变量已经为true了,就放弃进入,开始用while语句自旋。

自旋锁流程
自旋锁流程

不过对于一个多线程程序,其他线程可以在任意位置接入,比如这个程序的第4行和第5行不是一个原子操作,倘若这个时候恰好另一个线程获得了控制权,读取到flag值为false,继续执行,但是在释放flag之前控制权有转会了第一个线程,由于第一个线程已经执行了取值操作,也默认flag为false,继续执行,导致受保护数据被重复访问。产生问题。

这时候,一个非常自然的想法就是:我们能不能把对flag的操作换成原子数据类型操作呢?答案是肯定的!

当程序执行到第六行时,准备进入临界区 //TODO ,首先判断flag是否为false,如果不是,说明已经有一个程序在临界区中间了。否则将flag赋值为true,自己进入临界区。

一点细节是,如果进入临界区失败,则true值会被赋予expected,这是我们需要在while语句中恢复expected的值。

memory_order是什么呢?请看:无锁数据结构设计 之 详解C++内存顺序(Memory Order)

 

参考资料:

https://blog.poxiao.me/p/spinlock-implementation-in-cpp11/

http://blog.csdn.net/yockie/article/details/8838661

 

无锁数据结构设计 之 原子数据类型Atomic介绍

  • 这是mhy12345的无锁数据结构教程的第一篇,原子数据类型介绍。在阅读这篇文章之前,先安利一本这方面叙述非常详细的书《C++并发编程实战》(C++ Concurrency IN ACTION)
  • 想要详细了解无锁编程可移步无锁编程教程,里面从原理上介绍了atomic类型。

原子操作,即不可分割的操作,这样的操作在观察者看来,要不然就做完了,要不然就没有做完。原子操作本身是数据库中的一个概念,举一个例子,“在数据库中删除name为mhy12345的数据项,并且添加一个myh54321的数据项”对应了一个用户改名操作。这种操作如果从中间断开,只完成了一半,会产生灾难性后果。

为了使得我们数据结构能在多线程环境下安全运行,并且尽量不使用锁mutex(时间开销太大),原子数据类型就成了最佳选择方案。C++11提供了一系列原子数据类型,包含在头文件<atomic>里面,我们首先介绍原子数据类型的模板 std::atomic<T> a ,这是一个泛类型模板,支持极少数原子操作——

对于上述的原子操作函数,我们可以理解为函数的调用不会由于进程调度而被切断。例如其中的 compare_excahnge_strong(x,y) 函数,在单线程情况下,等同于一个if语句——

在多线程情况下,该if语句是可以被进程调度切断,这在某些情况下是我们不希望发生的,而这时,我们可以将这个语句用 compare_excahnge_strong 实现。

每一种操作还有一个内存顺序参数memory_order可以选择,这方面内容将在无锁数据结构设计 之 详解C++内存顺序(Memory Order)中介绍。不过,现在,我们可以直接忽略参数中所有memory_order相关项。

接下来,我们将详细介绍这几个函数——

前三个函数并不需要太详细的讲解,因为赋值、读取操作本身在我们的理解中就已经不可分割了,实际上,在当今大多数处理器上,即使一个普通的int的读写也都是原子的。

exchange(x)在我学习期间基本没有看到过使用,不过含义也非常简单:将desired储存,返回是原来的值。本质就是一个数据交换的方式。

定义很多,只用看第一条定义就好了,将变量的值与expected比较,如果相等就用desired更新,返回true,否则返回false,将变量的值放在expected里面。其等价的伪代码在前文已经写过了。

也许读者会问:这个函数看起来非常奇怪,真的在实际工程中会用吗?其实,这两个函数才是atomic的精粹所在!

无论是互斥锁实现,还是无锁栈,无锁队列的实现,都需要用到这些函数。具体细节可以移步 无锁数据结构设计 之 通过atomic实现自旋锁

看了这些文章,可能又有了新的疑惑,我怎么没看出来 compare_exchange_strong 和 compare_exchange_weak 有什么区别?

其实答案很简单, compare_exchange_weak 可以理解为 compare_exchange_strong 的一个有bug,但是更加高效的实现——

在一些特殊情况下,即使expected和变量的值是相同的,也有可能返回false,不过这样一个bug对于最常见的情况:将函数放在一个while循环中并不会产生影响,下面是一个典型的 compare_exchange_weak 放在while循环中的例子。在该例子中,如果少数情况条件判断将本应返回true的情况判断成了false,也并不会导致什么问题(只是多执行一遍while循环罢了)

所以说如果我们并没有意图通过函数返回值判断是否expected与变量的值确实不同,或者对于错误有容许度,我们完全可以用weak替换strong。

 

参考资料:

Cplusplus reference:http://en.cppreference.com/w/cpp/atomic/atomic