专利快速检索-快速检索全球专利，免费商用专利数据库-IPRDB

1. 发明授权

US07424477B1 Shared synchronized skip-list data structure and technique employing linearizable operations 有权
标题翻译：共享同步跳过列表数据结构和采用线性化操作的技术
公开(公告)号：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.
摘要翻译：本文描述了一组结构和技术，由此可以以无锁的方式实现示例性并发共享对象，即共享跳过列表。实际上，我们已经开发出了一些无锁共享的跳过列表的许多有趣的变体，包括可用于提供无锁共享字典的变体。在一些变型中，实现了键值字典。

2. 发明授权

US07788242B2 Method and system for implementing a concurrent set of objects 有权
标题翻译：用于实现一组并发对象的方法和系统
公开(公告)号：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.
摘要翻译：一种用于将对象插入到并发集合中的方法，包括获得与对象相关联的密钥，使用包含密钥的第一线程遍历并发集合，在遍历并发集合的同时识别第一插入点，其中第一插入点在当前节点，并且在前导节点之后，在识别出第一插入点之后为先前节点获得第一锁定，在获得锁定之后验证前导节点和当前节点，在验证之后将新节点插入并发集合，其中新的节点与对象相关联，并在插入新节点后释放第一个锁。

3. 发明申请

US20080059470A1 Method and system for implementing a concurrent set of objects 有权
标题翻译：用于实现一组并发对象的方法和系统
公开(公告)号：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.
摘要翻译：一种用于将对象插入到并发集合中的方法，包括获得与对象相关联的密钥，使用包含密钥的第一线程遍历并发集合，在遍历并发集合的同时识别第一插入点，其中第一插入点在当前节点，并且在前导节点之后，在识别出第一插入点之后为先前节点获得第一锁定，在获得锁定之后验证前导节点和当前节点，在验证之后将新节点插入并发集合，其中新的节点与对象相关联，并在插入新节点后释放第一个锁。

4. 发明授权

US06826757B2 Lock-free implementation of concurrent shared object with dynamic node allocation and distinguishing pointer value 有权
标题翻译：并行共享对象的锁定实现与动态节点分配和区分指针值
公开(公告)号：US06826757B2
公开(公告)日：2004-11-30
申请号：US09837670
申请日：2001-04-18
申请人： Guy L. Steele, Jr. , Alexander T. Garthwaite , Paul A. Martin , Nir N. Shavit , Mark S. Moir , David L. Detlefs
发明人： Guy L. Steele, Jr. , Alexander T. Garthwaite , Paul A. Martin , Nir N. Shavit , Mark S. Moir , David L. Detlefs
IPC分类号： G06F946
CPC分类号： G06F9/52
摘要： A novel linked-list-based concurrent shared object implementation has been developed that provides non-blocking and linearizable access to the concurrent shared object. In an application of the underlying techniques to a deque, non-blocking completion of access operations is achieved without restricting concurrency in accessing the deque's two ends. In various realizations in accordance with the present invention, the set of values that may be pushed onto a shared object is not constrained by use of distinguishing values. In addition, an explicit reclamation embodiment facilitates use in environments or applications where automatic reclamation of storage is unavailable or impractical.
摘要翻译：已经开发了一种基于链表的并行共享对象实现，它提供对并发共享对象的非阻塞和线性化访问。在底层技术应用于deque时，实现访问操作的非阻塞完成，而不会限制访问deque的两端的并发性。在根据本发明的各种实现中，可以推送到共享对象上的值集合不受使用区分值的约束。此外，显式的回收实施例有利于在存储器的自动回收不可用或不切实际的环境或应用中使用。

5. 发明授权

US07805467B2 Code preparation technique employing lock-free pointer operations 有权
标题翻译：采用无锁指针操作的代码准备技术
公开(公告)号：US07805467B2
公开(公告)日：2010-09-28
申请号：US11343678
申请日：2006-01-30
申请人： Mark S. Moir , David L. Detlefs , Simon Doherty , Maurice P. Herlihy , Victor M. Luchangco , Paul A. Martin , Guy L. Steele, Jr.
发明人： Mark S. Moir , David L. Detlefs , Simon Doherty , Maurice P. Herlihy , Victor M. Luchangco , Paul A. Martin , Guy L. Steele, Jr.
IPC分类号： G06F12/00
CPC分类号： G06F12/0261 , G06F9/46 , G06F9/526
摘要： A methodology has been discovered for transforming garbage collection-dependent algorithms, shared object implementations and/or concurrent software mechanisms into a form that does not presume the existence of an independent, or execution environment provided, garbage collector. Algorithms, shared object implementations and/or mechanisms designed or transformed using techniques described herein provide explicit reclamation of storage using lock-free pointer operations. Transformations can be applied to lock-free algorithms and shared object implementations and preserve lock-freedom of such algorithms and implementations. As a result, existing and future lock-free algorithms and shared object implementations that depend on a garbage-collected execution environment can be exploited in environments that do not provide garbage collection. Furthermore, algorithms and shared object implementations that employ explicit reclamation of storage using lock-free pointer operations such as described herein may be employed in the implementation of a garbage collector itself.
摘要翻译：已经发现了一种方法，用于将垃圾回收依赖算法，共享对象实现和/或并发软件机制转换为不假定存在独立或执行环境（垃圾收集器）的形式。使用本文描述的技术设计或变换的算法，共享对象实现和/或机制使用无锁指针操作来提供存储的显式回收。转换可以应用于无锁算法和共享对象实现，并保持这种算法和实现的锁定自由度。因此，依赖于垃圾回收执行环境的现有和将来的无锁算法和共享对象实现可以在不提供垃圾回收的环境中被利用。此外，使用如本文所述的无锁定指针操作的使用显式回收存储的算法和共享对象实现可以用于实现垃圾收集器本身。

6. 发明授权

US07870344B2 Method and apparatus for emulating linked-load/store-conditional synchronization 有权
标题翻译：用于模拟链接加载/存储条件同步的方法和装置
公开(公告)号：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）。我们的实施是无障碍的。因此，在无争议的情况下是高效的，并且依赖于竞争案件中的争用管理机制。它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。

7. 发明授权

US07293143B1 Efficient non-blocking k-compare-single-swap operation 有权
标题翻译：高效无阻塞k-比较 - 单互换操作
公开(公告)号：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）。我们的实施是无障碍的。因此，在无争议的情况下是高效的，并且依赖于竞争案件中的争用管理机制。它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。

8. 发明授权

US09135178B2 Efficient non-blocking K-compare-single-swap operation 有权
标题翻译：高效无阻塞K比较 - 单互换操作
公开(公告)号：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）。我们的实施是无障碍的。因此，在无争议的情况下是高效的，并且依赖于竞争案件中的争用管理机制。它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。

9. 发明授权

US07793053B2 Efficient non-blocking k-compare-single-swap operation 有权
标题翻译：高效无阻塞k-比较 - 单互换操作
公开(公告)号：US07793053B2
公开(公告)日：2010-09-07
申请号：US11864574
申请日：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）。我们的实施是无障碍的。因此，在无争议的情况下效率高，依靠竞争管理机制。它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。

10. 发明授权

US07475228B2 Ensuring progress in a system that supports execution of obstruction-free operations 有权
标题翻译：确保在支持执行无障碍操作的系统中取得进展
公开(公告)号：US07475228B2
公开(公告)日：2009-01-06
申请号：US11325062
申请日：2006-01-03
申请人： Mark S. Moir , Victor M. Luchangco , Nir N. Shavit
发明人： Mark S. Moir , Victor M. Luchangco , Nir N. Shavit
IPC分类号： G06F9/52
CPC分类号： G06F9/52
摘要： One embodiment of the present invention provides a system that ensures that progress is made in an environment that supports execution of obstruction-free operations. During execution, when a process pi invokes an operation, the system checks a panic flag, which indicates whether a progress-ensuring mechanism is to be activated. If the panic flag is set, the progress-ensuring mechanism is activated, which causes the system to attempt to perform the operation by coordinating actions between processes to ensure that progress is made in spite of contention between the processes. On the other hand, if the panic flag is not set, the system attempts to perform the operation essentially as if the progress-ensuring mechanism were not present. In this case, if there is an indication that contention between processes is impeding progress, the system sets the panic flag, which causes the progress-ensuring mechanism to be activated so that processes will coordinate their actions to ensure that progress is made.
摘要翻译：本发明的一个实施例提供一种确保在支持执行无障碍操作的环境中进行的系统。在执行期间，当进程pi调用操作时，系统检查一个紧急标志，指示是否激活进度保证机制。如果设置了恐慌标志，则会启动进度保证机制，从而使系统尝试通过协调进程之间的动作来尝试执行操作，以确保进程尽可能在进程之间发生争用。另一方面，如果不设置紧急状态标志，则系统试图执行操作，基本上就像进度保证机制不存在一样。在这种情况下，如果存在进程之间的争用妨碍进展的指示，则系统设置紧急标志，这导致进程确保机制被激活，以便进程将协调其动作以确保进行进展。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式