Concurrent programming without locks
Concurrent programming without locks
复制标题
DOI：
10.1145/1233307.1233309
复制
发表时间：
2007-05
期刊：
影响因子：
--
通讯作者：
K. Fraser;T. Harris
中科院分区：
文献类型：
--
作者：
K. Fraser;T. Harris
互斥锁仍然是对共享内存数据结构进行并发控制的事实上的机制。然而，它们表面上的简单性具有欺骗性：很难设计可伸缩的锁定策略，因为锁可能存在优先级反转、死锁和护送等问题。此外，在构建复合操作时，基于锁的可伸缩系统不容易组合。在寻找这些问题的解决方案的过程中，人们对非阻塞系统产生了兴趣，这种系统通过避免互斥而同时仍确保安全，从而承诺了可伸缩性和健壮性。然而，用于构建非阻塞系统的现有技术很少适合于实际使用，这些技术增加了大量的存储开销、序列化无冲突的操作，或者需要在今天的CPU上不容易获得的指令。在本文中，我们提供了三个API，它们使开发任意数据结构的非阻塞实现变得更容易。第一个API是多字比较和交换操作(MCAS)，它自动更新一组内存位置。这可用于将数据结构从一种一致状态推进到另一种一致状态。第二个API是基于字的软件事务存储器(WSTM)，与MCAS相比，它可以更直接地重用顺序代码，并且在读取位置而不是更新位置时提供更好的可伸缩性。第三个API是基于对象的软件事务存储器(OSTM)。OSTM允许比WSTM更简单的实现，但代价是重新设计代码以使用OSTM对象。我们将介绍这三个API的实际实现，这些API构建于当今所有主要CPU系列的可用操作中。我们通过使用这些API来构建高度并发的跳跃列表和红黑树来说明这些API的使用。我们将结果实现的性能相互比较，并与基于锁的高性能系统进行比较。这些结果表明，可以构建性能与复杂的基于锁的设计相当或更好的有用的非阻塞数据结构。
Mutual exclusion locks remain the de facto mechanism for concurrency control on shared-memory data structures. However, their apparent simplicity is deceptive: It is hard to design scalable locking strategies because locks can harbor problems such as priority inversion, deadlock, and convoying. Furthermore, scalable lock-based systems are not readily composable when building compound operations. In looking for solutions to these problems, interest has developed in nonblocking systems which have promised scalability and robustness by eschewing mutual exclusion while still ensuring safety. However, existing techniques for building nonblocking systems are rarely suitable for practical use, imposing substantial storage overheads, serializing nonconflicting operations, or requiring instructions not readily available on today's CPUs. In this article we present three APIs which make it easier to develop nonblocking implementations of arbitrary data structures. The first API is a multiword compare-and-swap operation (MCAS) which atomically updates a set of memory locations. This can be used to advance a data structure from one consistent state to another. The second API is a word-based software transactional memory (WSTM) which can allow sequential code to be reused more directly than with MCAS and which provides better scalability when locations are being read rather than being updated. The third API is an object-based software transactional memory (OSTM). OSTM allows a simpler implementation than WSTM, but at the cost of reengineering the code to use OSTM objects. We present practical implementations of all three of these APIs, built from operations available across all of today's major CPU families. We illustrate the use of these APIs by using them to build highly concurrent skip lists and red-black trees. We compare the performance of the resulting implementations against one another and against high-performance lock-based systems. These results demonstrate that it is possible to build useful nonblocking data structures with performance comparable to, or better than, sophisticated lock-based designs.