-
公开(公告)号：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.
摘要翻译： 已经发现了一种方法，用于将垃圾回收依赖算法，共享对象实现和/或并发软件机制转换为不假定存在独立或执行环境（垃圾收集器）的形式。 使用本文描述的技术设计或变换的算法，共享对象实现和/或机制使用无锁指针操作来提供存储的显式回收。 转换可以应用于无锁算法和共享对象实现，并保持这种算法和实现的锁定自由度。 因此，依赖于垃圾回收执行环境的现有和将来的无锁算法和共享对象实现可以在不提供垃圾回收的环境中被利用。 此外，使用如本文所述的无锁定指针操作的使用显式回收存储的算法和共享对象实现可以用于实现垃圾收集器本身。
-
公开(公告)号：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问题。 然而，这个假设限制了它们的适用性。 我们的研究结果表明，对于重要的数据结构类，设计人员可以首先解决实现依赖于垃圾回收的更容易的问题，然后应用我们的方法来实现与垃圾回收无关的实现。 我们的方法是基于众所周知的参考计数技术，并采用双重比较和交换操作。
-
3.发明授权公开(公告)号：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的两端的并发性。 在根据本发明的各种实现中，可以推送到共享对象上的值集合不受使用区分值的约束。 此外，显式的回收实施例有利于在存储器的自动回收不可用或不切实际的环境或应用中使用。
-
4.发明授权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端的无限数量的推送和弹出进行，而不需要调用内存分配或回收，只要推送次数和流量数之间的差异保持不变 在给定范围内。 描述垃圾收集相关和显式回收实现。
-
5.发明授权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实现的一个有趣的特征是，处理器可以检测这些边界情况，例如，确定阵列是空还是满，而不检查原子操作中两个终端指针的相对位置。
-
公开(公告)号：US20100211931A1
公开(公告)日：2010-08-19
申请号：US12370742
申请日：2009-02-13
申请人： Yosseff Levanoni , David L. Detlefs , Weirong Zhu , Timothy L. Harris , Michael M. Magruder , Mathew B. Tolton
发明人： Yosseff Levanoni , David L. Detlefs , Weirong Zhu , Timothy L. Harris , Michael M. Magruder , Mathew B. Tolton
IPC分类号： G06F9/44
CPC分类号： G06F9/466 , G06F11/141
摘要： A software transactional memory system is provided with overflow handling. The system includes a global version counter with an epoch number and a version number. The system accesses the global version counter prior to and subsequent to memory accesses of transactions to validate read accesses of the transaction. The system includes mechanisms to detect global version number overflow and may allow some or all transactions to execute to completion subsequent to the global version number overflowing. The system also provides publication, privatization, and granular safety properties.
摘要翻译： 软件事务内存系统提供溢出处理。 该系统包括具有时代号和版本号的全局版本计数器。 系统在事务的内存访问之前和之后访问全局版本计数器，以验证事务的读取访问。 该系统包括检测全局版本号溢出的机制，并且可允许一些或所有事务在全球版本号码溢出之后执行完成。 该系统还提供出版物，私有化和粒状安全属性。
-
公开(公告)号：US20090328019A1
公开(公告)日：2009-12-31
申请号：US12163902
申请日：2008-06-27
IPC分类号： G06F9/45
CPC分类号： G06F8/443 , G06F11/3624
摘要： A dynamic race detection system is provided that detects race conditions in code that executes concurrently in a computer system. The dynamic race detection system uses a modified software transactional memory (STM) system to detect race conditions. A compiler converts portions of the code that are not configured to operate with the STM system into pseudo STM code that operates with the STM system. The dynamic race detection system detects race conditions in response to either a pseudo STM transaction in the pseudo STM code failing to validate when executed or an actual STM transaction failing to validate when executed because of conflict with a concurrent pseudo STM transaction.
摘要翻译： 提供了一种动态竞争检测系统，其检测在计算机系统中并发执行的代码中的竞争条件。 动态竞争检测系统使用修改后的软件事务存储器（STM）系统来检测竞争条件。 编译器将未配置为与STM系统一起运行的代码部分转换为与STM系统一起运行的伪STM代码。 动态竞争检测系统响应于伪STM代码中的伪STM事务在执行时无法验证或由于与并发的伪STM事务冲突而被执行时实际的STM事务失败而检测到竞争条件。
-
公开(公告)号：US20090328018A1
公开(公告)日：2009-12-31
申请号：US12163284
申请日：2008-06-27
IPC分类号： G06F9/45
CPC分类号： G06F8/443
摘要： A compiler is provided that determines when the use of software transactional memory (STM) primitives may be optimized with respect to a set of collectively dominating STM primitives. The compiler analysis coordinates the use of variables containing possible shadow copy pointers to allow the analysis to be performed for both direct write and buffered write STM systems. The coordination of the variables containing the possible shadow copy pointers ensures that the results of STM primitives are properly reused. The compiler analysis identifies memory accesses where STM primitives may be eliminated, combined, or substituted for lower overhead STM primitives.
摘要翻译： 提供了一种编译器，其确定何时可以相对于一组统一主导的STM原语来优化软件事务存储器（STM）原语的使用。 编译器分析协调使用包含可能的卷影复制指针的变量，以便对直写和缓冲写STM系统执行分析。 包含可能的卷影复制指针的变量的协调确保了STM原语的结果被适当重复使用。 编译器分析识别存储器访问，其中STM原语可以被消除，组合或代替较低开销的STM原语。
-
公开(公告)号：US20090327636A1
公开(公告)日：2009-12-31
申请号：US12163788
申请日：2008-06-27
CPC分类号： G06F9/466
摘要： A software transactional memory system is provided that generates and stores compressed transactional locks in a portion of object headers. The software transactional memory system allocates preferred write log memory with a predefined size of memory that corresponds to a number of bits in the compressed transactional locks. The compressed transactional locks identify write log entries in corresponding write logs in the preferred write log memory. If the preferred write log memory becomes full, additional write log memory is allocated for write log entries and subsequent transactional locks are stored uncompressed in an auxiliary memory. A pointer that may be used to locate the uncompressed transactional lock is stored in the header. If an object header with a compressed transactional lock is needed for another use, the compressed transactional lock is uncompressed and stored in the auxiliary memory. A pointer that may be used to locate the uncompressed transactional lock is stored in the header.
摘要翻译： 提供了一种软件事务存储器系统，其在对象头部的一部分中生成并存储压缩事务锁。 软件事务存储系统将优选的写日志存储器与对应于压缩事务锁中的多个位的预定义大小的存储器分配。 压缩事务锁在首选写入日志存储器中的相应写入日志中标识写入日志条目。 如果首选的写入日志内存已满，则会为写入日志条目分配额外的写入日志内存，而后续的事务锁存在未压缩的辅助存储器中。 可用于定位未压缩事务锁的指针存储在标题中。 如果需要具有压缩事务锁定的对象标头进行另一次使用，压缩事务锁将被解压缩并存储在辅助存储器中。 可用于定位未压缩事务锁的指针存储在标题中。
-
公开(公告)号：US07636745B1
公开(公告)日：2009-12-22
申请号：US10986401
申请日：2004-11-11
申请人： David L. Detlefs
发明人： David L. Detlefs
CPC分类号： G06F13/385 , Y10S707/99931 , Y10S707/99957
摘要： A garbage collector uses the results a whole-heap marking operation to select collection sets for subsequent collection. It repeatedly calculates a measure of the cumulative collection efficiency since the marking operation, and it initiates another marking operation when the cumulative efficiency begins to deteriorate.
摘要翻译： 垃圾回收器使用结果进行全堆标记操作来选择收集集以供后续收集。 它反复计算出自标记操作以来的累积收集效率的量度，并且当累积效率开始恶化时，它开始另一个标记操作。
-
-
-
-
-
-
-
-
-
搜索结果
68 条记录 (耗时 0.039 秒)
