• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

基于无锁的C#并发队列实现

原作者: [db:作者] 来自: [db:来源] 收藏 邀请


最近开始学习无锁编程,和传统的基于Lock的算法相比,无锁编程具有其独特的优点,Angel Lucifer的关于无锁编程一文对此有详细的描述。

无锁编程的目标是在不使用Lock的前提下保证并发过程中共享数据的一致性,其主要的实现基础是CAS操作,也就是compare_and_swap,通过处理器提供的指令,可以原子地更新共享数据,并同时监测其他线程的干扰,.Net中的对应实现是InterLocked.CompareExchange函数。

既然不使用Lock,那在无锁编程中要时刻注意的是,代码可能在任意语句中被中断。如果是单个变量,我们可以使用 InterLocked.XXX 保证操作的原子性,但是如果有多个操作要完成的话,简单地组合 InterLocked.XXX 是远远不够的。通常的原则是对函数中用到的共享变量,先在代码开始处用局部变量保存它的内容,在后面更新共享变量时,使用前述变量来判断其是否发生了改变,如果共享变量发生了改变,那么我们可能需要重试,或者在某些可能的情况下,当前线程可以"帮助"其他更新中的线程完成更新。

从上面可以总结出无锁算法的两个基本特征:

1. 无锁算法总是包含一个循环结构,以保证更新失败后重试

2. 无锁算法在更新共享变量时,总是使用CAS和原始值进行比较,以保证没有冲突

下面是按照Michael-Scott算法实现的并发队列,其中的Dequeue算法在IBM的非阻塞算法一文中有详细介绍。代码如下:

根据自己的测试(双核CPU),在轻度和中度争用情况下,无锁算法比基于锁的算法性能好很多,在争用非常严重的情况下(100个并发线程以上/每CPU),基于锁的算法性能开始显示出优势,因为一旦发生争用,基于锁的算法会立刻切换到其他线程,而无锁算法会进入下一次循环,导致CPU的占用。但是如此严重的争用在实际中并不多见,并且可以采用SpinWait的方法加以改进。基于锁的算法在测试中曾经出现过类似死锁的现象,无锁算法则完全没有出过类似问题,另外,处理器核心越多,基于锁的算法效率越差。
 
从上面的算法实现中,可以体会到无锁算法的优势:在并发的多个线程中,总是有线程能够推进,算法总能在有限的循环次数内完成,并且在某些冲突的情况下,一个线程可以“帮助”其他线程完成被中断的工作,这些对提高吞吐量都有很大的作用。
 

鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
【转】C#异步转同步发布时间:2022-07-14
下一篇:
.NetC#Dictionary和参数字符串互转发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap