-
公开(公告)号：US06934741B2
公开(公告)日：2005-08-23
申请号：US09892813
申请日：2001-06-27
IPC分类号： G06F9/44 , G06F15/167
CPC分类号： G06F9/4493
摘要： A garbage collector employs a plurality of task queues for a parallel-execution operation in a garbage-collection cycle. Each task queue is associated with a different ordered pair of the threads that perform the parallel-execution operation in parallel. One of the threads, referred to as that task queue's “enqueuer” thread, is the only one that can “push” onto that queue an identifier of a dynamically identified task. The other thread, referred to as that task queue's “dequeuer,” is the only one that can “pop” tasks from that task queue for execution. Since, for each task queue, there is only one thread that can “push” task identifiers on to it and only one thread that can “pop” task identifiers from it, the garbage collector can share dynamically identified tasks optimally among its threads without suffering the cost imposed by making combinations of otherwise separate machine instructions atomic.
摘要翻译： 垃圾收集器采用多个任务队列进行垃圾回收循环中的并行执行操作。 每个任务队列与并行执行并行执行操作的线程的不同有序对相关联。 其中一个线程称为该任务队列的“入队”线程，是唯一能够将该队列推送到动态识别任务的标识符的线程。 称为该任务队列的“dequeuer”的另一个线程是唯一可以从任务队列中“弹出”任务执行的线程。 因为对于每个任务队列，只有一个线程可以将任务标识符“推”给它，并且只有一个线程可以从其中“弹出”任务标识符，垃圾收集器可以在其线程之间最佳地共享动态识别的任务，而不会遭受痛苦 通过组合以其他方式分离的机器指令原子强加的成本。
-
公开(公告)号：US07103887B2
公开(公告)日：2006-09-05
申请号：US09893256
申请日：2001-06-27
CPC分类号： G06F9/4843
摘要： In response to source code that represents instructions for dynamically allocating memory to objects, a compiler/interpreter produces instructions that implement a garbage collector. The garbage collector operates in garbage-collection cycles, which include parallel-execution operations such as locating reachable objects. Each thread maintains a respective task queue onto which it pushes identifiers of objects thus found and from which it pops those identifiers in order to begin the tasks of locating the further objects to which objects specified by the thus-popped identifiers refer. A thread's access to its respective task queue ordinarily occurs on a last-in, first-out basis, but the access mode switches to a first-in, first-out basis if the number of task-queue entries exceeds a predetermined threshold.
-
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实现的一个有趣的特征是，处理器可以检测这些边界情况，例如，确定阵列是空还是满，而不检查原子操作中两个终端指针的相对位置。
-
公开(公告)号：US07159215B2
公开(公告)日：2007-01-02
申请号：US09893264
申请日：2001-06-27
申请人： Nir N. Shavit , Xiaolan Zhang , Christine H. Flood
发明人： Nir N. Shavit , Xiaolan Zhang , Christine H. Flood
IPC分类号： G06F9/46
CPC分类号： G06F12/0269 , G06F9/4493
摘要： A “garbage collector” employed to reclaim memory dynamically allocated to data objects employs multiple execution threads to perform a parallel-execution operation and its garbage-collection cycle. A thread executes tasks that it selects from lists whose entries represent tasks dynamically identified during other tasks' performance. When a thread fails to find a task in one of these lists, it sets to an inactivity-indicating value a field associated with it in a global status word. It also determines whether any field associated with any of the other threads indicates activity. If not, the thread concludes that the parallel-execution operation has been completed. Otherwise, it returns to searching for further tasks to perform.
摘要翻译： 用于回收动态分配给数据对象的内存的“垃圾收集器”使用多个执行线程来执行并行执行操作及其垃圾回收循环。 线程执行从列表中选择的任务，其条目表示在其他任务执行期间动态识别的任务。 当一个线程无法在其中一个列表中找到任务时，它将在全局状态字中设置为与其关联的字段的不活动指示值。 它还确定与任何其他线程相关联的任何字段是否指示活动。 如果没有，线程认为并行执行操作已经完成。 否则，它返回到搜索进一步的任务。
-
公开(公告)号：US07640544B2
公开(公告)日：2009-12-29
申请号：US10996508
申请日：2004-11-23
CPC分类号： G06F12/0276 , Y10S707/99953 , Y10S707/99957
摘要： A multiprocessor, multi-program, stop-the-world garbage collection program is described. The system initially over partitions the root sources, and then iteratively employs static and dynamic work balancing. Garbage collection threads compete dynamically for the initial partitions. Work stealing double-ended queues, where contention is reduced, are described to provide dynamic load balancing among the threads. Contention is resolved by using atomic instructions. The heap is broken into a young and an old generation where parallel semi-space copying is used to collect the young generation and parallel mark-compacting the old generation. Speed and efficiency of collection is enhanced by use of card tables and linking objects, and overflow conditions are efficiently handled by linking using class pointers. A garbage collection termination employs a global status word.
摘要翻译： 描述了一个多处理器，多程序，停止世界的垃圾收集程序。 系统最初对根源进行分区，然后迭代地采用静态和动态的工作平衡。 垃圾收集线程可以动态竞争初始分区。 被描述为在线程之间提供动态负载平衡的工作窃取双端队列，其中争用减少。 竞争通过使用原子指令来解决。 堆被打破成一个年轻和老一代，平行的半空间复制用于收集年轻一代和平行的标记压实老一代。 通过使用卡表和链接对象来增强收集的速度和效率，并且通过使用类指针进行链接来有效地处理溢出条件。 垃圾收集终端采用全局状态字。
-
公开(公告)号：US06823351B1
公开(公告)日：2004-11-23
申请号：US09697729
申请日：2000-10-26
IPC分类号： G06F1730
CPC分类号： G06F12/0276 , Y10S707/99953 , Y10S707/99957
摘要： A multiprocessor, multi-program, stop-the-world garbage collection program is described. The system initially over partitions the root sources, and then iteratively employs static and dynamic work balancing. Garbage collection threads compete dynamically for the initial partitions. Work stealing double-ended queues, where contention is reduced, are described to provide dynamic load balancing among the threads. Contention is resolved by using atomic instructions. The heap is broken into a young and an old generation where parallel semi-space copying is used to collect the young generation and parallel mark-compacting the old generation. Speed and efficiency of collection is enhanced by use of card tables and linking objects, and overflow conditions are efficiently handled by linking using class pointers. A garbage collection termination employs a global status word.
摘要翻译： 描述了一个多处理器，多程序，停止世界的垃圾收集程序。 系统最初对根源进行分区，然后迭代地采用静态和动态的工作平衡。 垃圾收集线程可以动态竞争初始分区。 被描述为在线程之间提供动态负载平衡的工作窃取双端队列，其中争用减少。 竞争通过使用原子指令来解决。 堆被打破成一个年轻和老一代，平行的半空间复制用于收集年轻一代和平行的标记压实老一代。 通过使用卡表和链接对象来增强收集的速度和效率，并且通过使用类指针进行链接来有效地处理溢出条件。 垃圾收集终端采用全局状态字。
-
公开(公告)号：US08473950B2
公开(公告)日：2013-06-25
申请号：US12490287
申请日：2009-06-23
CPC分类号： G06F9/466
摘要： A system for managing transactions, including a first reference cell associated with a starting value for a first variable, a first thread having an outer atomic transaction including a first instruction to write a first value to the first variable, a second thread, executing in parallel with the first thread, having an inner atomic transaction including a second instruction to write a second value to the first variable, where the inner atomic transaction is nested within the outer atomic transaction, a first value node created by the outer atomic transaction and storing the first value in response to execution of the first instruction, and a second value node created by the inner atomic transaction, storing the second value in response to execution of the second instruction, and having a previous node pointer referencing the first value node.
摘要翻译： 一种用于管理事务的系统，包括与第一变量的起始值相关联的第一参考单元，具有包含向第一变量写入第一值的第一指令的外部原子事务的第一线程，并行执行的第二线程 具有第一线程，具有包含向第一变量写入第二值的第二指令的内部原子事务，其中内部原子事务嵌套在外部原子事务内，由外部原子事务创建的第一个值节点并存储 响应于第一指令的执行的第一值和由内部原子事务创建的第二值节点，响应于第二指令的执行存储第二值，并且具有引用第一值节点的先前节点指针。
-
公开(公告)号：US07583687B2
公开(公告)日：2009-09-01
申请号：US11325209
申请日：2006-01-03
摘要： One embodiment of the present invention provides a system that facilitates performing operations on a lock-free double-ended queue (deque). This deque is implemented as a doubly-linked list of nodes formed into a ring, so that node pointers in one direction form an inner ring, and node pointers in the other direction form an outer ring. The deque has an inner hat, which points to a node next to the last occupied node along the inner ring, and an outer hat, which points to a node next to the last occupied node along the outer ring. The system uses a double compare-and-swap (DCAS) operation while performing pop and push operations onto either end of the deque, as well as growing and shrinking operations to change the number of nodes that are in the ring used by the deque.
摘要翻译： 本发明的一个实施例提供一种有助于在无锁双端队列（deque）上执行操作的系统。 该deque被实现为形成环的节点的双向链表，使得在一个方向上的节点指针形成内环，并且在另一方向上的节点指针形成外环。 德克有一个内帽，它指向沿着内圈的最后一个占用节点旁边的一个节点，以及一个外帽，它指向沿着外圈的最后占用节点旁边的一个节点。 系统使用双重比较和交换（DCAS）操作，同时在deque的任一端执行弹出和推送操作，以及增长和缩小操作以更改由deque使用的环中的节点数。
-
9.发明授权Multi-threaded garbage collector employing cascaded memory arrays of task identifiers to implement work stealing queues for task identification and processing 有权多线程垃圾收集器采用任务标识符的级联存储器阵列来实现任务识别和处理的工作窃取队列公开(公告)号：US07016923B2
公开(公告)日：2006-03-21
申请号：US10287851
申请日：2002-11-05
IPC分类号： G06F12/00
CPC分类号： G06F12/0276 , Y10S707/99953 , Y10S707/99957
摘要： A computer system employing a plurality of concurrent threads to perform tasks that dynamically identify further similar tasks employs a double-ended queue (“deque”) to list the dynamically identified tasks. If a thread's deque runs out of tasks while other threads' deques have tasks remaining, the thread whose deque has become empty will remove one or more entries from another thread's deque and perform the tasks thereby identified. When a thread's deque becomes too full, it may allocate space for another deque, transfer entries from its existing deque, place an identifier of the existing deque into the new deque, and adopt the new deque as the one that it uses for storing and retrieving task identifiers. Alternatively, it may transfer some of the existing deque's entries into a newly allocated array and place an identifier of that array into the existing deque. The thread thereby deals with deque overflows without introducing additional synchronization requirements or restricting the deque's range of use.
摘要翻译： 采用多个并行线程来执行动态地识别进一步类似任务的任务的计算机系统采用双端队列（“deque”）列出动态识别的任务。 如果一个线程的deque用完了任务，而其他线程的deques有剩余的任务，则其deque已经变空的线程将从另一个线程的deque中删除一个或多个条目，然后执行这样识别的任务。 当一个线程的deque变得太满时，它可以为另一个deque分配空间，从现有deque传输条目，将现有deque的标识符放置到新deque中，并采用新的deque作为它用于存储和检索的deque 任务标识符。 或者，它可以将一些现有deque的条目转移到新分配的数组中，并将该数组的标识符放置到现有deque中。 因此，线程处理德克尔溢出，而不引入额外的同步要求或限制德克的使用范围。
-
10.发明授权Method and apparatus for reducing remembered set overhead in a generational garbage collector by constraining collection set choice 有权通过约束收集集选择减少代数垃圾收集器中记忆集开销的方法和装置公开(公告)号：US07539837B1
公开(公告)日：2009-05-26
申请号：US11128791
申请日：2005-05-13
CPC分类号： G06F12/0276 , Y10S707/99953 , Y10S707/99957
摘要： A remembered set for a memory heap region in a garbage-collected computer system is modified to classify reference locations stored therein by the heap region from which the references originate so that the number of references originating from a given region can be easily determined. If the number of remembered set entries for references from a second region to a first region reaches a predetermined threshold, the second region is constrained so that it will be collected at the same time as, or before, the first region. Then, all entries in the remembered set associated with the first region for references from the second region to the first region can be deleted, and no such entries need be entered in the future thereby reducing the size of that remembered set and the time required to scan it.
摘要翻译： 对垃圾收集的计算机系统中的存储器堆区域的记忆集进行修改，以便通过引用源所在的堆区域对存储在其中的引用位置进行分类，从而可以容易地确定源自给定区域的引用数量。 如果用于从第二区域到第一区域的引用的记忆设置条目的数量达到预定阈值，则第二区域被约束，使得其将在与第一区域相同的时间或之前被收集。 然后，可以删除与第一区域相关联的用于从第二区域到第一区域的引用的记住集合中的所有条目，并且将来不需要输入这样的条目，从而减小该记忆集的大小以及所需的时间 扫描它
-
-
-
-
-
-
-
-
-
搜索结果
15 条记录 (耗时 0.026 秒)
