公开(公告)号：US10049127B1

公开(公告)日：2018-08-14

申请号：US10995885

申请日：2004-11-23

申请人： Nir N. Shavit ,  Maurice P. Herlihy

发明人： Nir N. Shavit ,  Maurice P. Herlihy

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

摘要： Efficiency with respect to traditional techniques is a key issue facing designers of software transactional synchronization mechanisms. Meta-transactional synchronization allows integration of transactional support into an object-oriented programming language, such as the Java language through the existing synchronization structure of the JVM. Meta-transactional synchronization provides source-level transactional operations that co-exist with synchronized operations. An implementation of a shared object in an object-oriented programming language tracks concurrently executing transactions attempting to access the shared object with at least one header word of the shared object.

公开(公告)号：US07937378B2

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

申请号：US12191008

申请日：2008-08-13

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

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

IPC分类号： G06F7/00

CPC分类号： G06F17/30985

摘要： Apparatus, methods, and computer program products are disclosed for performing a wait-free search of a concurrent, lock-free skiplist to determine existence of a sought-after key.

摘要翻译： 公开了装置，方法和计算机程序产品，用于执行同时，无锁的滑雪板的等待搜索以确定所寻找的密钥的存在。

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

公开(公告)号：US20080228691A1

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

申请号：US11717453

申请日：2007-03-12

申请人： Nir N. Shavit ,  Maurice P. Herlihy

发明人： Nir N. Shavit ,  Maurice P. Herlihy

IPC分类号： G06F17/30

CPC分类号： G06F17/30949

摘要： Concurrent cuckoo hashing is performed on a hash table that includes a number of locations; each may hold a value. A plurality of processes may concurrently execute on the table; each process includes a sequence of operations, which are divided into a number of phases. Each phase corresponds to one operation in the sequence. An overflow buffer is provided for each location in the table. Each overflow buffer may hold a value displaced from its corresponding location in the table. A plurality of sequences of operations is concurrently executed. Each phase in a sequence executes by acquiring one or two locks on two locations in the table; a lock acts on a location and its overflow buffer. An operation of a phase is then executed. If, on conclusion of the phase execution, any overflow buffer holds a value, the execution is repeated until all overflow buffers are empty.

摘要翻译： 并发杜鹃散列在包含多个位置的散列表上执行; 每个可能持有一个价值。 多个处理可以在桌子上同时执行; 每个过程包括一系列操作，它们分为多个阶段。 每个阶段对应于序列中的一个操作。 为表中的每个位置提供一个溢出缓冲区。 每个溢出缓冲区可以保持从表中相应位置偏移的值。 同时执行多个操作序列。 序列中的每个阶段通过在表中的两个位置获取一个或两个锁来执行; 锁定位置及其溢出缓冲区。 然后执行阶段的操作。 如果在相位执行结束时，任何溢出缓冲区都保存一个值，则重复执行，直到所有溢出缓冲区为空。

公开(公告)号：US08375062B2

公开(公告)日：2013-02-12

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

公开(公告)号：US07809916B1

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

申请号：US11863901

申请日：2007-09-28

申请人： Nir N. Shavit ,  Maurice P. Herlihy

发明人： Nir N. Shavit ,  Maurice P. Herlihy

IPC分类号： G06F12/06

CPC分类号： G06F17/3033 ,  G06F9/526

摘要： Methods and apparatus provide a lock resizer for resizing of a lock array of a lock-based concurrent hash table. The lock resizer provides a data structure with memory locations which is apportioned into buckets that contain a plurality of the memory locations. It is understood that the data structure can dynamically add new memory locations. The lock resizer further provides a location lock for each distinct memory location and a bucket lock for each distinct bucket. A resizing flag can reference a thread to indicate whether or not the thread is resizing the amount of locks. Upon detection of the existence of a policy condition, the lock resizer resizes the amount of location locks and/or bucket locks in order to create new location locks and new bucket locks, thereby ensuring that as new memory locations are added, all buckets can contain up to a fixed number of memory locations.

摘要翻译： 方法和装置提供一种用于调整基于锁的并发哈希表的锁阵列大小的锁定调整器。 锁定调整器提供具有分配到包含多个存储器位置的存储器的存储器位置的数据结构。 据了解，数据结构可以动态添加新的内存位置。 锁定调整器还为每个不同的存储器位置提​​供位置锁定，并为每个不同的桶提供桶锁。 调整大小的标志可以引用线程来指示线程是否正在调整锁的大小。 在检测到策略条件的存在之后，锁定调整器调整位置锁和/或桶锁的大小，以便创建新的位置锁和新的桶锁，从而确保在添加新的存储器位置时，所有桶可以包含 达到固定数量的内存位置。

公开(公告)号：US20100042584A1

公开(公告)日：2010-02-18

申请号：US12191008

申请日：2008-08-13

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

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

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

CPC分类号： G06F17/30985

摘要： Apparatus, methods, and computer program products are disclosed for performing a wait-free search of a concurrent, lock-free skiplist to determine existence of a sought-after key.

摘要翻译： 公开了装置，方法和计算机程序产品，用于执行同时，无锁的滑雪板的等待搜索以确定所寻找的密钥的存在。

公开(公告)号：US07657500B2

公开(公告)日：2010-02-02

申请号：US11717453

申请日：2007-03-12

申请人： Nir N. Shavit ,  Maurice P. Herlihy

发明人： Nir N. Shavit ,  Maurice P. Herlihy

IPC分类号： G06F7/00 ,  G06F17/00 ,  G06F17/30 ,  G06F12/00 ,  G06F9/26 ,  G06F9/34

CPC分类号： G06F17/30949

摘要： Concurrent cuckoo hashing is performed on a hash table that includes a number of locations; each may hold a value. A plurality of processes may concurrently execute on the table; each process includes a sequence of operations, which are divided into a number of phases. Each phase corresponds to one operation in the sequence. An overflow buffer is provided for each location in the table. Each overflow buffer may hold a value displaced from its corresponding location in the table. A plurality of sequences of operations is concurrently executed. Each phase in a sequence executes by acquiring one or two locks on two locations in the table; a lock acts on a location and its overflow buffer. An operation of a phase is then executed. If, on conclusion of the phase execution, any overflow buffer holds a value, the execution is repeated until all overflow buffers are empty.

摘要翻译： 并发杜鹃散列在包含多个位置的散列表上执行; 每个可能持有一个价值。 多个处理可以在桌子上同时执行; 每个过程包括一系列操作，它们分为多个阶段。 每个阶段对应于序列中的一个操作。 为表中的每个位置提供一个溢出缓冲区。 每个溢出缓冲区可以保持从表中相应位置偏移的值。 同时执行多个操作序列。 序列中的每个阶段通过在表中的两个位置获取一个或两个锁来执行; 锁定位置及其溢出缓冲区。 然后执行阶段的操作。 如果在相位执行结束时，任何溢出缓冲区都保存一个值，则重复执行，直到所有溢出缓冲区为空。

公开(公告)号：US20120311606A1

公开(公告)日：2012-12-06

申请号：US13152079

申请日：2011-06-02

申请人： Virendra J. Marathe ,  Nir N. Shavit ,  David Dice

发明人： Virendra J. Marathe ,  Nir N. Shavit ,  David Dice

IPC分类号： G06F9/46

CPC分类号： G06F9/526

摘要： The system and methods described herein may be used to implement a scalable, hierarchal, queue-based lock using flat combining. A thread executing on a processor core in a cluster of cores that share a memory may post a request to acquire a shared lock in a node of a publication list for the cluster using a non-atomic operation. A combiner thread may build an ordered (logical) local request queue that includes its own node and nodes of other threads (in the cluster) that include lock requests. The combiner thread may splice the local request queue into a (logical) global request queue for the shared lock as a sub-queue. A thread whose request has been posted in a node that has been combined into a local sub-queue and spliced into the global request queue may spin on a lock ownership indicator in its node until it is granted the shared lock.

摘要翻译： 本文描述的系统和方法可以用于使用平坦组合来实现可扩展的，分级的基于队列的锁。 在共享内存的核心集群中的处理器核心上执行的线程可以使用非原子操作来发布用于获取集群的发布列表的节点中的共享锁定的请求。 组合线程可以构建一个有序（逻辑）本地请求队列，其包括其自己的节点和包含锁定请求的其他线程（在集群中）的节点。 组合器线程可以将本地请求队列拼接成用于共享锁的（逻辑）全局请求队列作为子队列。 已经将其请求已经发布在已经组合到本地子队列中并被拼接到全局请求队列中的节点的线程可以旋转其节点中的所有权所有者指示符，直到被授予共享锁为止。

公开(公告)号：US08103838B2

公开(公告)日：2012-01-24

申请号：US12350792

申请日：2009-01-08

申请人： David Dice ,  Nir N. Shavit

发明人： David Dice ,  Nir N. Shavit

IPC分类号： G06F12/16

CPC分类号： G06F9/52

摘要： In traditional transactional locking systems, such as Transactional Locking with Read-Write locks (TLRW), threads may frequently update lock metadata, causing system performance degradation. A system and method for implementing transactional locking using reader-lists (TLRL) may associate a respective reader-list with each stripe of data in a shared memory system. Before reading a given stripe as part of a transaction, a thread may add itself to the stripe's reader-list, if the thread is not already on the reader-list. A thread may leave itself on a reader-list after finishing the transaction. Before a thread modifies a stripe, the modifying thread may acquire a write-lock for the stripe. The writer thread may indicate to each reader thread on the stripe's reader-list that if the reader thread is executing a transaction, the reader thread should abort. The indication may include setting an invalidation flag for the reader. The writer thread may clear the reader-list of a stripe it modified.

摘要翻译： 在传统的事务锁定系统中，例如使用读写锁定（TLRW）的事务锁定，线程可能会频繁更新锁元数据，从而导致系统性能下降。 用于使用读取器列表（TLRL）实现事务锁定的系统和方法可将相应的读取器列表与共享存储器系统中的每条数据条相关联。 在作为事务的一部分读取给定的条带之前，线程可能会将自身添加到条带的读取器列表中，如果该线程尚未在读取器列表中。 完成交易后，线程可能会在读取器列表上留下。 在线程修改条带之前，修改线程可以获取条带的写锁定。 作者线程可能会在条形码读取器列表上向每个读取器线程指示如果读取器线程正在执行事务，则读取器线程应该中止。 该指示可以包括设置读取器的无效标志。 作者线程可以清除其修改的条带的阅读器列表。