公开(公告)号：US07533221B1

公开(公告)日：2009-05-12

申请号：US11026850

申请日：2004-12-30

申请人： Simon Doherty ,  Mark S. Moir ,  Victor Luchangco ,  Maurice P. Herlihy

发明人： Simon Doherty ,  Mark S. Moir ,  Victor Luchangco ,  Maurice P. Herlihy

IPC分类号： G06F12/00

CPC分类号： G06F12/023 ,  G06F9/526

摘要： Many conventional lock-free data structures exploit techniques that are possible only because state-of-the-art 64-bit processors are still running 32-bit operating systems and applications. As software catches up to hardware, “64-bit-clean” lock-free data structures, which cannot use such techniques, are needed. We present several 64-bit-clean lock-free implementations: including load-linked/store conditional variables of arbitrary size, a FIFO queue, and a freelist. In addition to being portable to 64-bit software (or more generally full-architectural-width pointer operations), our implementations also improve on existing techniques in that they are (or can be) space-adaptive and do not require a priori knowledge of the number of threads that will access them.

摘要翻译： 许多传统的无锁数据结构利用了仅仅因为最先进的64位处理器仍在运行32位操作系统和应用程序而可能的技术。 随着软件的升级，硬件需要“64位清理”的无锁数据结构，不能使用这种技术。 我们提出了几个64位无干扰的无锁实现：包括任意大小的加载链接/存储条件变量，FIFO队列和freelist。 除了可移植到64位软件（或更通常的全架构宽度指针操作）之外，我们的实现还改进了现有技术，因为它们（或可以）是空间自适应的，并且不需要先验知识 将访问它们的线程数。

公开(公告)号：US07577798B1

公开(公告)日：2009-08-18

申请号：US11026255

申请日：2004-12-30

申请人： Mark S. Moir ,  Simon Doherty ,  Victor Luchangco ,  Maurice P. Herlihy

发明人： Mark S. Moir ,  Simon Doherty ,  Victor Luchangco ,  Maurice P. Herlihy

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

CPC分类号： G06F9/526 ,  G06F2209/521

摘要： Many conventional lock-free data structures exploit techniques that are possible only because state-of-the-art 64-bit processors are still running 32-bit operating systems and applications. As software catches up to hardware, “64-bit-clean” lock-free data structures, which cannot use such techniques, are needed. We present several 64-bit-clean lock-free implementations: including load-linked/store conditional variables of arbitrary size, a FIFO queue, and a freelist. In addition to being portable to 64-bit software (or more generally full-architectural-width pointer operations), our implementations also improve on existing techniques in that they are (or can be) space-adaptive and do not require a priori knowledge of the number of threads that will access them.

摘要翻译： 许多传统的无锁数据结构利用了仅仅因为最先进的64位处理器仍在运行32位操作系统和应用程序而可能的技术。 随着软件的升级，硬件需要“64位清理”的无锁数据结构，不能使用这种技术。 我们提出了几个64位无干扰的无锁实现：包括任意大小的加载链接/存储条件变量，FIFO队列和freelist。 除了可移植到64位软件（或更通常的全架构宽度指针操作）之外，我们的实现还改进了现有技术，因为它们（或可以）是空间自适应的，并且不需要先验知识 将访问它们的线程数。

公开(公告)号：US07769791B2

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

申请号：US11226038

申请日：2005-09-14

申请人： Simon Doherty ,  Maurice P. Herlihy ,  Victor M. Luchangco ,  Mark S. Moir

发明人： Simon Doherty ,  Maurice P. Herlihy ,  Victor M. Luchangco ,  Mark S. Moir

IPC分类号： G06F12/00

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.

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

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

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

公开(公告)号：US07680986B1

公开(公告)日：2010-03-16

申请号：US11026849

申请日：2004-12-30

申请人： Mark S. Moir ,  Simon Doherty ,  Victor M. Luchangco ,  Maurice P. Herlihy

发明人： Mark S. Moir ,  Simon Doherty ,  Victor M. Luchangco ,  Maurice P. Herlihy

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

CPC分类号： G06F9/52

摘要： Many conventional lock-free data structures exploit techniques that are possible only because state-of-the-art 64-bit processors are still running 32-bit operating systems and applications. As software catches up to hardware, “64-bit-clean” lock-free data structures, which cannot use such techniques, are needed. We present several 64-bit-clean lock-free implementations: including load-linked/store conditional variables of arbitrary size, a FIFO queue, and a freelist. In addition to being portable to 64-bit software (or more generally full-architectural-width pointer operations), our implementations also improve on existing techniques in that they are (or can be) space-adaptive and do not require a priori knowledge of the number of threads that will access them.

摘要翻译： 许多传统的无锁数据结构利用了仅仅因为最先进的64位处理器仍在运行32位操作系统和应用程序而可能的技术。 随着软件的升级，硬件需要“64位清理”的无锁数据结构，不能使用这种技术。 我们提出了几个64位无干扰的无锁实现：包括任意大小的加载链接/存储条件变量，FIFO队列和freelist。 除了可移植到64位软件（或更通常的全架构宽度指针操作）之外，我们的实现还改进了现有技术，因为它们（或可以）是空间自适应的，并且不需要先验知识 将访问它们的线程数。

公开(公告)号：US20070288901A1

公开(公告)日：2007-12-13

申请号：US11552895

申请日：2006-10-25

申请人： Yosef Lev ,  Mark S. Moir ,  Maurice P. Herlihy

发明人： Yosef Lev ,  Mark S. Moir ,  Maurice P. Herlihy

IPC分类号： G06F9/44

CPC分类号： G06F11/3612

摘要： Transactional programming promises to substantially simplify the development and maintenance of correct, scalable, and efficient concurrent programs. Designs for supporting transactional programming using transactional memory implemented in hardware, software, and a mixture of the two have emerged recently. However, various features and capabilities for debugging programs executed using transactional memory are absent from conventional debuggers. Because transactional memory implementations provide the “illusion” of multiple memory locations changing value atomically, there are challenges involved with integrating debuggers with such programs to provide the user with a coherent view of program execution. For instance, when execution is halted for debugging, a user may request to view a transactional variable or memory location. The transactional variable or memory location may have a pre-transaction value and a tentative value. Allowing a user to only view one of the values reduces the capacity of a user to reason about the behavior of the code.

摘要翻译： 事务性规划将大大简化正确，可扩展和高效并发程序的开发和维护。 最近出现了使用在硬件，软件和两者的混合中实现的事务性存储来支持事务性编程的设计。 然而，常规调试器中不存在用于使用事务性存储器执行的调试程序的各种功能和功能。 由于事务性存储器实现提供了以原子方式改变值的多个存储器位置的“幻觉”，所以将调试器与这些程序集成存在挑战，以向用户提供程序执行的一致的视图。 例如，当执行停止调试时，用户可以请求查看事务变量或内存位置。 事务变量或存储器位置可以具有事务前值和临时值。 允许用户仅查看其中一个值可以降低用户对代码行为的理解能力。

公开(公告)号：US20090132563A1

公开(公告)日：2009-05-21

申请号：US12165086

申请日：2008-06-30

申请人： Maurice P. Herlihy ,  Yosef Lev ,  Victor Luchangco ,  Nir N. Shavit

发明人： Maurice P. Herlihy ,  Yosef Lev ,  Victor Luchangco ,  Nir N. Shavit

IPC分类号： G06F17/30

CPC分类号： G06F17/30958 ,  G06F17/30351

摘要： Apparatus, methods, and computer program products are disclosed for concurrently searching a memory containing a skiplist data structure. The method locates the skiplist data structure in the memory. The skiplist data structure includes a plurality of linked lists related by a skiplist invariant. Furthermore, the plurality of linked lists includes a first-level linked list and one or more higher-level linked lists. The skiplist data structure also includes a plurality of nodes, each of which includes a key field, at least one pointer field, and a lock field, respectively. Each of the plurality of nodes is linked to the first-level linked list through the at least one pointer field and ordered responsive to the key field. The method performs a search operation on the skiplist data structure, while the skiplist data structure is subject to concurrent alteration of the plurality of nodes by a plurality of execution threads that are configured to maintain the skiplist invariant and returns a result of the search operation.

摘要翻译： 公开了用于同时搜索包含滑雪板数据结构的存储器的装置，方法和计算机程序产品。 该方法将skiplist数据结构定位在内存中。 滑雪板数据结构包括由滑雪板不变量相关联的多个链接列表。 此外，多个链接列表包括第一级链接列表和一个或多个更高级别的链接列表。 滑雪板数据结构还包括多个节点，每个节点分别包括密钥字段，至少一个指针字段和锁定字段。 所述多个节点中的每一个通过所述至少一个指针字段链接到所述第一级链接列表，并响应于所述密钥字段排序。 该方法对滑雪板数据结构执行搜索操作，而滑雪板数据结构由多个执行线程进行多个节点的并发改变，所述多个执行线程被配置为维护滑雪板不变量并返回搜索操作的结果。

公开(公告)号：US07389383B2

公开(公告)日：2008-06-17

申请号：US11399049

申请日：2006-04-06

申请人： Marc Tremblay ,  Quinn A. Jacobson ,  Shailender Chaudhry ,  Mark S. Moir ,  Maurice P. Herlihy

发明人： Marc Tremblay ,  Quinn A. Jacobson ,  Shailender Chaudhry ,  Mark S. Moir ,  Maurice P. Herlihy

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

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.

摘要翻译： 本发明的一个实施例提供了一种系统，其有助于在事务性程序执行期间有选择地取消标记加载标记的高速缓存行，其中在事务执行期间监视负载标记的高速缓存行以检测来自其他线程的干扰访问。 在操作期间，系统在事务处理指令块期间遇到释放指令。 响应于释放指令，系统修改高速缓存行的状态，这些高速缓存行被特别加载标记以指示它们可以从监视释放，以解决遇到的释放指令。 在这样做时，系统可能会导致特别加载标记的高速缓存行变为未标记。 在该实施例的变型中，当遇到提交和启动新事务指令时，系统修改加载标记的高速缓存行以考虑正在遇到的提交和启动新事务指令。 在这样做时，系统会导致正常加载标记的高速缓存行变为未标记，而其他特别加载标记的高速缓存行可能会通过commit-and-start-new-transaction指令保持加载标记。

公开(公告)号：US07206903B1

公开(公告)日：2007-04-17

申请号：US10895519

申请日：2004-07-20

申请人： Mark S. Moir ,  Maurice P. Herlihy ,  Quinn A. Jacobson ,  Shailender Chaudhry ,  Marc Tremblay

发明人： Mark S. Moir ,  Maurice P. Herlihy ,  Quinn A. Jacobson ,  Shailender Chaudhry ,  Marc Tremblay

IPC分类号： G06F12/00

CPC分类号： G06F12/0842 ,  G06F9/30087 ,  G06F9/3834 ,  G06F9/3859

摘要： One embodiment of the present invention provides a system for releasing a memory location from transactional program execution. The system operates by executing a sequence of instructions during transactional program execution, wherein memory locations involved in the transactional program execution are monitored to detect interfering accesses from other threads, and wherein changes made during transactional execution are not committed until transactional execution completes without encountering an interfering data access from another thread. Upon encountering a release instruction for a memory location during the transactional program execution, the system modifies state information within the processor to release the memory location from monitoring. The system also executes a commit-and-start-new-transaction instruction, wherein the commit-and-start-new-transaction instruction atomically commits the transaction's stores, thereby removing them from the transaction's write set while the transaction's read set remains unaffected.

摘要翻译： 本发明的一个实施例提供了一种用于将存储器位置从事务程序执行释放的系统。 该系统通过在事务性程序执行期间执行指令序列来操作，其中监视涉及事务性程序执行的存储器位置以检测来自其他线程的干扰访问，并且其中在事务执行期间进行的改变不会被提交直到事务执行完成而不遇到 干扰来自另一个线程的数据访问。 在事务性程序执行期间遇到存储器位置的释放指令时，系统修改处理器内的状态信息以从监视释放存储器位置。 该系统还执行commit-and-start-new-transaction指令，其中commit-and-start-new-transaction指令以原子方式提交事务的存储，从而在事务的读取集保持不受影响的情况下将其从事务的写入集中移除。

公开(公告)号：US07089374B2

公开(公告)日：2006-08-08

申请号：US10764412

申请日：2004-01-23

申请人： Marc Tremblay ,  Quinn A. Jacobson ,  Shailender Chaudhry ,  Mark S. Moir ,  Maurice P. Herlihy

发明人： Marc Tremblay ,  Quinn A. Jacobson ,  Shailender Chaudhry ,  Mark S. Moir ,  Maurice P. Herlihy

IPC分类号： G06F12/00

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.

摘要翻译： 本发明的一个实施例提供了一种系统，其有助于在事务性程序执行期间有选择地取消标记加载标记的高速缓存行，其中在事务执行期间监视负载标记的高速缓存行以检测来自其他线程的干扰访问。 在操作期间，系统在事务处理指令块期间遇到释放指令。 响应于释放指令，系统修改高速缓存行的状态，这些高速缓存行被特别加载标记以指示它们可以从监视释放，以解决遇到的释放指令。 在这样做时，系统可能会导致特别加载标记的高速缓存行变为未标记。 在该实施例的变型中，当遇到提交和启动新事务指令时，系统修改加载标记的高速缓存行以考虑正在遇到的提交和启动新事务指令。 在这样做时，系统会导致正常加载标记的高速缓存行变为未标记，而其他特别加载标记的高速缓存行可能会通过commit-and-start-new-transaction指令保持加载标记。