公开(公告)号：US20080256074A1

公开(公告)日：2008-10-16

申请号：US12101316

申请日：2008-04-11

申请人： Yosef Lev ,  Nir N. Shavit ,  David Dice ,  Mark A. Moir

发明人： Yosef Lev ,  Nir N. Shavit ,  David Dice ,  Mark A. Moir

IPC分类号： G06F17/30

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

摘要： Apparatus, methods, and program products are disclosed that provide a technology that implicitly isolates a portion of a transactional memory that is shared between multiple threads for exclusive use by an isolating thread without the possibility of other transactions modifying the isolated portion of the transactional memory.

摘要翻译： 公开了装置，方法和程序产品，其提供隐含地隔离在多个线程之间共享的事务存储器的一部分以供隔离线程独占使用的技术，而不会有其他事务修改事务存储器的隔离部分的可能性。

公开(公告)号：US08332374B2

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

申请号：US12101316

申请日：2008-04-11

申请人： Yosef Lev ,  Nir N. Shavit ,  David Dice ,  Mark A. Moir

发明人： Yosef Lev ,  Nir N. Shavit ,  David Dice ,  Mark A. Moir

IPC分类号： G06F7/00 ,  G06F17/00 ,  G06F13/14

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

摘要： Apparatus, methods, and program products are disclosed that provide a technology that implicitly isolates a portion of a transactional memory that is shared between multiple threads for exclusive use by an isolating thread without the possibility of other transactions modifying the isolated portion of the transactional memory. In some of the described embodiments read locations of a shared memory are covered by a first set of lock objects, and write locations are covered by a second set of lock objects, each lock object in each set having a reader mode and a writer mode. Some of these embodiments acquiring each lock object in the first set using the reader mode, and acquire each lock object in the second set using the writer mode. These embodiments store result data values at write locations in the shared memory subsequent to the acquiring said first and second set of lock objects.

摘要翻译： 公开了装置，方法和程序产品，其提供隐含地隔离在多个线程之间共享的事务存储器的一部分以供隔离线程独占使用的技术，而不会有其他事务修改事务存储器的隔离部分的可能性。 在一些描述的实施例中，共享存储器的读取位置由第一组锁定对象覆盖，并且写入位置由第二组锁定对象覆盖，每个组中的每个锁定对象具有读取器模式和写入器模式。 这些实施例中的一些实施例使用读取器模式来获取第一组中的每个锁定对象，并且使用写入器模式来获取第二组中的每个锁定对象。 这些实施例在获取所述第一和第二组锁定对象之后将结果数据值存储在共享存储器中的写入位置处。

公开(公告)号：US08966491B2

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

申请号：US13458868

申请日：2012-04-27

申请人： Irina Calciu ,  David Dice ,  Victor M. Luchangco ,  Virendra J. Marathe ,  Nir N. Shavit ,  Yosef Lev

发明人： Irina Calciu ,  David Dice ,  Victor M. Luchangco ,  Virendra J. Marathe ,  Nir N. Shavit ,  Yosef Lev

IPC分类号： G06F9/46

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

摘要： NUMA-aware reader-writer locks may leverage lock cohorting techniques to band together writer requests from a single NUMA node. The locks may relax the order in which the lock schedules the execution of critical sections of code by reader threads and writer threads, allowing lock ownership to remain resident on a single NUMA node for long periods, while also taking advantage of parallelism between reader threads. Threads may contend on node-level structures to get permission to acquire a globally shared reader-writer lock. Writer threads may follow a lock cohorting strategy of passing ownership of the lock in write mode from one thread to a cohort writer thread without releasing the shared lock, while reader threads from multiple NUMA nodes may simultaneously acquire the shared lock in read mode. The reader-writer lock may follow a writer-preference policy, a reader-preference policy or a hybrid policy.

摘要翻译： NUMA感知的读写器锁可以利用锁定队列技术将来自单个NUMA节点的写入器请求带到一起。 锁可以放松锁定通过读取器线程和写入器线程调度关键代码段的顺序，允许锁定所有权长时间保持驻留在单个NUMA节点上，同时还利用读取器线程之间的并行性。 线程可能会争取节点级结构获得获取全局共享读写器锁的权限。 编写者线程可能遵循锁定队列策略，将锁定的所有权从写入模式从一个线程传递到队列写入器线程，而不会释放共享锁定，而来自多个NUMA节点的读取器线程可以同时在读取模式下获取共享锁定。 读写器锁可以遵循写入者偏好策略，读者偏好策略或混合策略。

公开(公告)号：US20130290967A1

公开(公告)日：2013-10-31

申请号：US13458868

申请日：2012-04-27

申请人： Irina Calciu ,  David Dice ,  Victor M. Luchangco ,  Virendra J. Marathe ,  Nir N. Shavit ,  Yosef Lev

发明人： Irina Calciu ,  David Dice ,  Victor M. Luchangco ,  Virendra J. Marathe ,  Nir N. Shavit ,  Yosef Lev

IPC分类号： G06F9/46

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

摘要： NUMA-aware reader-writer locks may leverage lock cohorting techniques to band together writer requests from a single NUMA node. The locks may relax the order in which the lock schedules the execution of critical sections of code by reader threads and writer threads, allowing lock ownership to remain resident on a single NUMA node for long periods, while also taking advantage of parallelism between reader threads. Threads may contend on node-level structures to get permission to acquire a globally shared reader-writer lock. Writer threads may follow a lock cohorting strategy of passing ownership of the lock in write mode from one thread to a cohort writer thread without releasing the shared lock, while reader threads from multiple NUMA nodes may simultaneously acquire the shared lock in read mode. The reader-writer lock may follow a writer-preference policy, a reader-preference policy or a hybrid policy.

摘要翻译： NUMA感知的读写器锁可以利用锁定队列技术将来自单个NUMA节点的写入器请求带到一起。 锁可以放松锁定通过读取器线程和写入器线程调度关键代码段的顺序，允许锁定所有权长时间保持驻留在单个NUMA节点上，同时还利用读取器线程之间的并行性。 线程可能会争取节点级结构获得获取全局共享读写器锁的权限。 编写者线程可能遵循锁定队列策略，将锁定的所有权从写入模式从一个线程传递到队列写入器线程，而不会释放共享锁定，而来自多个NUMA节点的读取器线程可以同时在读取模式下获取共享锁定。 读写器锁可以遵循写入者偏好策略，读者偏好策略或混合策略。

公开(公告)号：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）实现事务锁定的系统和方法可将相应的读取器列表与共享存储器系统中的每条数据条相关联。 在作为事务的一部分读取给定的条带之前，线程可能会将自身添加到条带的读取器列表中，如果该线程尚未在读取器列表中。 完成交易后，线程可能会在读取器列表上留下。 在线程修改条带之前，修改线程可以获取条带的写锁定。 作者线程可能会在条形码读取器列表上向每个读取器线程指示如果读取器线程正在执行事务，则读取器线程应该中止。 该指示可以包括设置读取器的无效标志。 作者线程可以清除其修改的条带的阅读器列表。

公开(公告)号：US08065499B2

公开(公告)日：2011-11-22

申请号：US11475262

申请日：2006-06-27

申请人： David Dice ,  Nir N. Shavit

发明人： David Dice ,  Nir N. Shavit

IPC分类号： G06F12/08

CPC分类号： G06F12/0806 ,  G06F9/466 ,  G06F9/52 ,  G06F9/526 ,  G06F12/0815 ,  G06F12/0893

摘要： A computer system includes multiple processing threads that execute in parallel. The multiple processing threads have access to a global environment including different types of metadata enabling the processing threads to carry out simultaneous execution depending on a currently selected type of lock mode. A mode controller monitoring the processing threads initiates switching from one type of lock mode to another depending on current operating conditions such as an amount of contention amongst the multiple processing threads to modify the shared data. The mode controller can switch from one lock mode another regardless of whether any of the multiple processes are in the midst of executing a respective transaction. A most efficient lock mode can be selected to carry out the parallel transactions. In certain cases, switching of lock modes causes one or more of the processing threads to abort and retry a respective transaction according to the new mode.

摘要翻译： 计算机系统包括并行执行的多个处理线程。 多个处理线程可以访问包括不同类型的元数据的全局环境，使得处理线程可以根据当前选择的锁定模式类型执行同时执行。 监视处理线程的模式控制器根据当前操作条件（例如多个处理线程之间的争用量）来启动从一种类型的锁定模式切换到另一种类型的锁模式以修改共享数据。 模式控制器可以从一种锁定模式切换，而不管多个进程中的任何一个是否在执行相应的事务中。 可以选择最有效的锁定模式来执行并行事务。 在某些情况下，切换锁定模式会使一个或多个处理线程根据新模式中止并重试相应的事务。

公开(公告)号：US20100332770A1

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

申请号：US12492613

申请日：2009-06-26

申请人： David Dice ,  Nir N. Shavit

发明人： David Dice ,  Nir N. Shavit

IPC分类号： G06F12/10

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

摘要： A system and method for concurrency control may use slotted read-write locks. A slotted read-write lock is a lock data structure associated with a shared memory area, wherein the slotted read-write lock indicates whether any thread has a read-lock and/or a write-lock for the shared memory area. Multiple threads may concurrently have the read-lock but only one thread can have the write-lock at any given time. The slotted read-write lock comprises multiple slots, each associated with a single thread. To acquire the slotted read-write lock for reading, a thread assigned to a slot performs a store operation to the slot and then attempts to determine that no other thread holds the slotted read-write lock for writing. To acquire the slotted read-write lock for writing, a thread assigned to a slot sets its write-bit and then attempts to determine that the write-lock is not held.

摘要翻译： 用于并发控制的系统和方法可以使用时隙读写锁。 时隙读写锁是与共享存储器区域相关联的锁定数据结构，其中，时隙读写锁定指示任何线程是否具有针对共享存储器区域的读锁定和/或写锁定。 多个线程可以同时具有读锁定，但只有一个线程可以在任何给定时间具有写锁定。 时隙读写锁定包括多个时隙，每个时隙与单个线程相关联。 为了获取读取时隙读写锁，分配给时隙的线程对该时隙执行存储操作，然后尝试确定没有其他线程保持用于写入的时隙读写锁。 要获取用于写入的时隙读写锁，分配给时隙的线程设置其写入位，然后尝试确定写锁定不被保持。

公开(公告)号：US07640402B2

公开(公告)日：2009-12-29

申请号：US11699802

申请日：2007-01-30

申请人： David Dice ,  Nir N. Shavit ,  Ori Shalev ,  Mark Moir

发明人： David Dice ,  Nir N. Shavit ,  Ori Shalev ,  Mark Moir

IPC分类号： G06F13/00

摘要： The present disclosure describes a unique way for each of multiple processes to operate in parallel and use the same shared data without causing corruption to the shared data. For example, during a commit phase, a corresponding transaction can attempt to increment a globally accessible version information variable and store a current value of the globally accessible version information variable for updating version information associated with modified data regardless of whether an associated attempt by the corresponding transaction to modify the globally accessible version information variable was successful. As an alternative mode, a corresponding transaction can merely read and store a current value of the globally accessible version information variable without attempting to update the globally accessible version information variable before such use. In yet another application, a parallel processing environment implements a combination of both aforementioned modes depending on a self-abort rate of the transaction.

公开(公告)号：US08775837B2

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

申请号：US13213833

申请日：2011-08-19

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

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

IPC分类号： G06F1/32 ,  G06F1/00 ,  G06F15/00 ,  G06F9/46

CPC分类号： G06F9/526 ,  G06F1/3228 ,  G06F1/324 ,  G06F9/485 ,  Y02D10/126

摘要： The systems and methods described herein may enable a processor core to run at higher speeds than other processor cores in the same package. A thread executing on one processor core may begin waiting for another thread to complete a particular action (e.g., to release a lock). In response to determining that other threads are waiting, the thread/core may enter an inactive state. A data structure may store information indicating which threads are waiting on which other threads. In response to determining that a quorum of threads/cores are in an inactive state, one of the threads/cores may enter a turbo mode in which it executes at a higher speed than the baseline speed for the cores. A thread holding a lock and executing in turbo mode may perform work delegated by waiting threads at the higher speed. A thread may exit the inactive state when the waited-for action is completed.

摘要翻译： 本文描述的系统和方法可以使处理器核心以比同一封装中的其它处理器核心更高的速度运行。 在一个处理器核心上执行的线程可以开始等待另一个线程来完成特定动作（例如，释放锁定）。 响应于确定其他线程正在等待，线程/内核可能进入非活动状态。 数据结构可以存储指示哪些线程在哪个其他线程上等待的信息。 响应于确定线程/核心的法定数量处于非活动状态，线程/内核中的一个可以进入turbo模式，在该模式下，该模式以比核心的基线速度更高的速度执行。 持有锁并以turbo模式执行的线程可以执行以较高速度等待线程委托的工作。 等待操作完成时，线程可能会退出非活动状态。