公开(公告)号：US07870344B2

公开(公告)日：2011-01-11

申请号：US11864649

申请日：2007-09-28

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

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

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

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）。 我们的实施是无障碍的。 因此，在无争议的情况下是高效的，并且依赖于竞争案件中的争用管理机制。 它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。 此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。

公开(公告)号：US07788242B2

公开(公告)日：2010-08-31

申请号：US11508762

申请日：2006-08-23

申请人： Nir N. Shavit ,  Maurice Herlihy ,  Steven K. Heller ,  Victor M. Luchangco ,  Mark S. Moir

发明人： Nir N. Shavit ,  Maurice Herlihy ,  Steven K. Heller ,  Victor M. Luchangco ,  Mark S. Moir

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

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

申请人： Nir N. Shavit ,  Maurice Herlihy ,  Steven K. Heller ,  Victor M. Luchangco ,  Mark S. Moir

发明人： Nir N. Shavit ,  Maurice Herlihy ,  Steven K. Heller ,  Victor M. Luchangco ,  Mark S. Moir

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.

摘要翻译： 一种用于将对象插入到并发集合中的方法，包括获得与对象相关联的密钥，使用包含密钥的第一线程遍历并发集合，在遍历并发集合的同时识别第一插入点，其中第一插入点在 当前节点，并且在前导节点之后，在识别出第一插入点之后为先前节点获得第一锁定，在获得锁定之后验证前导节点和当前节点，在验证之后将新节点插入并发集合，其中新的 节点与对象相关联，并在插入新节点后释放第一个锁。

公开(公告)号：US07328316B2

公开(公告)日：2008-02-05

申请号：US10621072

申请日：2003-07-16

申请人： 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实施的一个有趣的特征是其使用模块化竞争管理人员确保实践进度的能力。

公开(公告)号：US07293143B1

公开(公告)日：2007-11-06

申请号：US10670495

申请日：2003-09-24

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

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

IPC分类号： G06F12/00 ,  G06F7/00 ,  G06F13/00 ,  G06F12/16

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）。 我们的实施是无障碍的。 因此，在无争议的情况下是高效的，并且依赖于竞争案件中的争用管理机制。 它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。 此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。

公开(公告)号：US09430275B2

公开(公告)日：2016-08-30

申请号：US13170026

申请日：2011-06-27

申请人： Virendra J. Marathe ,  Victor M. Luchangco

发明人： Virendra J. Marathe ,  Victor M. Luchangco

IPC分类号： G06F9/455 ,  G06F9/46

CPC分类号： G06F9/467

摘要： Transactional memory implementations may be extended to support transaction communicators and/or transaction condition variables for which transaction isolation is relaxed, and through which concurrent transactions can communicate and be synchronized with each other. Transactional accesses to these objects may not be isolated unless called within communicator-isolating transactions. A waiter transaction may invoke a wait method of a transaction condition variable, be added to a wait list for the variable, and be suspended pending notification of a notification event from a notify method of the variable. A notifier transaction may invoke a notify method of the variable, which may remove the waiter from the wait list, schedule the waiter transaction for resumed execution, and notify the waiter of the notification event. A waiter transaction may commit only if the corresponding notifier transaction commits. If the waiter transaction aborts, the notification may be forwarded to another waiter.

摘要翻译： 事务性存储器实现可以被扩展以支持事务隔离被放宽的事务通信器和/或事务条件变量，以及通过哪些并发事务可以彼此通信和同步。 对这些对象的事务访问可能不被隔离，除非在通信器隔离事务中被调用。 服务员事务可以调用事务条件变量的等待方法，被添加到变量的等待列表中，并且从变量的通知方法通知一个通知事件。 通知器事务可以调用变量的通知方法，该方法可以从等待列表中移除服务员，安排服务员事务以恢复执行，并通知服务员通知事件。 只有当相应的通知程序事务提交时，服务员事务才可能执行。 如果服务员事务中止，通知可以转发给另一个服务员。

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

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

公开(公告)号：US08473952B2

公开(公告)日：2013-06-25

申请号：US12828105

申请日：2010-06-30

申请人： Virendra J. Marathe ,  Victor M. Luchangco

发明人： Virendra J. Marathe ,  Victor M. Luchangco

IPC分类号： G06F9/46

CPC分类号： G06F9/467 ,  G06F11/1474

摘要： Transactional memory implementations may be extended to include special transaction communicator objects through which concurrent transactions can communicate. Changes by a first transaction to a communicator may be visible to concurrent transactions before the first transaction commits. Although isolation of transactions may be compromised by such communication, the effects of this compromise may be limited by tracking dependencies among transactions, and preventing any transaction from committing unless every transaction whose changes it has observed also commits. For example, mutually dependent or cyclically dependent transactions may commit or abort together. Transactions that do not communicate with each other may remain isolated. The system may provide a communicator-isolating transaction that ensures isolation even for accesses to communicators, which may be implemented using nesting transactions. True (e.g., read-after-write) dependencies, ordering (e.g., write-after-write) dependencies, and/or anti-dependencies (e.g., write-after-read dependencies) may be tracked, and a resulting dependency graph may be perused by the commit protocol.

摘要翻译： 可以将事务性存储器实现扩展到包括特殊的事务通信器对象，并发事务可以通过该对象进行通信。 在第一个事务提交之前，第一个事务对通信器的更改可能对并发事务可见。 虽然交易的隔离可能会受到此类通信的影响，但是通过跟踪事务之间的依赖关系可以限制此妥协的影响，并且防止任何事务提交，除非其所观察到的更改的每个事务也都提交。 例如，相互依赖或循环依赖的交易可能会一起提交或中止。 不相互通信的事务可能会被隔离。 该系统可以提供隔离通信的事务，即使对于可以使用嵌套事务来实现的对通信器的访问也可以确保隔离。 可以跟踪真（例如，写后读取）依赖性，排序（例如，写后写入）依赖性和/或反依赖性（例如，读后读依赖性），并且所得到的依赖图可以 被提交协议所使用。

公开(公告)号：US20120311273A1

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

申请号：US13170026

申请日：2011-06-27

申请人： Virendra J. Marathe ,  Victor M. Luchangco

发明人： Virendra J. Marathe ,  Victor M. Luchangco

IPC分类号： G06F12/00

CPC分类号： G06F9/467

摘要： The systems and methods described herein may extend transactional memory implementations to support transaction communicators and/or transaction condition variables for which transaction isolation is relaxed, and through which concurrent transactions can communicate and be synchronized with each other. Transactional accesses to these objects may not be isolated unless called within communicator-isolating transactions. A waiter transaction may invoke a wait method of a transaction condition variable, be added to a wait list for the variable, and be suspended pending notification of a notification event from a notify method of the variable. A notifier transaction may invoke a notify method of the variable, which may remove the waiter from the wait list, schedule the waiter transaction for resumed execution, and notify the waiter of the notification event. A waiter transaction may commit only if the corresponding notifier transaction commits. If the waiter transaction aborts, the notification may be forwarded to another waiter.

摘要翻译： 本文描述的系统和方法可以扩展事务存储器实现以支持事务隔离被放宽的事务通信器和/或事务条件变量，以及通过哪些并发事务可以彼此通信和同步。 对这些对象的事务访问可能不被隔离，除非在通信器隔离事务中被调用。 服务员事务可以调用事务条件变量的等待方法，被添加到变量的等待列表中，并且从变量的通知方法通知一个通知事件。 通知器事务可以调用变量的通知方法，该方法可以从等待列表中移除服务员，安排服务员事务以恢复执行，并通知服务员通知事件。 只有当相应的通知程序事务提交时，服务员事务才可能执行。 如果服务员事务中止，通知可以转发给另一个服务员。