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

摘要翻译： 已经发现了一种方法，用于将垃圾回收依赖算法，共享对象实现和/或并发软件机制转换为不假定存在独立或执行环境（垃圾收集器）的形式。 使用本文描述的技术设计或变换的算法，共享对象实现和/或机制使用无锁指针操作来提供存储的显式回收。 转换可以应用于无锁算法和共享对象实现，并保持这种算法和实现的锁定自由度。 因此，依赖于垃圾回收执行环境的现有和将来的无锁算法和共享对象实现可以在不提供垃圾回收的环境中被利用。 此外，使用如本文所述的无锁定指针操作的使用显式回收存储的算法和共享对象实现可以用于实现垃圾收集器本身。

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

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

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

摘要翻译： 我们已经开发了一种将垃圾回收依赖算法，共享对象实现和/或并发软件机制转换为不假定存在独立或执行环境（垃圾收集器）的形式的方法。 使用本文描述的技术设计或变换的算法，共享对象实现和/或机制使用无锁指针操作来提供存储的显式回收。 转换可以应用于无锁算法和共享对象实现，并保持这种算法和实现的锁定自由度。 因此，依赖于垃圾回收执行环境的现有和将来的无锁算法和共享对象实现可以在不提供垃圾回收的环境中被利用。 此外，使用如本文所述的无锁定指针操作的使用显式回收存储的算法和共享对象实现可以用于实现垃圾收集器本身。