java 无锁并发,无锁编程多线程 不用锁
原名：无锁并发编程
原文：3358 research . Microsoft . com/en-us/um/people/thar ris/papers/2007-tocs . pdf
翻译：科里谢
摘要：互斥锁仍然是共享内存数据结构并发控制机制的事实标准。然而，它们明显的简单性是欺骗性的：很难设计一个可扩展的锁定策略，因为锁定机制可能隐藏问题，如优先级反转、死锁和锁定护送。此外，在构建复合操作时，可扩展的基于锁的系统不容易组合。为了找到这些问题的解决方案，研究人员对非阻塞系统感兴趣，这种系统通过避免互斥而保证了可伸缩性和健壮性，同时确保了安全性。然而，现有的用于构建非阻塞系统的技术很少适合于实际使用，它们强加了巨大的存储开销，串行化了非冲突操作，或者需要当前CPU不具备的指令。
在本文中，我们提出了三个API，它们使我们更容易开发任意数据结构的非阻塞实现。第一个API是多字比较和交换(MCAS)操作，它可以自动更新一组内存位置。这可用于将数据结构从一种一致状态更改为另一种一致状态。第二个API是基于单词的软件事务内存(WSTM)，它允许顺序代码被重用。它比MCAS更直接，并且在读取而不是更新内存位置时提供更好的可伸缩性。第三个API是基于对象的软件事务内存(基于对象
软件事务内存，OSTM).OSTM允许比WSTM更简洁的实现，但是当使用OSTM时需要代码重新设计的成本。
我们给出了所有这些API的实际实现，它们是基于现在所有主流CPU家族的操作而构建的。我们展示了如何使用这些API来构建高度并行的跳转列表和红黑树。我们相互比较了所得结果的性能，并与基于锁的高性能系统实现进行了比较。这些结果表明，有可能构建一个非阻塞的有用数据结构，它具有与复杂的基于锁的设计相同或更好的性能。
以及题目描述：D.4.1【操作系统】:进程管理——并发；互斥；同时发生
一般术语：算法、语言、性能
更多关键词和短语：并发性、无锁系统、事务内存
介绍
互斥锁是同步中使用最广泛和最基本的抽象之一。这种流行主要是由于它们看似简单的编程模型以及可用实现的有效性和可伸缩性。不幸的是，如果没有特别的编程注意，这些好处很少能在有更多锁的系统中保持：
为了确保正确性，程序员必须确保线程持有必要的锁，以避免同时执行冲突的操作。为了避免错误，程序员倾向于开发简单的锁定策略，导致一些非冲突操作的悲观序列化。为了确保活跃度，程序员必须小心避免引入死锁。因此，他们持有锁的时间可能会超过必要的时间。另外，如果没有调度的支持，程序员一定要知道优先级反转的问题。为了获得高性能，程序员必须平衡锁的粒度和应用程序获取和释放锁所需的时间。
本文重点介绍软件的设计与实现，软件是安全的，可以在多线程多处理器共享内存的机器上使用，但不涉及锁的使用。相反，我们提出了三种不同的API来原子地访问一组内存位置。这些API使得直接从顺序数据结构开发并发数据结构成为可能。我们相信这使我们更容易构建一个正确的多线程系统。此外，我们的实现是非阻塞的(这意味着即使任何一组线程处于停顿状态，剩余的线程仍然可以取得进展)；通常，它们允许分离访问并行性(意味着可以同时执行对非重叠位置的更新)。
为了介绍这些API，我们将勾画出它们所使用的代码片段，并将项目插入到一个链表中，该链表以升序保存整数。在每种情况下，列表结构都是sentinel头节点和尾节点，它们的键值分别小于和大于所有其他值。插入后，每个节点的键值保持不变。为了比较，图1示出了当作为单线程实现时相应的插入操作。在这个图中，就像在我们的每个例子中一样，插入操作是通过识别节点prev和curr并在它们之间放置一个新节点来实现的。
我们的三个可供选择的API都遵循一个共同的乐观风格[Kun和Robinson，1981]，其中核心序列代码被封装在一个循环中，以重试插入，直到成功提交内存更新。
我们的第一个API提供了多字比较和交换(multiwordcompare-and-swap，MCAS)，它概括了许多处理器中存在的单字CAS操作：它自动地将一个或多个内存位置从一组期望值更新为一组新值。图2显示了如何使用MCAS来表示插入。
与顺序算法相比，有两个基本变化。首先，代码必须调用MCAS来执行一组完整的内存访问，而不是单独更新共享位置，这需要自动完成。在这个例子中，只有一个更新使用MCAS，但相应的删除操作将需要向MCAS传递两个更新：一个是从列表中删除节点，另一个是将其下一个字段清除为NULL，以防止在删除的节点后并发插入新节点。其次，当读取代码的位置可能被另一个线程的MCAS同时更新时，必须调用MCASRead。
MCAS和MCASRead提供了一个相当低级的API。程序员在必要的时候一定要小心使用MCASRead。还必须记住，后来MCAS不知道哪些地方被读过。这可能会导致麻烦的代码。该程序保存了一个它已经读取的位置列表和它从这些地址中看到的值，然后将这些列表传递给MCAS，以确认这些值代表了共享内存的一致状态。
第二个抽象提供了基于单个字的软件事务存储器(WSTM)，它通过允许将一系列读和写操作组合成可以原子地应用于堆的软件事务来避免这些问题[Harris和Fraser，2003]。图3显示了一个使用WSTM的列表示例。相对序列码的变化是队列共享位置的读写操作由WSTMRead和WSTMWrite函数执行，这一整套内存访问封装在WSTMStartTransaction调用和WSTMCommitTransaction调用之间。
第三个抽象提供了基于对象的软件事务内存(OSTM)，它允许线程“打开”一组对象的事务访问，并再次自动提交更新[Fraser，2003]。
图4展示了这种编程风格：通过OSTM句柄访问每个对象，并且必须通过调用OSTMOpenForReading或OSTMOpenForWriting来访问基本数据。举个简短的例子，代码看起来比WSTM更详细，但是OSTM的实现更简单、更直接、更快。
尽管这些技术没有提供设计可伸缩并行数据结构的灵丹妙药，但它们仍然代表了程序员责任的转移：这个API的实现负责正确地确保不会同时执行冲突的操作，并负责防止并行操作之间的死锁和优先级反转。API的调用者仍然负责确保可扩展性，因此并发操作不太可能需要修改一组重叠的位置。但是，这只是性能问题，不是正确性或活动性问题。根据我们的经验，即使是直接从顺序代码开发的简单数据结构也可以提供有竞争力的性能，并且常常超过最先进的基于锁的设计。
【工作正在进行中.】
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。