多线程读写无锁链表： 之前有没有相同的实现？ (更新)

zylthinking

zhouzhenghui 发表于 2013-08-21 19:54
，并且循环反复重试场景下的才工作的实现，跟真正意义上的无锁相差甚远 ...

这是你的代码
    void lognode_put(struct lognode* node)
    {
        struct lognode* last;
        struct lognode* before;
        do {
            last = tail;
            if (last == &end) {
                __sync_val_compare_and_swap(&tail, last, head);
                continue;
            }
            before = __sync_val_compare_and_swap(&(last->next), NULL, node);
            if (before != NULL)
               __sync_val_compare_and_swap(&tail, last, before);
        } while (before != NULL);

        __sync_val_compare_and_swap(&tail, last, node);
    }

你解释解释什么叫  循环反复重试场景下的才工作， 你的循环怎么就不是了 循环反复重试场景下的才工作
还有， 链表接口你也在吐槽， 链表接口又怎么了？ 还有那个明明有数据读不出来的说法， 也还没解释呢

zhouzhenghui

不好意思，有些话只是随口说了玩玩，并不针对谁，毕竟论坛讨论，希望是给更多人看到，但说话的时候未免会根据自身的环境做出一些假设，如有不妥，还望见谅。

眼界不同，看到的世界也会不很一样，比如眼下讨论东西，还处于应用很不成熟的阶段，只参考ms queue，而不看这方面的前沿资料，论文什么的，理解上肯定会有不足。并不是说你的做法就不对，只是好处坏处一比较就自然明白了。

我之前也说过，自己测试没有错误，眼力也不行，所以找不出错误来，这很正常，承认自己不足，并不是自以为是吧。并行世界发生的事，人们理解起来很困难，容易出错，相信你也明白。但毕竟研究这块的人不多，我只是浸润的时间稍长些，所以把自己的经验拿出来分享，希望后来的人做出更大的成绩来，也许你和其他人将来可能很厉害了。所谓惺惺相惜，大概就是这个意思了。

一般意义上无锁指lockfree，是已经有明确公认的定义的，就是任何情况发生下，只要系统本身还在运行，在系统层面下必须是可以继续前进的，具体而言就是至少有一个线程在继续执行它的任务，你的实现是不满足lockfree的定义的。另外还有wait-free，是更高级的无锁，就是所有线程都可以在有限时间里完成其任务；而obstruct-free相对比较低级，允许存在通过等待别人完成工作从而采取反复重试的方法，即所谓“活锁”，你的这个实现更接近后者。

我代码中的反复重试跟你的反复重试有本质的区别，即无论其他线程是否工作，只要给我工作，就可以保证工作可以继续前进，也就是无论多少线程挂起，任务总体上是前进的。而你的反复重试，是等别人把任务完成，别人做不完，自己都始终循环在那里等，存在所谓的“活锁”，也大大浪费了很多执行机会。

比如get中，你只是把得到在队列中还有数据情况得到NULL后重试的任务交给到客户端，这种重试可能因为他人暂停而不断失败，还有就是上面你也明白线程在某点终止后的产生情况。

并不是说这种方法就不行，毕竟现实中线程在特定点会挂起的几率极低，而且大家只要都在运行，也的确不会死锁，我看到在不少实际项目中也采用类似的手段，因为实现一个完全正确的无锁并行结构不是很容易的事，只是这不是这里讨论的目的。

Aquester

zylthinking 发表于 2013-08-21 10:33
写了一个多线程读多线程写的无锁链表， 完全是自己的思路， 但不知道之前有没有其他人已经提出来过了， 和  ...

推荐相关的PPT：
http://blog.chinaunix.net/uid-20682147-id-3160080.html

zylthinking

zhouzhenghui 发表于 2013-08-21 21:18
不好意思，有些话只是随口说了玩玩，并不针对谁，毕竟论坛讨论，希望是给更多人看到，但说话的时候未免会根 ...

好吧， 今天火气比较大， 态度不好， 算是道歉吧。
我是感觉出来了， 你是混实验室做研究写论文的， 而我是混公司写代码卖钱的， 在取舍标准上却是存在差异。
若按理论性的不死小强作为标准， 我的手法却是不满足定义， 我简单的认为， 发生这种情况的概率比计算机断电的概率要小， 不予关心， 我更关心的是性能。 实际上， 若按理论计， 就不该存在没道理的线程消亡， 若论实际， 则总不能无视线程在指定地点无理由消亡的小概率。

但在其他方面， 我仍然存在异议：

我代码中的反复重试跟你的反复重试有本质的区别，即无论其他线程是否工作，只要给我工作，就可以保证工作可以继续前进，也就是无论多少线程挂起，任务总体上是前进的。而你的反复重试，是等别人把任务完成，别人做不完，自己都始终循环在那里等，存在所谓的“活锁”，也大大浪费了很多执行机会

就这个论断而言， 我认为相对你的实现， 我的反而离所谓活锁更远些。 为什么：

首先重试这两种实现谁也避免不了， 你的在  put/get 中重试， 我的在外部重试；
但要注意到， 一旦我 get 出来， 所有冲突全部会被规避， 理想情况下， 如果我 get 出  5 个元素， 这  5 个元素最后一个和第一个是连在一起的， 剩下的都是独立的， 因此看上去我每次取下一个元素都要等， 然而要注意到所有的这些元素， 其实运行在多核下， 而且每个都是单独一个线程， 每个线程从独立到串起来只需要一步操作， 即*ptr = node;
在理想情况下， 无论有多少个独立互不联通的节点， 他们是同时发起连接操作， 因此花费的时间应该是一个元素的操作时间而不是再将其乘以节点数；换言之， 我的操作趋向一个常量；我next操作中， 发生的等待次数应该是 1 次。 而且， 在现实中， 往往get数据之后, 通过 next fetch 数据之前， 客户端往往存在其他操作， 那么， 很可能利用这段时间， 那些节点会完成串联操作， 那么我就彻底不用等了。

相反 你的循环中虽然每一步都在想前进， 但你规避不了线程竞争， 类似于想吃胡萝卜的小毛驴， 你走一步他也走一步， 永远追不上， 因此趋向一个无限循环；自然， 我的没那么理想， 你的也不会那么倒霉；但总体评价， 我不认为比你的更靠近活锁， 恐怕浪费执行机会更多的不会是我; 进一步而言， 在 next 操作中我完全私有化， 完全不考虑原子性操作， 而你做不到这一点， 这一点差距多大， 我自己的测试为 1 亿条操作， 当时记得大概是 1000 个写线程， 50 个读线程， 使用 get 取与使用  getone 取数据， 性能相差恐怕在  30 倍左右， 时间没细算， 根据测试结果大体感觉的。

你只是把得到在队列中还有数据情况得到NULL后重试的任务交给到客户端， 这种重试可能因为他人暂停而不断失败

这个在编程模型上而言恐怕是更合适的， 很显然， 得到 NULL 后客户端完全可以不立刻重试， 而选择做其他工作， 这就是所谓不阻塞模式； 换言之， 给客户端充分自由；阻塞在自己函数内部不断重试， 恐怕才是不可取的。 而且他人暂停只有一种可能， 就是发生了线程切换， 这个可能是你代码里的一点优势， 你完成操作不需要等待别的线程， 但要注意的是不等待别的睡眠的线程， 等的是互相竞争的线程， 而我等的是睡眠的线程， 工作中的线程我反而不等待;  其他的暂停， 出了莫名其妙被杀死， 没有别的可能， 因为这代码是在我的控制之内， 我没有在     
struct lkf_node** last = __sync_lock_test_and_set(&(list->tail), &(list->root.next));
*last = ptr;
中间插入任何导致暂停的代码。

额外说说之前的事情， 凑巧想起来： 你说我的测试代码冗余， 你精简了很多， 但我发现你将我预先分配内存的代码精简了， 采用了动态分配；很显然， 这样的代码会导致大量时间浪费在 malloc 中， 而我们期待的应该是所有线程尽可能全部时间都花在线程竞争上；而且， 还有一个不好影响， 你可以注意到我测试的规模是 1000 个写线程， 每个 100000 次操作， 共一亿次操作， 你动态内存分配能做到这个规模吗， 恐怕还没到一半就被操作系统杀死了。

zhouzhenghui

题外话不说，直接举例吧，除了多核竞争外，比如操作系统中，中断发生操作某个共享数据结构，这也是一种特殊的并行，如果之前不加锁，算法达不到lock-free往上标准的话，是不行的，还有实时系统中的优先级调度，也是不行的。所谓的“杀死”状态，实际上是上述场景的一种简化。

你说的批量get，跟算法细节没什么关系，只是具体需求和设计的考量，之前你的问题中就是批量get的，我已经指明，给出的回复也都是针对的。

算法本身的效率问题，要做到lock-free，自然是要付出代价的，相对每一步做的事情要多得多，类似如果wait-free的话会更加的慢。但相对obstruct-free，就是满足全场景的使用，同时不会有空转等待的状态发生。你说我的代码中相互竞争会失败，我再解释的清楚一点，无论如何失败，至少有一个是成功的，它会继续执行，这就是所谓的lock-free。无论是多核并行，还是线程调度，至少计算资源的利用已经达到最高了。

至于你的算法中放宽了对数据获取的时间要求，并延迟到客户端来应对等措施，这些都是特定应用场景的实现，跟算法关系不大。

你提到所有节点都是动态分配的，这仅仅是为了测试算法本身，把内存管理这部分功能先抛开。你也明白，用了好多代码实际上在做内存管理的活，仅讨论算法的话，这部分会干扰主线，另外一面其实是良好的设计在于职责分明，分解得当。我说接口也有类似的意思，不是吐槽，而是关心更多的实际需求，否则一个只能在特定场景下应用的实现，价值上肯定会大打折扣。

话说回来，lock-free，包括wait-free实际上没多少东西，前人已经研究的差不多了。为什么没有大规模应用？就是因为内存管理的问题没有解决（仅仅预分配是不能满足的）。你再仔细看我给出的理论上（同时也是实际上）最正确最简洁的写法中，抛开动态分配的数据节点（可以用你的预分配方案取代），其中的head，tail节点也是要动态分配了。但一旦要改到静态时，就一下问题多多，为什么？因为ABA问题，动态（不回收策略）保证了不会有数据竞争发生。到这里，也大约就是无锁数据结构的全部了。

djsxut

顶一个，再慢慢看。

zylthinking

zhouzhenghui 发表于 2013-08-21 23:56
，比如操作系统中，中断发生操作某个共享数据结构，这也是一种特殊的并行，如果之前不加锁，算法达不到lock-free往上标准的话，是不行的，还有实时系统中的优先级调度，也是不行的...

如果是数学式的全覆盖， 实现自然不会覆盖那么全， 若论事实， 首先中断， 常识是中断必须快速执行完毕， 一个等不到数据就耍赖不退出的中断导致的问题应该是中断处理代码的责任； 而一旦退出， 那这个线程消亡的场景就不存在了。
优先级调度这个难以反驳些， 但若需要操作系统升高消费者线程优先级结果抢占了生产者线程的执行， 就算我这里有问题， 其他实现难道就没有问题？ 很显然， 调度器不会得知业务逻辑， 知道消费者得到数据后就应该降低其优先级， 现实是他会连续提高其优先级一段时间， 而这段时间内， 一旦生产者之前 put 的数据被消耗完毕， 照样被阻塞， 同样导致消费者线程空转。

无论如何失败，至少有一个是成功的，它会继续执行，这就是所谓的lock-free。无论是多核并行，还是线程调度，至少计算资源的利用已经达到最高了

这个不认同， 不错， 至少一个是成功的， 因此会继续执行， 但计算资源只是一个核心达到最高， 按两两配对来吧， 10 个 核心， 5 个成功可以了吧， 还有 5  个是失败的，  计算资源利用 50%, 怎么能算是最高呢？

好吧， 我非科研出身， 一辈子就本科毕业在网上抄了篇论文， 理论上不足正常， 这个帖子里也学到了点东西。 我代码着眼点就在于实用， 没想着覆盖所有的场景； 而且， 你也承认了， 论性能， 我这个实现应该是优于你的实现的。 我想对于我来说就很好了

pitonas

顶一下    zhouzhengh

pppStar

顶一下, 楼主,  
谢谢你给我们带来精彩的code

cdzmouse

顶一下，
赞同zhouzhenghui 说的

“一般意义上无锁指lockfree，是已经有明确公认的定义的，就是任何情况发生下，只要系统本身还在运行，在系统层面下必须是可以继续前进的，具体而言就是至少有一个线程在继续执行它的任务，你的实现是不满足lockfree的定义的。另外还有wait-free，是更高级的无锁，就是所有线程都可以在有限时间里完成其任务；而obstruct-free相对比较低级，允许存在通过等待别人完成工作从而采取反复重试的方法，即所谓“活锁”，你的这个实现更接近后者。”

不过，zylthinking的这个代码确实也比较适合大多数场合使用了，真正则的lock-free在很多时候限于外部其它模块要求，是不可达到的