Linux系统编程之----如何开发无锁数据结构（获奖名单已公布-2013-7-12）

chishanmingshen

最近在看这块，说说我的理解，请大家指点。。。

1.先说说几个概念
锁只是同步方法的一种，同步分阻塞同步和非阻塞同步。
lockfree就可以保证非阻塞同步，同时也尽量保证了waitfree，但依然做不到完全的waitfree。

2.既然讨论无锁，就得说说有锁会导致的问题
a）死锁
多个锁不按顺序的话
b）优先级反转
可能高优先级的等待低优先级的
c）影响实时性
等锁时间不定
d）信号安全
信号处理中不能用锁
e）崩溃处理
崩溃时可能占着锁
f）抢占的影响
被抢占时可能还占着锁
g）影响整体性能
切换进程影响性能

最后，锁的实现是跟硬件相关的，自然影响移植性。

3.无锁首先得根据业务逻辑，这个是首要的。
脱离业务去有锁或无锁是没有意义的。
根据业务流程去简化，一般可以将锁的存在压缩到最小。另外锁只是同步机制的一种，应该还有其它选择。

4.如果已经将有锁的存在压缩到最小的数据结构了，就可以考虑无锁算法了。
通用的lock free算法都是针对基本的数据结构的：buffer，list，queue，map
基本原理就是CAS机制了。现在几乎所有的CPU指令都支持CAS的原子操作，X86下对应的是CMPXCHG汇编指令。（可见，lockfree是依赖于机器体系结构的，而且lockfree其实还是有锁的，只是CAS给压缩含义了）

一般CAS会封装成下面的形式：（以32bit机为例）
bool cas32( int * pVal, int oldVal, int newVal );
pVal 表示要比较和替换数值的地址，oldVal表示期望的值，newVal表示希望替换成的值。

gcc中：
http://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Atomic-Builtins.html

1. bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
   
2. type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)
   
3. These builtins perform an atomic compare and swap. That is, if the current value of *ptr is oldval, then write newval into *ptr.
   
4. The “bool” version returns true if the comparison is successful and newval was written. The “val” version returns the contents of *ptr before the operation. 
   

复制代码

另外，gcc的对于内核中内存屏障也有封装：（内核的kfifo实现可以看到，内核在kfifo时有比CAS机制更加地lock free，用mb即可。当然mb实现也跟机器架构有关）

1. __sync_synchronize (...)
   
2. This builtin issues a full memory barrier.

复制代码

1.     #define LOCK_PREFIX    "lock;"  
   
2.     #define __sync_bool_compare_and_swap(mem, oldval, newval) \  
   
3.       ({ __typeof (*mem) ret;                             \  
   
4.              __asm __volatile (LOCK_PREFIX "cmpxchgl %2, %1;sete %%al; movzbl %%al,%%eax"                \  
   
5.                                 : "=a" (ret), "=m" (*mem)                  \  
   
6.                                 : "r" (newval), "m" (*mem), "a" (oldval)\  
   
7.                                 :"memory");         \  
   
8.                                   ret; })  

复制代码

returns true if the comparison is successful and newval was written.


5.下面以说说无锁队列的实现，说下我的理解

1. EnQueue(x)   
   
2. {
   
3.     q = newrecord();
   
4.     q->value = x;
   
5.     q->next = NULL;
   
6. 
   
7.     do{
   
8.         p = tail;   
   
9.     }while( CAS(p->next, NULL, q) != TRUE);  
   
10. 
    
11.     CAS(tail, p, q);
    
12. }
    
13. DeQueue()        
    
14. {
    
15.     do{
    
16.         p = head;
    
17.         if(p->next == NULL){
    
18.             returnERR_EMPTY_QUEUE;
    
19.         }
    
20.     while( CAS(head, p, p->next) != TRUE );
    
21.     returnp->next->value;
    
22. }

复制代码

由于是多线程编程，自然要考虑多些。
考虑加入队列的处理：如果thread 1 EnQueue(x)在成功完成第一个CAS，还没开始第二个CAS时挂掉了。那么other threads就会全死循环了:都在等着next字段为NUL的tail，但其实这个tail的next恒指向T1 在第一个CAS中新增的节点了。

解决此问题的修改后的：

1. EnQueue(x)      
   
2. {
   
3.     q = newrecord();
   
4.     q->value = x;
   
5.     q->next = NULL;
   
6. 
   
7.     p = tail;
   
8.     oldp = p
   
9.     do{
   
10.         while(p->next != NULL)
    
11.             p = p->next;
    
12.     }while( CAS(p.next, NULL, q) != TRUE);  
    
13. 
    
14.     CAS(tail, oldp, q);
    
15. }

复制代码

这样既保证了即使T1 挂掉，但是T1新增的节点内存还能继续使用。



回复 1# send_linux

chishanmingshen

6.CAS的ABA问题
thread 1在共享内存空间中读到的值为A，此时
1. thread 1被抢占了，thread 2执行
2. thread 2把共享变量里的值从A改成了B，再改回到A，此时被thread 1抢占。
3. thread 1回来看到共享变量里的值没有被改变，于是继续执行。
这个就是lock free的ABA问题，CAS无法判断目标内容从A变为B，然后又变为A这种情况。（这个A就是保护共享空间的内容，很可能就是指针：像队列、链表实现中，就是节点的地址！）
解决的办法通常是使用一个额外的tag来记录这种情况，并且使用CAS2（double CAS）同时检查tag和目标内存内容两个值都没有发生变化。注意：CAS2最多支持检查一个64 bit长度的内存指并原子交换他们的内容。但是，可以想象，那个tag也有溢出的问题，所以还是没有彻底解决ABA问题。其实，保证每次添加的节点内存唯一，这样就彻底了。

sxcong

理想是美好的，但理论上，"无锁队列，无锁缓存"在现行计算机系统里是不存在的。最多也只是"相当于..."。
保护有限的资源的锁是一种自然规律，逃避它是不可能的。“有没有优雅的无锁的数据结构实现呢”，听起来好象在问：有没有一种优雅的机器不损耗能量，也就是永动机呢？
所以才有了线程池，生产者消费者理论。不止计算机，在所有领域，资源有限的情况下，锁是必须的。所谓的"按需分配"永远是理想，就算资源满足所有的需求，也要有垄断产生，不完全是平均分配。比如,得罪了负责分配的这个人，有需也会让你没需，根本就得不到分配。

superwiles

基于epoll就号称高性能了，叫dpdk和netmap 情何以堪

send_linux

superwiles 发表于 2013-06-24 18:31
基于epoll就号称高性能了，叫dpdk和netmap 情何以堪

兄弟详细说说呢？

yuyunliuhen

透过 Linux 内核看无锁编程
http://www.ibm.com/developerworks/cn/linux/l-cn-lockfree/

他人写的，觉得不错，分享下

chishanmingshen

回复 26# yuyunliuhen

是啊，无锁就是要追求性能。

而内核对此自然更是要追求到极致了。

其实userland上用到的同步机制（比如上面提到的CAS），都已经在内核进行了封装。




   

jieforest

这里我以一个开源的消息组件LMAX Disruptor来探讨这个话题。
LMAX Disruptor是一个高性能、低延迟的消息组件框架，主页：http://lmax-exchange.github.io/disruptor/
LMAX Disruptor内部实现了一个高效的内存无锁队列。
Disruptor的中心数据结构是一个基于定长数组的环形队列，在数组创建时可以预先分配好空间，插入新元素时只要将新元素数据拷贝到已经分配好的内存中即可。对数组的元素访问对CPU cache 是非常友好的。关于数组的大小选择有一个讲究，大家都知道环形队列中会用到取余操作， 在大部分处理器上，取余操作并不高效。因此可以将数组大小设定为2的指数倍，这样计算余数只需要通过位操作 index & ( size -1 )就能够得到实际的index。
Disruptor对外只有一个变量，那就是队尾元素的下标：cursor，这也避免了对head/tail这两个变量的操作和协同。生产者和消费者对disruptor的访问分别需要通过producer barrier和consumer barrier来协调。生产者插入元素分为两个步骤，第一步申请一个空的slot, 每个slot只会被一个生产者占用，申请到空的slot的生产者将新元素的数据拷贝到该slot；第二步是发布，发布之后，新元素才能为消费者所见。如果只有一个生产者，第一步申请操作无需同步即可完成。如果有多个生产者，那么会有一个变量：claimSequence来记录申请位置，申请操作需要通过CAS来同步。
消费者需要等待有新元素进入方能继续消费，也就是说cursor大于自己当前的消费位置。等待策略有多种。可以选择sleep wait, busy spin等等，在使用disruptor时，可以根据场景选择不同的等待策略。如果消费者发现cursor相比其最后的一次消费位置前进了不止一个位置，它就可以选择批量消费这区段的元素，而不是一次一个的向前推进。这种做法在提高吞吐量的同时还可以使系统的延迟更加平滑。

lovegq

都说 无锁是追求性能， 我反问一句，有没有实际的代码或者demo或者方法能间接明了的证明
1  某种无锁算法到底比有锁快多少？或者节省多少资源，什么资源?
2  这种优化在普遍的场景下都适用么？


优化是一方面，可如果没有相应的检测手段，证明优化效果，只是根据传闻和“想象中的理论”做优化，本身有点儿不靠谱。
并且这种检测手段，还必须是间接快速，如果测试手段比优化本身还复杂，则...你怎么能证明你的优化是有效果的呢

最后还有一个疑问，“某种无锁”算法 在“这台机器”的“这种场景”下性能提高，能保证它在“那台机器”的“那种场景”下性能也提高么？
因为在实际中，遇到过大量“优化手段” 在家里的机器上提升明显，放到生成环境下，10台机器，一半没效果，一半反效果

crazyhadoop

回复 27# chishanmingshen


    锁对并发性能影响较大，想办法规避这种情况