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

公开(公告)号：US07793052B2

公开(公告)日：2010-09-07

申请号：US11967358

申请日：2007-12-31

申请人： James R. Goodman ,  Mark S. Moir ,  Fu'ad W. F. Al Tabba′ ,  Cong Wang

发明人： James R. Goodman ,  Mark S. Moir ,  Fu'ad W. F. Al Tabba′ ,  Cong Wang

IPC分类号： G06F12/00

CPC分类号： G06F9/526 ,  G06F9/466 ,  G06F11/141 ,  G06F11/1479 ,  G06F2209/521

摘要： A hybrid Single-Compare-Single-Store (SCSS) operation may exploit best-effort hardware transactional memory (HTM) for good performance in the case that it succeeds, and may transparently resort to software-mediated transactions if the hardware transactional mechanisms fail. The SCSS operation may compare a value in a control location to a specified expected value, and if they match, may store a new value in a separate data location. The control value may include a global lock, a transaction status indicator, and/or a portion of an ownership record, in different embodiments. If another transaction in progress owns the data location, the SCSS operation may abort the other transaction or may help it complete by copying the other transactions' write set into its own right set before acquiring ownership. A hybrid SCSS operation, which is usually nonblocking, may be applied to building software transactional memories (STMs) and/or hybrid transactional memories (HyTMs), in some embodiments.

摘要翻译： 混合单一比较单存储（SCSS）操作可以在成功的情况下利用尽力而为的硬件事务存储器（HTM）以获得良好的性能，并且如果硬件事务机制失败，则可以透明地诉诸软件介入的事务。 SCSS操作可以将控制位置中的值与指定的预期值进行比较，如果匹配，则可将新值存储在单独的数据位置。 在不同的实施例中，控制值可以包括全局锁定，事务状态指示符和/或所有权记录的一部分。 如果正在进行的另一个交易拥有数据位置，SCSS操作可能会中止其他交易，或者可以在获得所有权之前将其他交易的写入集合复制到自己的权利集中来帮助完成该交易。 在一些实施例中，通常不阻塞的混合SCSS操作可以应用于构建软件事务存储器（STM）和/或混合事务存储器（HyTM）。

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

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

公开(公告)号：US20100153662A1

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

申请号：US12334316

申请日：2008-12-12

申请人： Christopher A. Vick ,  Gregory M. Wright ,  Mark S. Moir

发明人： Christopher A. Vick ,  Gregory M. Wright ,  Mark S. Moir

IPC分类号： G06F12/00

CPC分类号： G06F8/52 ,  G06F9/3004 ,  G06F9/30087 ,  G06F9/3834 ,  G06F9/384 ,  G06F9/3857 ,  G06F9/3863

摘要： One embodiment of the present invention provides a system that facilitates precise exception semantics for a virtual machine. During operation, the system executes a program in the virtual machine using a processor that includes a gated store buffer that stores values to be written to a memory. This gated store buffer is configured to delay a store to the memory until after a speculatively-optimized region of the program commits. The processor signals an exception when it detects that a load following the store is attempting to access the same memory region being written by the store prior to the commitment of the speculatively-optimized region.

摘要翻译： 本发明的一个实施例提供一种促进虚拟机的精确异常语义的系统。 在操作期间，系统使用包括存储要写入存储器的值的门控存储缓冲器的处理器在虚拟机中执行程序。 该门控存储缓冲器配置为将存储器延迟到存储器，直到程序的推测优化区域提交。 处理器在检测到存储器之后的负载尝试访问由推测优化区域承诺之前由存储器写入的相同存储区域时，发出异常。

公开(公告)号：US07711909B1

公开(公告)日：2010-05-04

申请号：US11008692

申请日：2004-12-09

申请人： Yosef Lev ,  Mark S. Moir

发明人： Yosef Lev ,  Mark S. Moir

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

CPC分类号： G06F9/52

摘要： It has been discovered that globally indicating read-write conflicts and semi-transparent read sharing in a transactional memory space allows for a more expedient validation. Without being aware of particular transactions, a writing transaction can determine that a read-write conflict will occur with some transaction that has read one or more memory locations to be modified by the writing transaction. With semi-transparent reading, reading transactions can validate quickly. If a read-write conflict has not occurred since a reading transaction began (or since the last validation), then the previous reads are valid. Otherwise, the reading transaction investigates each memory location or ownership record to determine if a read-write conflict affected the investigating transaction.

摘要翻译： 已经发现，在事务存储器空间中全局地指示读写冲突和半透明读共享允许更方便的验证。 在不知道特定事务的情况下，写入事务可以确定读写冲突将发生，其中一些事务已读取要由写入事务修改的一个或多个存储器位置。 通过半透明阅读，阅读交易可以快速验证。 如果读取事务开始（或自上次验证）以来没有发生读写冲突，则之前的读取是有效的。 否则，阅读交易会调查每个内存位置或所有权记录，以确定读写冲突是否影响了调查交易。

公开(公告)号：US07689788B2

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

申请号：US11656843

申请日：2007-01-23

申请人： Mark S. Moir ,  Virendra J. Marathe

发明人： Mark S. Moir ,  Virendra J. Marathe

IPC分类号： G06F12/00

CPC分类号： G06F9/466

摘要： A method for executing transactions including obtaining a memory location required by a first transaction, where the first transaction is identified using a first transaction identification and a first transaction version; determining a second transaction with ownership of a memory group including the memory location, where the second transaction is identified using a second transaction identification and a second transaction version; copying an intermediate value associated with the memory group from the second transaction into transactional metadata associated with the first transaction; changing ownership of the memory group to the first transaction; and committing the first transaction.

摘要翻译： 一种用于执行交易的方法，包括获得第一交易所需的存储位置，其中使用第一交易标识和第一交易版本识别所述第一交易; 确定包括所述存储器位置的存储器组的所有权的第二事务，其中使用第二事务标识和第二事务版本识别所述第二事务; 将与所述存储器组相关联的中间值从所述第二事务复制到与所述第一事务相关联的事务元数据; 将内存组的所有权更改为第一笔交易; 并提交第一笔交易。

公开(公告)号：US07685583B2

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

申请号：US10620747

申请日：2003-07-16

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

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

IPC分类号： G06F9/44 ,  G06F9/45 ,  G06F17/00

CPC分类号： G06F9/524 ,  G06F9/526 ,  Y10S707/99944 ,  Y10S707/99947

摘要： We present a technique for implementing obstruction-free atomic multi-target transactions that target special “transactionable” locations in shared memory. A programming interface for using operations based on these transactions can be structured in several ways, including as n-word compare-and-swap (NCAS) operations or as atomic sequences of single-word loads and stores (e.g., as transactional memory).

摘要翻译： 我们提出一种实现无共享存储器中特殊“可交易”位置的无阻碍原子多目标事务的技术。 用于使用基于这些事务的操作的编程接口可以以多种方式被构造，包括作为n字比较和交换（NCAS）操作，或者作为单字加载和存储（例如，作为事务存储器）的原子序列。

公开(公告)号：US07502906B2

公开(公告)日：2009-03-10

申请号：US11612264

申请日：2006-12-18

申请人： Mark S. Moir ,  Simon Doherty

发明人： Mark S. Moir ,  Simon Doherty

IPC分类号： G06F12/00

CPC分类号： G06F12/0646

摘要： A computer system stores a dynamically sized array as a base array that contains references to subarrays in which the (composite) array's data elements reside. Each of the base-array elements that thus refers to a respective subarray is associated with a respective subarray size. Each base-array index is thereby at least implicitly associated with a cumulative base value equal to the sum of all preceding base indexes' associated subarray sizes. In response to a request for access to the element associated with a given (composite-array) index, the array-access system identifies the base index associated with the highest cumulative base value not greater than the composite-array index and performs the access to the subarray identified by the element associated with that base index. Composite-array expansion can be performed in a multi-threaded environment without locking, simply by employing a compare-and-swap or similar atomic operation.

摘要翻译： 计算机系统将动态大小的数组存储为基数组，其中包含对（复合）数组元素所在的子阵列的引用。 因此，引用相应子阵列的每个基数组元素与相应的子阵列大小相关联。 因此，每个基数组索引至少隐含地与等于所有先前的基本索引的相关子阵列大小的总和的累积基值相关联。 响应于访问与给定（复合数组）索引相关联的元素的请求，阵列访问系统识别与不大于复合数组索引的最高累积基值相关联的基本索引，并执行对 由与该基础索引相关联的元素识别的子阵列。 复合阵列扩展可以在没有锁定的多线程环境中执行，简单地通过采用比较和交换或类似的原子操作。

公开(公告)号：US20080229139A1

公开(公告)日：2008-09-18

申请号：US12130635

申请日：2008-05-30

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

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

IPC分类号： H04L1/22

CPC分类号： G06F9/524 ,  G06F9/526 ,  Y10S707/99944 ,  Y10S707/99947

摘要： We explore techniques for designing nonblocking algorithms that do not require advance knowledge of the number of processes that participate, whose time complexity and space consumption both adapt to various measures, rather than being based on predefined worst-case scenarios, and that cannot be prevented from future memory reclamation by process failures. These techniques can be implemented using widely available hardware synchronization primitives. We present our techniques in the context of solutions to the well-known Collect problem. We also explain how our techniques can be exploited to achieve other results with similar properties; these include long-lived renaming and dynamic memory management for nonblocking data structures.

摘要翻译： 我们探索设计非阻塞算法的技术，这些算法不需要提前了解参与的进程数量，其时间复杂度和空间消耗都适应各种测量，而不是基于预定义的最坏情况，并且不能防止 未来内存回收过程失败。 可以使用广泛可用的硬件同步原语来实现这些技术。 我们在众所周知的收集问题的解决方案的背景下介绍我们的技术。 我们还解释了如何利用我们的技术来实现具有相似属性的其他结果; 这些包括用于非阻塞数据结构的长期重命名和动态内存管理。

公开(公告)号：US20070288902A1

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

申请号：US11608830

申请日：2006-12-10

申请人： Yosef Lev ,  Mark S. Moir

发明人： Yosef Lev ,  Mark S. Moir

IPC分类号： G06F9/44

CPC分类号： G06F11/3632

摘要： 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. Unfortunately, conventional debugging programs are often inadequate when employed in relation to code that employs transactional memory and new or modified techniques are needed. We describe techniques whereby certain facilities of a transactional memory implementation can be leveraged to provide replay debugging. With replay debugging, the user can examine a partial or complete execution of an atomic block after it has happened—for example, right before the execution commits. Moreover, in some cases the user can modify the replayed execution, and decide to commit the new modified execution instead of the original replayed one.

摘要翻译： 事务性规划将大大简化正确，可扩展和高效并发程序的开发和维护。 最近出现了使用在硬件，软件和两者的混合中实现的事务性存储来支持事务性编程的设计。 不幸的是，传统的调试程序在采用事务性存储器的代码方面经常是不足够的，需要新的或修改的技术。 我们描述了可以利用事务性存储器实现的某些设施来提供重播调试的技术。 通过重播调试，用户可以在发生原子块之后检查原子块的部分或完全执行，例如在执行提交之前。 此外，在某些情况下，用户可以修改重播的执行，并决定提交新的修改的执行，而不是原始的被重播的执行。