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

codechurch

回复 11# zhaohongjian000

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

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

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

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

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


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




   

codechurch

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

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

codechurch

回复 15# zylthinking


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

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





   

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。。%是不可能的。）



   

codechurch

回复 23# zylthinking

这就是人们称之为“经验”的东西。

codechurch

回复 24# mmqmjy


的确，这里会【忙等】，属于自旋锁，而且“忙自旋”，系统忙得应该叫娘了。

   

codechurch

回复 29# zylthinking

看你这个态度，whatever。。。。

我没仔细看，是因为相信你的确是写出来一个无锁，原来根本不是，是自旋锁而已。

对不起，高看你了。