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

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

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

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

a.load();//获得a的值
a.store(x);//将新值存在a里面
a.exchange(x);//将x的值存入a,并返回原来的值
a.compare_exchange_weak(x,y);//将a的值与x比较,如果相等则将y存在a里面,否则将x的值变为a内部储存的值,返回是否储存成功
a.compare_excahnge_strong(x,y);//基本同上
a = <non-atomic-instance-of-T>; //等同于store

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

//将a的值与x比较,如果相等则将y存在a里面,否则将x的值变为a内部储存的值,返回是否储存成功
if (a == x) {
    a = y;
    return true;
}else {
    x = a;
    return false;
}

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

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

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

void store( T desired, std::memory_order order = std::memory_order_seq_cst ) noexcept;
void store( T desired, std::memory_order order = std::memory_order_seq_cst ) volatile noexcept;

T load( std::memory_order order = std::memory_order_seq_cst ) const noexcept;
T load( std::memory_order order = std::memory_order_seq_cst ) const volatile noexcept;

T operator=( T desired ) noexcept;
T operator=( T desired ) volatile noexcept;

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

T exchange( T desired, std::memory_order order = std::memory_order_seq_cst ) noexcept;
T exchange( T desired, std::memory_order order = std::memory_order_seq_cst ) volatile noexcept;
/*Atomically replaces the underlying value with desired. The operation is    read-modify-write operation. Memory is affected according to the value of order.*/

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

bool compare_exchange_weak( T& expected, T desired,
                            std::memory_order success, 
                            std::memory_order failure ) noexcept;
bool compare_exchange_weak( T& expected, T desired,
                            std::memory_order success, 
                            std::memory_order failure ) volatile noexcept;
bool compare_exchange_weak( T& expected, T desired,
                            std::memory_order order =
                                std::memory_order_seq_cst ) noexcept;
bool compare_exchange_weak( T& expected, T desired,
                            std::memory_order order =
                                std::memory_order_seq_cst ) volatile noexcept;
bool compare_exchange_strong( T& expected, T desired,
                              std::memory_order success, 
                              std::memory_order failure ) noexcept;
bool compare_exchange_strong( T& expected, T desired,
                              std::memory_order success, 
                              std::memory_order failure ) volatile noexcept;
bool compare_exchange_strong( T& expected, T desired,
                              std::memory_order order = 
                                  std::memory_order_seq_cst ) noexcept;
bool compare_exchange_strong( T& expected, T desired,
                              std::memory_order order = 
                                  std::memory_order_seq_cst ) volatile noexcept;
/*Atomically compares the object representation of this with the object representation of expected, as if by std::memcmp, and if those are bitwise-equal, replaces the former with desired (performs read-modify-write operation). Otherwise, loads the actual value stored in this into expected (performs load operation). */

定义很多,只用看第一条定义就好了,将变量的值与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 = count.load();
desired = expected+1
while(!count.compare_exchange_weak(expected,desired)) {
    desired = expected + 1;
}

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

 

参考资料:

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据