公开(公告)号：US07908441B2

公开(公告)日：2011-03-15

申请号：US10340156

申请日：2003-01-10

申请人： Mark S. Moir ,  Victor Luchangco ,  Maurice Herlihy

发明人： Mark S. Moir ,  Victor Luchangco ,  Maurice Herlihy

IPC分类号： G06F12/14 ,  G06F9/54

CPC分类号： G06F9/52 ,  Y10S707/955 ,  Y10S707/99953 ,  Y10S707/99957

摘要： Solutions to a value recycling problem facilitate implementations of computer programs that may execute as multithreaded computations in multiprocessor computers, as well as implementations of related shared data structures. Some exploitations allow non-blocking, shared data structures to be implemented using standard dynamic allocation mechanisms (such as malloc and free). Some exploitations allow non-blocking, indeed even lock-free or wait-free, implementations of dynamic storage allocation for shared data structures. In some exploitations, our techniques provide a way to manage dynamically allocated memory in a non-blocking manner without depending on garbage collection. While exploitations of solutions to the value recycling problem that we propose include management of dynamic storage allocation wherein values managed and recycled tend to include values that encode pointers, they are not limited thereto. Indeed, the techniques are more generally applicable to management of values in a multithreaded computation. For example, value recycling techniques may be exploited, in some cases, apart from dynamic storage allocation, to allow a multithreaded computation to avoid the classic ABA hazard.

摘要翻译： 价值回收问题的解决方案便于在多处理器计算机中作为多线程计算执行的计算机程序的实现，以及相关共享数据结构的实现。 一些利用可以使用标准的动态分配机制（如malloc和free）来实现非阻塞的共享数据结构。 一些剥削允许共享数据结构的动态存储分配的非阻塞，甚至无锁或无等待的实现。 在一些利用中，我们的技术提供了一种在不依赖垃圾收集的情况下以非阻塞方式管理动态分配的内存的方法。 虽然我们提出的解决价值回收问题的解决方案包括动态存储分配的管理，其中管理和再循环的值往往包括编码指针的值，但是并不限于此。 实际上，这些技术更普遍地适用于多线程计算中的值的管理。 例如，除了动态存储分配之外，还可以利用价值回收技术，在某些情况下，允许多线程计算避免经典的ABA危险。

公开(公告)号：US20090172299A1

公开(公告)日：2009-07-02

申请号：US11967358

申请日：2007-12-31

申请人： James R. Goodman ,  Mark S. Moir ,  Fu'ad W. F. Al Tabba' ,  Cong Wang

发明人： James R. Goodman ,  Mark S. Moir ,  Fu'ad W. F. Al Tabba' ,  Cong Wang

IPC分类号： G06F12/00 ,  G06F12/16 ,  G06F12/14

CPC分类号： G06F9/526 ,  G06F9/466 ,  G06F11/141 ,  G06F11/1479 ,  G06F2209/521

摘要： A hybrid Single-Compare-Single-Store (SCSS) operation may exploit best-effort hardware transactional memory (HTM) for good performance in the case that it succeeds, and may transparently resort to software-mediated transactions if the hardware transactional mechanisms fail. The SCSS operation may compare a value in a control location to a specified expected value, and if they match, may store a new value in a separate data location. The control value may include a global lock, a transaction status indicator, and/or a portion of an ownership record, in different embodiments. If another transaction in progress owns the data location, the SCSS operation may abort the other transaction or may help it complete by copying the other transactions' write set into its own right set before acquiring ownership. A hybrid SCSS operation, which is usually nonblocking, may be applied to building software transactional memories (STMs) and/or hybrid transactional memories (HyTMs), in some embodiments.

摘要翻译： 混合单一比较单存储（SCSS）操作可以在成功的情况下利用尽力而为的硬件事务存储器（HTM）以获得良好的性能，并且如果硬件事务机制失败，则可以透明地诉诸软件介入的事务。 SCSS操作可以将控制位置中的值与指定的预期值进行比较，如果匹配，则可将新值存储在单独的数据位置。 在不同的实施例中，控制值可以包括全局锁定，事务状态指示符和/或所有权记录的一部分。 如果正在进行的另一个交易拥有数据位置，SCSS操作可能会中止其他交易，或者可以在获得所有权之前将其他交易的写入集合复制到自己的权利集中来帮助完成该交易。 在一些实施例中，通常不阻塞的混合SCSS操作可以应用于构建软件事务存储器（STM）和/或混合事务存储器（HyTM）。

公开(公告)号：US07533221B1

公开(公告)日：2009-05-12

申请号：US11026850

申请日：2004-12-30

申请人： Simon Doherty ,  Mark S. Moir ,  Victor Luchangco ,  Maurice P. Herlihy

发明人： Simon Doherty ,  Mark S. Moir ,  Victor Luchangco ,  Maurice P. Herlihy

IPC分类号： G06F12/00

CPC分类号： G06F12/023 ,  G06F9/526

摘要： Many conventional lock-free data structures exploit techniques that are possible only because state-of-the-art 64-bit processors are still running 32-bit operating systems and applications. As software catches up to hardware, “64-bit-clean” lock-free data structures, which cannot use such techniques, are needed. We present several 64-bit-clean lock-free implementations: including load-linked/store conditional variables of arbitrary size, a FIFO queue, and a freelist. In addition to being portable to 64-bit software (or more generally full-architectural-width pointer operations), our implementations also improve on existing techniques in that they are (or can be) space-adaptive and do not require a priori knowledge of the number of threads that will access them.

摘要翻译： 许多传统的无锁数据结构利用了仅仅因为最先进的64位处理器仍在运行32位操作系统和应用程序而可能的技术。 随着软件的升级，硬件需要“64位清理”的无锁数据结构，不能使用这种技术。 我们提出了几个64位无干扰的无锁实现：包括任意大小的加载链接/存储条件变量，FIFO队列和freelist。 除了可移植到64位软件（或更通常的全架构宽度指针操作）之外，我们的实现还改进了现有技术，因为它们（或可以）是空间自适应的，并且不需要先验知识 将访问它们的线程数。

公开(公告)号：US07424477B1

公开(公告)日：2008-09-09

申请号：US10653828

申请日：2003-09-03

申请人： Paul A. Martin ,  Guy L. Steele, Jr. ,  Nir N. Shavit ,  Steven K. Heller ,  Mark S. Moir ,  Victor M. Luchangco

发明人： Paul A. Martin ,  Guy L. Steele, Jr. ,  Nir N. Shavit ,  Steven K. Heller ,  Mark S. Moir ,  Victor M. Luchangco

IPC分类号： G06F17/00 ,  G06F7/00

CPC分类号： G06F9/524 ,  Y10S707/99938 ,  Y10S707/99942 ,  Y10S707/99943

摘要： A set of structures and techniques are described herein whereby an exemplary concurrent shared object, namely a shared skip list, can be implemented in a lock-free manner. Indeed, we have developed a number of interesting variants of a lock-free shared skip-list, including variants that may be employed to provide a lock-free shared dictionary. In some variants, a key-value dictionary is implemented.

摘要翻译： 本文描述了一组结构和技术，由此可以以无锁的方式实现示例性并发共享对象，即共享跳过列表。 实际上，我们已经开发出了一些无锁共享的跳过列表的许多有趣的变体，包括可用于提供无锁共享字典的变体。 在一些变型中，实现了键值字典。

公开(公告)号：US07398355B1

公开(公告)日：2008-07-08

申请号：US11195093

申请日：2005-08-01

申请人： Mark S. Moir ,  Marc Tremblay ,  Shailender Chaudhry

发明人： Mark S. Moir ,  Marc Tremblay ,  Shailender Chaudhry

IPC分类号： G06F12/00 ,  G06F13/00 ,  G06F13/28 ,  G06F9/30 ,  G06F9/40 ,  G06F15/00

CPC分类号： G06F9/3004 ,  G06F9/30087 ,  G06F9/3834 ,  G06F9/3842 ,  G06F9/3859 ,  G06F9/3863 ,  G06F9/528 ,  G06F12/0815 ,  G06F12/0862

摘要： One embodiment of the present invention provides a system that avoids locks by transactionally executing critical sections. During operation, the system receives a program which includes one or more critical sections which are protected by locks. Next, the system modifies the program so that the critical sections which are protected by locks are executed transactionally without acquiring locks associated with the critical sections. More specifically, the program is modified so that: (1) during transactional execution of a critical section, the program first determines if a lock associated with the critical section is held by another process and if so aborts the transactional execution; (2) if the transactional execution of the critical section completes without encountering an interfering data access from another process, the program commits changes made during the transactional execution and optionally resumes normal non-transactional execution of the program past the critical section; and (3) if an interfering data access from another process is encountered during transactional execution of the critical section, the program discards changes made during the transactional execution, and attempts to re-execute the critical section zero or more times.

摘要翻译： 本发明的一个实施例提供一种通过事务执行关键部分来避免锁定的系统。 在操作期间，系统接收包括被锁保护的一个或多个关键部分的程序。 接下来，系统修改程序，使得受锁保护的关键部分在事务上执行，而不获取与关键部分相关联的锁定。 更具体地说，修改程序使得：（1）在关键部分的事务执行期间，程序首先确定与关键部分相关联的锁定是否被另一进程保持，如果是这样，中止事务执行; （2）如果关键部分的事务执行完成而没有遇到来自另一进程的干扰数据访问，则该程序提交在事务执行期间所做的更改，并且可选地恢复通过关键部分的程序的正常非事务性执行; 和（3）如果在关键部分的事务执行期间遇到来自其他进程的干扰数据访问，则程序将丢弃事务执行期间所做的更改，并尝试重新执行关键部分零次或多次。

公开(公告)号：US07395382B1

公开(公告)日：2008-07-01

申请号：US10915502

申请日：2004-08-10

申请人： Mark S. Moir

发明人： Mark S. Moir

IPC分类号： G06F12/14 ,  G06F12/10 ,  G06F13/14

CPC分类号： G06F9/466

摘要： A transactional memory implementation has been developed that is capable of coordinating concurrent hardware transactional memory (HTM) and software transactional memory (STM) transactions over a unified transactional memory space. Some implementations employ hardware transactional memory, if available or suitable, to improve performance. Some exploitations include a hardware transactional memory in which, or for which, hardware-mediated transactions are augmented to include within their transactional scope (or mechanism) one or more additional transactional locations that facilitate coordination with concurrently executing software-mediated transactions (if any).

摘要翻译： 已经开发了一种事务存储器实现，其能够通过统一的事务存储器空间协调并行硬件事务存储器（HTM）和软件事务存储器（STM）事务。 一些实现使用硬件事务存储器（如果可用或适合的）来提高性能。 一些利用包括一个硬件事务性内存，硬件交易内存在其中被扩充，或者由硬件交互的事务增加以在其事务范围（或机制）内包含一个或多个附加的事务位置，这些位置便于与并发执行软件中介的事务（如果有的话）协调） 。

公开(公告)号：US07194495B2

公开(公告)日：2007-03-20

申请号：US10340145

申请日：2003-01-10

申请人： Mark S. Moir ,  Victor Luchangco ,  Maurice Herlihy

发明人： Mark S. Moir ,  Victor Luchangco ,  Maurice Herlihy

IPC分类号： G06F17/30 ,  G06F12/02

CPC分类号： G06F9/52 ,  Y10S707/955 ,  Y10S707/99953 ,  Y10S707/99957

摘要： Solutions to a value recycling problem that we define herein facilitate implementations of computer programs that may execute as multithreaded computations in multiprocessor computers, as well as implementations of related shared data structures. Some exploitations of the techniques described herein allow non-blocking, shared data structures to be implemented using standard dynamic allocation mechanisms (such as malloc and free). Indeed, we present several exemplary realizations of dynamic-sized, non-blocking shared data structures that are not prevented from future memory reclamation by thread failures and which depend (in some implementations) only on widely-available hardware support for synchronization. Some exploitations of the techniques described herein allow non-blocking, indeed even lock-free or wait-free, implementations of dynamic storage allocation for shared data structures. A class of general solutions to value recycling is described in the context of an illustration we call the Repeat Offender Problem (ROP), including illustrative Application Program Interfaces (APIs) defined in terms of the ROP terminology. Furthermore, specific solutions, implementations and algorithm, including a Pass-The-Buck (PTB) implementation are described.

摘要翻译： 我们在这里定义的价值回收问题的解决方案便于在多处理器计算机中作为多线程计算执行的计算机程序的实现，以及相关共享数据结构的实现。 本文描述的技术的一些利用允许使用标准动态分配机制（诸如malloc和free）来实现非阻塞的共享数据结构。 实际上，我们提出了动态大小的非阻塞共享数据结构的几个示例性实现，这些结构通过线程故障不会阻止将来的内存回收，并且仅在广泛可用的硬件支持同步上依赖（在某些实现中）。 本文描述的技术的一些利用允许用于共享数据结构的动态存储分配的非阻塞，甚至无锁或无等待的实现。 在我们称为重复违规问题（ROP）的例证的上下文中描述了一类价值回收的一般解决方案，包括根据ROP术语定义的说明性应用程序接口（API）。 此外，描述了包括通过降压（PTB）实现的具体解决方案，实现和算法。

公开(公告)号：US09135178B2

公开(公告)日：2015-09-15

申请号：US13543267

申请日：2012-07-06

申请人： Nir N. Shavit ,  Mark S. Moir ,  Victor M. Luchangco

发明人： Nir N. Shavit ,  Mark S. Moir ,  Victor M. Luchangco

IPC分类号： G06F9/46 ,  G06F12/00 ,  G06F13/00 ,  G06F13/28 ,  G06F12/08 ,  G06F9/30 ,  G06F9/38 ,  G06F9/52

CPC分类号： G06F12/0844 ,  G06F9/30 ,  G06F9/3004 ,  G06F9/38 ,  G06F9/466 ,  G06F9/52 ,  G06F12/00 ,  G06F12/08 ,  G06F12/0815 ,  G06F12/084 ,  G06F12/0842 ,  G06F12/0846 ,  Y10S707/99942

摘要： The design of nonblocking linked data structures using single-location synchronization primitives such as compare-and-swap (CAS) is a complex affair that often requires severe restrictions on the way pointers are used. One way to address this problem is to provide stronger synchronization operations, for example, ones that atomically modify one memory location while simultaneously verifying the contents of others. We provide a simple and highly efficient nonblocking implementation of such an operation: an atomic k-word-compare single-swap operation (KCSS). Our implementation is obstruction-free. As a result, it is highly efficient in the uncontended case and relies on contention management mechanisms in the contended cases. It allows linked data structure manipulation without the complexity and restrictions of other solutions. Additionally, as a building block of some implementations of our techniques, we have developed the first nonblocking software implementation of load-linked/store-conditional that does not severely restrict word size.

摘要翻译： 使用单一位置同步原语（例如比较和交换（CAS））的非阻塞链接数据结构的设计是一种复杂的事情，通常需要对指针使用方式的严格限制。 解决这个问题的一个方法是提供更强大的同步操作，例如，在同时验证其他内容的同时原子地修改一个存储器位置的同步操作。 我们提供了这样一个操作的简单而高效的非阻塞实现：原子k字比较单交换操作（KCSS）。 我们的实施是无障碍的。 因此，在无争议的情况下是高效的，并且依赖于竞争案件中的争用管理机制。 它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。 此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。

公开(公告)号：US09052944B2

公开(公告)日：2015-06-09

申请号：US11106790

申请日：2005-04-15

申请人： Mark S. Moir ,  Victor M. Luchangco ,  Maurice Herlihy

发明人： Mark S. Moir ,  Victor M. Luchangco ,  Maurice Herlihy

IPC分类号： G06F12/00 ,  G06F13/00 ,  G06F13/28 ,  G06F9/46

CPC分类号： G06F9/526 ,  G06F9/466 ,  G06F9/467 ,  G06F12/1475 ,  G06F2212/1052

摘要： We teach a powerful approach that greatly simplifies the design of non-blocking mechanisms and data structures, in part by, largely separate the issues of correctness and progress. At a high level, our methodology includes designing an “obstruction-free” implementation of the desired mechanism or data structure, which may then be combined with a contention management mechanism whose role is to facilitate the conditions under which progress of the obstruction-free implementation is assured. In general, the contention management mechanism is separable semantically from an obstruction-free concurrent shared/sharable object implementation to which it is/may be applied. In some cases, the contention management mechanism may actually be coded separately from the obstruction-free implementation. We elaborate herein on the notions of obstruction-freedom and contention management, and various possibilities for combining the two. In addition, we include description of some exemplary applications to particular concurrent software mechanisms and data structure implementations.

摘要翻译： 我们教授一种强大的方法，大大简化了非阻塞机制和数据结构的设计，部分原因是在很大程度上分离了正确性和进度的问题。 在高层次上，我们的方法包括设计一个“无障碍”的所需机制或数据结构的实施，然后将其与争用管理机制结合起来，其作用是促进无障碍执行进展的条件 放心 一般来说，争用管理机制在语义上与可以应用于其的无障碍并发共享/可共享对象实现是可分离的。 在某些情况下，争用管理机制实际上可以与无障碍的实现分开编码。 我们在这里阐述了阻挠自由和争论管理的概念，以及结合两者的各种可能性。 此外，我们将特定并发软件机制和数据结构实现的一些示例性应用程序的描述。

公开(公告)号：US09021502B2

公开(公告)日：2015-04-28

申请号：US12345179

申请日：2008-12-29

申请人： David Dice ,  Mark S. Moir

发明人： David Dice ,  Mark S. Moir

IPC分类号： G06F3/00 ,  G06F9/46 ,  G06F9/54 ,  G06F9/30

CPC分类号： G06F9/466 ,  G06F9/3009 ,  G06F9/544

摘要： In shared-memory computer systems, threads may communicate with one another using shared memory. A receiving thread may poll a message target location repeatedly to detect the delivery of a message. Such polling may cause excessive cache coherency traffic and/or congestion on various system buses and/or other interconnects. A method for inter-processor communication may reduce such bus traffic by reducing the number of reads performed and/or the number of cache coherency messages necessary to pass messages. The method may include a thread reading the value of a message target location once, and determining that this value has been modified by detecting inter-processor messages, such as cache coherence messages, indicative of such modification. In systems that support transactional memory, a thread may use transactional memory primitives to detect the cache coherence messages. This may be done by starting a transaction, reading the target memory location, and spinning until the transaction is aborted.

摘要翻译： 在共享内存计算机系统中，线程可以使用共享内存彼此进行通信。 接收线程可以重复轮询消息目标位置以检测消息的传递。 这种轮询可能导致各种系统总线和/或其他互连上的高速缓存一致性业务和/或拥塞。 用于处理器间通信的方法可以通过减少执行的读取的数量和/或传递消息所需的高速缓存一致性消息的数量来减少这种总线流量。 该方法可以包括读取消息目标位置的值一次的线程，并且通过检测指示这种修改的处理器间消息（例如高速缓存一致性消息）来确定该值已被修改。 在支持事务内存的系统中，线程可以使用事务存储器原语来检测高速缓存一致性消息。 这可以通过启动事务，读取目标内存位置和旋转直到事务中止来完成。