在我的多线程应用程序中,我看到其中存在严重的锁争用,从而阻碍了跨多个核的良好可伸缩性.我决定使用无锁编程来解决这个问题.
如何编写无锁结构？
简短的回答是:
你不能.
答案很长:
如果你问这个问题,你可能不太了解能够创建一个无锁结构.创建无锁结构非常困难,只有该领域的专家才能做到这一点.而不是编写自己的,搜索现有的实现.当你找到它时,检查它的使用范围,它的记录程度,是否经过充分证明,有什么限制 - 甚至其他人发布的一些无锁结构也会被破坏.
如果找不到与您当前使用的结构相对应的无锁结构,请调整算法以便使用现有结构.
如果您仍然坚持创建自己的无锁结构,请务必:
从非常简单的事情开始
了解目标平台的内存模型(包括读/写重新排序约束,什么操作是原子的)
研究了很多其他人在实现无锁结构时遇到的问题
不要猜测它是否会起作用,证明它
大量测试结果
更多阅读:
免费锁定并在维基百科等待免费算法
Herb Sutter:无锁代码:一种虚假的安全感
使用像英特尔的线程构建模块这样的库,它包含了相当多的无锁结构和算法.我真的不建议你自己尝试编写无锁代码,它非常容易出错并且难以正确使用.
编写线程安全的无锁代码很难; 但Herb Sutter撰写的这篇文章将帮助您入门.
正如sblundy所指出的,如果所有对象都是不可变的,只读,你不需要担心锁定,但是,这意味着你可能需要经常复制对象.复制通常涉及malloc和malloc使用锁定来跨线程同步内存分配,因此不可变对象可能比你想象的少得多(malloc本身扩展性很差,malloc很慢 ;如果你在性能关键部分做了很多malloc,请不要期待良好的表现.
当你只需要更新简单变量(例如32或64位int或指针)时,对它们执行简单的加法或减法操作或只交换两个变量的值,大多数平台为此提供"原子操作"(进一步的GCC提供这些以及).原子与线程安全不同.但是,原子确保,例如,如果一个线程将64位值写入内存位置,而另一个线程从中读取,那么读取操作将在写入操作之前或写入操作之后获取值,但绝不会损坏值在写操作之间(例如,前32位已经是新的,最后的32位仍然是旧的值!如果你不对这样的变量使用原子访问,就会发生这种情况).
但是,如果你有一个具有3个值的C结构,想要更新,即使你用原子操作更新所有三个,这些是三个独立的操作,因此读者可能会看到结构中一个值已经被更新而两个没有被更新更新.如果你必须保证,你需要一个锁,读者要么看到结构中的所有值都是旧值或新值.
使锁定更好的一种方法是使用R/W锁.在许多情况下,对数据的更新很少(写操作),但访问数据非常频繁(读取数据),想到集合(哈希表,树).在这种情况下,R/W锁将为您带来巨大的性能提升,因为许多线程可以同时保持读锁(它们不会相互阻塞)并且只有当一个线程想要写锁时,所有其他线程在执行更新时被阻止.
避免线程问题的最佳方法是不跨线程共享任何数据.如果每个线程在大多数情况下处理其他线程无法访问的数据,则根本不需要锁定该数据(也没有原子操作).因此,尝试在线程之间尽可能少地共享数据.然后,如果你真的需要(ITC,Inter Thread Communication),你只需要一种快速的方法在线程之间移动数据.根据您的操作系统,平台和编程语言(遗憾的是您没有告诉我们这些),可能存在各种强大的ITC方法.
最后,使用共享数据但没有任何锁定的另一个技巧是确保线程不访问共享数据的相同部分.例如,如果两个线程共享一个数组,但是一个只能访问偶数,另一个只有奇数索引,你不需要锁定.或者如果两者共享相同的内存块而一个只使用它的上半部分,另一个只使用下一个,则不需要锁定.虽然没有说,但这将导致良好的表现; 尤其不适用于多核CPU.将一个线程写入此共享数据(运行一个核心)的操作可能会强制为另一个线程(在另一个核心上运行)刷新缓存,并且这些缓存刷新通常是在现代多核CPU上运行的多线程应用程序的瓶颈.
正如我的教授(来自"多处理器编程艺术"的Nir Shavit)告诉全班同学:请不要.主要原因是可测试性 - 您无法测试同步代码.你可以运行模拟,你甚至可以进行压力测试.但它充其量只是粗略的近似.你真正需要的是数学正确性证明.很少有人能够理解它们,更不用说写它们了.因此,正如其他人所说:使用现有的库.Joe Duffy的博客调查了一些技巧(第28节).你应该尝试的第一个是树分裂 - 打破较小的任务并组合.
不变性是避免锁定的一种方法.请参阅Eric Lippert关于不可变堆栈和队列之类的讨论和实现.
在重新.Suma的回答是,Maurice Herlithy在"多处理器编程艺术"中表示,实际上任何东西都可以在没有锁的情况下编写(参见第6章).iirc,这主要涉及将任务拆分为处理节点元素(如函数闭包),并将每个元素排入队列.线程将通过跟踪最新缓存的节点中的所有节点来计算状态.显然,在最坏的情况下,这可能会导致顺序性能,但它确实具有重要的无锁属性,可以防止线程在持有锁时长时间安排线程的情况.Herlithy还实现了理论上的无等待的性能,这意味着一个线程不会结束等待永远赢得原子排队(这是很多复杂的代码).
多线程队列/堆栈非常难(检查ABA问题).其他事情可能很简单.习惯于while(true){atomicCAS直到我交换它}块; 他们非常强大.对CAS的正确性的直觉可以帮助开发,尽管你应该使用良好的测试和可能更强大的工具(可能是SKETCH,即将推出的MIT Kendo,或者旋转？)来检查正确性,如果你可以将它简化为一个简单的结构.
请发布有关您的问题的更多信息 没有细节,很难给出一个好的答案.
如果我理解正确的话,编辑不可移植性很好但它的适用性是有限的.它并没有真正克服读写后的危害; 考虑执行"mem = NewNode(mem)"的两个线程; 他们都可以读取mem,然后都写出来; 对于经典增量函数来说不正确.此外,由于堆分配(必须跨线程同步),它可能很慢.
不可变性会产生这种效果.对对象的更改会导致新对象.Lisp以这种方式工作.
Effective Java的第13项解释了这种技术.
京公网安备 11010802040832号 | 京ICP备19059560号-6 