八条设计多线程程序的简单规则

前言:最近在看该作者的《The Art of Concurrency》,里面第四章就是上面这篇文章,觉得很实用而且很有共鸣。作者基于在并行编程领域的20多年工作经验总结成上面八条简单的原则,一下子帮我把之前并行编程时的一些认识给理清了,量化了,实在是“居家旅行,并行编程,必备良药”。花了几天时间把它翻译了一下,不知道各位在看了之后是否有些共鸣呢?

阅读全文>>

更新:
[2010.3.6] Scalability翻译从”可扩展性“改成”可伸缩性“.

前言:最近在看该作者的《The Art of Concurrency》,里面第四章就是上面这篇文章,觉得很实用而且很有共鸣。作者基于在并行编程领域的20多年工作经验总结成下面八条简单的原则,一下子帮我把之前并行编程时的一些认识给理清了,量化了,实在是“居家旅行,并行编程,必备良药”。花了几天时间把它翻译了一下,不知道各位在看了之后是否有些共鸣呢?


作者:Clay Breshears
译者:并行实验室 Parallel Labs

在Intel,并行化技术主要有四个步骤:分析,设计与实现,调试以及性能调优。这些步骤用来对一段串行代码进行并行化。尽管这四个步骤中的第一、三、四步都已经有了很多相关文档,但是关于怎样进行设计与实现的却不多。

并行编程更像是一门艺术,而不是一门科学。这里将会给出八条设计多线程程序的简单规则,你可以把他们一一放进你的多线程程序设计百宝箱中。通过参考这些规则,你能写出高质量、高效率的多线程程序。我努力试着将这些规则按照(半)时间顺序组织起来,但是它们之间并没有硬性的先后顺序。就像“别在泳池边奔跑”和“别在浅水区跳水”一样,两个都是好主意,但是后者也能放在前者的前面,反之亦然。

规则一:找到真正不相关的计算任务
如果你将要执行的运算任务相互之间不独立的话,你是不可能将它们并行化的。我可以很容易的举出一些真实世界中相互独立的任务如何为了达成同一个目的而工作的例子。比如说一个DVD出租店,它先把收到的求租电影的订单分给员工们,员工再从存放电影DVD的地方根据订单找到影片拷贝。当一个员工取出一张古典音乐喜剧的拷贝时,他并不影响另一个寻找最近科幻电影大作的员工,也不影响另一个寻找某热门犯罪连续剧第二季花絮的员工(我假设所有不能被满足的订单在递交给DVD出租店之前就已经被处理过了)。同样的,每个订单的打包和邮递工作也不会影响其他订单的查找、运送和处理工作。

你也可能会遇到某些不能被并行化的而只能串行执行的计算任务,它们大多数是因为循环之间或者计算步骤之间有依赖关系从而导致它们只能按照特定的顺序串行执行。一个很好的例子是驯鹿怀孕的过程。通常驯鹿需要八个月来生小驯鹿,你不可能为了早点生个小驯鹿就让八个驯鹿来一起来生,想一个月就生出一个来。但是,如果圣诞老人希望尽快的扩充雪橇队伍,他可以让八只驯鹿一起生,这样八个月后就能有八只小驯鹿了(注:可以理解为尽管单个任务的执行时间没缩短,但是吞吐量却大了)。

规则二:尽可能地在最高层进行并行化
在对一段串行代码进行并行化时我们有两种方法可以选择,一个是自底向上,另一个是自顶向下。在对我们的代码进行分析的过程中,我们先找到花费了最多执行时间的程序热点(hotspots)。对这些代码段进行并行化是使我们获得最大的性能提升的最好办法。

在自底向上的方法中,你可以考虑先直接对那些程序热点进行并行化。如果这不太可能实现的话,我们可以顺着它的调用栈(call stack)向上查找,看看能不能找到其他的可以并行化的程序热点。假如你的程序热点在一个嵌套循环的最里层,我们可以从内向外的逐一检查每一层循环,看看某一层是否能被并行执行。即使我们能一开始就很顺利的把程序热点并行化了,我们仍然应该去检查一下是否可能在调用栈中更高的某一层上实现并行化。这样做能提高每个线程所执行的任务的粒度。(注:每个线程所执行的任务的粒度可以理解为成功并行化了的部分在整个程序中所占的比例,根据Amdahl定律,并行化的部分越多,程序的整体性能越高)

为了更清楚的描述这条规则,让我们举一个对视频编码程序进行并行化的例子。如果你的程序热点是针对每个像素的计算,你可以先找到对一帧视频中的每个像素进行计算的循环,并考虑对它进行并行化。以此为基础向“上”找,你可能会发现对每一帧进行处理的循环也是可以被并行化的,这意味着每个线程都可以以帧为单位对一组数据进行独立的处理。如果这个视频编码程序同时要对好几个视频进行处理,那么让每个线程单独处理一个视频流将会是最高层的并行化。

在另一种自顶向下的并行化方法中,我们可以先对整个程序以及计算的流程(为了完成计算任务而依序组合起来的各个程序模块)进行分析。如果并行化的机会不是很明显,我们可以挑出那些包含了程序热点的模块并对他们进行分析,如果不行就再分析更小的程序热点模块,直到能找到独立的计算任务为止。

对视频编码程序的例子来说,如果你的程序热点是针对单个像素的计算,采用自顶向下的方法时就可以首先考虑该程序对多个不同的视频流进行编码的情况(每个编码任务都包含了像素计算的任务)。如果你能在这一层成功进行并行化,那么你已经得到了最高层的并行。如果没能成功,那我们可以向“下”找,看看每个视频流的不同帧的计算是否能被并行处理,最后看看每个帧的不同像素的计算是否能被并行处理。

并行任务的粒度可以理解成在进行同步之前所需要完成的计算量。同步之间运行的时间越长,粒度越大。细粒度的并行存在的隐患就是给每个线程分配的任务可能不够多,以至于都不够弥补使用多线程所带来的开销。此时,在计算量不变的情况下使用更多的线程只会让情况变得更加糟糕。粗粒度的并行化拥有相对来说更少的线程开销,并且更可能在线程增多的情况下仍然有很好的可扩展性。尽可能的在最高层对程序热点实现并行化是实现对多线程的粗粒度任务划分的主要方法之一。

规则三:尽早针对众核趋势做好可伸缩性的规划
当我写这本书的时候,四核处理器已经成为了主流。未来处理器的核心数量只会越来越多。所以你应该在你的软件中为这个发展趋势做好规划。可伸缩性(scalability)被用来用来衡量一个程序应对变化的能力,典型的变化有系统资源(例如核心数量,内存大小,总线速度)或数据集大小的增加等。在面对越来越多的可用核心时,你必须写出能灵活高效的利用不同数量的核心的代码。

C. Northcote Parkinson说过,“数据的增长是为了适应处理能力的增加”。这意味着随着计算能力的增长加(核心数量的增加),很有可能我们会有更多的数据需要处理。我们永远会有更多的计算任务需要完成。不管是增加科学模拟中的建模精度,还是处理更清晰的高清视频,又或者搜索许多更大的数据库,如果你拥有了更多的计算资源,总会有人想要处理更多的数据。

用数据分解(data decomposition)的方法来设计和实现并行化能给你提供更多的高可扩展性的解决方案。任务分解(task decomposition)的方法可能会面临程序中可独立运行的函数或者代码段数量有限或者数量固定的问题。等到每一个独立的任务已经在单独的线程和核心上运行的时候,再想通过增加线程的数量来利用空闲的多余核心的方法就提高不了程序的性能了。因为在一个程序中数据的大小比独立的计算任务的数量更有可能增加,所以基于数据分解的设计将更有可能获得很好的可伸缩性。

即使有的程序已经基于任务分解的模式给每个线程分配了不同的计算任务,我们仍然可以在需要处理的数据增加的时候利用更多的线程来完成工作。例如我们需要修建一个杂货店,这项工程由一些不同的任务组成。如果开发商又买了一块相邻的地皮,并且商店要盖的楼层数翻倍了,我们可以雇佣更多的工人去完成这些的任务,比如说更多的油漆工,更多的盖顶工,更多的电工。因此,我们应该注意是否能对增加了的数据进行数据分解,以便利用空闲核心上的可用线程来完成这个工作,哪怕是在我们已经采用了任务分解的方式的程序中。

规则四:尽可能利用已有的线程安全库
如果你的程序热点的计算任务能通过库函数调用来完成,强烈建议你考虑使用同等功能的库函数,而不是调用自己手写的代码。即使是串行程序,“重新造轮子”来完成已经被高度优化的库函数实现了的功能仍不是一个好主意。许多的库,例如Intel Math Kernel Library(Intel MKL)和Intel Integrated Performance Primitives (Intel IPP),提供了能更好的利用多核处理器的并行版本的函数。

比使用并行版本的函数库更重要的一点是:我们需要确保所有的库函数调用都是线程安全的(thread-safe)。如果你已经把你串行代码中的程序热点替换成了一个库函数调用,你仍有可能在调用树(call tree)的更高层上发现能把程序分解成独立的计算任务的代码段。当你有好几个并行的计算任务,并且它们都同时调用了库函数(特别是第三方函数库),那么函数库中引用并更新共享变量的函数可能会造成数据竞争(data race)。记得好好检查你在并行编程中所调用的函数库的文档中关于线程安全性的描述。当你在设计和编写自己的用于并行执行的函数库时,请务必确保函数是可重入(reentrant)的。如果不能确保的话,你应该给共享的资源加上同步机制。

规则五:使用合适的多线程模型
如果并行版的函数库不足以完成程序的并行化,而你又想使用可以自己控制的线程,在隐式的多线程模型能满足你的功能需求的前提下请尽量使用该模型(例如OpenMP或者Intel Thread Building Block)而不是显式的多线程模型(例如Pthread)。显式的多线程模型确实能提供对线程的更精确的控制。但是,如果你仅仅是想把你的计算密集型循环给并行化,或者你不需要显式多线程模型提供的诸多特性,那么我们最好还是能满足需要就好。实现的复杂度越高,犯错误的几率就越大,以后代码的维护难度也会越大。

OpenMP采用的是数据分解的方法,它尤其适合并行化那些需要处理大量数据的循环。尽管这种类型的并行化可能是唯一一种你能引入的并行模式,但是可能还会有其他的要求(例如由你的雇主或者管理层所决定的工程方案)让你不能使用OpenMP。如果是那样的话,我建议你先使用OpenMP来快速开发出并行化后的模型,估算一下可能的性能提升、可扩展性以及大概需要多少时间才能把这些串行代码用显式多线程库给并行化。

规则六:永远不要假设具体的执行顺序
在串行程序中我们可以非常容易地预测某个程序的当前状态结束之后它会变成什么状态。然而,多个线程的执行顺序却是不确定的,它是由操作系统的调度器(scheduler)决定的。这意味着我们不可能准确的预测两个执行状态之间多个线程的执行顺序,甚至连预测哪个线程会在下一步被调度执行也不能。这样的机制主要是为了隐藏程序运行时的延迟,特别是当运行的线程的数量多于核心的数量时。例如,如果一个线程因为要访问不在cache中的地址,或者需要处理一个I/O请求而被阻塞了(blocked),那么操作系统的调度器就会把该线程调度到等待队列里,同时把另一个等待执行的线程调度进来并执行它。

数据竞争(data race)就是由这种调度的不确定性造成的。如果你假设一个线程对共享变量的写操作会在另一个线程对该共享变量的读操作之前完成,你的预测可能会一直正确,有可能有些时候会正确,也有可能从来都不会正确。如果你足够幸运的话,有时候在一个特定平台上每次你运行这个程序时线程的执行顺序都不会改变。但是系统间的每个不同(例如数据在磁盘上存储的位置,内存的速度或者插座中的交流电源)都有可能影响线程的调度。对一段需要特定的线程执行顺序的代码来说,如果仅仅依靠乐观的估计而不采取任何实质性的措施的话,很有可能会受到数据竞争,死锁等问题的困扰。

从性能的角度来讲,最好的情形当然是让所有的线程尽可能没有约束的运行,就像比赛中的赛马或猎犬的一样。除非必要的话,尽可能不要规定一个特定的执行顺序。你需要找到那些确实需要规定执行顺序的地方,并且实现一些必要的同步方法来调整线程间的执行顺序。

拿接力赛跑来说,第一棒的选手会竭尽全力的奔跑。但是为了成功的完成接力赛,第二个,第三个和最后一棒都需要先等到拿到接力棒之后才能开始跑他们的赛段。接力棒的交接就是他们的同步机制,这样就确保了接力过程中的“执行”顺序。

规则七:尽可能使用线程本地存储或者对特定的数据加锁
同步(Synchronization)本身并不属于计算任务,它只是为了确保程序的并行执行能得到正确的结果所产生的额外开销。虽然它产生了额外的开销但是又不可或缺。因此我们还是要尽可能的把同步所产生的开销降低到最低。你可以使用线程私有的存储空间或者独占的内存地址(例如一个用线程ID来进行索引的数组)来达到这个目的。

那些很少需要在线程间共享的临时变量可以被每个线程单独地在本地进行声明或分配。那些存储着每个线程的部分结果(partial result)的变量也应该是线程私有的。但是在把每个线程的部分结果保存到一个共享的变量的时候就需要采取一些适当的同步措施了。如果我们能确保这样的共享更新操作能尽可能少的进行,我们就可以把同步的额外开销降到最低了。如果我们使用显式的线程编程模型的话,我们可以使用那些线程本地存储(Thread Local Storage)的API来保证线程私有变量在多个并行区域的执行过程中,或者在一个并行函数的多次调用的过程中的一致性。

如果线程本地存储不可行,而且你必须用同步的对象(例如锁)来协调对共享资源的访问的话,请确保对数据进行了适当的锁操作。最简单的方法就是对锁和数据对象采取一一对应的分配策略。如果对变量的内存地址的访问都是在同一个临界区进行的话,我们就可以使用一把锁来对多个数据进行保护。

如果你有大量的数据需要保护,例如由一万个数据的数组,我们该怎么办呢?如果我们对整个数组只用一个锁来进行保护的话,很可能会造成严重的锁竞争从而导致性能瓶颈。那么我们是不是可以给每个数组元素创建一个锁呢?然而即使是有32个或者64个线程在同时访问这个数组,这样做看起来也浪费了很多的内存空间来保护那些只有百分之一不到的发生概率的访问冲突。不过有一种折中的解决方案,叫做“取模锁”(modulo lock)。取模锁是用来保护数据集合中的所有的第N个元素,其中N是锁的数量。例如,有两个锁,一个保护所有的奇数个的元素,另一个保护所有的偶数个元素。当需要访问一个被保护的变量时,线程需要先对要访问的地址进行取模操作,然后再去获得对应的取模锁。使用的锁的数量应该是基于线程的数量以及两个线程同时访问相同元素的可能性来决定。

但是,当你决定用锁来对数据进行保护时,请一定不要用多于一个的锁来给一个单独的元素进行加锁。西格尔定律告诉我们“一个人看着一个表能知道现在几点了,但是他要是有两个表那么他就确定不了时间了”。如果两个不同的锁都对同一个变量进行了保护,那么可能出现代码中的某一部分通过第一个锁来进行访问的同时,代码中的另一部分通过第二个锁也进行了访问。正在执行这两个代码段的多个线程就可能发生数据竞争,因为它们都以为它们对这个被保护的变量有独占的访问权限。

规则八:敢于更换更易并行化的算法
当比较串行或者并行程序的性能的时候,运行时间就是衡量的首要标准。程序员会根据算法的时间复杂度来进行选择。时间复杂度和一个程序的性能是息息相关的。它的含义就是,当其他的一切条件都一样时,完成同样功能的时间复杂度为O(NlogN)的算法(例如快速排序)要比O(n^2)的算法(例如选择排序)要快。

在并行程序中,拥有更好的时间复杂度的算法也会更快一些。然而,有些时候时间复杂度更好的算法却不是很容易被并行化。如果算法的热点不太容易被并行化的话(而且在调用栈的更高层中你又找不到能很容易被并行化的热点),那么你可以尝试换一个稍微慢一点但是却更容易被并行化的算法。当然,还有可能一些其他的改动措施也能让你比较轻松的把某一段代码给并行化了。

这里我们可以给出一个线性代数中两个矩阵相乘的例子。Strassen的算法拥有最好的时间复杂度:O(n^2.81)。这当然比传统的三重循环的O(n^3)的算法要好。Strassen的算法把每个分成四部分,然后进行七次递归调用来对n/2 x n/2的子矩阵进行乘运算。如果想把这七次递归调用并行化的话,我们可以在每次的递归调用的时候创建一个新线程来进行运算,直到子矩阵到达一个预设的大小为止。这样的话线程的数量就会指数级的成倍增长。随着子矩阵越来越小,给新创建的线程分配的计算任务就会越来越少。还有另一种方法,就是先创建一个有七个线程的线程池。七次子矩阵相乘的运算任务可以分别分配给这七个线程以完成并行化。这样的话线程池就会跟串行版本的程序一样递归调用Strassen算法来对子矩阵进行乘运算。然而,这种方法的缺点就在于对一个拥有大于八个核的系统来说,永远只有七个核在工作,其他的资源都被浪费了。

另一个更容易被并行化的矩阵乘法就是三重循环的算法了。我们可以有很多方法来对矩阵进行数据分解(按行分解,按列分解或者按块分解)然后再把它们分配给不同的线程。通过用OpenMP在某一层循环中加上编译指示,或者用显式线程模型实现矩阵分割,我们很容易的就能完成并行化。只需要更少的代码改动就可以对这个简单的串行算法完成并行化,并且代码的整体结构改动也会比Strassen算法要少很多。

总结
我们已经列出了八条简单的规则,在把串行程序并行化的过程中你应该时刻记住它们。通过遵循这些规则以及一些实际的编程规则,你应该可以更容易的创造更健壮的并行化解决方案,同时能包含更少的并行化时的问题,以及在更短的时间里得到最好的性能。

原文链接:8 Simple Rules for Designing Threaded Applications

Pthreads并行编程之spin lock与mutex性能对比分析

POSIX threads(简称Pthreads)是在多核平台上进行并行编程的一套常用的API。线程同步(Thread Synchronization)是并行编程中非常重要的通讯手段,其中最典型的应用就是用Pthreads提供的锁机制(lock)来对多个线程之间共 享的临界区(Critical Section)进行保护(另一种常用的同步机制是barrier)。

Pthreads提供了多种锁机制:
(1) Mutex(互斥量):pthread_mutex_***
(2) Spin lock(自旋锁):pthread_spin_***
(3) Condition Variable(条件变量):pthread_con_***
(4) Read/Write lock(读写锁):pthread_rwlock_***

Pthreads提供的Mutex锁操作相关的API主要有:
pthread_mutex_lock (pthread_mutex_t *mutex);
pthread_mutex_trylock (pthread_mutex_t *mutex);
pthread_mutex_unlock (pthread_mutex_t *mutex);

Pthreads提供的与Spin Lock锁操作相关的API主要有:
pthread_spin_lock (pthread_spinlock_t *lock);
pthread_spin_trylock (pthread_spinlock_t *lock);
pthread_spin_unlock (pthread_spinlock_t *lock);

从实现原理上来讲,Mutex是属于sleep-waiting类型 的锁。例如在一个双核的机器上有两个线程(线程A和线程B),它们分别运行在Core0和Core1上。当线程A想要 pthread_mutex_lock操作去得到一个临界区的锁时,如果这个锁正被线程B所持有,那么线程A就会被阻塞(bolcking),Core0 会在此时进行上下文切换(Context Switch),这样Core0就可以运行其他的任务(例如另一个线程C)而不必进行忙等待。而Spin lock则不然,它是属于busy-waiting类型的锁,如果线程A是使用pthread_spin_lock操作去请求锁,那么线程A就会一直在 Core0上进行忙等待并不停的进行锁请求,直到得到这个锁为止。

阅读全文>>

POSIX threads(简称Pthreads)是在多核平台上进行并行编程的一套常用的API。线程同步(Thread Synchronization)是并行编程中非常重要的通讯手段,其中最典型的应用就是用Pthreads提供的锁机制(lock)来对多个线程之间共 享的临界区(Critical Section)进行保护(另一种常用的同步机制是barrier)。

Pthreads提供了多种锁机制:
(1) Mutex(互斥量):pthread_mutex_***
(2) Spin lock(自旋锁):pthread_spin_***
(3) Condition Variable(条件变量):pthread_con_***
(4) Read/Write lock(读写锁):pthread_rwlock_***

Pthreads提供的Mutex锁操作相关的API主要有:
pthread_mutex_lock (pthread_mutex_t *mutex);
pthread_mutex_trylock (pthread_mutex_t *mutex);
pthread_mutex_unlock (pthread_mutex_t *mutex);

Pthreads提供的与Spin Lock锁操作相关的API主要有:
pthread_spin_lock (pthread_spinlock_t *lock);
pthread_spin_trylock (pthread_spinlock_t *lock);
pthread_spin_unlock (pthread_spinlock_t *lock);

从实现原理上来讲,Mutex属于sleep-waiting类型的锁。例如在一个双核的机器上有两个线程(线程A和线程B),它们分别运行在Core0和Core1上。假设线程A想要通过pthread_mutex_lock操作去得到一个临界区的锁,而此时这个锁正被线程B所持有,那么线程A就会被阻塞(blocking),Core0 会在此时进行上下文切换(Context Switch)将线程A置于等待队列中,此时Core0就可以运行其他的任务(例如另一个线程C)而不必进行忙等待。而Spin lock则不然,它属于busy-waiting类型的锁,如果线程A是使用pthread_spin_lock操作去请求锁,那么线程A就会一直在 Core0上进行忙等待并不停的进行锁请求,直到得到这个锁为止。

如果大家去查阅Linux glibc中对pthreads API的实现NPTL(Native POSIX Thread Library) 的源码的话(使用”getconf GNU_LIBPTHREAD_VERSION”命令可以得到我们系统中NPTL的版本号),就会发现pthread_mutex_lock()操作如果没有锁成功的话就会调用system_wait()的系统调用(现在NPTL的实现采用了用户空间的futex,不需要频繁进行系统调用,性能已经大有改善),并将当前线程加入该mutex的等待队列里。而spin lock则可以理解为在一个while(1)循环中用内嵌的汇编代码实现的锁操作(印象中看过一篇论文介绍说在linux内核中spin lock操作只需要两条CPU指令,解锁操作只用一条指令就可以完成)。有兴趣的朋友可以参考另一个名为sanos的微内核中pthreds API的实现:mutex.c spinlock.c,尽管与NPTL中的代码实现不尽相同,但是因为它的实现非常简单易懂,对我们理解spin lock和mutex的特性还是很有帮助的。

那么在实际编程中mutex和spin lcok哪个的性能更好呢?我们知道spin lock在Linux内核中有非常广泛的利用,那么这是不是说明spin lock的性能更好呢?下面让我们来用实际的代码测试一下(请确保你的系统中已经安装了最近的g++)。

// Name: spinlockvsmutex1.cc
// Source: http://www.alexonlinux.com/pthread-mutex-vs-pthread-spinlock
// Compiler(spin lock version): g++ -o spin_version -DUSE_SPINLOCK spinlockvsmutex1.cc -lpthread
// Compiler(mutex version): g++ -o mutex_version spinlockvsmutex1.cc -lpthread
#include <stdio.h>
#include <unistd.h>
#include <sys/syscall.h>
#include <errno.h>
#include <sys/time.h>
#include <list>
#include <pthread.h>

#define LOOPS 50000000

using namespace std;

list<int> the_list;

#ifdef USE_SPINLOCK
pthread_spinlock_t spinlock;
#else
pthread_mutex_t mutex;
#endif

//Get the thread id
pid_t gettid() { return syscall( __NR_gettid ); }

void *consumer(void *ptr)
{
    int i;

    printf("Consumer TID %lun", (unsigned long)gettid());

    while (1)
    {
#ifdef USE_SPINLOCK
        pthread_spin_lock(&spinlock);
#else
        pthread_mutex_lock(&mutex);
#endif

        if (the_list.empty())
        {
#ifdef USE_SPINLOCK
            pthread_spin_unlock(&spinlock);
#else
            pthread_mutex_unlock(&mutex);
#endif
            break;
        }

        i = the_list.front();
        the_list.pop_front();

#ifdef USE_SPINLOCK
        pthread_spin_unlock(&spinlock);
#else
        pthread_mutex_unlock(&mutex);
#endif
    }

    return NULL;
}

int main()
{
    int i;
    pthread_t thr1, thr2;
    struct timeval tv1, tv2;

#ifdef USE_SPINLOCK
    pthread_spin_init(&spinlock, 0);
#else
    pthread_mutex_init(&mutex, NULL);
#endif

    // Creating the list content...
    for (i = 0; i < LOOPS; i++)
        the_list.push_back(i);

    // Measuring time before starting the threads...
    gettimeofday(&tv1, NULL);

    pthread_create(&thr1, NULL, consumer, NULL);
    pthread_create(&thr2, NULL, consumer, NULL);

    pthread_join(thr1, NULL);
    pthread_join(thr2, NULL);

    // Measuring time after threads finished...
    gettimeofday(&tv2, NULL);

    if (tv1.tv_usec > tv2.tv_usec)
    {
        tv2.tv_sec--;
        tv2.tv_usec += 1000000;
    }

    printf("Result - %ld.%ldn", tv2.tv_sec - tv1.tv_sec,
        tv2.tv_usec - tv1.tv_usec);

#ifdef USE_SPINLOCK
    pthread_spin_destroy(&spinlock);
#else
    pthread_mutex_destroy(&mutex);
#endif

    return 0;
}

该程序运行过程如下:主线程先初始化一个list结构,并根据LOOPS的值将对应数量的entry插入该list,之后创建两个新线程,它们都执行consumer()这个任务。两个被创建的新线程同时对这个list进行pop操作。主线程会计算从创建两个新线程到两个新线程结束之间所用的时间,输出为下文中的”Result “。

测试机器参数:
Ubuntu 9.04 X86_64
Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz
4.0 GB Memory

从下面是测试结果:

gchen@gchen-desktop:~/Workspace/mutex$ g++ -o spin_version -DUSE_SPINLOCK spinvsmutex1.cc -lpthread
gchen@gchen-desktop:~/Workspace/mutex$ g++ -o mutex_version spinvsmutex1.cc -lpthread
gchen@gchen-desktop:~/Workspace/mutex$ time ./spin_version
Consumer TID 5520
Consumer TID 5521
Result - 5.888750

real    0m10.918s
user    0m15.601s
sys    0m0.804s

gchen@gchen-desktop:~/Workspace/mutex$ time ./mutex_version
Consumer TID 5691
Consumer TID 5692
Result - 9.116376

real    0m14.031s
user    0m12.245s
sys    0m4.368s

可以看见spin lock的版本在该程序中表现出来的性能更好。另外值得注意的是sys时间,mutex版本花费了更多的系统调用时间,这就是因为mutex会在锁冲突时调用system wait造成的。

但是,是不是说spin lock就一定更好了呢?让我们再来看一个锁冲突程度非常剧烈的实例程序:

//Name: svm2.c
//Source: http://www.solarisinternals.com/wiki/index.php/DTrace_Topics_Locks
//Compile(spin lock version): gcc -o spin -DUSE_SPINLOCK svm2.c -lpthread
//Compile(mutex version): gcc -o mutex svm2.c -lpthread
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/syscall.h>

#define        THREAD_NUM     2

pthread_t g_thread[THREAD_NUM];
#ifdef USE_SPINLOCK
pthread_spinlock_t g_spin;
#else
pthread_mutex_t g_mutex;
#endif
__uint64_t g_count;

pid_t gettid()
{
    return syscall(SYS_gettid);
}

void *run_amuck(void *arg)
{
       int i, j;

       printf("Thread %lu started.n", (unsigned long)gettid());

       for (i = 0; i < 10000; i++) {
#ifdef USE_SPINLOCK
           pthread_spin_lock(&g_spin);
#else
               pthread_mutex_lock(&g_mutex);
#endif
               for (j = 0; j < 100000; j++) {
                       if (g_count++ == 123456789)
                               printf("Thread %lu wins!n", (unsigned long)gettid());
               }
#ifdef USE_SPINLOCK
           pthread_spin_unlock(&g_spin);
#else
               pthread_mutex_unlock(&g_mutex);
#endif
       }
       
       printf("Thread %lu finished!n", (unsigned long)gettid());

       return (NULL);
}

int main(int argc, char *argv[])
{
       int i, threads = THREAD_NUM;

       printf("Creating %d threads...n", threads);
#ifdef USE_SPINLOCK
       pthread_spin_init(&g_spin, 0);
#else
       pthread_mutex_init(&g_mutex, NULL);
#endif
       for (i = 0; i < threads; i++)
               pthread_create(&g_thread[i], NULL, run_amuck, (void *) i);

       for (i = 0; i < threads; i++)
               pthread_join(g_thread[i], NULL);

       printf("Done.n");

       return (0);
}

这个程序的特征就是临界区非常大,这样两个线程的锁竞争会非常的剧烈。当然这个是一个极端情况,实际应用程序中临界区不会如此大,锁竞争也不会如此激烈。测试结果显示mutex版本性能更好:

gchen@gchen-desktop:~/Workspace/mutex$ time ./spin
Creating 2 threads...
Thread 31796 started.
Thread 31797 started.
Thread 31797 wins!
Thread 31797 finished!
Thread 31796 finished!
Done.

real    0m5.748s
user    0m10.257s
sys    0m0.004s

gchen@gchen-desktop:~/Workspace/mutex$ time ./mutex
Creating 2 threads...
Thread 31801 started.
Thread 31802 started.
Thread 31802 wins!
Thread 31802 finished!
Thread 31801 finished!
Done.

real    0m4.823s
user    0m4.772s
sys    0m0.032s

另外一个值得注意的细节是spin lock耗费了更多的user time。这就是因为两个线程分别运行在两个核上,大部分时间只有一个线程能拿到锁,所以另一个线程就一直在它运行的core上进行忙等待,CPU占用率一直是100%;而mutex则不同,当对锁的请求失败后上下文切换就会发生,这样就能空出一个核来进行别的运算任务了。(其实这种上下文切换对已经拿着锁的那个线程性能也是有影响的,因为当该线程释放该锁时它需要通知操作系统去唤醒那些被阻塞的线程,这也是额外的开销)

总结
(1)Mutex适合对锁操作非常频繁的场景,并且具有更好的适应性。尽管相比spin lock它会花费更多的开销(主要是上下文切换),但是它能适合实际开发中复杂的应用场景,在保证一定性能的前提下提供更大的灵活度。

(2)spin lock的lock/unlock性能更好(花费更少的cpu指令),但是它只适应用于临界区运行时间很短的场景。而在实际软件开发中,除非程序员对自己的程序的锁操作行为非常的了解,否则使用spin lock不是一个好主意(通常一个多线程程序中对锁的操作有数以万次,如果失败的锁操作(contended lock requests)过多的话就会浪费很多的时间进行空等待)。

(3)更保险的方法或许是先(保守的)使用 Mutex,然后如果对性能还有进一步的需求,可以尝试使用spin lock进行调优。毕竟我们的程序不像Linux kernel那样对性能需求那么高(Linux Kernel最常用的锁操作是spin lock和rw lock)。

2010年3月3日补记:这个观点在Oracle的文档中得到了支持:

During configuration, Berkeley DB selects a mutex implementation for the architecture. Berkeley DB normally prefers blocking-mutex implementations over non-blocking ones. For example, Berkeley DB will select POSIX pthread mutex interfaces rather than assembly-code test-and-set spin mutexes because pthread mutexes are usually more efficient and less likely to waste CPU cycles spinning without getting any work accomplished.

p.s.调用syscall(SYS_gettid)和syscall( __NR_gettid )都可以得到当前线程的id:)

转载请注明来自: www.parallellabs.com