-
1.发明授权Obstruction-free data structures and mechanisms with separable and/or substitutable contention management mechanisms 有权无障碍的数据结构和具有可分离和/或可替换的争用管理机制的机制公开(公告)号：US09052944B2
公开(公告)日：2015-06-09
申请号：US11106790
申请日：2005-04-15
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.
摘要翻译： 我们教授一种强大的方法，大大简化了非阻塞机制和数据结构的设计，部分原因是在很大程度上分离了正确性和进度的问题。 在高层次上，我们的方法包括设计一个“无障碍”的所需机制或数据结构的实施，然后将其与争用管理机制结合起来，其作用是促进无障碍执行进展的条件 放心 一般来说，争用管理机制在语义上与可以应用于其的无障碍并发共享/可共享对象实现是可分离的。 在某些情况下，争用管理机制实际上可以与无障碍的实现分开编码。 我们在这里阐述了阻挠自由和争论管理的概念，以及结合两者的各种可能性。 此外，我们将特定并发软件机制和数据结构实现的一些示例性应用程序的描述。
-
2.发明授权Software transactional memory for dynamically sizable shared data structures 有权用于动态大小的共享数据结构的软件事务内存公开(公告)号：US07895401B2
公开(公告)日：2011-02-22
申请号：US11961097
申请日：2007-12-20
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实施的一个有趣的特征是其使用模块化竞争管理人员确保实践进度的能力。
-
3.发明授权Obstruction-free mechanism for atomic update of multiple non-contiguous locations in shared memory 有权共享内存中多个不连续位置的原子更新的无障碍机制公开(公告)号：US07685583B2
公开(公告)日：2010-03-23
申请号：US10620747
申请日：2003-07-16
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
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.
摘要翻译： 我们探索设计非阻塞算法的技术，这些算法不需要提前了解参与的进程数量，其时间复杂度和空间消耗都适应各种测量，而不是基于预定义的最坏情况，并且不能防止 未来内存回收过程失败。 可以使用广泛可用的硬件同步原语来实现这些技术。 我们在众所周知的收集问题的解决方案的背景下介绍我们的技术。 我们还解释了如何利用我们的技术来实现具有相似属性的其他结果; 这些包括用于非阻塞数据结构的长期重命名和动态内存管理。
-
5.发明申请Software Transactional Memory for Dynamically Sizable Shared Data Structures 有权用于动态相似的共享数据结构的软件事务内存公开(公告)号：US20110138134A1
公开(公告)日：2011-06-09
申请号：US13030992
申请日：2011-02-18
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实施的一个有趣的特征是其使用模块化竞争管理人员确保实践进度的能力。
-
公开(公告)号：US08019785B2
公开(公告)日：2011-09-13
申请号：US12130635
申请日：2008-05-30
IPC分类号： G06F7/00
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.
摘要翻译： 我们探索设计非阻塞算法的技术，这些算法不需要提前了解参与过程的数量，其时间复杂度和空间消耗都适应于各种测量，而不是基于预定义的最坏情况，并且不能防止 未来内存回收过程失败。 可以使用广泛可用的硬件同步原语来实现这些技术。 我们在众所周知的收集问题的解决方案的背景下介绍我们的技术。 我们还解释了如何利用我们的技术来实现具有相似属性的其他结果; 这些包括用于非阻塞数据结构的长期重命名和动态内存管理。
-
公开(公告)号：US07788242B2
公开(公告)日：2010-08-31
申请号：US11508762
申请日：2006-08-23
CPC分类号： G06F17/30362 , G06F17/30958
摘要： A method for inserting an object into a concurrent set including obtaining a key associated with the object, traversing the concurrent set using a first thread containing the key, identifying a first insertion point while traversing the concurrent set, where the first insertion point is before a current node and after a predecessor node, obtaining a first lock for the predecessor node after identifying the first insertion point, validating the predecessor node and the current node after obtaining the lock, inserting a new node into the concurrent set after validating, where the new node is associated with the object, and releasing the first lock after inserting the new node.
摘要翻译： 一种用于将对象插入到并发集合中的方法，包括获得与对象相关联的密钥，使用包含密钥的第一线程遍历并发集合，在遍历并发集合的同时识别第一插入点，其中第一插入点在 当前节点，并且在前导节点之后，在识别出第一插入点之后为先前节点获得第一锁定，在获得锁定之后验证前导节点和当前节点，在验证之后将新节点插入并发集合，其中新的 节点与对象相关联，并在插入新节点后释放第一个锁。
-
公开(公告)号：US20080059470A1
公开(公告)日：2008-03-06
申请号：US11508762
申请日：2006-08-23
IPC分类号： G06F17/30
CPC分类号： G06F17/30362 , G06F17/30958
摘要： A method for inserting an object into a concurrent set including obtaining a key associated with the object, traversing the concurrent set using a first thread containing the key, identifying a first insertion point while traversing the concurrent set, where the first insertion point is before a current node and after a predecessor node, obtaining a first lock for the predecessor node after identifying the first insertion point, validating the predecessor node and the current node after obtaining the lock, inserting a new node into the concurrent set after validating, where the new node is associated with the object, and releasing the first lock after inserting the new node.
摘要翻译： 一种用于将对象插入到并发集合中的方法，包括获得与对象相关联的密钥，使用包含密钥的第一线程遍历并发集合，在遍历并发集合的同时识别第一插入点，其中第一插入点在 当前节点，并且在前导节点之后，在识别出第一插入点之后为先前节点获得第一锁定，在获得锁定之后验证前导节点和当前节点，在验证之后将新节点插入并发集合，其中新的 节点与对象相关联，并在插入新节点后释放第一个锁。
-
9.发明授权Software transactional memory for dynamically sizable shared data structures 有权用于动态大小的共享数据结构的软件事务内存公开(公告)号：US07328316B2
公开(公告)日：2008-02-05
申请号：US10621072
申请日：2003-07-16
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实施的一个有趣的特征是其使用模块化竞争管理人员确保实践进度的能力。
-
公开(公告)号：US08244990B2
公开(公告)日：2012-08-14
申请号：US10620748
申请日：2003-07-16
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实现更好的性能。 阻碍自由的优点在于，我们可以修改和尝试竞争管理机制，而无需修改（并因此重新验证）底层的非阻塞算法。 相比之下，在“无障碍和无等待”算法的上下文中保证进度的不同机制的工作受到以下事实的阻碍：对“帮助”机制的修改通常需要再次完成整个算法的证明。
-
-
-
-
-
-
-
-
-
搜索结果
116 条记录 (耗时 0.025 秒)
