基于多核处理器的有锁编程与非阻塞算法研究

王文义,王兴启

(中原工学院,郑州 450007)

基于多核处理器的有锁编程与非阻塞算法研究

王文义,王兴启

(中原工学院,郑州 450007)

对在多核环境下的锁的使用以及因硬件发展所带来的无锁编程模式进行了研究.

多核处理器;锁竞争;非阻塞算法;并行程序设计

并发事件与并行处理技术历来是诸如气象、材料、核物理、地质勘探和航空航天等许多重要应用领域中的核心工作.经过长期的研究与积累,传统的并行程序设计方法已日趋成熟并已普遍被人们所接受[1].但当今多核处理器(Chip M ultiProcesso r,CM P)的出现却对这些传统方法提出了严峻挑战,使这些算法要么失效,要么可用性大为降低.单核处理器由于受限于自身条件,其性能已达到极限,而多核处理器却能够以更低的频率(低功耗)去处理更高的工作负载,既提高了处理器性能,又大幅降低了功耗,这恰恰是当今所谓的绿色计算 GC(Green Computing)对计算机提出的目标要求.问题是:在尽最大可能承袭传统方法的同时(无人希望耗资巨大开发出的并行应用程序因硬件的更新而报废),我们如何能够尽快找到可行的与多核技术相配的并行编程模式.

Am dahl将程序分为可加速与不可加速两大部分[2].程序的加速比是同一个任务在单处理器系统和并行处理器系统中运行消耗的时间的比率,用它来衡量并行系统或程序并行化的性能和效果.加速比为:

式中:p为不可加速部分所占的比例;n为处理器的个数.

由公式(1)可知,当 n→∞时,S(n)=1/p,所以加速比的极限值为1/p,与处理器的个数无关.就此而言,似乎多核处理器对提高加速比的前景并不被看好.

Gustafson定律提出了不同的假设,用以证明加速系数可以超越Amdahl的限制.Gustafson认为可以把软件中的串行部分 p视为是固定的,并假设在单处理器上执行 p所需要的时间为t,则在多核处理器上执行时间为tm=pt+(1-p)t/n,所以加速比[2]为:

由公式(2)可知,因为串行部分 p不变,所以加速比S(n)将随着 n的增加而增加.倘若现实情况的确与Gustafson的上述假设吻合的话,那么软件的性能可以随着处理器个数的增加而增加.运用Amdahl与Gustafson所提出的两公式所得到的加速比差异如此之大,那么到底用哪一个更接近实际呢?

实际上在多核程序中,串行部分所占的比例并非是一成不变的,而加锁保护导致的串行化便是其中重要的组成部分.在并行程序中,通过一定的算法,任务被划分成多个子任务,以便在各个节点上运行.但对于各个节点来说,锁的使用使程序只能在一个核上运行,于是失去了多核的意义.通常处理器的个数越多,任务数量越大,加锁保护所带来的串行化就越严重.本文侧重从锁竞争问题入手,对程序加锁问题进行分析,并对可用于多核环境中的并行编程模式进行探讨.

1 锁竞争导致的串行化

在双核系统中,假如有2个线程A、B要使用同一把锁,那么当线程A获取锁后,在A未解锁前线程B将处于阻塞状态,这时只有线程A在运行,2个CPU核中将只有一个得到利用,而另一个核则处于空闲状态.这里只是2个线程的情况,实际上在多核处理器中会有很多线程[3-4],如果这些线程都去竞争同一把锁,则会使问题的复杂度大为增加.拟考虑使用3种方法来解决这个问题.

1.1 复制独占访问资源

要避免锁竞争,最好的方法就是对资源进行复制,让每个线程都拥有一个私有的副本,让线程对独占资源的访问变成对自己副本的访问.如果需要的话,在程序最后可以将这些副本合并成一个单一的共享资源副本.例如,如果独占资源是一个计数器,就可以让每个线程都有一个私有的计数器,最后如果需要计算计数值总和,就可以在所有线程都完成计数以后,再将各私有计数器的结果累加起来.

1.2 有锁编程——竞争多把锁

如果某个资源上的锁无法消除,就可以考虑将资源划分成若干个部分,然后用彼此独立的锁分别给予保护.通过这种方法可以将一个数据结构或散列表划分成多个子结构或子表,将原来对整个结构或表的竞争转变为竞争多个子锁.如图1所示,在对一棵树进行访问时,若有2个线程需要访问,传统的方法是线程1在执行时,首先获得访问的锁,然后才能进行访问,当访问结束的时候,就释放锁,然后再进行线程2访问.可以把整个树分成3个锁,即对根节点下的3个节点分别上锁,而对整个树则不加锁,这样如果线程1在对子树节点1进行访问的时候,而线程2则可以对其余2节点进行访问,于是就可以实现线程的并行,从而大大减少访问的时间.

图1 将树的访问化为对子结构的访问以化解竞争

竞争多把锁又称为分布式锁竞争,相关的设计模式有2种:多核编程中的线程分组竞争模式和线程随机竞争模式 .

(1)线程分组竞争模式.如图2所示,有2个线程需要执行.在线程执行中,对同一线程不能同时执行添加和删除动作.图2中的4个线程动作分成2组执行:添加线程1(或删除线程1)和添加线程2(或删除线程2)之间不存在锁竞争,可以并行执行.这只是2组线程的分组竞争.在n个CPU核的情况下,如果将线程组数控制在≥n的时候,则至少在同一时间有 n个线程在执行.这样就可以保证CPU不会产生闲置现象.

图2 线程分组竞争示意图

(2)线程随机竞争模式.分组竞争模式虽然能避免锁的竞争,但并不是任意的共享数据都能够采用这种模式,比如在数据结构和图中,对于不同的子结构或子图来说,分组竞争模式虽然可以有效避免锁的竞争,但是对于同一个子结构或子图,如果查找的数据恰好位于同一个子结构或子图中,则锁竞争仍不可避免.

在这种分布式数据结构的随机锁竞争中,需要掌握的是在一个有 k个CPU核的机器上,线程数 m和划分的子数据结构个数n究竟为多少时,才能保证至少有k个线程在并行运行时的概率不低于给定的概率P.在通常情况下,n越大,各子任务出现竞争的概率就越小,而运行的线程数量就越多,所以可以设n≥m.在实际情况中,n并不是越大越好,因为当 n过大时,由于锁的数量和 n相等,它会占用过多的系统资源,而这是我们所不希望的.

在计算至少有k个线程在同时(并行)运行的概率P的时候,如果发生锁竞争,则对于同一个子数据结构来说,至少在同一时刻有2个线程需要访问它.这时就至少有k个不同的子数据结构被所有的m个线程访问.假设访问每个子数据结构的线程数为 Xi(0≤Xi≤m,i∈{1,2,…,n}),则有整数方程:

要保证至少有k个线程在竞争,就要保证上述方程中至少有k个大于0的解,则能保证至少有 k个线程在并行运行.

方程(3)的解的总个数为 Cn-1m+n-1,方程至少有 k个线程在运行的概率为故概率

通过前面的分析可知,子数据结构越多,则线程对于同一个子数据结构竞争的概率就越小.当然,CPU的核数越多,可同时并行处理的子数据结构也就越多,故线程竞争同一把锁的概率也就越小.例如:

当 k=2,m=4,n=4时,则 P=0.886;

当k=4,m=4,n=4时,则 P=0.03;

……

由数据可知:在CPU的核数固定且子数据结构相同的情况下,线程数 m越大,则线程竞争同一把锁的概率也就越大.

1.3 非阻塞算法

锁竞争导致了程序的串行化,那么能不能不使用锁呢?不使用锁的算法称为非阻塞算法(nonblocking),也叫无锁编程模式.多数非阻塞算法都包含一个循环,该循环试图执行由一个或多个由比较并交换(Compare-and-sw ap,CAS)操作组成的动作,如果某次CAS操作失败,就重新执行整个动作.例如,若要对一指定的变量m进行加1操作,则其有锁代码如下:

这种算法,避免了锁的使用,同时也就消除了竞争,线程可以持续执行.

2 锁与无锁编程分析

对于复制独占访问资源这种方法来说,如果任务可以拆分的话,这无疑是一种很好的方法.这种方法比较简单而且易于理解.然而现实中的许多问题并不能通过简单的拆分来解决.所以不得不使用有锁编程和非阻塞算法2种方法[7—8].对于前者而言,由于以前的程序都基于单核,程序员对于锁的使用比较容易,同时这种编程难度比较小,易于理解和掌握.但由于无锁编程是发生在线程挂起的情况下,其他线程并没有受到影响,这无疑可以加快程序的运行.而在有锁编程中,一旦持有该锁的线程被挂起,其他线程将被阻塞.如果锁的获得是按照先来先服务的顺序,那么这种情况将会更加糟糕,因为一旦前面的一个线程被挂起,那么后面等待获取该锁的线程都将被阻塞,如图3所示.

图3 锁竞争引起的线程阻塞

在无锁编程中,由于使用了串行化的原子操作,所以单从执行效率上来说它可以被视为是一种速度更快的锁.这种方法相对于等价的有锁算法来说要复杂的多,往往还需要考虑更多额外的因素.例如,在线程的安全载入操作(fetch-and-op)中,假如要读取一个数(存储单元为 m),并对它进行计算,最后存储该值.代码如下:

由此可以看出,从代码行数量上来说,无锁编程较之于单线程编程,程序量显然是增加了,同时,它还增加了计算量,而且计算要遵从阿姆尔达定律,因此其加速比性能会随着CPU核数的增加而降低[9].特别地,若在m_old=m和InterlockedCompareExchange之间有另一处理器要对其进行fetch-and-op操作,若原处理器读到的m的初值为A,而另一处理器先将其修改为B,然后又改回A.此时原处理器在执行的时候,它所看到的m值并没有发生变化,尽管对此我们可以采用内存垃圾回收机制来解决,但这却加大了程序出错的风险.

3 结 语

与单核计算机相比,多核计算机能够以较低的频率和能耗去处理更多的任务,但它的出现却也带来了诸多新的问题,因为它使得系统变得更加复杂,同时也使编程难度大为增加.本文主要从多核环境所带来的编程模式问题入手,侧重对多核环境下因锁的使用所带来的程序串行化问题进行了深入分析,希望所述问题能对从事多核编程的读者有所启发.

[1] Hwang Kai.高等计算机系统结构——并行性、可扩展性、可编程性[M].王鼎兴,译.北京:清华大学出版社,1995.

[2] 周伟明.多核计算与程序设计[M].武汉:华中科技出版社,2009.

[3] 李宝峰,富弘毅,李韬译.多核程序设计技术——通过软件多线程提升性能[M].北京:电子工业出版社,2007.

[4] 汤彬,李培耀.Window s下多线程编程技术[J].上海工程技术大学学报,2002,16(4):320-328.

[5] 伊君翰.基于多核处理器的并行编程模型[J].计算机工程,2009,35(8):62-65.

[6] 武华北,孙济洲,王文义.面向混合并行计算系统编程环境的研究与实现[J].计算机科学,2010(4):143-145.

[7] Rajwar R,Goodman J.Transactional Lock-free execution of Lock-based Program s[C]//Proc.10thInt.Conf.A rchitectural Support fo r Programming Languages and Operating System s.San Jose,California:ACM p ress,2002:5-17.

[8] Philippas Hang Y.Integrating Non-blocking Synchronisation in Parallel App lications:Perfo rmance Advantages and Methodologics[C]//.Proc.Of the 3rdACM Wo rkshop on Software and Perfo rmance.San Jose,California:ACM Press,2002:55-67.

[9] Shameem A,Jason R.多核程序设计技术——通过软件多线程提升性能[M].北京:电子工业出版社,2007.

Study of the Lock’s Programm ing and Non-lock Algorithm Based on M ulti-core Processors

WANGWen-yi,WANG Xing-qi
(Zhongyuan U niversity of Technology,Zhengzhou 450007,China)

This paper focused on the use of the lock in the M ulti-core environment and the non-lock p rogramming mode w hich caused by the development of hardware.

multi-co re p rocesso r;lock competition;non-block algo rithm;parallel p rogramm ing

TP301

A DO I:10.3969/j.issn.1671-6906.2010.04.004

1671-6906(2010)04-0015-04

2010-07-13

河南省基础与前沿技术研究项目(082300410300)

王文义(1947-),男,河南洛阳人,教授.