公开(公告)号：US20120278576A1

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

申请号：US13543267

申请日：2012-07-06

申请人： Nir N. Shavit ,  Mark S. Moir ,  Victor M. Luchangco

发明人： Nir N. Shavit ,  Mark S. Moir ,  Victor M. Luchangco

IPC分类号： G06F12/14

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

公开(公告)号：US08261024B1

公开(公告)日：2012-09-04

申请号：US11263414

申请日：2005-10-31

申请人： Nir N. Shavit ,  Ori Shalev

发明人： Nir N. Shavit ,  Ori Shalev

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

CPC分类号： G06F9/526 ,  G06F2209/522 ,  G06F2209/523

摘要： From among a plurality of threads accessing a shared data object, one thread acquires a “master” status to arbitrate among the requests of competing threads during a given session of data access to the shared data object. During the session, the master thread resolves any conflicts resulting from attempts to access or modify the shared data object by other threads, and only the master thread may apply modifications to the shared data object during the session. Meanwhile, during the session, non-master threads may perform non-blocking read operations on the shared data object. During a subsequent session, a different thread may acquire master status.

摘要翻译： 在访问共享数据对象的多个线程中，一个线程在给予共享数据对象的数据访问的给定会话期间获取“主”状态以在竞争线程的请求中进行仲裁。 在会话期间，主线程解决由其他线程访问或修改共享数据对象所产生的任何冲突，只有主线程可以在会话期间对共享数据对象应用修改。 同时，在会话期间，非主线程可以对共享数据对象执行非阻塞读操作。 在后续会话中，不同的线程可能获取主状态。

公开(公告)号：US08230421B2

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

申请号：US11864667

申请日：2007-09-28

申请人： Nir N. Shavit ,  Mark S. Moir ,  Victor M. Luchangco

发明人： Nir N. Shavit ,  Mark S. Moir ,  Victor M. Luchangco

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

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

公开(公告)号：US07945912B1

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

申请号：US11445962

申请日：2006-06-02

申请人： Daniel S. Nussbaum ,  Nir N. Shavit ,  Victor M. Luchangco

发明人： Daniel S. Nussbaum ,  Nir N. Shavit ,  Victor M. Luchangco

IPC分类号： G06F9/46

CPC分类号： G06F9/526

摘要： In general, in one aspect, the invention relates to a method of establishing a queue-based lock including inserting a first qnode into a local queue, where the first qnode is associated with a first thread, splicing the local queue into the global queue, obtaining a lock for the first thread when the first qnode is at the head of the global queue, and executing a critical section of the first thread after obtaining the lock.

摘要翻译： 通常，一方面，本发明涉及一种建立基于队列的锁的方法，包括将第一qnode插入到本地队列中，其中第一qnode与第一线程相关联，将本地队列拼接到全局队列中， 当第一个qnode位于全局队列的头部时，为第一个线程获取锁定，并在获取锁定之后执行第一个线程的临界区段。

公开(公告)号：US07865671B2

公开(公告)日：2011-01-04

申请号：US11864624

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

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

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

公开(公告)号：US07496726B1

公开(公告)日：2009-02-24

申请号：US11110910

申请日：2005-04-18

申请人： Daniel S. Nussbaum ,  Victor M. Luchangco ,  Mark S. Moir ,  Ori Shalev ,  Nir N. Shavit

发明人： Daniel S. Nussbaum ,  Victor M. Luchangco ,  Mark S. Moir ,  Ori Shalev ,  Nir N. Shavit

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

CPC分类号： G06F9/526 ,  G06F9/30087 ,  G06F9/466 ,  G06F9/5016

摘要： A system for controlling contention between conflicting transactions in a transactional memory system. During operation, the system receives a request to access a cache line and then determines if the cache line is already in use by an existing transaction in a cache state that is incompatible with the request. If so, the system determines if the request is from a processor which is in a polite mode. If this is true, the system denies the request to access the cache line and continues executing the existing transaction.

摘要翻译： 一种用于控制事务性存储器系统中冲突事务之间争用的系统。 在操作期间，系统接收到访问高速缓存行的请求，然后确定高速缓存状态中的高速缓存状态中的高速缓存行是否已被使用，该缓存状态与请求不兼容。 如果是这样，系统确定请求是否来自处于礼貌模式的处理器。 如果这是真的，系统将拒绝访问高速缓存行的请求，并继续执行现有事务。

公开(公告)号：US07412572B1

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

申请号：US10965336

申请日：2004-10-14

申请人： Nir N. Shavit ,  Ori Shalev

发明人： Nir N. Shavit ,  Ori Shalev

IPC分类号： G06F12/00

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

摘要： A multiple-location read, single-location write operation is implemented using transient blocking synchronization support. The multiple-location read, single-location write operation involves first acquiring transient ownership of a memory location to be modified and then acquiring transient ownership of at least one other memory location, the contents of which are read and used to modify the memory location first acquired.

摘要翻译： 使用瞬态阻塞同步支持实现多位置读取，单位置写入操作。 多位置读取单位置写入操作涉及首先获取待修改的存储器位置的瞬时所有权，然后获取至少一个其他存储器位置的瞬时所有权，其内容被读取并用于首先修改存储器位置 获得了