vdh*_*ant 85 .net c# multithreading lock-free
我正在阅读Jon Skeet给出一个问题的答案,并在其中提到了这一点:
就我而言,无锁多线程是真正的线程专家,其中我不是一个.
这不是我第一次听到这个,但是如果你有兴趣学习如何编写无锁多线程代码,我发现很少有人在谈论你如何实际做到这一点.
所以我的问题是除了学习关于线程的所有内容之外,等等你在哪里开始尝试学习专门编写无锁多线程代码以及什么是好资源.
干杯
And*_*ass 98
当前的"无锁"实现大多数时候遵循相同的模式:
(*可选:取决于数据结构/算法)
最后一点与螺旋锁类似.实际上,它是一个基本的自旋锁.:)
我同意@nobugz的观点:无锁多线程中使用的互锁操作的成本主要取决于它必须执行的缓存和内存一致性任务.
但是,如果使用"无锁"的数据结构,您获得的是"锁定"非常精细.这降低了两个并发线程访问相同"锁定"(内存位置)的机会.
大部分时间的技巧是你没有专用的锁 - 而是将例如数组中的所有元素或链表中的所有节点视为"自旋锁".如果自上次阅读以来没有更新,您可以阅读,修改并尝试更新.如果有,你重试.
这使得你的"锁定"(哦,对不起,非锁定:)非常细粒度,而不会引入额外的内存或资源需求.
使其更精细化会降低等待的可能性.在不引入额外资源要求的情况下尽可能细化它听起来很棒,不是吗？
然而,大多数乐趣可以来自确保正确的装载/存储订购.
与一个人的直觉相反,CPU可以自由地重新排序内存读/写 - 顺便说一下,它们非常聪明:你将很难从单个线程中观察到这一点.但是,当您开始在多个核心上执行多线程时,您将遇到问题.你的直觉会崩溃:只是因为你的代码中的指令较早,并不意味着它实际上会更早发生.CPU可以不按顺序处理指令:他们特别喜欢对存储器访问的指令执行此操作,以隐藏主存储器延迟并更好地利用其缓存.
现在,确信不会直觉,一系列代码不会"自上而下"流动,而是运行就好像根本没有序列 - 并且可能被称为"魔鬼的游乐场".我认为对于将要进行的加载/存储重新排序给出确切的答案是不可行的.相反,人们总是谈论mays,mights和cans,并为最坏的情况做好准备."哦,CPU 可能会在写入之前对此读取进行重新排序,因此最好在此处设置内存屏障."
事实上,即使这些mays和mights在CPU架构上也会有所不同,这一点很复杂.这可能是这种情况,例如,东西是保证不会发生在一个架构 可能会发生在另一个上.
要获得正确的"无锁"多线程,您必须了解内存模型.
然而,正如这个故事MFENCE所证明的那样,获取内存模型并保证正确并不是微不足道的,因此英特尔和AMD对文档进行了一些修正,引起了JVM开发人员的一些骚动.事实证明,开发人员从一开始就依赖的文档起初并不那么精确.
.NET中的锁会导致隐式内存障碍,因此您可以安全地使用它们(大多数情况下,这就是......例如,参见Joe Duffy - Brad Abrams - Vance Morrison对延迟初始化,锁,挥发物和记忆的伟大看法障碍.:)(请务必按照该页面上的链接.)
作为额外的奖励,您将在侧面任务中介绍.NET内存模型.:)
Vance Morrison还有一个"oldie but goldie":每个开发者必须了解多线程应用程序.
......当然,正如@Eric所提到的,Joe Duffy是关于这个主题的权威读物.
一个好的STM可以获得接近细粒度的锁定,并且可能提供与手工实现接近或相同的性能.其中之一是STM.NET从DevLabs项目 MS的.
如果你不是一个只有.NET的狂热者,那么Doug Lea在JSR-166上做了一些很棒的工作.
Cliff Click对哈希表有一个有趣的看法,它不依赖于锁定条带化 - 就像Java和.NET并发哈希表一样 - 并且似乎可以很好地扩展到750个CPU.
如果你不害怕冒险进入Linux领域,下面的文章提供了对当前内存架构内部以及缓存行共享如何破坏性能的更深入了解:每个程序员应该了解内存.
@Ben对MPI做了很多评论:我真诚地同意MPI可能会在某些领域大放异彩.与试图智能的半成品锁定实现相比,基于MPI的解决方案可以更容易推理,更容易实现并且更不容易出错.(但是 - 主观上 - 对于基于STM的解决方案也是如此.)我还打赌,正如许多成功的例子所表明的那样,在Erlang中正确编写一个像样的分布式应用程序要轻松多年.
然而,当MPI在单个多核系统上运行时,它有自己的成本和自身的麻烦.例如,在Erlang中,围绕进程调度和消息队列的同步存在需要解决的问题.
此外,MPI系统的核心通常是为"轻量级进程" 实现一种协同的N:M调度.例如,这意味着轻量级进程之间存在不可避免的上下文切换.确实,它不是"经典的上下文切换",而是主要是用户空间操作,并且可以快速进行 - 但是我真诚地怀疑它可以在20-200个周期内进行互锁操作.即使在Intel McRT库中,用户模式上下文切换肯定也较慢.N:具有轻量级过程的M调度并不新鲜.LWP在Solaris中存在了很长时间.他们被遗弃了.新台币有纤维.他们现在大部分都是遗物.NetBSD中有"激活".他们被遗弃了.Linux对N:M线程的主题有自己的看法.现在似乎有点死了.
有时会有新的竞争者:例如来自英特尔的McRT,或者最近的用户模式调度以及来自微软的ConCRT.
在最低级别,它们执行N:M MPI调度程序所做的事情.Erlang - 或任何MPI系统 - 可以通过利用新的UMS在SMP系统上获益匪浅.
我猜OP的问题不是针对任何解决方案的优点和主观论点,但如果我必须回答这个问题,我想这取决于任务:构建低级别,高性能的基本数据结构具有多个内核的单个系统,无论是低锁定/"无锁定"技术还是STM都将在性能方面产生最佳效果,并且可能在性能方面随时击败MPI解决方案,即使上述皱纹被解决了例如在Erlang.
为了构建在单个系统上运行的任何适度更复杂的东西,我可能会选择经典的粗粒度锁定,或者如果性能非常令人关注,那就是STM.
对于构建分布式系统,MPI系统可能是一个自然的选择.
请注意,还有针对.NET的MPI实现(尽管它们似乎没有那么活跃).
Eri*_*ert 27
乔达菲的书:
http://www.bluebytesoftware.com/books/winconc/winconc_book_resources.html
他还写了一篇关于这些主题的博客.
诀窍越来越低锁定程序的权利是在一个深层次的理解恰恰什么内存模型的规则是您具体的硬件,操作系统和运行时环境的组合.
我个人并不聪明到能够在InterlockedIncrement之外进行正确的低锁编程,但如果你是,那很好,那就去吧.只需确保在代码中留下大量文档,以便不那么聪明的人不会意外破坏您的内存模型不变量,并引入一个不可能发现的错误.
Han*_*ant 19
这些天没有"无锁线程"这样的东西.对于学术界等而言,这是一个有趣的游乐场,早在上个世纪末,计算机硬件变得缓慢且昂贵. Dekker的算法总是我最喜欢的,现代硬件已经把它放到了牧场.它不再起作用了.
两个发展已经结束了这一点:RAM的速度和CPU之间的差距越来越大.并且芯片制造商能够在芯片上放置多个CPU内核.
RAM速度问题要求芯片设计人员在CPU芯片上放置缓冲器.缓冲区存储代码和数据,可由CPU内核快速访问.并且可以以低得多的速率从RAM读取和写入RAM.此缓冲区称为CPU缓存,大多数CPU至少有两个.第一级缓存小而快,第二级缓存大而慢.只要CPU可以从第一级缓存读取数据和指令,它就会快速运行.高速缓存未命中非常昂贵,如果数据不在第一个高速缓存中,它会使CPU休眠多达10个周期,如果它不在第二个高速缓存中则多达200个周期,并且需要从内存.
每个CPU核心都有自己的缓存,它们存储自己的RAM"视图".当CPU写入数据时,写入缓存,然后缓慢地刷新到RAM.不可避免的是,每个核心现在都有不同的RAM内容视图.换句话说,在RAM写周期完成且 CPU刷新自己的视图之前,一个CPU不知道另一个CPU写了什么.
这与线程非常不兼容.当您必须读取由另一个线程写入的数据时,您始终非常关心另一个线程的状态.为了确保这一点,您需要显式编程所谓的内存屏障.它是一个低级CPU原语,可确保所有CPU缓存处于一致状态并具有RAM的最新视图.所有挂起的写入都必须刷新到RAM,然后需要刷新缓存.
这在.NET中可用,Thread.MemoryBarrier()方法实现一个.鉴于这是锁定语句所执行作业的90%(以及执行时间的95%以上),您只是避免使用.NET提供的工具并尝试实现自己的工具.
| 归档时间： |
|
| 查看次数： |
23372 次 |
| 最近记录： |
