谁能帮我解释这个无锁链表是怎么实现的，帮我分析一下

zhaohongjian000

zylthinking 发表于 2014-11-21 17:01
那你干脆说所有的无锁结构不过都实现了锁得了， 反正就算是 mutex, 还有 pthread_mutex_try_lock 呢；
...

我是这么说的呀，不过我说的是自旋锁。mutex通常在第一次尝试失败后陷入内核，然后等待通知。自旋锁没这功能。
当然从广义上来说，实现的都是锁。

codechurch

回复 11# zhaohongjian000

lock-free可不是自旋锁的变种（也不是实质上的类似实现）。

lock-free在运行中是这样工作的：

    每个并发端是尝试操作，如果某个操作成功了，就可能导致其他并发者的尝试失败，其他并发者可以再次尝试。

    全局而言，一次尝试失败，其实也意味着一个并发操作的成功。所以，假设有N个并发操作端，同时产生并发，那么，对一个端而言，最多尝试为N-1。

    无锁跟自旋锁的关键在于： 无锁的每次尝试失败，对全局而言，都有一次进展，即一次操作成功。而自旋锁不是这样，一个尝试失败就是一次失败，并不一定意味着其他端的成功。


比lock-free更高级的是【无等待】，即不需要尝试，每个并发者都能无等待地成功完成操作。当然，这个还是属于“GC主义”的幻想阶段。




   

codechurch

对主贴而言，能写出这个相当不简单，我没有仔细看，但，我提出一个问题，希望楼主注意一下：

     对于没有加版本号的比较交换，我都认为其应该严格验证。因为可能会出现吊诡的ABA’问题。这个还不是一时半会能测试出来的。你的测试程序用一个特制的堆，可能规避了ABA’问题，但是，如果在项目中，你试用了别的堆，ABA'可能就出现了。

shan_ghost

codechurch 发表于 2014-11-25 09:58
对主贴而言，能写出这个相当不简单，我没有仔细看，但，我提出一个问题，希望楼主注意一下：

     对于没 ...

+1

去年尝试搞过个无锁链表，设计了几个用例，都通过了，但最后一个多线程随机读写用例就测试出了ABA问题。

要解决ABA问题，就必须想办法打上TAG（或采用其他方案）。

zylthinking

codechurch 发表于 2014-11-25 09:58
对主贴而言，能写出这个相当不简单，我没有仔细看，但，我提出一个问题，希望楼主注意一下：

     对于没 ...

我认为是没有 bug 的， 只不过使用场景并不是很大；  之所以使用所谓特殊的堆， 只不过是测试的时候省心而已
曾经尝试用于正式代码， 每次加入后很快就剔除了， 因为发现根本用不到他提供的那点语意；

多白了， 这玩意最适用场景在于多写一读， 而且得是成千上百线程才能看出效果； 曾经测试了这个东西与其他几种锁实现的性能对比， 结论如下：

http://www.cnblogs.com/zylthinking/p/3736032.html

1. 原子操作与锁
   
2. 
   
3. 1. 既然比较两者性能， 必然锁的区域极小， 可以使用原子操作代替
   
4. 
   
5. 2. 若这个极小区域就是操作的全部， 只是频繁被调用， 则看并发的线程数量， 在并发量小时，  线程冲突小， 而一个 yield 可以保证较长时间内其他线程不来打搅， 获得的是一个类似批处理的结果， 性能较原子操作高; 自然， 若仅仅只有一个线程， 大家都是批处理， 还是原子操作性能高些; 随着线程数增加， 线程冲突频繁， 此时基本上无视线程多少的原子操作开始超越 yield 锁; 若是 futex 锁， 似乎比 yield 锁可以取得更高性能；但  futex 太重， 估计要超过 yield 锁需要的线程数是个不太现实的数字;
   
6. 
   
7. 3, 若这个极小区域是一个较长调用的一部分， 则锁区域比重降低， 意味着同时访问临界区的概率降低， 此时锁自身的成本成为性能主要影响因素， 原子操作性能会超过yield锁，  但由于锁区域比重低， 因此整体性能并不会表现出很大差异
   
8. 
   
9. 
   
10. 
    
11. 唯一貌似原子操作比 yield 锁性能大很多的就是 情况 2 的极大并发下 及 锁区域很大下， 但很大的锁区域恐怕原子操作不能够做等价实现， 因此没有意义
    
12. 
    
13. 结论就是整体而言， 原子操作性能要高些， 但有限
    

复制代码

codechurch

回复 15# zylthinking


其实我都不用看，我就可以断定你这个实现有ABA'问题。

你应该看过老外的那个实现，为了规避ABA'，他引入了一个带GC的堆，不可能有你这么简单的实现。





   

shan_ghost

http://en.wikipedia.org/wiki/ABA_problem

那些讲lock_free的，用的都是示例性的玩具代码。所有这些代码都有ABA问题。

其实在去年我自己搞那个lockfree算法时，也没意识到ABA问题。后来是发现最后一个用例总是出错，又检查发现代码逻辑没有问题，这才意识到中间有逻辑漏洞。



简单说，ABA问题就是（从链表中删除一个节点时）：

1、A线程先读出链表首指针和首指针指向节点的next指针后，就发生了线程切换，

2、B线程开始执行，一番复杂的动作后，控制权返回A

3、A执行CAS操作，具体操作是：检查A读出的首指针和链表首指针内容是否相同，相同则可认为A读出的内容仍然有效，所以只要把next指针内容赋给链表首指针即可；否则CAS操作失败——这套操作中间，硬件保证不可中断


但实际上，2阶段，B线程及其它线程可能执行了非常复杂的操作，有一定的概率，使得链表首指针指向的位置不变，但内容已经变了。此时CAS操作仍能通过，但A给出的next已经是脏的，这就导致数据被**。

codechurch

回复 17# shan_ghost

是，ABA'可能是并发问题里最吊诡的问题。

发表在专业杂志上的第一个无锁实现，当然是个牛人老外写的，一年后被证明存在ABA'问题，他后来修改了代码，这才有了现在的lock-free的第一个模范容器，在这个容器里，牛人使用c++语言实现，并实现了一个简单的GC堆来规避ABA'。因为使用gc堆，A被删除后，不会在这个周期内被再次使用，A就不能变成A'来捣乱了。而垃圾收集开始时，并发线程就要停止，ABA'当然也不能出现。）

除了此办法外，就是使用64位（对32位机器而言）比较交换的原子指令，其中32位为要交换的指针，另外32位是版本号，每次对此指针的改动，都要把版本号加1，这样来规避ABA'。（当然，有趣的是，ABA'依然在理论上存在，就是版本加1后，可能导致上溢，经数环后版本号诡异地又一样，但，在一瞬间上溢并且经过数环，99.9999999。。%是不可能的。）



   

mmqmjy

1.list->root.next的操作实际上起到了读锁的作用，保证同一时刻只有一个在读
2.list->tail对写操作进行序列化，虽然不是很完全，但是保证了写操作的原子性
3.写操作*ptr=node是原子的，读操作可能重置list->tail也是原子的
4.每当“锁”失败时，用自旋来等待
5.这个链表其实就是用了锁，根本不能叫无锁链表

@codechurch 18楼说的lock-free容器是啥？

shan_ghost

mmqmjy 发表于 2014-11-27 00:07
1.list->root.next的操作实际上起到了读锁的作用，保证同一时刻只有一个在读
2.list->tail对写操作进行序列 ...

CPU提供了一种叫做 compare&swap 的指令（简称CAS），这种指令会先做比较，比较成功再做赋值操作，硬件保证这套动作是原子的。

lockfree就是利用这种指令而不是传统的同步技术编写的、支持并行的数据管理代码。




另，你这一大段，和梦呓差不多，完全的不知所谓。

并行的难点在于保证整个操作的原子性（要么正确完成，要么完全别动，不允许出现第三种结果）。“保证同一时刻只有一个在读”不是目标，也无需作为目标；零零碎碎的这里保证一个在读、那里保证只有一个在写，也不等于整体上的原子性——而且我也看不出究竟怎么就保证了“保证同一时刻只有一个在读”。



换句话说，如果一个数据结构有40个相互关联的项目，那么原子操作就是，要么正确维护了这40个项目，要么一个项目都没动——无论中间出现了多么复杂的访问权切换动作。
——对于单向链表来说，就是指向一个节点的指针、节点内部数据（可能有大量数据项）以及节点携带的next指针，对三者的维护操作，要么全部成功，要么全部失败。


对这类复杂的数据结构，有两种处理方式来保证原子性：
1、通过各种同步技术，使得一次只能有一个线程可以做修改链表（或者，读写锁也行：读时其他线程可以读，但不能写[否则导致脏读]；写时其他线程读写都不被允许）

2、把一个节点视为一个整体，一个线程要么申请到整个节点（用于读写），要么申请不到；同样，一个线程要么成功归还一个节点，要么无法归还；然后，仅保护这个申请/归还动作，即可保证数据完整性。

——这个保护，当然也可以用传统的同步技术；但CAS指令也非常适合第二类情况的管理：你可以先读取链表首节点，然后用它比较在它执行时，实际的链表首节点是不是还是之前取得的链表首节点
——若是，说明没有其它线程对链表做操作，而CAS指令是原子的，肯定不会被其他线程打断，所以一旦compare操作成功，就可以swap，然后返回成功
——若否，说明在读链表首节点之后、CAS指令执行之前，已经切换到其它线程并被其它线程修改过了，所以一旦compare操作失败，就不得再执行swap操作，并返回失败


但，这里有个陷阱：只靠检查首节点指针有无改变，并不能保证链表真的就没被动过，这是两码事。
这就是ABA‘问题。

为了避免ABA’问题，就必须额外做点什么，以保证只要compare操作通过，那么链表就肯定没被别的线程动过。