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

1. 发明申请

US20060218561A1 Code preparation technique employing lock-free pointer operations 有权
标题翻译：采用无锁指针操作的代码准备技术
公开(公告)号：US20060218561A1
公开(公告)日：2006-09-28
申请号：US11343678
申请日：2006-01-30
申请人： Mark Moir , David Detlefs , Simon Doherty , Maurice Herlihy , Victor Luchangco , Paul Martin , Guy Steele
发明人： Mark Moir , David Detlefs , Simon Doherty , Maurice Herlihy , Victor Luchangco , Paul Martin , Guy Steele
IPC分类号： G06F9/46
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.
摘要翻译：已经发现了一种方法，用于将垃圾回收依赖算法，共享对象实现和/或并发软件机制转换为不假定存在独立或执行环境（垃圾收集器）的形式。使用本文描述的技术设计或变换的算法，共享对象实现和/或机制使用无锁指针操作来提供存储的显式回收。转换可以应用于无锁算法和共享对象实现，并保持这种算法和实现的锁定自由度。因此，依赖于垃圾回收执行环境的现有和将来的无锁算法和共享对象实现可以在不提供垃圾回收的环境中被利用。此外，使用如本文所述的无锁定指针操作的使用显式回收存储的算法和共享对象实现可以用于实现垃圾收集器本身。

2. 发明申请

US20060037026A1 Lightweight reference counting using single-target synchronization 有权
标题翻译：使用单目标同步的轻量级参考计数
公开(公告)号：US20060037026A1
公开(公告)日：2006-02-16
申请号：US11226038
申请日：2005-09-14
申请人： Simon Doherty , Maurice Herlihy , Victor Luchangco , Mark Moir
发明人： Simon Doherty , Maurice Herlihy , Victor Luchangco , Mark Moir
IPC分类号： G06F9/46
CPC分类号： G06F12/0261 , G06F9/46 , G06F9/526
摘要： We have developed a methodology 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.
摘要翻译：我们已经开发了一种将垃圾回收依赖算法，共享对象实现和/或并发软件机制转换为不假定存在独立或执行环境（垃圾收集器）的形式的方法。使用本文描述的技术设计或变换的算法，共享对象实现和/或机制使用无锁指针操作来提供存储的显式回收。转换可以应用于无锁算法和共享对象实现，并保持这种算法和实现的锁定自由度。因此，依赖于垃圾回收执行环境的现有和将来的无锁算法和共享对象实现可以在不提供垃圾回收的环境中被利用。此外，使用如本文所述的无锁定指针操作的使用显式回收存储的算法和共享对象实现可以用于实现垃圾收集器本身。

3. 发明申请

US20060161737A1 Concurrency technique for shared objects 审中-公开
标题翻译：共享对象的并发技术
公开(公告)号：US20060161737A1
公开(公告)日：2006-07-20
申请号：US11384627
申请日：2006-03-20
申请人： Paul Martin , David Detlefs , Alexander Garthwaite , Guy Steele , Mark Moir
发明人： Paul Martin , David Detlefs , Alexander Garthwaite , Guy Steele , Mark Moir
IPC分类号： G06F13/28
CPC分类号： G06F7/785 , G06F9/30032 , G06F9/526 , G06F9/544 , G06F2205/064 , G06F2209/521
摘要： In some embodiments, a Hat Trick deque requires only a single DCAS for most pushes and pops. The left and right ends do not interfere with each other until there is one or fewer items in the queue, and then a DCAS adjudicates between competing pops. By choosing a granularity greater than a single node, the user can amortize the costs of adding additional storage over multiple push (and pop) operations that employ the added storage. A suitable removal strategy can provide similar amortization advantages. The technique of leaving spare nodes linked in the structure allows an indefinite number of pushes and pops at a given deque end to proceed without the need to invoke memory allocation or reclamation so long as the difference between the number of pushes and the number of pops remains within given bounds. Both garbage collection dependent and explicit reclamation implementations are described.
摘要翻译：在一些实施例中，帽子技巧deque仅需要单个DCAS用于大多数按压和弹出。在队列中有一个或多个项目之前，左右两端不会相互干扰，然后DCAS在竞争弹出之间进行裁决。通过选择大于单个节点的粒度，用户可以通过使用添加的存储的多个推送（和弹出）操作来分摊添加附加存储的成本。合适的清除策略可以提供类似的摊销优势。在结构中链接的备用节点的技术允许在给定的deque端的无限数量的推送和弹出进行，而不需要调用内存分配或回收，只要推送次数和流量数之间的差异保持不变在给定范围内。描述垃圾收集相关和显式回收实现。

4. 发明申请

US20080098181A1 Software Transactional Memory for Dynamically Sizable Shared Data Structures 有权
标题翻译：用于动态相似的共享数据结构的软件事务内存
公开(公告)号：US20080098181A1
公开(公告)日：2008-04-24
申请号：US11961097
申请日：2007-12-20
申请人： Mark Moir , Victor Luchangco , Maurice Herlihy
发明人： Mark Moir , Victor 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实施的一个有趣的特征是其使用模块化竞争管理人员确保实践进度的能力。

5. 发明申请

US20060173885A1 Obstruction-free data structures and mechanisms with separable and/or substitutable contention management mechanisms 有权
标题翻译：无障碍的数据结构和具有可分离和/或可替换的争用管理机制的机制
公开(公告)号：US20060173885A1
公开(公告)日：2006-08-03
申请号：US11106790
申请日：2005-04-15
申请人： Mark Moir , Victor Luchangco , Maurice Herlihy
发明人： Mark Moir , Victor Luchangco , Maurice Herlihy
IPC分类号： G06F17/00 , G06F7/00
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.
摘要翻译：我们教授一种强大的方法，大大简化了非阻塞机制和数据结构的设计，部分原因是在很大程度上分离了正确性和进度的问题。在高层次上，我们的方法包括设计一个“无阻碍”的所需机制或数据结构的实施，然后将其与争用管理机制结合起来，其作用是促进无障碍实施进展的条件放心一般来说，争用管理机制在语义上与可以应用于其的无障碍并发共享/可共享对象实现是可分离的。在某些情况下，争用管理机制实际上可以与无障碍的实现分开编码。我们在这里阐述了阻挠自由和争论管理的概念，以及结合两者的各种可能性。此外，我们将特定并发软件机制和数据结构实现的一些示例性应用程序的描述。

6. 发明申请

US20080077748A1 Efficient Non-Blocking K-Compare-Single-Swap Operation 有权
标题翻译：高效的非阻塞K比较单互换操作
公开(公告)号：US20080077748A1
公开(公告)日：2008-03-27
申请号：US11864624
申请日：2007-09-28
申请人： Nir Shavit , Mark Moir , Victor Luchangco
发明人： Nir Shavit , Mark Moir , Victor Luchangco
IPC分类号： G06F12/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. 发明申请

US20080109608A1 Efficient Non-Blocking K-Compare-Single-Swap Operation 有权
公开(公告)号：US20080109608A1
公开(公告)日：2008-05-08
申请号：US11864667
申请日：2007-09-28
申请人： Nir Shavit , Mark Moir , Victor Luchangco
发明人： Nir Shavit , Mark Moir , Victor Luchangco
IPC分类号： G06F12/16 , G06F12/02 , G06F9/30
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.

8. 发明申请

US20080077775A1 Efficient Non-Blocking K-Compare-Single-Swap Operation 有权
公开(公告)号：US20080077775A1
公开(公告)日：2008-03-27
申请号：US11864649
申请日：2007-09-28
申请人： Nir Shavit , Mark Moir , Victor Luchangco
发明人： Nir Shavit , Mark Moir , Victor Luchangco
IPC分类号： G06F9/312 , G06F9/455
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.

9. 发明申请

US20070157202A1 Ensuring progress in a system that supports execution of obstruction-free operations 有权
标题翻译：确保在支持执行无障碍操作的系统中取得进展
公开(公告)号：US20070157202A1
公开(公告)日：2007-07-05
申请号：US11325062
申请日：2006-01-03
申请人： Mark Moir , Victor Luchangco , Nir Shavit
发明人： Mark Moir , Victor Luchangco , Nir Shavit
IPC分类号： G06F9/46
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.
摘要翻译：本发明的一个实施例提供一种确保在支持执行无障碍操作的环境中进行的系统。在执行期间，当进程p 调用操作时，系统检查紧急标志，该标志指示进程保证机制是否被激活。如果设置了恐慌标志，则会启动进度保证机制，从而使系统尝试通过协调进程之间的动作来尝试执行操作，以确保进程尽可能在进程之间发生争用。另一方面，如果不设置紧急状态标志，则系统试图执行操作，基本上就像进度保证机制不存在一样。在这种情况下，如果存在进程之间的争用妨碍进展的指示，则系统设置紧急标志，这导致进程确保机制被激活，以便进程将协调其动作以确保进行进展。

10. 发明申请

US20060200632A1 Selectively unmarking load-marked cache lines during transactional program execution 有权
公开(公告)号：US20060200632A1
公开(公告)日：2006-09-07
申请号：US11399049
申请日：2006-04-06
申请人： Marc Tremblay , Quinn Jacobson , Shailender Chaudhry , Mark Moir , Maurice Herlihy
发明人： Marc Tremblay , Quinn Jacobson , Shailender Chaudhry , Mark Moir , Maurice Herlihy
IPC分类号： G06F12/14
CPC分类号： G06F12/0815 , G06F9/3004 , G06F9/30087 , G06F9/3834 , G06F9/3836 , G06F9/3842 , G06F9/3851 , G06F9/3857 , G06F9/3863 , G06F9/467 , G06F12/0862
摘要： One embodiment of the present invention provides a system that facilitates selectively unmarking load-marked cache lines during transactional program execution, wherein load-marked cache lines are monitored during transactional execution to detect interfering accesses from other threads. During operation, the system encounters a release instruction during transactional execution of a block of instructions. In response to the release instruction, the system modifies the state of cache lines, which are specially load-marked to indicate they can be released from monitoring, to account for the release instruction being encountered. In doing so, the system can potentially cause the specially load-marked cache lines to become unmarked. In a variation on this embodiment, upon encountering a commit-and-start-new-transaction instruction, the system modifies load-marked cache lines to account for the commit-and-start-new-transaction instruction being encountered. In doing so, the system causes normally load-marked cache lines to become unmarked, while other specially load-marked cache lines may remain load-marked past the commit-and-start-new-transaction instruction.

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式