公开(公告)号：US20120310987A1

公开(公告)日：2012-12-06

申请号：US13167606

申请日：2011-06-23

申请人： Aleksandar Dragojevic ,  Maurice Herlihy ,  Yosef Lev ,  Mark S. Moir

发明人： Aleksandar Dragojevic ,  Maurice Herlihy ,  Yosef Lev ,  Mark S. Moir

IPC分类号： G06F17/30

CPC分类号： G06F9/467 ,  G06F12/0261 ,  G06F12/0815

摘要： The systems and methods described herein may be used to implement a shared dynamic-sized data structure using hardware transactional memory to simplify and/or improve memory management of the data structure. An application (or thread thereof) may indicate (or register) the intended use of an element of the data structure and may initialize the value of the data structure element. Thereafter, another thread or application may use hardware transactions to access the data structure element while confirming that the data structure element is still part of the dynamic data structure and/or that memory allocated to the data structure element has not been freed. Various indicators may be used determine whether memory allocated to the element element can be freed.

摘要翻译： 本文描述的系统和方法可以用于使用硬件事务存储器实现共享的动态大小的数据结构，以简化和/或改善数据结构的存储器管理。 应用程序（或其线程）可以指示（或注册）数据结构的元素的预期用途，并且可以初始化数据结构元素的值。 此后，另一个线程或应用程序可以使用硬件事务来访问数据结构元素，同时确认数据结构元素仍然是动态数据结构的一部分，和/或分配给数据结构元素的存储器尚未被释放。 可以使用各种指示器来确定分配给元素元素的内存是否可以被释放。

公开(公告)号：US09043363B2

公开(公告)日：2015-05-26

申请号：US13167606

申请日：2011-06-23

申请人： Aleksandar Dragojevic ,  Maurice Herlihy ,  Yosef Lev ,  Mark S. Moir

发明人： Aleksandar Dragojevic ,  Maurice Herlihy ,  Yosef Lev ,  Mark S. Moir

IPC分类号： G06F17/30 ,  G06F9/46

CPC分类号： G06F9/467 ,  G06F12/0261 ,  G06F12/0815

摘要： The systems and methods described herein may be used to implement a shared dynamic-sized data structure using hardware transactional memory to simplify and/or improve memory management of the data structure. An application (or thread thereof) may indicate (or register) the intended use of an element of the data structure and may initialize the value of the data structure element. Thereafter, another thread or application may use hardware transactions to access the data structure element while confirming that the data structure element is still part of the dynamic data structure and/or that memory allocated to the data structure element has not been freed. Various indicators may be used determine whether memory allocated to the element can be freed.

摘要翻译： 本文描述的系统和方法可以用于使用硬件事务存储器实现共享的动态大小的数据结构，以简化和/或改善数据结构的存储器管理。 应用程序（或其线程）可以指示（或注册）数据结构的元素的预期用途，并且可以初始化数据结构元素的值。 此后，另一个线程或应用程序可以使用硬件事务来访问数据结构元素，同时确认数据结构元素仍然是动态数据结构的一部分，和/或分配给数据结构元素的存储器尚未被释放。 可以使用各种指标来确定分配给元素的内存是否可以被释放。

公开(公告)号：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.

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

公开(公告)号：US07895401B2

公开(公告)日：2011-02-22

申请号：US11961097

申请日：2007-12-20

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

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

IPC分类号： G06F12/00

CPC分类号： G06F9/524 ,  G06F9/526 ,  Y10S707/99944 ,  Y10S707/99947

摘要： We propose a new form of software transactional memory (STM) designed to support dynamic-sized data structures, and we describe a novel non-blocking implementation. The non-blocking property we consider is obstruction-freedom. Obstruction-freedom is weaker than lock-freedom; as a result, it admits substantially simpler and more efficient implementations. An interesting feature of our obstruction-free STM implementation is its ability to use of modular contention managers to ensure progress in practice.

摘要翻译： 我们提出了一种旨在支持动态大小的数据结构的新形式的软件事务内存（STM），我们描述了一种新的非阻塞实现。 我们认为的非阻塞性是阻碍自由。 障碍自由弱于锁定自由; 因此，它承认基本上更简单和更有效的实现。 我们无障碍STM实施的一个有趣的特征是其使用模块化竞争管理人员确保实践进度的能力。

公开(公告)号：US07685583B2

公开(公告)日：2010-03-23

申请号：US10620747

申请日：2003-07-16

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

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

IPC分类号： G06F9/44 ,  G06F9/45 ,  G06F17/00

CPC分类号： G06F9/524 ,  G06F9/526 ,  Y10S707/99944 ,  Y10S707/99947

摘要： We present a technique for implementing obstruction-free atomic multi-target transactions that target special “transactionable” locations in shared memory. A programming interface for using operations based on these transactions can be structured in several ways, including as n-word compare-and-swap (NCAS) operations or as atomic sequences of single-word loads and stores (e.g., as transactional memory).

摘要翻译： 我们提出一种实现无共享存储器中特殊“可交易”位置的无阻碍原子多目标事务的技术。 用于使用基于这些事务的操作的编程接口可以以多种方式被构造，包括作为n字比较和交换（NCAS）操作，或者作为单字加载和存储（例如，作为事务存储器）的原子序列。

公开(公告)号：US20080229139A1

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

申请号：US12130635

申请日：2008-05-30

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

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

IPC分类号： H04L1/22

CPC分类号： G06F9/524 ,  G06F9/526 ,  Y10S707/99944 ,  Y10S707/99947

摘要： We explore techniques for designing nonblocking algorithms that do not require advance knowledge of the number of processes that participate, whose time complexity and space consumption both adapt to various measures, rather than being based on predefined worst-case scenarios, and that cannot be prevented from future memory reclamation by process failures. These techniques can be implemented using widely available hardware synchronization primitives. We present our techniques in the context of solutions to the well-known Collect problem. We also explain how our techniques can be exploited to achieve other results with similar properties; these include long-lived renaming and dynamic memory management for nonblocking data structures.

摘要翻译： 我们探索设计非阻塞算法的技术，这些算法不需要提前了解参与的进程数量，其时间复杂度和空间消耗都适应各种测量，而不是基于预定义的最坏情况，并且不能防止 未来内存回收过程失败。 可以使用广泛可用的硬件同步原语来实现这些技术。 我们在众所周知的收集问题的解决方案的背景下介绍我们的技术。 我们还解释了如何利用我们的技术来实现具有相似属性的其他结果; 这些包括用于非阻塞数据结构的长期重命名和动态内存管理。

公开(公告)号：US20110138134A1

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

申请号：US13030992

申请日：2011-02-18

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

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

IPC分类号： G06F12/00

CPC分类号： G06F9/524 ,  G06F9/526 ,  Y10S707/99944 ,  Y10S707/99947

摘要： We propose a new form of software transactional memory (STM) designed to support dynamic-sized data structures, and we describe a novel non-blocking implementation. The non-blocking property we consider is obstruction-freedom. Obstruction-freedom is weaker than lock-freedom; as a result, it admits substantially simpler and more efficient implementations. An interesting feature of our obstruction-free STM implementation is its ability to use of modular contention managers to ensure progress in practice.

摘要翻译： 我们提出了一种旨在支持动态大小的数据结构的新形式的软件事务内存（STM），我们描述了一种新的非阻塞实现。 我们认为的非阻塞性是阻碍自由。 障碍自由弱于锁定自由; 因此，它承认基本上更简单和更有效的实现。 我们无障碍STM实施的一个有趣的特征是其使用模块化竞争管理人员确保实践进度的能力。

公开(公告)号：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危险。

公开(公告)号：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）实现的具体解决方案，实现和算法。

公开(公告)号：US08244990B2

公开(公告)日：2012-08-14

申请号：US10620748

申请日：2003-07-16

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

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

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

CPC分类号： G06F9/524 ,  G06F9/526 ,  Y10S707/99944 ,  Y10S707/99947

摘要： We introduce obstruction-freedom—a new non-blocking condition for shared data structures that weakens the progress requirements of traditional nonblocking conditions, and as a result admits solutions that are significantly simpler and more efficient in the typical case of low contention. We demonstrate the merits of obstruction-freedom by showing how to implement an obstruction-free double-ended queue that has better properties than any previous nonblocking deque implementation of which we are aware. The beauty of obstruction-freedom is that we can modify and experiment with the contention management mechanisms without needing to modify (and therefore reverify) the underlying non-blocking algorithm. In contrast, work on different mechanisms for guaranteeing progress in the context of lock-free and wait-free algorithms has been hampered by the fact that modifications to the “helping” mechanisms has generally required the proofs for the entire algorithm to be done again.

摘要翻译： 我们引入阻碍自由 - 一种新的非阻塞条件，用于共享数据结构，从而削弱传统非阻塞条件的进度要求，从而承认在低竞争的典型情况下，解决方案显着简化和更有效率。 我们通过展示如何实现无阻塞的双端口队列，证明阻塞自由的优点，该队列具有比以前任何我们所知道的任何以前的非阻塞deque实现更好的性能。 阻碍自由的优点在于，我们可以修改和尝试竞争管理机制，而无需修改（并因此重新验证）底层的非阻塞算法。 相比之下，在“无障碍和无等待”算法的上下文中保证进度的不同机制的工作受到以下事实的阻碍：对“帮助”机制的修改通常需要再次完成整个算法的证明。