线程清理手机内存垃圾

多核编程入门作者:chengjia4574@gmail.
comsinaweibo:jiayy时间:2012-8-8说明:本文是多核编程的入门资料汇总,来源主要是国外国内的一些网站及自己使用过程中一些记录,写作目的主要是内部分享用(@NSFOCUS).
在多核使用过程中,得益于很多网络资源,所以也把自己整理的产品无关的东西共享出来,希望对多核感兴趣的同学可以入门用.
目录一.
并发与并行的区别11.
1串行.
11.
2并发.
11.
3并行.
11.
4多核编程的难点.
2二.
多核体系架构.
32.
1多核处理器定义.
32.
2多核发展趋势.
32.
3一个多核处理器架构例子.
52.
4LINUX线程核绑定.
62.
4.
1核亲和性绑定62.
4.
2资源控制cgroup.
8三.
内存模型.
83.
1操作原子性.
93.
1.
1原子性的3种保证机制93.
1.
2硬件原子操作93.
1.
3总线锁-原子操作原语123.
2缓存一致性.
163.
2.
1定义163.
2.
2CC协议.
173.
2.
3伪共享213.
3顺序一致性.
243.
3.
1定义243.
3.
2几种顺序约束253.
3.
3乱序执行和内存屏障28四.
并发级别.
314.
1WAIT-FREEDOM无等待并发.
324.
2LOCK-FREEDOM无锁并发.
324.
3OBSTRUCTION-FREEDOM无阻塞并发334.
4BLOCKINGALGOITHMS阻塞并发.
33五.
锁345.
1信号量.
345.
2自旋锁.
355.
3读写锁.
355.
4顺序锁.
375.
5RCU.
38六.
无锁编程.
386.
1定义.
39七.
并发数据结构、开源库.
417.
1一些开源的并发库.
417.
2一次无锁哈希表跟基于锁的哈希表性能对比测试417.
2.
1测试平台417.
2.
2测试过程427.
2.
3哈希算法437.
2.
4测试结果44八.
多核工程实践.
448.
1网络设备:INTELDPDK.
448.
2网络游戏.
448.
3手机开发.
45九.
参考45表格索引表3.
1CC示意图24表3.
2CC示意图224插图索引图1.
1并发和并行的区别.
2图2.
1PC和手机核心增长趋势图.
4图2.
2最新的MACPRO已经配备12个核心4图2.
3三星推出了8核心的手机处理器.
4图2.
4共享缓存多核处理器体系架构图实例.
5图2.
5处理器各组件功能说明.
5图2.
6共享缓存多核处理器架构缓存示意图.
6图3.
1DPDK,CAS实现代码.
14图3.
2DPDK:原子ADD实现代码15图3.
3DPDK:原子自增实现代码.
15图3.
4MESI协议17图3.
5MOESI状态机.
18图3.
6CC协议示例代码18图3.
7初始状态.
19图3.
8X已经写入缓存.
20图3.
9X增加了10010.
20图3.
10CORE1从CORE0的缓存里读走数据21图3.
11伪共享.
22图3.
12缓存行伪共享.
23图3.
13缓存行填充.
23图3.
14一些体系架构的内存顺序标准.
27图3.
15强内存顺序模型和弱内存顺序模型一些例子.
27图3.
16编译乱序和运行乱序.
28图3.
17乱序执行.
30图3.
18内存屏障.
31图4.
1几种并发级别的对比.
34图5.
1读写锁.
35图5.
2申请读锁.
36图5.
3释放读锁.
36图5.
4申请写锁.
37图5.
5释放写锁.
37图6.
1什么是无锁编程.
39图6.
2无锁编程涉及的技术.
40图7.
1INTELE5-265842图7.
2E5-2658核分布42一.
并发与并行的区别首先了解几个概念:1.
1串行最基本的程序执行方式,串行程序的整个运行时,只有一个调用栈和一个运行时上下文.

单进程/单线程程序可以认为是串行程序.
1.
2并发多线程出现后比较常见的程序执行方式,多线程程序运行时,会有多个运行时上下文和对应的多个调用栈.
逻辑上多个线程同时发生,物理上是由操作系统调度,CPU某一时刻依然只执行一个线程的任务,但是某个执行中的线程随时可能被OS调度走,而随后运行的线程操作的数据可能跟刚刚被调度走的线程造成冲突,所以有共享数据同步问题.

多进程如果有共享数据,也符合并发程序的特点.
相对于多线程并发,多进程并发解耦更彻底,数据分割更清晰.
另外,前述并发情况是从用户程序的角度,从内核的角度,还会有其他类似的场景,比如中断.
中断处理程序和中断之前执行的程序也有可能有共享数据冲突的问题.

1.
3并行多核处理器出现后会越来越常见的程序执行方式,物理上多个任务可以同时运行,这个概念介于操作系统和体系架构之间,从操作系统而言,依然是调度多个线程/进程去CPU执行,只不过有了多个CPU/核心,不同线程/进程可以绑定从而完全占用一颗核心,所以从体系架构的角度,同一时刻是有多个任务同时运行,另外一些说法,如'多处理器程序''多核程序'都可以认为属于并行程序的范畴.
从概念的范围看,并行voidsetProcessToCPU(int_cpuID){cpu_set_tmask;cpu_set_tget;CPU_ZERO(&mask);CPU_SET(_cpuID,&mask);if(sched_setaffinity(0,sizeof(mask),&mask)#includevoidsetThreadToCPU(int_cpuID){cpu_set_tmask;cpu_set_tget;CPU_ZERO(&mask);CPU_SET(_cpuID,&mask);if(pthread_setaffinity_np(pthread_self(),sizeof(mask),&mask)cnt这块内存进行加1操作图3.
3Dpdk:原子自增实现代码3.
1.
3.
5各个平台的原子操作原语各个平台或者语言都推出了自己的原子操作原语实现,使用的时候可以直接调用相关APIWindowshttp://msdn.
microsoft.
com/en-us/library/ms684122(v=VS.
85).
aspxGNUhttp://gcc.
gnu.
org/onlinedocs/gcc-4.
1.
2/gcc/Atomic-Builtins.
htmlSolarishttp://www.
oracle.
com/technetwork/indexes/documentation/index.
htmlJavahttp://docs.
oracle.
com/javase/1.
5.
0/docs/api/java/util/concurrent/atomic/package-summary.
html.
nethttp://msdn.
microsoft.
com/en-us/library/system.
threading.
interlocked.
aspxDpdkrte_atomic.
h3.
2缓存一致性3.
2.
1定义缓存一致性Cachecoherence简称CC,缓存一致性协议是在共享缓存多处理器架构确保最终一致性最突出、最重要的机制.
这些协议在缓存线(cache-line)级别实现了对一致性的保证.
缓存线是从主内存中读取数据和向内存中写入数据的缓存单位(至少从一致性机制的角度看是这样的).
商用处理器上三个最突出最重要的缓存一致性协议—MOESI,MESI,andMESIF—的缩写都来自它们为缓存线定义的各种状态:Modified(已修改),Owned(被占用),Exclusive(独占的),Shared(共享的),Invalid(无效的),andForward(转发的).
缓存一致性协议在对内存确保最终一致性的内存一致性机制的帮助下对这些状态进行管理.

Intel奔腾:MESI协议AMDopteron:MOESI协议Inteli7:MESIF协议问题:为什么需要缓存CC答案:从第二章的[图2.
6]可以看到,一般每个核心都有一个私有的L1级和L2级Cache,同一个物理CPU上的多个核心共享一个L3级缓存,这样的设计是出于提高内存访问性能的考虑.
但是这样就有一个问题了,每个核心之间的私有L1,L2级缓存之间需要同步啊.
比如,核心1上的线程A对一个共享变量global_counter进行了加1操作,这个被写入的新值存到核心1的L1缓存里了;此时另一个核心2上的线程B要读global_counter了,但是核心2的L1缓存里的global_counter的值还是旧值,最新被写入的值现在还在核心1上.
这就需要CPU有一个模块来保证,同一个内存的数据在同一时刻对任何对其可见的核心看来,数据是一致的,由第二章[图2.
5]知道,这种专门的组件就是缓存控制器(Cbox,Bbox),其实现了缓存一致性协议.
3.
2.
2CC协议3.
2.
2.
1MESI图3.
4MESI协议详细了解参考:Cache一致性协议之MESI:http://blog.
csdn.
net/muxiqingyang/article/details/66151993.
2.
2.
2MOESI下面是基于MOESI的一个例子,展示的是共享缓存多处理器中共享读写的生命周期.
原文在这里:[http://www.
oschina.
net/translate/nonblocking-algorithms-and-scalable-multicore-programing]图3.
5MOESI状态机图3.
6CC协议示例代码这个程序非常简单,定义了一个volatile变量x,初始值是443,然后程序开始后将x的值增加10010,并启动一个线程打印x的值.
在单处理器上,这个程序是非常简单的,下面的过程显示的是两个核跑这个程序,core0跑main,core1跑thread的缓存状态机变迁过程.
图3.
7初始状态上图是两个core的l2缓存的初始状态,假设每个core有一个256字节的l2缓存,每个cacheline长度是64byte.
可以看到初始状态下,两个core的l2缓存都已经满了,缓存线处于invalid,shared,modified,exclusive等多种状态中.
假设x的地址是0x20c4,它被缓存散列函数哈希到cacheline3上,由初始状态图知道,该缓存线已经有一个数据0x00c0,对x的probewritehit到这条缓存,这时候原有缓存的内容会被写回内存,cacheline3状态变为invalid,然后x的值被写入这个cacheline,状态变成独占exclusive,图3.
8x已经写入缓存然后core0开始为x增加10010,结果保存在cacheline3里,状态如下图3.
9x增加了10010Core1跑thread函数,需要读取x的值并调用fprintf,这个载入动作会发出一个读取探测,要求从midified的状态转换为owned状态(如图5所示).
MOESI协议允许缓存到缓存的数据转移,所以core1从core0缓存里读走数据,同时core1的cacheline3变成shared状态图3.
10Core1从core0的缓存里读走数据3.
2.
2.
3MESIFIntel提出了另外一种MESI协议的变种,即MESIF协议,该协议与MOESI协议有较大的不同,也远比MOESI协议复杂,该协议由Intel的QPI(QuickPathInterconnect)技术引入,其主要目的是解决"基于点到点的全互连处理器系统"的Cache共享一致性问题,而不是"基于共享总线的处理器系统"的Cache共享一致性问题.
在基于点到点互连的NUMA(Non-UniformMemroyArchitecture)处理器系统中,包含多个子处理器系统,这些子处理器系统由多个CPU组成.
如果这个处理器系统需要进行全机Cache共享一致性,该处理器系统也被称为ccNUMA(CacheCohenrentNUMA)处理器系统.
MESIF协议主要解决ccNUMA处理器结构的Cache共享一致性问题,这种结构通常使用目录表,而不使用总线监听处理Cache的共享一致性.
关于MESIF,可以参阅陈怀临的"浅谈intelqpi的MESIF协议和home,souresnoop"http://www.
360doc.
com/content/10/1207/13/158286_75798413.
shtml3.
2.
3伪共享3.
2.
3.
1定义从上一节可以知道,缓存一致性协议操作的最小对象的缓存行,缓存行内数据的修改、写入内存、写入其他缓存等操作都会改变其状态,这样,在共享缓存多核架构里,数据结构如果组织不好,就非常容易出现多个核线程反复修改同一条缓存行的数据导致缓存行状态频繁变化从而导致严重性能问题,这就是伪共享现象.
下图就是一个伪共享的例子,core1上运行的线程想修改变量x,core2上运行的线程想修改变量y,但x和y刚好在一个缓存行上.
每个线程都要去竞争缓存行的所有权来更新变量.
如果核心1获得了所有权,缓存子系统将会使核心2中对应的缓存行失效.
当核心2获得了所有权然后执行更新操作,核心1就要使自己对应的缓存行失效.
这会来来回回的经过L3缓存,大大影响了性能.
如果互相竞争的核心位于不同的插槽,就要额外横跨插槽连接,问题可能更加严重.
图3.
11伪共享3.
2.
3.
2解决与缓存行导致性能问题的严重相比,对这个问题的解决方案显得非常简单,这就是缓存行填充,通过填充缓存行,使得某个核心线程频繁操作的数据独享缓存行,这样就不会出现伪共享问题了.
下面是一个例子.
图3.
12缓存行伪共享图3.
13缓存行填充32位机longlong是8字节,这样一个缓存行64字节可以存8个counter,这样最差的情况下同时会有8个线程争夺同一个缓存行的操作权,性能会非常低.
解决方式非常简单,如图3.
13所示,每个counter变量增加一个填充变量pad,使得一个counter变量刚好是一个缓存行大小,这样数组counters每个元素占用一个缓存行,所有线程独占自己的缓存行,避免了伪共享问题.
3.
3顺序一致性3.
3.
1定义Sequentialconsistency,简称SC,定义如下…theresultofanyexecutionisthesameasiftheoperationsofalltheprocessorswereexecutedinsomesequentialorder,andtheoperationsofeachindividualprocessorappearinthissequenceintheorderspecifiedbyitsprogram[lamport]下面用一个小例子说明这个定义的意思:假设我们有两个线程(线程1和线程2)分别运行在两个CPU上,有两个初始值为0的全局共享变量x和y,两个线程分别执行下面两条指令:初始条件:x=y=0;表3.
1CC示意图线程1线程2x=1;y=1;r1=y;r2=x;因为多线程程序是交错执行的,所以程序可能有如下几种执行顺序:表3.
2CC示意图2Execution1Execution2Execution3x=1;r1=y;y=1;r2=x;结果:r1==0andr2==1y=1;r2=x;x=1;r1=y;结果:r1==1andr2==0x=1;y=1;r1=y;r2=x;结果:r1==1andr2==1Execution1Execution2Execution3当然上面三种情况并没包括所有可能的执行顺序,但是它们已经包括所有可能出现的结果了,所以我们只举上面三个例子.
我们注意到这个程序只可能出现上面三种结果,但是不可能出现r1==0andr2==0的情况.
SC其实就是规定了两件事情:(1)每个线程内部的指令都是按照程序规定的顺序(programorder)执行的(单个线程的视角)(2)线程执行的交错顺序可以是任意的,但是所有线程所看见的整个程序的总体执行顺序都是一样的(整个程序的视角)第一点很容易理解,就是说线程1里面的两条语句一定在该线程中一定是x=1先执行,r1=y后执行.
第二点就是说线程1和线程2所看见的整个程序的执行顺序都是一样的,举例子就是假设线程1看见整个程序的执行顺序是我们上面例子中的Execution1,那么线程2看见的整个程序的执行顺序也是Execution1,不能是Execution2或者Execution3.
有一个更形象点的例子.
伸出你的双手,掌心面向你,两个手分别代表两个线程,从食指到小拇指的四根手指头分别代表每个线程要依次执行的四条指令.
SC的意思就是说:(1)对每个手来说,它的四条指令的执行顺序必须是从食指执行到小拇指(2)你两个手的八条指令(八根手指头)可以在满足(1)的条件下任意交错执行(例如可以是左1,左2,右1,右2,右3,左3,左4,右4,也可以是左1,左2,左3,左4,右1,右2,右3,右4,也可以是右1,右2,右3,左1,左2,右4,左3,左4)其实说简单点,SC就是我们最容易理解的那个多线程程序执行顺序的模型.
CC保证的是对一个地址访问的一致性,SC保证的是对一系列地址访问的一致性.
3.
3.
2几种顺序约束顺序的内存一致性模型为我们提供了一种简单的并且直观的程序模型.
但是,这种模型实际上阻止了硬件或者编译器对程序代码进行的大部分优化操作.
为此,人们提出了很多松弛的(relaxed)内存顺序模型,给予处理器权利对内存的操作进行适当的调整.
例如Alpha处理器,PowerPC处理器以及我们现在使用的x86,x64系列的处理器等等.
下面是一些内存顺序模型3.
3.
2.
1TSO(整体存储定序)数据载入间的执行顺序不可改变.
数据存储间的顺序不可改变.
数据存储同相关的它之前的数据载入间的顺序不可改变.
数据载入同其相关的它之前的数据存储的顺序可以改变.
向同一个地址存储数据具有全局性的执行顺序.
原子操作按顺序执行.
这方面的例子包括x86TSO26和SPARCTSO.
3.
3.
2.
2PSO(部分存储定序)数据载入间的执行顺序不可改变.
数据存储间的执行顺序可以改变.
数据载入同数据存储间相对顺序可以改变.
向同一个地址存储数据具有全局性的执行顺序.
原子操作同数据存储间的顺序可以改变.
这方面的例子包括SPARCPSO.
3.
3.
2.
3RMO(宽松内存定序)数据载入间的顺序可以改变.
数据载入同数据存储间的顺序可以改变.
数据存储间的顺序可以改变.
向同一个地址存储数据具有全局性的执行顺序.
原子操作同数据存储和数据载入间的顺序可以改变.
这方面的例子包括Power27和ARM.
7图3.
14一些体系架构的内存顺序标准图3.
15强内存顺序模型和弱内存顺序模型一些例子最左边的内存顺序一致性约束越弱,右边的约束是在左边的基础上加上更多的约束,X86/64算是比较强的约束.
3.
3.
3乱序执行和内存屏障任何非严格满足SC规定的内存顺序模型都产生所谓乱序执行问题,从编程人员的代码,到编译器,到CPU运行,中间可能至少需要对代码次序做三次调整,每一次调整都是为了最终执行的性能更高.
如下图图3.
16编译乱序和运行乱序在串行程序里,编译器和CPU对代码所进行的乱序执行的优化对程序员都是封装好了的,无痛的,所以程序员不需要关心这些代码在执行时被乱序成什么样子.
在并发程序里,乱序执行可能会造成程序运行结果与编程人员预期不一致,所以必须使用同步机制,类似mutex,semaphore等同步机制在实现的时候考虑了编译和执行的乱序问题,可以保证关键代码区不会被乱序执行.
另外一些编程场景,比如为了追求极致性能而自己写更高效的锁实现,或自己编写无锁程序,则会被暴露到这个问题面前.
下面通过一个例子解释乱序执行和内存屏障这两个概念.
[来源:http://preshing.
com/20120625/memory-ordering-at-compile-time]示例代码:intA,B;voidfoo(){A=B+1;B=0;}普通编译选项:$gcc-S-masm=intelfoo.
c$catfoo.
s.
.
.
moveax,DWORDPTR_B(redothisathome.
.
.
)addeax,1movDWORDPTR_A,eaxmovDWORDPTR_B,0加上-o2优化编译选项,可以看到,B的赋值操作顺序变了$gcc-O2-S-masm=intelfoo.
c$catfoo.
s.
.
.
moveax,DWORDPTRBmovDWORDPTRB,0addeax,1movDWORDPTRA,eax.
.
.
上述情况在某些场景下导致的后果是不可接受的,比如下面这段伪代码中,生产者线程执行于一个专门的处理器之上,它先生成一条消息,然后通过更新ready的值,向执行在另外一个处理器之上的消费者线程发送信号,由于乱序执行,这段代码在目前大部分平台上执行是有问题的:处理器有可能会在将数据存储到message->value的动作执行完成之前和/或其它处理器能够看到message->value的值之前,执行consume函数对消息进行接收或者执行将数据保存到ready的动作.
图3.
17乱序执行回到之前的例子,加上一句内存屏障命令intA,B;voidfoo(){A=B+1;asmvolatile(memory");B=0;}依然采用o2优化编译选项,发现这次B的赋值操作顺序没有变化$gcc-O2-S-masm=intelfoo.
c$catfoo.
s.
.
.
moveax,DWORDPTR_Baddeax,1movDWORDPTR_A,eaxmovDWORDPTR_B,0.
.
.
在内存顺序一致性模型不够强的多核平台上,例子2的正确实现应该是下面这种,需要加上两个内存屏障语句.
图3.
18内存屏障X86的内存屏障#definebarrier()__asm____volatile_memory")更多X86内存屏障请参考:http://blog.
csdn.
net/cnctloveyu/article/details/5486339四.
并发级别往往一个并发算法会说自己是wait-free的或者lock-free的,或者是non-blocking的,这些专有词汇其实表示的是并发的程度,或者说并发的级别.
并发级别的理解是阅读各种并发算法设计论文以及并发数据结构实现的必备基础.
4.
1Wait-freedom无等待并发Wait-freedom指的是每一个线程都一直运行下去而无须等待外部条件,整个流程中任何操作都能在一个有限的步骤内完成,这是最高的并发级别,没有任何阻塞.
结合上面原子操作部分的知识,可以简单认为能够直接调用一个原子操作实现的算法或程序就属于Wait-free,比如下面的increment_reference_counter函数就是wait-free的,它封装了atomic_increment这个原子自增原语,多个线程可以同时调用这个函数对同一个内存变量进行自增,而无须任何阻塞(其实也是有阻塞的,是总线锁级别)与此做对比,CAS类的调用就不是wait-free的,注意wait-free的原语都不能包含内部循环,而CAS原语使用时通常包含在"循环直到成功"的循环内部.
voidincrement_reference_counter(rc_base*obj){atomic_increment(obj->rc);}4.
2Lock-freedom无锁并发Lock-freedom指的是整个系统作为一个整体一直运行下去,系统内部单个线程某段时间内可能会饥饿,这是比wait-freedom弱的并发级别,但系统整体上看依然是没有阻塞的.
所有wait-free的算法显然都满足lock-free的要求.
Lock-free算法通常可以通过同步原语CAS实现.
voidstack_push(stack*s,node*n){node*head;do{head=s->head;n->next=head;}while(!
atomic_compare_exchange(s->head,head,n));}多个线程同时调用上述函数,理论上某个线程可以一直困在循环内部,但一旦有一个线程原子操作失败而返回循环,意味着有其他线程成功执行了原子操作而退出循环,从而保证系统整体是没有阻塞的.
其实6.
1的函数也可以用下面的原语实现,在这种实现里,不再是所有线程都无阻塞了,某些线程可能会因为CAS失败而回绕若干次循环.
voidincrement_reference_counter(rc_base*obj){Intrc;Do{rc=obj->rc;}while(!
atomic_compare_exchange(obj->rc,rc,rc+1));}4.
3Obstruction-freedom无阻塞并发Obstruction-free是指在任何时间点,一个孤立运行线程的每一个操作可以在有限步之内结束.

只要没有竞争,线程就可以持续运行,一旦共享数据被修改,Obstruction-free要求中止已经完成的部分操作,并进行回滚,obstruction-free是并发级别更低的非阻塞并发,该算法在不出现冲突性操作的情况下提供单线程式的执行进度保证,所有Lock-Free的算法都是Obstruction-free的.
4.
4Blockingalgoithms阻塞并发阻塞类的算法是并发级别最低的同步算法,它一般需要产生阻塞.
可以简单认为基于锁的实现是blocking的算法.
详细参考第五章上述几种并发级别可以使用下图描述:图4.
1几种并发级别的对比蓝色是阻塞的算法,绿色是非阻塞算法,金字塔越上方,并发级别越高,性能越好,右边的金字塔是实现工具(原子操作、锁、互斥体等)五.
锁锁的概念是承接原子操作的,根本目的都是为了并发保护,只不过抽象的层次更高,多核环境下的锁的实现要依赖于第三章的理论基础.
下面是几种常见的锁机制的简介,其中给出了读写锁的具体实现(来自DPDK),其他锁的具体实现可以参考linux内核代码5.
1信号量Linux中的信号量是一种睡眠锁.
如果有一个任务试图获得一个已被持有的信号量时,信号量会将其推入等待队列,然后让其睡眠.
这时处理器获得自由去执行其它代码.
当持有信号量的进程将信号量释放后,在等待队列中的一个任务将被唤醒,从而便可以获得这个信号量.
信号量的睡眠特性,使得信号量适用于锁会被长时间持有的情况;只能在进程上下文中使用,因为中断上下文中是不能被调度的;另外当代码持有信号量时,不可以再持有自旋锁.

5.
2自旋锁自旋锁最多只能被一个可执行线程持有,如果一个执行线程试图请求一个已被争用(已经被持有)的自旋锁,那么这个线程就会一直进行忙循环——旋转——等待锁重新可用.
要是锁未被争用,请求它的执行线程便能立刻得到它并且继续进行.
自旋锁可以在任何时刻防止多于一个的执行线程同时进入临界区.
事实上,自旋锁的初衷就是:在短期间内进行轻量级的锁定.
一个被争用的自旋锁使得请求它的线程在等待锁重新可用期间进行自旋(特别浪费处理器时间),所以自旋锁不应该被持有时间过长.
另外自旋锁不允许任务睡眠(持有自旋锁的任务睡眠会造成自死锁),它能够在中断上下文中使用.
5.
3读写锁读写锁实际是一种特殊的自旋锁,它把对共享资源的访问者划分成读者和写者,读者只对共享资源进行读访问,写者则需要对共享资源进行写操作.
这种锁相对于自旋锁而言,能提高并发性,因为在多处理器系统中,它允许同时有多个读者来访问共享资源,最大可能的读者数为实际的逻辑CPU数.
写者是排他性的,一个读写锁同时只能有一个写者或多个读者(与CPU数相关),但不能同时既有读者又有写者.
在读写锁保持期间也是抢占失效的.
如果读写锁当前没有读者,也没有写者,那么写者可以立刻获得读写锁,否则它必须自旋在那里,直到没有任何写者或读者.
如果读写锁没有写者,那么读者可以立即获得该读写锁,否则读者必须自旋在那里,直到写者释放该读写锁.
DPDK里有一个读写锁的实现图5.
1读写锁这把锁的核心是一个volatileint32的变量,这个变量值为-1的时候表示处于写锁状态,值大于0表示处于读锁状态.
图5.
2申请读锁通过原子CAS操作实现读锁获取,多个线程可以同时调用这个函数获取读锁,同时也可能有其他线程在申请写锁,如果这时锁处于写锁持有状态,x<0,则所有申请读锁的线程会循环等待,可见这是一种特殊的自旋锁.
否则说明锁处于读锁状态或0状态,可以进入CAS操作尝试申请,每个想持有的线程原子地为变量cnt加1,成功了就相当于获取了读锁,否则说明其他线程获取了,这里的其他线程既有可能是其他申请读锁的线程,也有可能是申请写锁的线程(x一开始为0时),所以CAS失败后需要重新判断x是否小于0,然后再调用CAS申请图5.
3释放读锁释放读锁的操作没有使用原子原语,而是通过总线锁和指令decl实现为cnt减1操作,也可以调用atomic_dec为cnt做原子减1操作图5.
4申请写锁写锁的申请跟读锁申请类似,如果x不为0,说明还有线程持有读锁,则循环等待,等全部持有的读锁都释放了,x变回0,这时通过CAS操作为x赋值-1,成功则申请了一把写锁.
图5.
5释放写锁写锁的释放跟读锁释放相反,写锁释放是atomic_inc的操作,inc加1后又变回05.
4顺序锁顺序锁也是对读写锁的一种优化,对于顺序锁,读者绝不会被写者阻塞,也就说,读者可以在写者对被顺序锁保护的共享资源进行写操作时仍然可以继续读,而不必等待写者完成写操作,写者也不需要等待所有读者完成读操作才去进行写操作.
但是,写者与写者之间仍然是互斥的,即如果有写者在进行写操作,其他写者必须自旋在那里,直到写者释放了顺序锁.

这种锁有一个限制,它必须要求被保护的共享资源不含有指针,因为写者可能使得指针失效,但读者如果正要访问该指针,将导致OOPs.
如果读者在读操作期间,写者已经发生了写操作,那么,读者必须重新读取数据,以便确保得到的数据是完整的.
这种锁对于读写同时进行的概率比较小的情况,性能是非常好的,而且它允许读写同时进行,因而更大地提高了并发性.
5.
5RCURCU(Read-CopyUpdate),顾名思义就是读-拷贝修改,它是基于其原理命名的.
对于被RCU保护的共享数据结构,读者不需要获得任何锁就可以访问它,但写者在访问它时首先拷贝一个副本,然后对副本进行修改,最后使用一个回调(callback)机制在适当的时机把指向原来数据的指针重新指向新的被修改的数据.
这个时机就是所有引用该数据的CPU都退出对共享数据的操作.
RCU也是读写锁的高性能版本,但是它比大读者锁具有更好的扩展性和性能.

RCU既允许多个读者同时访问被保护的数据,又允许多个读者和多个写者同时访问被保护的数据(注意:是否可以有多个写者并行访问取决于写者之间使用的同步机制),读者没有任何同步开销,而写者的同步开销则取决于使用的写者间同步机制.
但RCU不能替代读写锁,因为如果写比较多时,对读者的性能提高不能弥补写者导致的损失.
六.
无锁编程前面简单介绍了锁,这章简单介绍一下无锁编程.
有一个观念需要先了解:虽然无锁编程对于多核编程作用有限,但是它对于理解多线程编程的许多深层次问题还是有很好的借鉴作用.
前半句的意思是说无锁编程的难度导致只能有极少一部分人能真正利用这种技术做出东西,其他人只能等待这部分人的成果,后半句的意思是即便你成为不了前面这些人,但稍微了解一下他们做的东西,可以大大帮助你理解多核编程的很多概念.
6.
1定义图6.
1什么是无锁编程基本的概念与第四章,并发级别是一致的,就是多线程程序里,不需要依赖于锁这样的阻塞机制就可以保证同步的编程技术.
图6.
2无锁编程涉及的技术从上图可以看到,如果要自己编写无锁程序,基本上要掌握前面几章涉及的所有概念.
是一个非常艰巨的工程.
七.
并发数据结构、开源库7.
1一些开源的并发库http://openmp.
org/wp/openmp开放标准的并行程序指导性注释,没用过http://software.
intel.
com/zh-cn/articles/parallelization-using-intel-threading-building-blocks-intel-tbbinteltbb,Intel的C++多线程库,没有用过,有人说性能很不好https://code.
google.
com/p/nbds/无锁数据结构库,关键是针对缓存做了优化,需要注意的是里边的哈希表是没有删除的,说多了都是泪http://mcg.
cs.
tau.
ac.
il/projects/hopscotch-hashing-1并发的hopscotch哈希表实现da-data.
blogspot.
nl/2013/03/optimistic-cukoo-hashing-for.
html并发的cukoo实现,查找非常快,但增加和删除目前是大锁,作者说以后会推出无锁的增加和删除,不知道什么时候出来http://ww2.
cs.
mu.
oz.
au/~astivala/paralleldp/实现了无锁的基于数组的哈希表,无锁的基于链表的哈希表,对比了多种实现的性能,无锁实现仍然是没有删除,另外,无锁实现没有针对缓存做优化http://dpdk.
org/rte_ring.
c实现了无锁的生产者消费者队列另外,据说apacheprotableruntime里边有很多lock-free算法,Windows里的Interlocked系列函数内部实现也用到了很多lock-free算法,没有验证过.
上述代码里,详细调试过的有nbds的无锁hashtable,用它构造了一个哈希表作为流表,与基于DPDKexample的一种哈希表+dpdkrwlock的实现做L3转发性能对比,发现不删流的情况下性能差不多,当然测试是在冲突率不是很高的情况下测试的.
7.
2一次无锁哈希表跟基于锁的哈希表性能对比测试7.
2.
1测试平台测试在一台intelE5-2658上进行,这款CPU有两个物理CPU,每个物理CPU有8个核,每个核有两个核线程.
测试只使用到一颗物理CPU,只用到core1~core8图7.
1Intele5-2658图7.
2E5-2658核分布发包和统计工具是testcenter发包仪器,使用两块万兆网卡对发udp包.
7.
2.
2测试过程1)DPDK示例程序examples里有l2fwd示例程序,测试程序在l2fwd的基础上改写.
如图,l2fwd只有收包和发包两个步骤,测试程序增加了解码和查表(增加节点、拷贝mac)的操作.
3)测试时,固定2个core线程负责两个网卡的收包和发包,中间的解码+会话表处理灵活配置核心,测试对比了2个,4个,6个核线程的情况4)哈希表部分API使用函数指针做了一个抽象层(lookup,insert,delete),具体实现替换为不同的哈希表实现7.
2.
3哈希算法1)第一种哈希使用DPDKlibrte_hash/rte_fbk_hash.
c增加rte_rwlock实现,在原有哈希算法基础上,每个bucket增加一个rwlock,lookup的时候需要获取读锁,返回前释放.
Insert需要先获取写锁,然后lookup一遍没有相同值再插入,返回前释放写锁,delete也需要获取写锁.
2)第二种哈希使用nbds的hashtable.
c实现,在原有哈希算法基础上,将key,value的真实值替换为DPDK的mempool实现,将所有内存的申请替换为DPDK的rte_malloc实现.
7.
2.
4测试结果3)简单测试发现,随着中间工作核线程数目增加,性能有明显提升4)多次反复测试发现,两种哈希实现性能相差不大.
5)Nbds没有实现真正的delete算法,研究中发现,大部分开源的无锁结构都没有实现删除算法,删除算法会导致"状态爆炸"即中间可能的状态太多导致正确性很难证明.