多核编程锁竞争问题及其对策

作者： Zhouweiming 周伟明 (42 篇文章) 日期： 三月 26, 2009 在 10:08 上午

多核编程锁竞争问题及其对策

注：本文主要内容摘自笔者所著的《多核计算与程序设计》一书，略有修改，后续还会继续发布系列文章，如有需要，可以考虑将一下地址加入到您的浏览器收藏夹中：http://software.intel.com/zh-cn/blogs/category/multicore/。

在多核系统中编程，主要是使用多线程技术让程序并发执行。不过与单核系统编程的多线程编程有了很大的不同，具体来讲，有以下几个方面的区别：

1）锁竞争导致的串行化的区别

2）线程分解与执行的区别

3）CPU核负载平衡的区别

4）任务调度策略的区别

5）CPU Cache存取的区别（伪共享问题）

6）任务优先级抢占的区别

7）串行计算与并行及分布式计算的区别

本文先讲解其中的锁竞争问题及其对策。

锁竞争导致的串行化的区别

在单核系统中，如果某个线程获取了锁，那么这个线程将获取CPU的运行时间，其他等待获取锁的线程将被阻塞住，并得不到CPU的运行时间。因此单核系统中，即使使用了锁，影响计算时间的只是加锁、解锁操作本身耗费的时间，CPU还是一直处于运行状态的，并不会因为锁的问题出现CPU空闲现象，除非程序有BUG，出现死锁现象。

而在多核系统中，比如在双核系统中有两个线程A、B要使用同一把锁，那么当线程A获取锁后，在A未解锁前线程B将处于阻塞状态，这是只有线程A在运行，两个CPU核只有一个得到利用，另外一个CPU核处于空闲状态。

上面说的是两个线程的情况，实际上即使有更多线程，如果线程都处于等待同一把锁状态时，会导致只有一个线程在运行的情况，这样多个线程受锁竞争的影响出现串行化执行现象。

锁竞争导致的串行化现象对加速比指标有非常重大的影响，不论CPU核有多少，最终只有一个核在运行，加速比只有1，多核的性能只相当于单核的性能。

锁竞争的解决策略

锁竞争的解决方法有许多种，一种最简单的方法就是将竞争一把锁改为竞争多把锁，这样将可以使得同时有多个线程在运行，避免了同时只有一个线程在执行的情况。

竞争多把锁又叫分布式锁竞争，相关的设计模式有线程分组竞争模式和线程随机竞争模式，相关的材料可以参考以下两篇文章：

1、多核编程中的线程分组竞争模式

讨论了使用线程分组锁竞争方式来消除锁竞争导致的CPU饥饿现象，队列池就是线程分组竞争的一个非常好的实践，线程分组竞争模式相对于无锁编程具有更好的优势。 阅读全文

2、多核编程中的任务随机竞争模式的概率分析

本文主要分析了多个线程在随机分布式锁竞争的情况下，有不少于CPU核数个数的线程在运行的概率。然后将随机竞争和无锁编程的性能进行了理论上的比较。阅读全文

除了上面两种模式外，某些情况下还有一些更高效的方法来消除锁竞争问题，其基本思想就是减少锁的使用，多核编程中的条件同步模式这篇文章中讲解了一种减少锁的使用的方法。另外一种减少锁的方法是批量处理模式，以链表遍历为例，将每迭代一个节点就进行一次加锁解锁改为迭代多个节点进行一次加锁解锁，可以有效地减少锁的使用。

要彻底消除锁竞争，最理想的境界就是不使用锁，这就要用到老子是伟大的多核计算科学家一文中所说的自私的方法，有关如何在程序中实现自私，可以参考以下几篇文章。

多核分布式队列的实现：偷与自私的运用（1）

多核分布式队列的实现：偷与自私的运用（2）

多核分布式队列的实现：偷与自私的运用（3）

多核分布式队列的实现：偷与自私的运用（4）

这篇文章暂时先讲到这里，下一篇文章将讲解多核编程的伪共享问题。

 详情请看：多核编程伪共享问题及其对策

更多的多核相关的资源，可以访问：

1）Intel软件社区多核论坛：http://forum.csdn.net/Intel/IntelMulti-core/

2）Intel的博客：http://softwareblogs-zho.intel.com/

关于国内多核相关的书籍介绍可以参考下面这篇文章：

“多核编程高处并不“寒””，文章地址： http://news.csdn.net/n/20081107/120632.html

这篇文章里有我对现在市面上有关多核编程和并行计算书籍的一个点评。可以给大家购买书籍作为一个参考。

多核相关的开源项目介绍:

1、Intel 开源项目TBB库，链接：http://www.threadingbuildingblocks.org/

这是一个专门针对多核的开源项目，包含一些常见的多核数据结构与算法，如分段锁的哈希表、分布式内存管理、动态任务调度器等，其中最重要的一个是动态任务调度器，可以使用动态任务调度器将串行算法自动变成并行算法，免去程序员学习并行算法之苦。

TBB开源项目的使用方法详见O’Reilly出版的James Reinders的《Intel Threading Building Blocks》一书，如果要了解它的实现原理和方法，可以参考我写的《多核计算与程序设计》一书。

2、Capi开源项目，链接：http://gforge.osdn.net.cn/projects/capi 

这个项目是我开发的一个针对多核的数据结构与算法库，提供了许多实用的适应多核系统的数据结构与算法，主要的功能有以下一些：

1）各种并行算法，如并行归并排序、并行基数排序等并行排序算法；并行顺序搜索及终止检测算法、并行Dijikstra最短路径算法等并行搜索算法；并行前缀和、并行矩阵乘法等并行数值算法；等等。

2）分布式查找算法，如分段锁的哈希表、动态分布式哈希数组、动态哈希AVL树等。

3）抢夺式内存管理算法，即使在分配和释放共享内存时，也几乎不需要使用锁。

4）基于偷取和自私的分布式队列，用分布式队列实现的两种动态任务调度器、以及用动态嵌套任务调度器实现的Parallel_For()功能，用Parallel_For()实现的并行快速排序算法、并行归并算法等。

5）任务图调度器，可以用来实现对有依赖关系的执行块的并行计算。

这个开源项目和TBB相比起来各有特色，TBB库的优势在于它是商业化的开源项目，代码经过优化和相对完善的测试。CAPI的代码专门为学习而设计，代码没有经过优化，代码简单易懂，易于学习，并且实现了比TBB库更多的数据结构与算法容器，有一些创新的数据结构与算法在里面。其缺点是，现在发布的版本为0.2版本，如果进行商业使用需要自行增加测试用例进行更完善的测试和优化。

CAPI开源项目的实现原理和使用方法详见我写的《多核计算与程序设计》一书。

 

分类： 其他, 博客征文专栏, 并行计算

如需了解英特尔软件产品相关的性能和优化选项，请参阅优化注意事项.

 评论 (10)

2009年03月26日 18:12


xiaolinaxin		 不错
2009年03月27日 03:11

zhangzhe65
zhangzhe65总分:
275
注册用户
 想请教有关OpenMP中，循环并行化时加规约与不加规约时，所求得计算结果是一样的，为什么？
#pragram omp parallel for
for (i=0;i<n;i++)
sum+=a[i];

和
#pragram omp parallel for reduction(+:sum)
for (i=0;i<n;i++)
sum+=a[i];
结果完全相同，运行多次，上面并没有产生数据竞争。
2009年03月27日 06:59


we		 看看，还是不错的！
2009年03月28日 07:53


prestonlao		 想请教有关OpenMP中，循环并行化时加规约与不加规约时，所求得计算结果是一样的，为什么？ #pragram omp parallel for for (i=0;i
2009年03月29日 05:42


CHRISTOPHER		 可以看看
2009年03月29日 19:20

Zhouweiming 周伟明
Zhouweiming 周伟明总分:
4,910
黑带
 To prestonlao: 请检查一下编译器设置中的使用OpenMP开关是否打开，是否使用多线程库进行编译链接
2009年03月29日 23:19


a3819		 还没有学
2009年03月30日 06:51


zaishishi		 多核编程可用汇编语言吗？ 好像都是C,C++?
2009年06月24日 21:44

qgdbr
qgdbr总分:
25
注册用户
 谢谢谢谢~ 很有帮助~
2010年12月14日 22:02


刘阳		 有JBOSS高手能讲JBOSS内核架构培训课的吗？QQ:174629429

 引用 (19)


 写评论  

欲获得技术支持，请访问软件支持页面.
姓名 (必填)*

电子邮件 (必填，不在本页面显示)*

您的 URL (可选)


评论*