多核编程中的任务分组竞争模式

 

在多核编程中，锁竞争导致的CPU饥饿现象是引起多核CPU性能无法发挥的最重要原因之一，在 多核编程中的锁竞争难题一文中已经讲过锁竞争对性能的影响，如何消解锁竞争导致的CPU饥饿现象成了迫切需要解决的问题。

目前业界发展的无锁编程技术可以有效降低锁竞争引起的性能下降问题，无锁编程主要是采用原子操作来替代锁，只存在原子操作串行化问题，由于原子操作只是一条指令，速度非常快，因此可以近似地看成是无锁竞争的，除非原子操作非常频繁。无锁编程难度非常高，从目前的情况来看，普通程序员要亲自进行无锁编程是不现实的事情。并且目前只有少数数据结构可以实现无锁编程，从目前商用的无锁编程库NOBLE来看，只提供了队列、栈、链表、词典、带引用计数的垃圾回收内存管理等少数几种无锁编程结构，只能解决部分锁竞争问题，这个库的售价高昂，以下是从NOBLE的网站上拷贝下来的售价。
$1395 USD, NOBLE Professional Edition, Evaluation License 1 Months, Windows
$3295 USD, NOBLE Professional Edition, Evaluation License 3 Months, Windows

看了这个售价，估计国内也没有多少公司愿意出这么高昂的价钱的购买这个一个功能有限，且使用起来不像以前的使用锁的库那么方便的库。

既然没有无锁编程的免费午餐可以享用，那么使用锁来编程的话，可不可以避免锁竞争导致的CPU饥饿现象呢？答案是可以的，这就是文章标题中的任务分组竞争模式，它使用锁来进行保护共享数据，但是又避免了锁竞争时出现CPU饥饿现象。其实这个模式在业界已经有了很成功的实践，那就是队列池。当然这个模式的应用不仅仅限于队列池，也可以用到很多其他的满足一定条件的共享数据保护上。

先看一下任务分组竞争模式的基本思想，所谓任务分组竞争就是将任务分成若干个组，每个组的任务间存在锁竞争，但是不同组之间的任务不存在锁竞争。下图以添加操作和删除操作作为示例来显示2个分组任务竞争的情况：

 

图中显示了两个分组的任务竞争情况，共有四个任务分成两组进行竞争，添加操作任务1和删除操作任务1之间存在锁竞争情况，添加操作任务2和删除操作任务2之间存在锁竞争情况，但是添加操作任务1（或删除操作任务1）和添加操作任务2和删除操作任务2之间不存在锁竞争。

在这种分组锁竞争模式下，任意一组任务中，至少有一个任务在执行，因此如果有N组任务的话，那么至少有N个任务在执行，如果N大于等于CPU的核数，那么任意一个CPU      核上都有任务一直在运行，可以充分保证CPU不会产生饥饿现象。

 

并不是任意共享数据都可以采用任务分组竞争的形式来进行访问，共享数据必须可以分成若干个独立的子数据，每次操作只需要操作某个子数据，一次操作中不需要操作多个子数据。

任务分组竞争模式和无锁编程相比，有着很大的优势，最重要的优势有两点：

一、使用有锁编程，编程难度很小，易于为普通程序员掌握。

二、并发性比无锁编程更好，无锁编程中存在原子操作竞争问题，其竞争激烈程度会随CPU核数增加而增加，特别是当原子操作包含在大循环中时，原子操作竞争最坏情况下会使性能降到和单核CPU一样。而任务分组模式中各个CPU核完全是并行运行的，CPU核相互间不存在竞争问题，因此CPU核数增加不会造成任何影响。

以上讲的是任务分组竞争模式的一种情况，实际情况中很多情况和这种模式并不完全符合，因此任务分组模式存在一些变种以适应更多的实际情况。下图便是一个最常见的变种：

如上图所示，在这个变种中添加操作任务只有一个，而删除操作任务却有两个，添加操作任务A如果操作子内存区域1，则使用lock1，操作子内存区域2时则使用lock2。添加操作任务A可以和删除操作任务1和删除操作任务2存在锁竞争，但是删除操作任务1和删除操作任务2之间不存在锁竞争。从运行情况来看，3个任务中至少有2个在同时运行，如果有N个子内存区域和N个删除操作任务的话，那么至少有N个任务在同时运行，因此这种锁竞争模式中，同样可以保证当CPU核数少于等于任务分组的个数时，不会发生CPU饥饿现象。队列池便是这种模式的一个很好的成功实践。

任务分组竞争模式是消除锁竞争造成多核CPU性能下降的最有效方式，它的性能近似于单核CPU中的多任务编程的性能，这种模式也是设计本地分布式数据结构的一种有效方法。

参考资料：

[1]《并行编程模式》Timothy Mattson等著 敖富江译

[2]《多核程序设计技术》Shameem Akhter等著 李宝峰等译

[3]《并行程序设计》 Barry Wilkinson, Michael Allen著，陆鑫达等译

[4] “ NOBLE: A Non-Blocking Inter-Process Communication Library. ”  H. S UNDELL , P. T SIGAS . Proceedings ofthe 6th Workshop on Languages, Compilers and Runtime Systems for Scalable omputers (LCR’02), Lecture Notes in Computer Science, Springer Verlag, 2002.

[5] http://www.nobel.org/