一个可无限伸缩且无ABA问题的无锁队列 – menggucaoyuan

        关于无锁队列,详细的介绍请参考陈硕先生的《无锁队列的实现》一文。然进一步,如何实现一个不限node数目即能够无限伸缩的无锁队列,即是本文的要旨。

        无锁队列有两种实现形式,分别是数组与链表。以数组实现的无锁队列,限定了基本node的数目,然没有ABA问题。以链表实现的无锁队列,在内存允许的情况下可以添加任意数目的node,然有ABA问题。如何取二者的优点而摒弃其各自的缺点呢?

        如果要做到可以无限伸缩,那么这种无锁队列须采用链表实现,然如何解决ABA问题呢?

        ABA问题的本质就是地址重用,即两个(或多个)访问者访问一个node,其中一个释放了这个node,此时os会回收这个node。然后另外一个访问者要新生成一个node时,os会把刚释放掉的那个node的内存空间分配给这个访问者。在这个过程中,如果我们不把释放掉的node还给os,是不是问题就解决了?

        可保存需要释放的node而不还给os的技术,我能想到的是内存池。一个以链表形式实现的无锁队列使用它的内存池时,如果要对这个内存池加锁,那就不是无锁队列了。

        这个内存池中每个node大小一致,用一个数组形式的无锁队列实现即可。本文需要的无锁队列便是用链表实现的,而且基于数组无锁队列内存池。

        这里面还有一个问题。还是上面的那个场景,node被访问者释放后,此时由内存池保存着,然后另一个访问者要申请一个node的内存空间,便会向内存池申请,如果内存池是把那个刚被释放掉的node空间分配给它呢?相当于内存池替代了os,问题依然没有解决。

        既然内存空间现在由内存池而非os管理着,哪我们就可以想办法解决了。

        还是上面那个场景,如果内存池中有很多个node,队列形式的内存池还会把刚被释放掉的node空间分配出去吗?所以需要在内存池中保存多个node。但保存多少合适呢?保存的node数量大于等于同时向内存池申请node空间的访问者即可。

        node的数量取决于访问者的数目,若访问者是线程,则这个数目就是就是写线程的数目,这个参数可以让使用者设置。为了编程方便,我假设线程池线程写线程最多不会超过2048个,这个值应该大于当前多数服务器中CPU数量。

         我在64位linux上用C实现了本文讨论的无锁队列,代码已经上传到百度网盘,请点击这里下载

         欢迎批评指正。

         此记。

本文链接:http://www.cnblogs.com/menggucaoyuan/p/3209285.html,转载请注明。



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量