-
1.发明授权公开(公告)号：US06826757B2
公开(公告)日：2004-11-30
申请号：US09837670
申请日：2001-04-18
申请人： Guy L. Steele, Jr. , Alexander T. Garthwaite , Paul A. Martin , Nir N. Shavit , Mark S. Moir , David L. Detlefs
发明人： Guy L. Steele, Jr. , Alexander T. Garthwaite , Paul A. Martin , Nir N. Shavit , Mark S. Moir , David L. Detlefs
IPC分类号： G06F946
CPC分类号： G06F9/52
摘要： A novel linked-list-based concurrent shared object implementation has been developed that provides non-blocking and linearizable access to the concurrent shared object. In an application of the underlying techniques to a deque, non-blocking completion of access operations is achieved without restricting concurrency in accessing the deque's two ends. In various realizations in accordance with the present invention, the set of values that may be pushed onto a shared object is not constrained by use of distinguishing values. In addition, an explicit reclamation embodiment facilitates use in environments or applications where automatic reclamation of storage is unavailable or impractical.
摘要翻译： 已经开发了一种基于链表的并行共享对象实现，它提供对并发共享对象的非阻塞和线性化访问。 在底层技术应用于deque时，实现访问操作的非阻塞完成，而不会限制访问deque的两端的并发性。 在根据本发明的各种实现中，可以推送到共享对象上的值集合不受使用区分值的约束。 此外，显式的回收实施例有利于在存储器的自动回收不可用或不切实际的环境或应用中使用。
-
2.发明授权Concurrent shared object implemented using a linked-list with amortized node allocation 有权使用具有摊销节点分配的链接列表实现的并发共享对象公开(公告)号：US07017160B2
公开(公告)日：2006-03-21
申请号：US09837669
申请日：2001-04-18
申请人： Paul A. Martin , David L. Detlefs , Alexander T. Garthwaite , Guy L. Steele, Jr. , Mark S. Moir
发明人： Paul A. Martin , David L. Detlefs , Alexander T. Garthwaite , Guy L. Steele, Jr. , Mark S. Moir
CPC分类号： G06F7/785 , G06F9/30032 , G06F9/526 , G06F9/544 , G06F2205/064 , G06F2209/521
摘要： The Hat Trick deque requires only a single DCAS for most pushes and pops. The left and right ends do not interfere with each other until there is one or fewer items in the queue, and then a DCAS adjudicates between competing pops. By choosing a granularity greater than a single node, the user can amortize the costs of adding additional storage over multiple push (and pop) operations that employ the added storage. A suitable removal strategy can provide similar amortization advantages. The technique of leaving spare nodes linked in the structure allows an indefinite number of pushes and pops at a given deque end to proceed without the need to invoke memory allocation or reclamation so long as the difference between the number of pushes and the number of pops remains within given bounds. Both garbage collection dependent and explicit reclamation implementations are described.
摘要翻译： 帽子技巧deque只需要一个单一的DCAS大多数按钮和弹出。 在队列中有一个或多个项目之前，左右两端不会相互干扰，然后DCAS在竞争弹出之间进行裁决。 通过选择大于单个节点的粒度，用户可以通过使用添加的存储的多个推送（和弹出）操作来分摊添加附加存储的成本。 合适的清除策略可以提供类似的摊销优势。 在结构中链接的备用节点的技术允许在给定的deque端的无限数量的推送和弹出进行，而不需要调用内存分配或回收，只要推送次数和流量数之间的差异保持不变 在给定范围内。 描述垃圾收集相关和显式回收实现。
-
3.发明授权Maintaining a double-ended queue in a contiguous array with concurrent non-blocking insert and remove operations using a double compare-and-swap primitive 有权在具有并发的非阻塞插入和删除操作的连续数组中维护双端口队列，使用双重比较和交换原语公开(公告)号：US07539849B1
公开(公告)日：2009-05-26
申请号：US09547288
申请日：2000-04-11
申请人： Nir N. Shavit , Ole Agesen , David L. Detlefs , Christine H. Flood , Alexander T. Garthwaite , Paul A. Martin , Guy L. Steele, Jr.
发明人： Nir N. Shavit , Ole Agesen , David L. Detlefs , Christine H. Flood , Alexander T. Garthwaite , Paul A. Martin , Guy L. Steele, Jr.
IPC分类号： G06F7/06
CPC分类号： G06F9/52 , G06F9/544 , Y10S707/99942
摘要： An array-based concurrent shared object implementation has been developed that provides non-blocking and linearizable access to the concurrent shared object. In an application of the underlying techniques to a deque, the array-based algorithm allows uninterrupted concurrent access to both ends of the deque, while returning appropriate exceptions in the boundary cases when the deque is empty or full. An interesting characteristic of the concurrent deque implementation is that a processor can detect these boundary cases, e.g., determine whether the array is empty or full, without checking the relative locations of the two end pointers in an atomic operation.
摘要翻译： 已经开发了一种基于数组的并发共享对象实现，它提供对并发共享对象的非阻塞和线性化访问。 在将Deck的基础技术应用于deque时，基于阵列的算法允许对deque两端进行不间断的并发访问，同时在deque为空或满时在边界情况下返回适当的异常。 并发deque实现的一个有趣的特征是，处理器可以检测这些边界情况，例如，确定阵列是空还是满，而不检查原子操作中两个终端指针的相对位置。
-
公开(公告)号：US06993770B1
公开(公告)日：2006-01-31
申请号：US09837671
申请日：2001-04-18
IPC分类号： G06F9/54
CPC分类号： G06F9/526 , G06F12/0261 , Y10S707/99944 , Y10S707/99947
摘要： We present a methodology for transforming concurrent data structure implementations that depend on garbage collection to equivalent implementations that do not. Assuming the existence of garbage collection makes it easier to design implementations of concurrent data structures, particularly because it eliminates the well-known ABA problem. However, this assumption limits their applicability. Our results demonstrate that, for a significant class of data structures, designers can first tackle the easier problem of an implementation that does depend on garbage collection, and then apply our methodology to achieve a garbage-collection-independent implementation. Our methodology is based on the well-known reference counting technique, and employs the double compare-and-swap operation.
摘要翻译： 我们提出一种方法，用于将依赖于垃圾回收的并行数据结构实现转换为不具有相同的实现。 假设垃圾收集的存在使得设计并发数据结构的实现变得更加容易，特别是因为它消除了众所周知的ABA问题。 然而，这个假设限制了它们的适用性。 我们的研究结果表明，对于重要的数据结构类，设计人员可以首先解决实现依赖于垃圾回收的更容易的问题，然后应用我们的方法来实现与垃圾回收无关的实现。 我们的方法是基于众所周知的参考计数技术，并采用双重比较和交换操作。
-
公开(公告)号：US07805467B2
公开(公告)日：2010-09-28
申请号：US11343678
申请日：2006-01-30
申请人： Mark S. Moir , David L. Detlefs , Simon Doherty , Maurice P. Herlihy , Victor M. Luchangco , Paul A. Martin , Guy L. Steele, Jr.
发明人： Mark S. Moir , David L. Detlefs , Simon Doherty , Maurice P. Herlihy , Victor M. Luchangco , Paul A. Martin , Guy L. Steele, Jr.
IPC分类号： G06F12/00
CPC分类号： G06F12/0261 , G06F9/46 , G06F9/526
摘要： A methodology has been discovered for transforming garbage collection-dependent algorithms, shared object implementations and/or concurrent software mechanisms into a form that does not presume the existence of an independent, or execution environment provided, garbage collector. Algorithms, shared object implementations and/or mechanisms designed or transformed using techniques described herein provide explicit reclamation of storage using lock-free pointer operations. Transformations can be applied to lock-free algorithms and shared object implementations and preserve lock-freedom of such algorithms and implementations. As a result, existing and future lock-free algorithms and shared object implementations that depend on a garbage-collected execution environment can be exploited in environments that do not provide garbage collection. Furthermore, algorithms and shared object implementations that employ explicit reclamation of storage using lock-free pointer operations such as described herein may be employed in the implementation of a garbage collector itself.
摘要翻译： 已经发现了一种方法，用于将垃圾回收依赖算法，共享对象实现和/或并发软件机制转换为不假定存在独立或执行环境（垃圾收集器）的形式。 使用本文描述的技术设计或变换的算法，共享对象实现和/或机制使用无锁指针操作来提供存储的显式回收。 转换可以应用于无锁算法和共享对象实现，并保持这种算法和实现的锁定自由度。 因此，依赖于垃圾回收执行环境的现有和将来的无锁算法和共享对象实现可以在不提供垃圾回收的环境中被利用。 此外，使用如本文所述的无锁定指针操作的使用显式回收存储的算法和共享对象实现可以用于实现垃圾收集器本身。
-
6.发明授权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.
摘要翻译： 本文描述了一组结构和技术，由此可以以无锁的方式实现示例性并发共享对象，即共享跳过列表。 实际上，我们已经开发出了一些无锁共享的跳过列表的许多有趣的变体，包括可用于提供无锁共享字典的变体。 在一些变型中，实现了键值字典。
-
7.发明授权Maintaining a double-ended queue as a linked-list with sentinel nodes and delete flags with concurrent non-blocking insert and remove operations using a double compare-and-swap primitive 有权将双端队列作为链接列表维护，并使用哨兵节点和删除标志，并发使用并发的非阻塞插入和删除操作，使用双重比较和交换原语公开(公告)号：US07000234B1
公开(公告)日：2006-02-14
申请号：US09547290
申请日：2000-04-11
IPC分类号： G06F9/54
CPC分类号： G06F7/785 , G06F5/10 , G06F2205/064
摘要： A linked-list-based concurrent shared object implementation has been developed that provides non-blocking and linearizable access to the concurrent shared object. In an application of the underlying techniques to a deque, the linked-list-based algorithm allows non-blocking completion of access operations without restricting concurrency in accessing the deque's two ends. The new implementation is based at least in part on a new technique for splitting a pop operation into two steps, marking that a node is about to be deleted, and then deleting it. Once marked, the node logically deleted, and the actual deletion from the list can be deferred. In one realization, actual deletion is performed as part of a next push or pop operation performed at the corresponding end of the deque. An important aspect of the overall technique is synchronization of delete operations when processors detect that there are only marked nodes in the list and attempt to delete one or more of these nodes concurrently from both ends of the deque.
摘要翻译： 已经开发了基于链接列表的并发共享对象实现，其提供对并发共享对象的非阻塞和线性化访问。 在基于deque的基础技术的应用中，基于链表的算法允许非阻塞地完成访问操作，而不会限制访问deque两端的并发性。 新的实现至少部分地基于用于将弹出操作分成两个步骤的新技术，标记节点即将被删除，然后删除它。 一旦标记，节点将被逻辑删除，并且可以推迟从列表中实际删除。 在一个实现中，实际删除被执行为在deque的对应端执行的下一个推或者弹出操作的一部分。 总体技术的一个重要方面是当处理器检测到列表中只有标记节点并且尝试从德克两端同时删除这些节点中的一个或多个时，删除操作的同步。
-
8.发明授权Method and apparatus for implementing a lock-free skip list that supports concurrent accesses 有权用于实现支持并发访问的无锁跳过列表的方法和装置公开(公告)号：US07308448B1
公开(公告)日：2007-12-11
申请号：US10805095
申请日：2004-03-19
申请人： Paul A. Martin
发明人： Paul A. Martin
CPC分类号： G06F9/52 , Y10S707/99938
摘要： One embodiment of the present invention provides a system that supports concurrent accesses to a skip list that is lock-free, which means that the skip list can be simultaneously accessed by multiple processes without requiring the processes to perform locking operations. During a node deletion operation, the system receives reference to a target node to be deleted from the skip list. The system marks a next pointer in the target node to indicate that the target node is deleted, wherein next pointer contains the address of an immediately following node in the skip list. This marking operation does not destroy the address of the immediately following node, and furthermore, the marking operation is performed atomically and thereby without interference from other processes. The system then atomically modifies the next pointer of an immediately preceding node in the skip list to point to an immediately following node in the skip list, instead of pointing to the target node, thereby splicing the target node out of the skip list.
摘要翻译： 本发明的一个实施例提供了支持对无锁定的跳过列表的并发访问的系统，这意味着可以通过多个进程同时访问跳过列表，而不需要进行执行锁定操作。 在节点删除操作期间，系统从跳过列表接收到要删除的目标节点的引用。 系统标记目标节点中的下一个指针，以指示目标节点被删除，其中下一个指针包含跳过列表中紧随其后的节点的地址。 该标记操作不会破坏紧随其后的节点的地址，此外，标记操作以原子方式执行，从而不受其他过程的干扰。 系统然后对跳过列表中紧邻的前一个节点的下一个指针进行原子修改，以指向跳过列表中紧跟的节点，而不是指向目标节点，从而将目标节点拼接在跳过列表之外。
-
公开(公告)号：US06167645A
公开(公告)日：2001-01-02
申请号：US09105351
申请日：1998-06-26
IPC分类号： G09F700
CPC分类号： B60R13/105 , B60R19/52
摘要： A license plate bracket includes a pair of resilient hooks for hooking the bracket to the grille of a vehicle. The hooks, in part, replace conventional hardware such as screws and bolts which are incompatible with the thin plastic ribs found on modern vehicle front grilles. The entire bracket, including the hooks, can be formed as a one-piece plastic molding.
摘要翻译： 车牌支架包括一对用于将支架钩在车辆格栅上的弹性钩。 这些钩部分地替代了与现代车辆前格栅上发现的薄塑料肋不兼容的常规硬件，例如螺钉和螺栓。 包括钩子在内的整个支架可以形成为单件塑料模制件。
-
10.发明授权公开(公告)号：US07702628B1
公开(公告)日：2010-04-20
申请号：US10883347
申请日：2004-06-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.
摘要翻译： 本发明的一个实施例提供一种对完全动态和无锁定的散列表执行操作的系统。 该哈希表使用包含数据节点和包含桶指针的桶阵列的链表来实现，其中桶指针指向作为哈希桶的链表的部分，并且其中链表仅包含数据节点并且不存在虚节点 。
-
-
-
-
-
-
-
-
-
搜索结果
23 条记录 (耗时 0.029 秒)
