《多线程队列的算法优化》有35个想法

  1. 不过,好在一般来讲next指针是32位数据,而现代的CPU已经能保证多线程程序中32位数据读写操作的原子性,所以这个不是问题。
    这个不能一定保证的。

    这种方法不一定好,程序会变得很复杂。

    ”在进行enqueue和dequeue时都会先锁住这个锁以锁住整个队列然后再进行相关的操作“
    这个也是可以改善的,在一个线程写队列,一个线程读队列,这两个线程是通过pthread_cond_signal通信的话。在这种情况下的话,不需要锁住整个队列,只要锁住一个队列的一个单元

    1. @jet
      “这个不一定能保证”
      请说说具体什么时候不能保证?我原文漏说了条件 应该是内存对齐了的32位数据的操作是原子操作,具体我另一篇博文详细讲过了

      用pthread_cond_signal的话那就是阻塞型等待了,这种同步方式让线程停止工作,我在服务器端的程序中见过这样的用法,但是在多核上就不太可行了。因为在多核上(例如4个核)让一个线程停下来的代价太高了,所以一般如果dequeue一个空队列没取到值的话当前线程就会尝试对这个队列或另一个队列再进行一次dequeue操作

      1. 这个原子操作会存在memory barrier的语义么? 不存在的话 多核时候应该是无法保证正确性的。

  2. “用pthread_cond_signal的话那就是阻塞型等待了,这种同步方式让线程停止工作,我在服务器端的程序中见过这样的用法,但是在多核上就不太可行了。因为在多核上(例如4个核)让一个线程停下来的代价太高了”

    不知道博主说的是什么意思?难道是pthread_cond_signal()引起上下文切换太多?

    1. @spriteray
      我的本意是指pthread_cond_singal()会完成一次unlock,然后让该线程sleep,然后再等待被唤醒,然后再完成一次lock这个函数才执行完毕,调用它过程会让线程整个停下来。如果是每个线程拥有一个独立队列,用work stealing算法来分配任务的多线程程序,意味着对每个队列来说是单写者多读者的情况,更高效的办法就不是调用pthread_cond_singal()来阻塞的等待新任务,而是在dequeue直接返回false然后紧接着再去调用一次dequeue从另一个队列里去取任务,不让CPU闲着。当然,这得看应用场景,我文中所举的算法不是对任何场景都应用的,要不然java.util.concurrent就不会有那么多不同的concurrent queue算法了

  3. ”在进行enqueue和dequeue时都会先锁住这个锁以锁住整个队列然后再进行相关的操作“
    关于上面的解析。
    举个场景:一个主线程和一个工作线程池,他们之间有个环形数据队列。主线程写队列,工作线程读这个队列并且改变读到的那个队列单元的其中一个标识字段,使该单元重新变为可写的。主线程通过pthread_cond_signal驱动工作线程池工作。
    那么这个场景的特性是,主线程每次只会驱动一个工作线程去读队列(这点是最关键的)。
    根据这个特性,所以每次主线程写这个队列时是不需要对整个队列加锁的,只是在找到可写的单元时才需要加锁。工作线程读队列也一样,只要找到可读的单元时才需要加锁。

    1. @jet
      我文中的算法比较适合每个线程拥有一个独立的队列,不同线程间用work stealing的算法来分配任务的情况。你所列是一个全局共享的队列再加上线程池的情况,各有各的优势,关键还是得看应用场景,举例来说Java Concurrent包里的队列算法就有很多个。其实关键的出发点都是尽可能分离读和写,然后尽可能多并发。多谢指教。

  4. 不客气,共同学习!
    请问楼主,有没有研究c/c++下的 volatile,多线程,对齐,原子操作,锁等的关系?
    我发现他们之间是一个很有趣的话题,而且有点复杂。当然这些也跟cpu,系统,编译器有关了
    希望能和你共同探讨一下! 🙂

  5. 谢谢分享。学习、收藏了。
    文章中的方法可以很地处理队列插入/删除两个操作的互斥的问题。
    对于多线程同时插入的动作,不知道有没有办法优化呢?

    1. 如果想要对同时插入的情况做最更多的优化就必须使用硬件直接提供的CompareAndSwitch指令了,这已经是non blocking算法的范畴了,我的建议是:除非你是这方面的专家,一般情况下别去碰non blocking,因为太容易出错了

  6. 我们在为一个多级并行编程模型写底层runtime的时候,也用到了这些non-blocking,甚至更进一步的Non-fence队列;有个叫fastflow的工作,其实做得挺好的了;剑桥大学写出xen的那个小组的工作也很pratical。有机会交流一下,哈哈!

  7. 不知道博主是否认真想过你的例子没?虽然是伪码,但是也不能误导大家啊~
    enqueue 是没问题,但是 dequeue就是错的。这里必须要对tail指针进行赋值。
    比如剩下最后一个节点了,tail指针是指向这个node的,但是你dequeue的时候将它取出,free掉了,这里不改tail不是一个bug?那么又回到和原始模型一样,你得给tail 加锁,指回null 节点,性能提升的仅仅是enqueue少加了一次锁。
    ps:无锁编程也不是太难的事吧,把cas 搞熟,还是比较好写queue和stack的

    1. 这个算法本身在initialize()里面初始化了一个伪头结点,所以在任何时候都能保证至少还剩一个节点(即这个伪节点),因此free(node)不可能free掉tail指向的node,也就不会出现你说的bug。
      无锁编程保证正确性太难,java.util.concurrent库里面的无锁算法实现的时候1个人年只能写500行。

      1. 是的,是我看错,以为第一个节点是固定不动的,这个算法是对的

  8. 有个问题请教博主,也是类似的一类问题,那就是c++风格的容器和 linux c风格的容器 的实现的差异。
    linux 的容器 都是类似list一样的嵌入式的实现,有个很好的好处就是一个 obj可以归属于过个容器(比如链表)也就是多维的,而c++的容器是一维的,就很难办到同样的事情。就比如说这个例子,dequeue 取值是 拷贝的语义来实现,内部是通过node节点来管理的。相比linux的风格来说,这里就有比较多的内存分配销毁的负担。
    请教一下博主对linux c 的并发容器的理解,或者再写篇博文出来 : )

  9. 冠诚你好。
    看了你这篇博文,受教很多,想请问一下你文中提到的消息队列还有Work stealing有没有什么比较好的参考资料?
    关于队列这块,我自己目前也就是在线程池中实现了用pthread_cond_wait/signal的等待队列。不知道还有没有在什么场景下需要有什么样其他的队列实现呢?请指教~~

  10. 楼主你好!
    我们最近遇到队列的问题,碰到楼主的文章,真是救星啊。
    不过使用楼主说的这种算法有个问题,我们的机器是64位的,指针大小也都是64位的,不知道会不会影响?
    我们在测试过程发现了问题:数据量比较大的时候就会core。现在就是怀疑指针的赋值操作是不是原子的
    还有个问题请教,能不能测试指针的操作是否原子性的,怎么测试?
    谢谢!

    1. 是C/C++还是Java?前者的话可以用GCC提供的原子操作,Java的话有专门的原子操作API。请参考这篇文章:http://www.parallellabs.com/2010/04/15/atomic-operation-in-multithreaded-application/

  11. hi,请问下,上面代码的dequeue出队的是head的next节点上的数据,为何free的却是head指向的节点?即上面代码的L38和L41。虽然这样理论上也没啥影响,依然可以获得所有入队的数据,但是总感觉好奇怪啊,为啥不能直接free掉head的next节点呢?还是我理解有误?请帮忙回复下,谢谢。

电子邮件地址不会被公开。 必填项已用*标注