Linux系统编程之----如何开发无锁数据结构（获奖名单已公布-2013-7-12）
获奖名单已公布，详情请看：http://bbs.chinaunix.net/thread-4090480-1-1.html如何开发一个无锁数据结构，例如无锁队列，无锁缓存。
涉及到并行/并发计算时，通常都会想到加锁，加锁可以保护共享的数据，不过也会存在一些问题。
1. 由于临界区无法并发运行，进入临界区就需要等待，加锁使得效率的降低。多核CPU也不能发挥全部马力
2. 在复杂的情况下，很容易造成死锁，并发进程、线程之间无止境的互相等待。
3. 在中断/信号处理函数中不能加锁，给并发处理带来困难。
总之，在基于锁的多线程/多进程编程，你需要保证对竞争条件很敏感的共享数据上的任何操作，都通过加锁或解锁一个独占(mutex)来实现原子操作。
那么，在实际应用中，有没有优雅的无锁的数据结构实现呢，请大家各抒己见。
活动时间：2013年6月21日-7月10日
邀请嘉宾：
crazyhadoop，ChinaUnix论坛Linux环境编程版版主
本期奖品：
最佳经验分享奖5名，奖励《Linux高性能服务器编程》图书一本；
所有参与讨论的会员，即可获得社区积分20分
图书简介：
http://images.china-pub.com/ebook3765001-3770000/3768005/zcover.jpg
作者： 游双
出版社：机械工业出版社
ISBN：9787111425199
上架时间：2013-5-30
出版日期：2013 年6月
开本：16开
页码：345
版次：1-1
样章阅读：
http://wenku.it168.com/d_001050115.shtml
最近在看这块，说说我的理解，请大家指点。。。:D)
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.htmlbool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)
These builtins perform an atomic compare and swap. That is, if the current value of *ptr is oldval, then write newval into *ptr.
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实现也跟机器架构有关）__sync_synchronize (...)
This builtin issues a full memory barrier. #define LOCK_PREFIX "lock;"
#define __sync_bool_compare_and_swap(mem, oldval, newval) \
({ __typeof (*mem) ret; \
__asm __volatile (LOCK_PREFIX "cmpxchgl %2, %1;sete %%al; movzbl %%al,%%eax" \
: "=a" (ret), "=m" (*mem) \
: "r" (newval), "m" (*mem), "a" (oldval)\
:"memory"); \
ret; }) returns true if the comparison is successful and newval was written.
5.下面以说说无锁队列的实现，说下我的理解EnQueue(x)
{
q = newrecord();
q->value = x;
q->next = NULL;
do{
p = tail;
}while( CAS(p->next, NULL, q) != TRUE);
CAS(tail, p, q);
}
DeQueue()
{
do{
p = head;
if(p->next == NULL){
returnERR_EMPTY_QUEUE;
}
while( CAS(head, p, p->next) != TRUE );
returnp->next->value;
}由于是多线程编程，自然要考虑多些。
考虑加入队列的处理：如果thread 1 EnQueue(x)在成功完成第一个CAS，还没开始第二个CAS时挂掉了。那么other threads就会全死循环了:都在等着next字段为NUL的tail，但其实这个tail的next恒指向T1 在第一个CAS中新增的节点了。
解决此问题的修改后的：EnQueue(x)
{
q = newrecord();
q->value = x;
q->next = NULL;
p = tail;
oldp = p
do{
while(p->next != NULL)
p = p->next;
}while( CAS(p.next, NULL, q) != TRUE);
CAS(tail, oldp, q);
}这样既保证了即使T1 挂掉，但是T1新增的节点内存还能继续使用。
回复 1# send_linux 本帖最后由 hellioncu 于 2013-06-21 10:40 编辑
所谓的“无锁数据结构"其实不是真的没有锁，只是没有使用普通的那种锁，一般用原子操作（原子增、减、比较和交换CAS等）修改关键计数器、指针等，利用内存屏障避免乱序执行问题，在读写互斥时一般采用忙等待。
无锁数据结构的适用性比普通的有锁结构小，一般用于在读写冲突概率较小，而对性能又要求很高的场合。
至于死锁，解决的问题很简单，就是对资源的访问（加解锁）次序保持一致即可，跟是否使用“无锁数据结构“没有直接的关系。 回复 2# hellioncu
是的，无锁数据结构巧妙的规避了竞争条件。当然也是有代价的 这个要具体情况具体分析了吧 ，因为一些算法需要的就是一个流程下来的，不可能用什么方法把数据拆分处理这样就比较难办了。 另外涉及到多核的话是共享内存还是独立内存的体系结构也是有影响的。
所以愚见 无锁数据结构，可以运算前把数据都拆分了 然后再运算.... 本帖最后由 qingduo04 于 2013-06-21 14:08 编辑
鱼和熊掌不能兼得啊！
回复 1# send_linux
这个话题很有意义。顶一把
Godbach 发表于 2013-06-21 15:46 static/image/common/back.gif
回复 1# send_linux
这个话题很有意义。顶一把
分享分享嘛，呵呵 高级，聆听高手教诲。 这是一本好书，可惜只有TMD三章，虽然有新东西 但是大部分都是TCP/IP卷的东东，看来要看到高性能的部分 只能买书了 hanzhenlll 发表于 2013-06-21 17:18 static/image/common/back.gif
这是一本好书，可惜只有TMD三章，虽然有新东西 但是大部分都是TCP/IP卷的东东，看来要看到高性能的部分 ...
多多交流哈，可以有机会获赠的哦