-
公开(公告)号：US07945912B1
公开(公告)日：2011-05-17
申请号：US11445962
申请日：2006-06-02
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位于全局队列的头部时，为第一个线程获取锁定，并在获取锁定之后执行第一个线程的临界区段。
-
2.发明授权Controlling contention via transactional timers among conflicting transactions issued by processors operating in insistent or polite mode 有权通过以持续或礼貌模式运行的处理器发出的冲突交易中的事务定时器控制争用公开(公告)号：US07496726B1
公开(公告)日：2009-02-24
申请号：US11110910
申请日：2005-04-18
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.
摘要翻译： 一种用于控制事务性存储器系统中冲突事务之间争用的系统。 在操作期间，系统接收到访问高速缓存行的请求，然后确定高速缓存状态中的高速缓存状态中的高速缓存行是否已被使用，该缓存状态与请求不兼容。 如果是这样，系统确定请求是否来自处于礼貌模式的处理器。 如果这是真的，系统将拒绝访问高速缓存行的请求，并继续执行现有事务。
-
3.发明授权Ensuring progress in a system that supports execution of obstruction-free operations 有权确保在支持执行无障碍操作的系统中取得进展公开(公告)号：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调用操作时，系统检查一个紧急标志，指示是否激活进度保证机制。 如果设置了恐慌标志，则会启动进度保证机制，从而使系统尝试通过协调进程之间的动作来尝试执行操作，以确保进程尽可能在进程之间发生争用。 另一方面，如果不设置紧急状态标志，则系统试图执行操作，基本上就像进度保证机制不存在一样。 在这种情况下，如果存在进程之间的争用妨碍进展的指示，则系统设置紧急标志，这导致进程确保机制被激活，以便进程将协调其动作以确保进行进展。
-
4.发明授权Shared synchronized skip-list data structure and technique employing linearizable operations 有权共享同步跳过列表数据结构和采用线性化操作的技术公开(公告)号：US07424477B1
公开(公告)日：2008-09-09
申请号：US10653828
申请日：2003-09-03
申请人： Paul A. Martin , Guy L. Steele, Jr. , Nir N. Shavit , Steven K. Heller , Mark S. Moir , Victor M. Luchangco
发明人： Paul A. Martin , Guy L. Steele, Jr. , Nir N. Shavit , Steven K. Heller , Mark S. Moir , Victor M. Luchangco
CPC分类号： G06F9/524 , Y10S707/99938 , Y10S707/99942 , Y10S707/99943
摘要： A set of structures and techniques are described herein whereby an exemplary concurrent shared object, namely a shared skip list, can be implemented in a lock-free manner. Indeed, we have developed a number of interesting variants of a lock-free shared skip-list, including variants that may be employed to provide a lock-free shared dictionary. In some variants, a key-value dictionary is implemented.
摘要翻译： 本文描述了一组结构和技术，由此可以以无锁的方式实现示例性并发共享对象，即共享跳过列表。 实际上，我们已经开发出了一些无锁共享的跳过列表的许多有趣的变体，包括可用于提供无锁共享字典的变体。 在一些变型中，实现了键值字典。
-
公开(公告)号：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节点的读取器线程可以同时在读取模式下获取共享锁定。 读写器锁可以遵循写入者偏好策略，读者偏好策略或混合策略。
-
7.发明授权Method and apparatus for emulating linked-load/store-conditional synchronization 有权用于模拟链接加载/存储条件同步的方法和装置公开(公告)号：US07870344B2
公开(公告)日：2011-01-11
申请号：US11864649
申请日：2007-09-28
申请人： Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
发明人： Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
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）。 我们的实施是无障碍的。 因此，在无争议的情况下是高效的，并且依赖于竞争案件中的争用管理机制。 它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。 此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。
-
公开(公告)号：US07788242B2
公开(公告)日：2010-08-31
申请号：US11508762
申请日：2006-08-23
CPC分类号： G06F17/30362 , G06F17/30958
摘要： A method for inserting an object into a concurrent set including obtaining a key associated with the object, traversing the concurrent set using a first thread containing the key, identifying a first insertion point while traversing the concurrent set, where the first insertion point is before a current node and after a predecessor node, obtaining a first lock for the predecessor node after identifying the first insertion point, validating the predecessor node and the current node after obtaining the lock, inserting a new node into the concurrent set after validating, where the new node is associated with the object, and releasing the first lock after inserting the new node.
摘要翻译： 一种用于将对象插入到并发集合中的方法，包括获得与对象相关联的密钥，使用包含密钥的第一线程遍历并发集合，在遍历并发集合的同时识别第一插入点，其中第一插入点在 当前节点，并且在前导节点之后，在识别出第一插入点之后为先前节点获得第一锁定，在获得锁定之后验证前导节点和当前节点，在验证之后将新节点插入并发集合，其中新的 节点与对象相关联，并在插入新节点后释放第一个锁。
-
公开(公告)号：US20080059470A1
公开(公告)日：2008-03-06
申请号：US11508762
申请日：2006-08-23
IPC分类号： G06F17/30
CPC分类号： G06F17/30362 , G06F17/30958
摘要： A method for inserting an object into a concurrent set including obtaining a key associated with the object, traversing the concurrent set using a first thread containing the key, identifying a first insertion point while traversing the concurrent set, where the first insertion point is before a current node and after a predecessor node, obtaining a first lock for the predecessor node after identifying the first insertion point, validating the predecessor node and the current node after obtaining the lock, inserting a new node into the concurrent set after validating, where the new node is associated with the object, and releasing the first lock after inserting the new node.
摘要翻译： 一种用于将对象插入到并发集合中的方法，包括获得与对象相关联的密钥，使用包含密钥的第一线程遍历并发集合，在遍历并发集合的同时识别第一插入点，其中第一插入点在 当前节点，并且在前导节点之后，在识别出第一插入点之后为先前节点获得第一锁定，在获得锁定之后验证前导节点和当前节点，在验证之后将新节点插入并发集合，其中新的 节点与对象相关联，并在插入新节点后释放第一个锁。
-
公开(公告)号：US07293143B1
公开(公告)日：2007-11-06
申请号：US10670495
申请日：2003-09-24
申请人： Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
发明人： Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
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）。 我们的实施是无障碍的。 因此，在无争议的情况下是高效的，并且依赖于竞争案件中的争用管理机制。 它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。 此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。
-
-
-
-
-
-
-
-
-
搜索结果
45 条记录 (耗时 0.031 秒)
