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

公开(公告)号：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）技术可以建立在各种价值回收解决方案中的任何一种上，以直接方式转换许多无锁数据结构实现，这些实现假定垃圾收集（即 ，不明确地释放内存）到动态大小的数据结构中。

公开(公告)号：US20070256060A1

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

申请号：US11412662

申请日：2006-04-27

申请人： Sukyoung Ryu ,  Eric Allen ,  Victor Luchangco ,  Joseph Hallett ,  Samuel Tobin-Hochstadt

发明人： Sukyoung Ryu ,  Eric Allen ,  Victor Luchangco ,  Joseph Hallett ,  Samuel Tobin-Hochstadt

IPC分类号： G06F9/45

CPC分类号： G06F8/437

摘要： One embodiment of the present invention provides a system for generating executable code. During operation, the system receives source code, wherein the source code can include declarations for types and operations, wherein the type declarations may be parameterized, and wherein the source code may specify subtyping relationships between declared types. Next, the system compiles or interprets the source code to produce executable code, wherein the type parameters may be instantiated by different types during execution, and wherein the result of executing operations may depend upon the instantiations of the type parameters. While compiling or interpreting the source code, the system checks the types and operations in the source code to ensure that the executable code generated is type-safe, and hence will not generate type errors during execution.

摘要翻译： 本发明的一个实施例提供了一种用于生成可执行代码的系统。 在操作期间，系统接收源代码，其中源代码可以包括类型和操作的声明，其中类型声明可以被参数化，并且其中源代码可以指定声明类型之间的子类型关系。 接下来，系统编译或解释源代码以产生可执行代码，其中类型参数可以在执行期间由不同类型实例化，并且其中执行操作的结果可以取决于类型参数的实例。 在编译或解释源代码时，系统将检查源代码中的类型和操作，以确保生成的可执行代码是类型安全的，因此在执行期间不会生成类型错误。

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

公开(公告)号：US07254597B2

公开(公告)日：2007-08-07

申请号：US10340154

申请日：2003-01-10

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

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

IPC分类号： G06F12/12

CPC分类号： G06F9/52 ,  Y10S707/955 ,  Y10S707/99953 ,  Y10S707/99957

摘要： 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 variety of solutions to the proposed value recycling problem may be implemented. 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 value recycling problem can be applied in a variety of ways to implement dynamic-sized data structures.

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

公开(公告)号：US07908441B2

公开(公告)日：2011-03-15

申请号：US10340156

申请日：2003-01-10

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

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

IPC分类号： G06F12/14 ,  G06F9/54

CPC分类号： G06F9/52 ,  Y10S707/955 ,  Y10S707/99953 ,  Y10S707/99957

摘要： Solutions to a value recycling problem 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 allow non-blocking, shared data structures to be implemented using standard dynamic allocation mechanisms (such as malloc and free). Some exploitations allow non-blocking, indeed even lock-free or wait-free, implementations of dynamic storage allocation for shared data structures. In some exploitations, our techniques provide a way to manage dynamically allocated memory in a non-blocking manner without depending on garbage collection. While exploitations of solutions to the value recycling problem that we propose include management of dynamic storage allocation wherein values managed and recycled tend to include values that encode pointers, they are not limited thereto. Indeed, the techniques are more generally applicable to management of values in a multithreaded computation. For example, value recycling techniques may be exploited, in some cases, apart from dynamic storage allocation, to allow a multithreaded computation to avoid the classic ABA hazard.

摘要翻译： 价值回收问题的解决方案便于在多处理器计算机中作为多线程计算执行的计算机程序的实现，以及相关共享数据结构的实现。 一些利用可以使用标准的动态分配机制（如malloc和free）来实现非阻塞的共享数据结构。 一些剥削允许共享数据结构的动态存储分配的非阻塞，甚至无锁或无等待的实现。 在一些利用中，我们的技术提供了一种在不依赖垃圾收集的情况下以非阻塞方式管理动态分配的内存的方法。 虽然我们提出的解决价值回收问题的解决方案包括动态存储分配的管理，其中管理和再循环的值往往包括编码指针的值，但是并不限于此。 实际上，这些技术更普遍地适用于多线程计算中的值的管理。 例如，除了动态存储分配之外，还可以利用价值回收技术，在某些情况下，允许多线程计算避免经典的ABA危险。

公开(公告)号：US07702628B1

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

申请号：US10883347

申请日：2004-06-30

申请人： Victor Luchangco ,  Paul A. Martin ,  Jan-Willem Maessen

发明人： Victor Luchangco ,  Paul A. Martin ,  Jan-Willem Maessen

IPC分类号： G06F7/00 ,  G06F17/30

CPC分类号： G06F17/30949 ,  Y10S707/99936

摘要： One embodiment of the present invention provides a system that performs operations on a hash table that is fully dynamic and lock-free. This hash table is implemented with a linked list containing data nodes and a bucket array containing bucket pointers, wherein the bucket pointers point to portions of the linked list that function as hash buckets, and wherein the linked list contains only data nodes and no dummy nodes.

摘要翻译： 本发明的一个实施例提供一种对完全动态和无锁定的散列表执行操作的系统。 该哈希表使用包含数据节点和包含桶指针的桶阵列的链表来实现，其中桶指针指向作为哈希桶的链表的部分，并且其中链表仅包含数据节点并且不存在虚节点 。

公开(公告)号：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数据结构定位在内存中。 滑雪板数据结构包括由滑雪板不变量相关联的多个链接列表。 此外，多个链接列表包括第一级链接列表和一个或多个更高级别的链接列表。 滑雪板数据结构还包括多个节点，每个节点分别包括密钥字段，至少一个指针字段和锁定字段。 所述多个节点中的每一个通过所述至少一个指针字段链接到所述第一级链接列表，并响应于所述密钥字段排序。 该方法对滑雪板数据结构执行搜索操作，而滑雪板数据结构由多个执行线程进行多个节点的并发改变，所述多个执行线程被配置为维护滑雪板不变量并返回搜索操作的结果。

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

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