-
1.发明授权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实现的一个有趣的特征是，处理器可以检测这些边界情况，例如，确定阵列是空还是满，而不检查原子操作中两个终端指针的相对位置。
-
公开(公告)号：US07890722B1
公开(公告)日：2011-02-15
申请号：US11099720
申请日：2005-04-06
申请人： Guy L. Steele, Jr. , Ole Agesen , Nir N. Shavit
发明人： Guy L. Steele, Jr. , Ole Agesen , Nir N. Shavit
IPC分类号： G06F12/14
CPC分类号： G06F9/524 , G06F9/30021 , G06F9/3004 , G06F9/30087
摘要： A sequentially performed implementation of a compound compare-and-swap (nCAS) operation has been developed. In one implementation, a double compare-and-swap (DCAS) operation does not result in a fault, interrupt, or trap in the situation where memory address A2 is invalid and the contents of memory address A1 are unequal to C1. In some realizations, memory locations addressed by a sequentially performed nCAS or DCAS instruction are reserved (e.g., locked) in a predefined order in accordance with a fixed total order of memory locations. In this way, deadlock between concurrently executed instances of sequentially performed nCAS instructions can be avoided. Other realizations defer responsibility for deadlock avoidance to the programmer.
摘要翻译： 已经开发了顺序执行的复合比较和交换（nCAS）操作。 在一个实现中，在存储器地址A2无效并且存储器地址A1的内容不等于C1的情况下，双重比较和交换（DCAS）操作不会导致故障，中断或陷阱。 在一些实现中，依次执行的nCAS或DCAS指令寻址的存储器单元根据存储单元的固定总顺序以预定义的顺序被保留（例如锁定）。 以这种方式，可以避免顺序执行的nCAS指令的同时执行的实例之间的死锁。 其他实现方式将程序员的死锁责任推迟。
-
3.发明授权公开(公告)号：US06880071B2
公开(公告)日：2005-04-12
申请号：US09829207
申请日：2001-04-09
申请人： Guy L. Steele, Jr. , Ole Agesen , Nir N. Shavit
发明人： Guy L. Steele, Jr. , Ole Agesen , Nir N. Shavit
CPC分类号： G06F9/524 , G06F9/30021 , G06F9/3004 , G06F9/30087
摘要： A sequentially performed implementation of a compound compare-and-swap (nCAS) operation has been developed. In one implementation, a double compare-and-swap (DCAS) operation does not result in a fault, interrupt, or trap in the situation where memory address A2 is invalid and the contents of memory address A1 are unequal to C1. In some realizations, memory locations addressed by a sequentially performed nCAS or DCAS instruction are reserved (e.g., locked) in a predefined order in accordance with a fixed total order of memory locations. In this way, deadlock between concurrently executed instances of sequentially performed nCAS instructions can be avoided. Other realizations defer responsibility for deadlock avoidance to the programmer.
摘要翻译： 已经开发了顺序执行的复合比较和交换（nCAS）操作。 在一个实现中，在存储器地址A2无效并且存储器地址A1的内容不等于C1的情况下，双重比较和交换（DCAS）操作不会导致故障，中断或陷阱。 在一些实现中，依次执行的nCAS或DCAS指令寻址的存储器单元根据存储单元的固定总顺序以预定义的顺序被保留（例如锁定）。 以这种方式，可以避免顺序执行的nCAS指令的同时执行的实例之间的死锁。 其他实现方式将程序员的死锁责任推迟。
-
4.发明授权公开(公告)号：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的两端的并发性。 在根据本发明的各种实现中，可以推送到共享对象上的值集合不受使用区分值的约束。 此外，显式的回收实施例有利于在存储器的自动回收不可用或不切实际的环境或应用中使用。
-
5.发明授权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的对应端执行的下一个推或者弹出操作的一部分。 总体技术的一个重要方面是当处理器检测到列表中只有标记节点并且尝试从德克两端同时删除这些节点中的一个或多个时，删除操作的同步。
-
6.发明授权公开(公告)号：US06718492B1
公开(公告)日：2004-04-06
申请号：US09545019
申请日：2000-04-07
IPC分类号： G06F1100
CPC分类号： G06F9/30018 , G06F7/762 , G06F9/30032
摘要： A system is disclosed for providing, from an input data word comprising a plurality of input data units having an input arrangement and a mask word comprising a plurality of mask bits each associated with one of the data units, an output data word in which the data units are arranged according to the mask bits. The system includes a bit balancer module and a plurality of rearrangement modules. The bit balancer module is configured to divide the input data units comprising the input data word into a plurality of data word portions, each data unit being assigned to one of the data word portions based on a pattern of mask bits of the mask word relative to the mask bit associated with the respective data unit. Each rearrangement module is configured to provide, from one of the data word portions and associated mask bits, an output data word portion in which the data units are arranged according to the mask bits. The data units of the output data word portions provided by the rearrangement modules are interleaved to provide the output data word.
摘要翻译： 公开了一种用于从包括具有输入布置的多个输入数据单元的输入数据字和包括与数据单元之一相关联的多个掩码位的掩码字的输入数据字提供的系统，其中数据 单位根据掩码位排列。 该系统包括位平衡器模块和多个重排模块。 位平衡器模块被配置为将包括输入数据字的输入数据单元划分成多个数据字部分，每个数据单元基于掩模字的掩码位的图案相对于数据字部分中的一个分配给相对于 与相应数据单元相关联的掩码位。 每个重排模块被配置为从数据字部分和关联的掩码位之一提供根据掩码位数据单元排列的输出数据字部分。 由重排模块提供的输出数据字部分的数据单元被交织以提供输出数据字。
-
7.发明授权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.
摘要翻译： 本文描述了一组结构和技术，由此可以以无锁的方式实现示例性并发共享对象，即共享跳过列表。 实际上，我们已经开发出了一些无锁共享的跳过列表的许多有趣的变体，包括可用于提供无锁共享字典的变体。 在一些变型中，实现了键值字典。
-
8.发明授权Bounded-pause time garbage collection system and method including write barrier associated with a source instance of a partially relocated object 失效有界 - 暂停时间垃圾收集系统和方法，包括与部分重定位对象的源实例相关联的写入障碍
公开(公告)号：US5873105A
公开(公告)日：1999-02-16
申请号：US883291
申请日：1997-06-26
申请人： Marc Tremblay , James Michael O'Connor , Guy L. Steele, Jr. , Sanjay Vishin , Ole Agesen , Steven Heller , Derek R. White
发明人： Marc Tremblay , James Michael O'Connor , Guy L. Steele, Jr. , Sanjay Vishin , Ole Agesen , Steven Heller , Derek R. White
CPC分类号： G06F12/0276 , Y10S707/99957
摘要： A write barrier to stores into a partially relocated large or popular memory object facilitates bounded pause time implementations of relocating garbage collectors, including e.g., copying collectors, generational collectors, and collectors providing compaction. Such a write barrier allows a garbage collector implementation to interrupt relocation of large or popular memory objects so as to meet bounded pause time guarantees. A partially relocated object identifier store including "copy from" identifier storage accessible to write barrier logic allows the write barrier logic to maintain consistency between FromSpace and ToSpace instances of a partially relocated memory object. "Copy from" identifier storage allows the write barrier logic, or a trap handler responsive thereto, to broadcast a store-oriented memory access targeting the FromSpace instance to both FromSpace and ToSpace instances. Optional "How far" indication storage facilitates differentiation by the write barrier logic between a copied portion and an uncopied portion of the partially relocated memory object.
摘要翻译： 将存储到部分重定位的大型或流行的存储器对象中的写入屏障有助于重新定位垃圾收集器的有限暂停时间实现，包括例如复制收集器，代人收集器和提供压缩的收集器。 这样的写屏障允许垃圾回收器实现中断大型或流行的存储器对象的重新定位，以便满足有限的暂停时间保证。 包含写入屏障逻辑可访问的“复制”标识符存储的部分重新定位的对象标识符存储允许写入屏障逻辑保持部分重新定位的存储器对象的FromSpace和ToSpace实例之间的一致性。 从“标识符存储器复制”允许写屏障逻辑或响应于此的陷阱处理器将针对FromSpace实例的面向存储器的存储器访问广播到FromSpace和ToSpace实例。 可选的“多远”指示存储有助于通过写入屏障逻辑在部分重定位的存储器对象的复制部分和未遮盖部分之间进行区分。
-
9.发明授权Bounded-pause time garbage collection system and method including read and write barriers associated with an instance of a partially relocated object 失效有界暂停时间垃圾收集系统和方法，包括与部分重定位对象的实例相关联的读写障碍
公开(公告)号：US5857210A
公开(公告)日：1999-01-05
申请号：US882801
申请日：1997-06-26
申请人： Marc Tremblay , James Michael O'Connor , Guy L. Steele, Jr. , Sanjay Vishin , Ole Agesen , Steven Heller , Derek R. White
发明人： Marc Tremblay , James Michael O'Connor , Guy L. Steele, Jr. , Sanjay Vishin , Ole Agesen , Steven Heller , Derek R. White
CPC分类号： G06F12/0269 , G06F12/0276 , Y10S707/99957
摘要： A partially relocated object identifier store including "copy from" and "copy to" identifier storage accessible to write and read barrier logic allows the write and read barrier logic to selectively direct store- and load-oriented accesses to an appropriate FromSpace or ToSpace instance of a partially relocated memory object, in accordance with the memory object's partial relocation state. In some embodiments, the barriers trap to a partially relocated object trap handler. In other embodiments, the write barrier itself directs accesses without software trap handler overheads. Optional "how far" indication storage facilitates differentiation by the barrier logic, or by the partially relocated object trap handler, between a copied portion and an uncopied portion of the partially relocated memory object.
摘要翻译： 包含从写入和读取屏障逻辑访问的“复制到”和“复制到”标识符存储器的部分重新定位的对象标识符存储允许写入和读取屏障逻辑选择性地将存储和负载导向的访问定向到适当的FromSpace或ToSpace实例 根据存储器对象的部分重定位状态，部分重新定位的存储器对象。 在一些实施例中，障碍物捕获到部分重定位的对象陷阱处理器。 在其他实施例中，写入屏障本身引导访问而不需要软件陷阱处理程序开销。 可选的“多远”指示存储有助于通过屏障逻辑或部分重新定位的对象陷阱处理器在部分重新定位的存储器对象的复制部分和未覆盖部分之间进行区分。
-
10.发明授权Bounded-pause time garbage collection system and method including write barrier associated with source and target instances of a partially relocated object 失效有界 - 暂停时间垃圾回收系统和方法，包括与部分重定位对象的源和目标实例相关联的写入障碍
公开(公告)号：US5873104A
公开(公告)日：1999-02-16
申请号：US882796
申请日：1997-06-26
申请人： Marc Tremblay , James Michael O'Connor , Guy L. Steele, Jr. , Sanjay Vishin , Ole Agesen , Steven Heller , Derek R. White
发明人： Marc Tremblay , James Michael O'Connor , Guy L. Steele, Jr. , Sanjay Vishin , Ole Agesen , Steven Heller , Derek R. White
CPC分类号： G06F12/0269 , G06F12/0276 , Y10S707/99957
摘要： A partially relocated object identifier store including "copy from" identifier and "copy to" identifier storage accessible to write barrier logic allows the write barrier logic to maintain consistency between FromSpace and ToSpace instances of a partially relocated memory object without software trap handler overhead. Optional "How far" indication storage facilitates differentiation by the write barrier logic between a copied portion and an uncopied portion of the partially relocated memory object. An optional "mode" indication facilitates differentiation by the write barrier logic between a copy phase and a pointer update phase of relocation by the garbage collector implementation. In some embodiments, pointer update and copying phases may overlap. "Copy to" identifier storage facilitates broadcast of a store-oriented memory access to the FromSpace instance to both FromSpace and ToSpace instances. Similarly, during pointer update, "Copy to" and "Copy From" identifier storage facilitate broadcast of a store-oriented memory access to either the FromSpace instance or the ToSpace instance to both FromSpace and ToSpace instances.
摘要翻译： 包含“复制”标识符和写入屏障逻辑可访问的“复制到”标识符存储的部分重新定位的对象标识符存储允许写入屏障逻辑在没有软件陷阱处理程序开销的情况下保持部分重新定位的存储器对象的FromSpace和ToSpace实例之间的一致性。 可选的“多远”指示存储有助于通过写入屏障逻辑在部分重定位的存储器对象的复制部分和未遮盖部分之间进行区分。 可选的“模式”指示有助于通过垃圾收集器实现的复制阶段和重新定位的指针更新阶段之间的写屏障逻辑的区分。 在一些实施例中，指针更新和复制阶段可以重叠。 “复制到”标识符存储便于将FromSpace实例的面向存储的存储器访问广播到FromSpace和ToSpace实例。 类似地，在指针更新期间，“复制到”和“复制自”标识符存储便于将FromSpace实例或ToSpace实例的面向存储的存储器访问广播到FromSpace和ToSpace实例。
-
-
-
-
-
-
-
-
-
搜索结果
65 条记录 (耗时 0.025 秒)
