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

shan_ghost

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

     对于没 ...

+1

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

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

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已经是脏的，这就导致数据被**。

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操作通过，那么链表就肯定没被别的线程动过。

shan_ghost

mmqmjy 发表于 2014-11-27 13:00

一边歇着去。


不懂不是问题，人都是从不懂来的。不懂装懂就惹人恶心了。

shan_ghost

好吧，我承认自己压根没看楼主贴的代码，他说是lockfree我就信了。看过以后不得不ORZ了。




首先呢，我得先对除ABA‘问题之外的讨论道歉。这的确不是一个lockfree实现，所以ABA‘的确完全不相关。


然后呢，看来我得先科普下何谓lockfree、以及lockfree有什么好处了。




长话短说，我在20楼提过，lockfree并不是没有锁，而是一个极小粒度的锁。

这个锁粒度小到什么程度呢？小到仅仅锁定了 一次比较+一次赋值操作，因而可以直接用CPU指令支持。


那么，用这么小粒度的锁，有什么好处呢？

显而易见，锁粒度越小，那么锁保护的时间就越短。而lockfree这种小到极致的锁呢，就使得所需的时间，小到一条指令这个极限。



如此一来，就成了“当且仅当两个以上的进/线程同时对同一个变量调用CAS指令时，才可能出现锁失败现象”——但同时，出现失败就意味着必定有一个线程成功执行了CAS。

——为什么会失败呢？因为取链表等结构当前状态的动作、和CAS动作是两条指令；那么如果两条指令之间出现了线程切换、且其它线程刚好执行了CAS操作，就会出现原线程的CAS执行失败。
——除了这个条件非常苛刻的失败条件，其它任何时候都不会出现CAS失败。


相比之下，传统的锁操作，仅上锁这个动作就需要很多条指令——包括上锁失败后通知操作系统、以便系统调度其它进/线程执行等等：这也很好理解，上锁等于请求资源，请求资源失败了自然只能等着，直到请求满足；否则，反而白白抢占了其他进/线程的CPU时间。
操作系统原理也提到过，操作系统知道每个进/线程是否在等待资源、等待什么资源，只有资源条件满足的进/线程才有得到调度的机会——这在整体上才能得到最优的效率。



那么，lockfree的好处就很明显了：通过小到极致的锁粒度，使得冲突几乎不可能发生、而且即便发生了，也肯定会有一个进/线程成功完成了操作（否则就不可能出现冲突）。




了解了这点，再看主贴这个实现，很明显，这根本不是一个lockfree实现。
实质上，它只是用CAS/test&set指令仿照传统锁做了个实现，并通过把这个实现和工作代码揉在一起，从而尽量节省了被保护的指令数量。




它的缺点是：
1、相对于lockfree算法，它的粒度仍然很大；所以压力大时，它比lockfree算法产生冲突的几率要大的多得多。
——前面有人提到的忙等问题，实质上就是这个缺陷的另一种说法：事实上lockfree算法也会用无限循环反复执行CAS操作，这其实也是忙等；但lockfree的锁粒度太小，且每一次CAS失败就意味着另外一个线程已经执行成功，所以这个消耗完全可接受：而这个算法锁粒度太大、相对于传统锁算法，它又无法在失败后交出CPU，所以一旦线程A在执行test&set后失去执行权，那么线程B、C……等等等等都会在死循环中跑满整个时间片，直到A再次得到执行权……

所以，烧烤CPU和有冲突就让程序走失败逻辑，选一个吧。


2、lockfree算法可区分“资源池无资源”和“CAS失败”，从而对两者区分处理；而这个算法则无法区分这两种情况——于是只好在“死循环烧烤CPU”和“无论是锁冲突还是无资源都作失败处理”两个后果中选择（事实上，可能只有后一个选择才是合理的）。
这个缺陷使得它的应用面极窄，很难找到合理的应用场景。




总结：
1、相对于传统锁和lockfree算法，它都太不可靠；
2、相对于不循环调用CAS操作的lockfree，它的速度更慢、且失败几率也更高；而一旦想通过循环调用来提高可靠性，它的消耗就会急剧上升、锁冲突几率也急剧上升、且一旦链表中没有可用节点就立刻陷入死循环
——甚至，一旦一个线程在test&set设置NULL标志后就失去执行权、且使用了忙等模式，那么它的效率完全就是个灾难，最差情况下甚至可能比传统锁还要差数十甚至数百万倍，因为其他线程的整个时间片都空耗在必然失败的忙等上了（换句话说，它的忙等模式完全无实用性可言）。


一言以蔽之，这就是lockfree算法乃至传统锁算法的一个全面劣化版，无论是性能还是可靠性，完全没有实用价值。

shan_ghost

zylthinking 发表于 2014-11-28 13:02
谁说我不是lockfree 限定范围到多写一读 使用 get 而不是getone 它就是lockfree 写之间互相free 读写互相 ...

lockfree是“先把该办的事办完，然后用一个CAS操作维护一下共享数据”；这和“把共享数据占住，然后慢慢办该办的事”，在本质上是不同的。

前者锁一个点，除了这个点不会影响其他人，所以叫“极小粒度”；后者锁一大片，只要占住共享数据的不放手，其他人谁都别想动，实质上是“极大粒度”。

shan_ghost

1、我没有在楼主的代码中看到任何文档说明，所以只能按通用算法的要求评判；此外，除了平均响应时间，最差响应时间等也是重要的性能指标。

专有算法的话……很久前我甚至搞过一个ring buff，因为需求只需要一个线程读、一个线程写，所以不光传统的锁，连CPU提供的特殊原子指令都没用到。
不过为了避免后来者用错，我专门搞了很大篇幅的注释，详细说明了它的应用场景。


2、lock free算法之所以兴起，是因为它借用了CPU的原子操作指令（一般是CAS）来避免进/线程像传统线程那样被系统挂起，以得到更好的响应时间保证、更好的性能或者避免死锁/活锁等不良状态这三种好处（之一甚至全部）。

所以，恕我忽略了那些利用原子指令设置标志，以模拟排斥其他线程执行的、去除了操作系统相关内容的旗语/临界区/mutex类似物。因为这类模拟和传统锁相差无几，但却几乎无法避免“某个线程忙等完整个时间片”之类故障——这类故障出现几率极低，但一旦出现，影响却非常严重（比如前面提到的，A线程设置标志后失去执行权，那么在它重新执行前，其它线程都只能空转到时间片结束）。