无锁编程教程:简介


无锁程序的设计非常复杂,一方面,需要读者对于并行计算涉及概念有较深的理解,另一方面,由于不同平台表现不一致,调试困难等客观原因,即使写出了程序也不容易检验。我的无锁编程始于Bruce Dawson的论文,十分幸运的是,我甚至有机会在工作中,借鉴Bruce的一些无锁数据结构编程技巧,并运用到Xbox 360等平台的编程与调试中。

从那以后,我写了一系列资料,从最基本的理论推导到最实际的代码编写,甚至最底层的硬件细节都有所涉及。然而不幸的是,这些资料甚至有些都是相互矛盾的,比如,有一些材料直接假定了顺序一致性(sequential consistency),并借此避免了任何有关于内存顺序细节的讨论,而在另一些材料中却没有做这些假设。随着C++11原子数据类型 的出现,本来就非常混乱的无锁编程变得更加复杂,让我们更难解释无锁算法的运行原理了。

在这篇文章中,我希望能够重新系统得介绍无锁编程,从对于每一个基本概念的定义开始。运用流程图,展示出这些概念如何互相关联,进而分析这些概念的一些细节。如果你准备继续读下去,我假设你已经理解最简单的多线程程序的编写,以及锁(mutex),信号量(semaphores)等同步机制。

无锁编程是什么?

大多数人对于无所编程的理解都停留在“不用锁来写多线程程序”。毋庸置疑,这样的定义是没有问题的,但是并不完整。对于无锁编程,被学术界认可的定义更加宽泛,学术界认为,“无锁(lockfree)”仅仅是一种代码的性质罢了。

简单的来说,如果程序的一部分满足接下来提到的这些条件,那么我们就可以认为他是“无锁”的,反之,如果不满足,则程序不是“无锁”的。

通过上图,我我们发现“无锁(lock-free)”这个词中的“锁(lock)”并不是指代码中的“锁(mutex)”,而是指的是能够通过某种方式“阻塞(locking up)”整个程序的可能性。这个可能性可能来源于经典的“死锁(deadlock)”,也可能由于很糟糕的内存调度顺序使得程序停滞不前(这可能变成一些恶意攻击者的突破口)。这听起来挺搞笑的,但是由于持有锁(mutex)的线程的调用顺序是任意的,因此最坏的情况是可能发生的,纵使有些时候,理论计算告诉我们“最坏情况”是一个不可能事件(概率为0),但是从概念上来说,只要“可能发生”阻塞,那么这个程序就不是无锁的。

举一个例子,对于下面的无锁程序,在初始 X=0 的情况下,什么样的调度顺序可以导致程序永远按无法退出循环?(这个问题留给读者自己思考)

没有人指望一个很大的工程是完全无锁的,通常来说,我们希望这个工程中某一个访问了公有内存的代码片段是无锁的。举一个例子,我们可能希望拥有一个“无锁队列”,这个无锁队列支持若干无锁的操作,诸如 push , pop , isEmpty 等等操作。

The Art of Multiprocessor Programming的作者Herlihy 和 Shavit倾向于将上述的操作描述成类的方法,进而对无锁(lock-free)有了一个更简单的定义:

在无限次执行中,可以完成无限次方法调用。

换句话来说,只要程序不停地调用这些“无锁”的方法,已完成的函数调用不停增加,则从算法上来看,系统是不可能发生死锁的。

从无锁编程的定义,我们可以引出一个很重要的结果:假如说我们停止了一个线程,这个操作是不会影响其他线程的执行的。正因为如此,在编写实际程序的时候,所有的线程都必须能够在有限的时间内完成,不论其他的线程干了什么。

顺带一提,如果一个操作被设计成阻塞操作,他有可能仍然是无锁的。比如无锁队列的删除会在队列为空的时候被阻塞,这并不影响他是无锁的。

无锁编程的技巧

当你尝试去实现一个无阻塞的无锁程序,这会引出一系列技巧,比如:原子操作(atomic operations),内存屏障(memory barriers), ABA问题等。从这里开始,问题就变得棘手起来。

这些技巧是如何关联起来的呢?我准备使用一个流程图来解释这个问题:

原子的“读-修改-写”操作

原子操作的定义为一系列可以访问内存,并且不可分割的操作。没有任何线程可以观测到进行了一半的原子操作。在现代的处理器中,很多的操作都是原子的,比如:基础数据类型的“对齐读取(aligned reads)”和“对齐写(aligned writes)”通常是原子的。

更近一步,我们有了 读-修改-写(Read-modify-write) (RMW)操作,这个操作使我们可以原子化更复杂的操作,特别的,当有多个写线程时,这个操作非常有用。原因在于,当多个线程试图去读-修改-写一个内存区域时,他们会自动被排成不想交的一列,并依次执行。在之前的博客中,我已经讲过读-修改-写操作了,比如在 轻量锁, a 自旋锁 和  轻量的日志系统.

RMW操作的例子有Win32编程中的  _InterlockedIncrement ,IOS编程中的 OSAtomicAdd32 ,和C++11中的 std::atomic<int>::fetch_add 。值得注意的是,C++11标准并不保证这个实现是无锁的,具体是不是通过无锁来实现依赖于你的平台。因此,你最好提前了解你的平台是否支持这些无锁操作,或者通过调用 std::atomic<>::is_lock_free 来查看。

不同的CPU系列使用不同的方式支持RMW操作。比如PowerPC和ARM等处理器使用load-link/store-conditional 指令,这种指令使你能够在底层自定义你自己的RMW操作,即使通常并没有人这么干,毕竟普通的RMW操作已经足够了。

正如流程图中所说,RMW十分重要,即使是在只有一个处理器的系统中。如果没有了原子性,一个线程可能被中途打断,并导致一些潜在的问题。

“比较并交换”循环

最常讨论的RMW操作是 比较并交换(compare-and-swap) (CAS)。在Win32里面,CAS通过一系列intrinsics函数实现的,比如 _InterlockedCompareExchange 。通常情况下,我们在循环中使用CAS操作来尝试提交一些操作。具体来说,我们首先拷贝一些公有变量到局部变量中,并进行一些操作来改动局部变量的值,最后,将这些改动借助CAS操作提交至公有可见。

这样的循环是无锁的,因为如果一个线程的if条件测试为false,这意味着他一定紧接着另一个线程执行完毕相同操作的线程之后。尽管在一些架构下,存在 弱化的CAS操作,在这些CAS操作中,上述不一定是if语句判断false的充要条件,但是这些弱化的CAS操作仍然能够有效避免ABA问题。

顺序一致性

顺序一致性(Sequential Consistency)意味着所有的线程都有共同的对于内存访问操作的顺序的判定。这个判定的内存访问操作的顺序恰好等同于在源代码中的内存访问定义的顺序。在线性一致性模型中,一些内存顺序有关的问题不会发生。

一个非常简单(但是显然不可能在实际中使用的)解决内存一致性的方式是禁用编译器优化,并且强制所有的线程在同一个处理器上面运行。这样,即使存在着线程的切换,处理器将永远无法发现自己的内存顺序出现了问题。

一些编程语言即使在优化了代码之后,在多核环境中,依然保证了顺序移植性。在C++11中,你可以定义拥有默认内存顺序(memory ordering)的公共的原子数据类型来实现内存访问的移植性。在Java中,你可以将公有变量标记为 volatile 已实现顺序移植性。下面是一个例子:

由于C++原子操作保证了顺序一致性,因此结果r1 = r2 = 0是不会发生的。从编译器层面来看,编译器添加了一些额外的指令(如内存屏障或RMW操作)来保证顺序一致性。这些额外的指令带来了更大的时间花销,但是让程序员能够以最直观的方式操作内存顺序。

内存顺序

正如流程图中所述,当你在多核计算机上运行无锁程序,且你的程序并没有保证内存顺序一致性的时候,你需要思考如何避免内存乱序的发生。

在线代的处理器结构中,这些试图矫正内存顺序的方法可以分为两类分别是矫正 编译器导致的内存乱序(compiler reordering)处理器导致的内存乱序(processor reordering) 具体而言有如下方式:

  • 一系列轻量级的同步以及屏障指令,这些我将在之后讨论
  • 一系列内存屏障的指令,我在之前已经展示过
  • 一些内存顺序的指令,提供了acquire和release语义

Acquire语义防止该语句后的语句内存乱序,而Release语义防止了该语句之前语句的错排,这些语义特别适合用于处理“生产者/消费者”关联的线程关系,一个线程生产并广播消息,而另一个线程接收消息,这些我也将在之后的文章中详述。

不同处理器有不同的内存模型

不同的处理器有不同的内存模型,在内存重拍的问题上,不同的CPU以来的规则是依赖于硬件的,比如PowerPC和ARM处理器可以修改内存写的执行顺序,而Inter和AMD的x86/64处理器则不行。因此,古老的处理器有更加弱的内存模型(relaxed memory model).

通过C++11,我们可以调用一些固有的模板来无视掉这些由于平台导致的问题。不过我认为程序员们需要知道不同平台的区别。其中比较重要的一点事,在x86/64的处理器层面,所有的读(load)操作都自带了acquire语义,而所有的写(store)操作都自带了release语义,至少对于非SSE指令集和非并行储存的内存模型而言是这样的。从结果上来看,一些在x86/64上运行正常的程序在其他处理器上崩溃就不是一件很奇怪的事情了。

如果你对于处理器如何将内存操作重排感兴趣的话,我推荐你阅读Is Parallel Programming Hard的附录C。并且时刻警醒内存重排有时候是来自于编译器而非处理器。

在这篇文章中,我们有过多的提及无锁编程的一些实际代码编写上的策略,比如什么时候我们应该用无锁编程,我们应该做到什么程度,以及验证你程序有效性的必要性。对于大多数读者,这个简介只是为了给你一些无锁编程的最基本的概念,让你在之后的阅读中不会因为一些简单的概念而困惑。与之前相似,如果你发现有任何的不准确的地方,请通过评论告诉我。

原创文章地址:【无锁编程教程:简介】,转载时请注明出处mhy12345.xyz

《无锁编程教程:简介》有3个想法

发表评论

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

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