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

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算法乃至传统锁算法的一个全面劣化版，无论是性能还是可靠性，完全没有实用价值。

zylthinking

shan_ghost 发表于 2014-11-28 12:42
好吧，我承认自己压根没看楼主贴的代码，他说是lockfree我就信了。看过以后不得不ORZ了。

谁说我不是lockfree 限定范围到多写一读 使用 get 而不是getone 它就是lockfree 写之间互相free 读写互相free 只有一读 自然读之间也free 唯一不free的就是拿到数据后遍历可能存在短时间数据不ready 情况

最后劝告一句别为了和别人比赛把我向地下踩 什么劣质实现  get 与 put 思路我想并不是随便哪个把aba两边的a当作大腿根的人能想到的 写性能我想应该达到了近乎极致了

shan_ghost

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

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

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

井蛙夏虫

回复 30# folklore
我说的要求是lock free需要的。
wait free比lock free更严格的要求在于wait free要保证操作在有限的步骤完成,
而lock free可能由于与别的线程的冲突导致无限次的尝试。

   

zylthinking

shan_ghost 发表于 2014-11-28 13:15
lockfree是“先把该办的事办完，然后用一个CAS操作维护一下共享数据”；这和“把共享数据占住，然后慢慢 ...

你先搞明白代码再说 及我为什么强调单读再说

mmqmjy

其实吧，看到标题写着“无锁”就进来贴一大段“科普”也是挺烦人的
进来这讨论的人谁不知道那点常识
关键还搞错概念误导别人就不好了

把lock-free解释成“极小粒度”的锁也真是醉了
lock-free的概念请看12楼

另外read-copy-update只是lock-free的一种形式，不要把两者画等号
实际上如果使用GC的话，queue和stack都是可以lock-free的

@zylthinking 的代码，如果限定一个读线程并使用get_one，确实是lock-free的

zylthinking

shan_ghost 发表于 2014-11-28 12:42
好吧，我承认自己压根没看楼主贴的代码，他说是lockfree我就信了。看过以后不得不ORZ了。

令再提一句 根据我的测试 在锁定范围很小的情况下 随着线程数的的增加 这个个实现的性能会逐渐超过 原子测试不通过则yield的yield锁实现 线程数量很低时也比yield锁稍有优势 反而是线程数量不多不少时 yield 锁占优  在锁定区域很小前提下任意测试场景中 pthread mutex 都垫底

所以张嘴就说全面劣质前 最好昧心自问一下自己的嘴巴靠不靠谱 虽然代码的缺陷导致它应用场景不高 但也不是毫无用处 而且我从不规避它的缺陷 所以戴着aba帽子出场 并以甩掉两个a为目的的 别怪我不客气

zylthinking

mmqmjy 发表于 2014-11-28 14:19
其实吧，看到标题写着“无锁”就进来贴一大段“科普”也是挺烦人的
进来这讨论的人谁不知道那点常识
关键 ...

getone 是我后加的 只是为了完整 最开始实现只有get 并且我对get/put的思路还是有些得意的 有些限制就是信号处理搞不定 若在put两行代码中间来个信号并exit或jmp了我是搞不定的 但我也不在意了

mmqmjy

说缺陷的话其实也不是什么大缺陷
无非就是一个put没完成会导致无法get
但是想想就算没有这个问题，链表空时get也会拿到NULL
所以还是需要等待**的机制，这个就看程序的实现了

shan_ghost

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

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


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

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