公开(公告)号：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位软件（或更通常的全架构宽度指针操作）之外，我们的实现还改进了现有技术，因为它们（或可以）是空间自适应的，并且不需要先验知识 将访问它们的线程数。

公开(公告)号：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调用操作时，系统检查一个紧急标志，指示是否激活进度保证机制。 如果设置了恐慌标志，则会启动进度保证机制，从而使系统尝试通过协调进程之间的动作来尝试执行操作，以确保进程尽可能在进程之间发生争用。 另一方面，如果不设置紧急状态标志，则系统试图执行操作，基本上就像进度保证机制不存在一样。 在这种情况下，如果存在进程之间的争用妨碍进展的指示，则系统设置紧急标志，这导致进程确保机制被激活，以便进程将协调其动作以确保进行进展。

公开(公告)号：US07395274B2

公开(公告)日：2008-07-01

申请号：US10621078

申请日：2003-07-16

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

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

IPC分类号： G06F9/54

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.

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

公开(公告)号：US07299242B2

公开(公告)日：2007-11-20

申请号：US10340150

申请日：2003-01-10

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

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

IPC分类号： G06F9/46 ,  G06F9/44 ,  G06F12/00

CPC分类号： G06F9/52 ,  Y10S707/99944 ,  Y10S707/99947 ,  Y10S707/99953

摘要： Solutions to a value recycling problem that we define herein facilitate implementations of computer programs that may execute as multithreaded computations in multiprocessor computers, as well as implementations of related shared data structures. Some exploitations of the techniques described herein allow non-blocking, shared data structures to be implemented using standard dynamic allocation mechanisms (such as malloc and free). A class of general solutions to value recycling is described in the context of an illustration we call the Repeat Offender Problem (ROP), including illustrative Application Program Interfaces (APIs) defined in terms of the ROP terminology. Furthermore, specific solutions, implementations and algorithm, including a Pass-The-Buck (PTB) implementation are also described. Solutions to the proposed value recycling problem have a variety of uses. For example, a single-word lock-free reference counting (SLFRC) technique may build on any of a variety of value recycling solutions to transform, in a straight-forward manner, many lock-free data structure implementations that assume garbage collection (i.e., which do not explicitly free memory) into dynamic-sized data structures.

摘要翻译： 我们在这里定义的价值回收问题的解决方案便于在多处理器计算机中作为多线程计算执行的计算机程序的实现，以及相关共享数据结构的实现。 本文描述的技术的一些利用允许使用标准动态分配机制（诸如malloc和free）来实现非阻塞的共享数据结构。 在我们称为重复违规问题（ROP）的例证的上下文中描述了一类价值回收的一般解决方案，包括根据ROP术语定义的说明性应用程序接口（API）。 此外，还描述了包括通过降压（PTB）实现的具体解决方案，实现和算法。 提出的价值回收问题的解决方案有各种用途。 例如，单字无锁引用计数（SLFRC）技术可以建立在各种价值回收解决方案中的任何一种上，以直接方式转换许多无锁数据结构实现，这些实现假定垃圾收集（即 ，不明确地释放内存）到动态大小的数据结构中。

公开(公告)号：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指令以原子方式提交事务的存储，从而在事务的读取集保持不受影响的情况下将其从事务的写入集中移除。

公开(公告)号：US07171537B1

公开(公告)日：2007-01-30

申请号：US10866570

申请日：2004-06-11

申请人： 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.

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

公开(公告)号：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指令保持加载标记。

公开(公告)号：US07017160B2

公开(公告)日：2006-03-21

申请号：US09837669

申请日：2001-04-18

申请人： Paul A. Martin ,  David L. Detlefs ,  Alexander T. Garthwaite ,  Guy L. Steele, Jr. ,  Mark S. Moir

发明人： Paul A. Martin ,  David L. Detlefs ,  Alexander T. Garthwaite ,  Guy L. Steele, Jr. ,  Mark S. Moir

IPC分类号： G06F9/44 ,  G06F9/54

CPC分类号： G06F7/785 ,  G06F9/30032 ,  G06F9/526 ,  G06F9/544 ,  G06F2205/064 ,  G06F2209/521

摘要： The 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端的无限数量的推送和弹出进行，而不需要调用内存分配或回收，只要推送次数和流量数之间的差异保持不变 在给定范围内。 描述垃圾收集相关和显式回收实现。

公开(公告)号：US09304776B2

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

申请号：US13362903

申请日：2012-01-31

申请人： David Dice ,  Mark S. Moir

发明人： David Dice ,  Mark S. Moir

IPC分类号： G06F9/30 ,  G06F9/38 ,  G06F9/32

CPC分类号： G06F9/30058 ,  G06F9/30079 ,  G06F9/325 ,  G06F9/3848

摘要： A computer system may recognize a busy-wait loop in program instructions at compile time and/or may recognize busy-wait looping behavior during execution of program instructions. The system may recognize that an exit condition for a busy-wait loop is specified by a conditional branch type instruction in the program instructions. In response to identifying the loop and the conditional branch type instruction that specifies its exit condition, the system may influence or override a prediction made by a dynamic branch predictor, resulting in a prediction that the exit condition will be met and that the loop will be exited regardless of any observed branch behavior for the conditional branch type instruction. The looping instructions may implement waiting for an inter-thread communication event to occur or for a lock to become available. When the exit condition is met, the loop may be exited without incurring a misprediction delay.

摘要翻译： 计算机系统可以在编译时识别程序指令中的忙等待循环和/或可以在程序指令执行期间识别忙等待循环行为。 系统可以认识到忙 - 等待循环的退出条件由程序指令中的条件分支类型指令指定。 响应于识别循环和指定其退出条件的条件分支类型指令，系统可以影响或覆盖由动态分支预测器做出的预测，导致预测退出条件将被满足，并且循环将 退出条件分支类型指令的任何观察到的分支行为。 循环指令可以实现等待线程间通信事件发生或锁定变得可用。 当满足退出条件时，可以退出循环而不产生误预计延迟。

公开(公告)号：US09208081B1

公开(公告)日：2015-12-08

申请号：US11948618

申请日：2007-11-30

申请人： David Dice ,  Nir N. Shavit ,  Mark S. Moir ,  Antonios Printezis

发明人： David Dice ,  Nir N. Shavit ,  Mark S. Moir ,  Antonios Printezis

IPC分类号： G06F12/00 ,  G06F12/02

CPC分类号： G06F12/0269 ,  G06F9/467 ,  G06F2212/1016

摘要： A processing thread obtains an initial status of a reference field associated with an object having data stored in memory. The reference field represents, at least in part, a status of current modification operations (e.g., a status of moving the object from one location in memory to another), if any, applied to the object. The processing thread applies a sequence of instructions to data retrieved from the object to produce computational results for storage in the object. Prior to storing the computational results in the object, the processing thread can confirm whether the reference field has changed since obtaining the initial status.

摘要翻译： 处理线程获得与具有存储在存储器中的数据的对象相关联的参考字段的初始状态。 参考字段至少部分地表示当前修改操作的状态（例如，将对象从存储器中的一个位置移动到另一个位置的状态）（如果有的话）。 处理线程对从对象检索的数据应用一系列指令，以产生用于存储在对象中的计算结果。 在将计算结果存储在对象之前，处理线程可以确认参考字段是否从获得初始状态改变。