公开(公告)号：US07340494B1

公开(公告)日：2008-03-04

申请号：US10985447

申请日：2004-11-11

申请人： David L. Detlefs ,  Steven K. Heller ,  Alexander T. Garthwaite

发明人： David L. Detlefs ,  Steven K. Heller ,  Alexander T. Garthwaite

IPC分类号： G06F17/30

CPC分类号： G06F12/0269 ,  Y10S707/99957

摘要： A garbage collector treats a garbage-collected heap as divided into heap regions, for each of which it maintains a respective remembered set, whose entries list the locations where references located in the heap outside that region refer to references inside that region. The remembered sets are used during space-incremental collection operations on collection sets of those regions; if the garbage collector determines that objects in the collection set are not referred to directly or indirectly from outside the collection set, it reclaims the memory space that they occupy. It places entries into the remembered sets independently of the locations at which the references were found, so any region can be chosen for inclusion in any collection set; no predetermined collection order is required. Instead, the garbage collector performs global marking operations and uses the results to select for collection-set membership the regions that it can most likely collect efficiently.

摘要翻译： 一个垃圾收集器将垃圾收集堆处理成堆区域，每个堆区域维护一个相应的记忆集，其中的条目列出了位于该区域外部的堆栈中的引用引用该区域内的引用的位置。 记忆集合用于在这些区域的集合集合的空间增量集合操作中; 如果垃圾收集器确定集合集中的对象不是从集合集外部直接或间接引用，则它回收它们占用的内存空间。 它将条目放入独立于找到引用位置的记忆集中，因此可以选择任何区域以包含在任何集合集合中; 不需要预定的收款单。 相反，垃圾回收器执行全局标记操作，并使用结果为收集集成员选择最有可能高效收集的区域。

公开(公告)号：US07272695B1

公开(公告)日：2007-09-18

申请号：US10939892

申请日：2004-09-13

申请人： David L. Detlefs ,  Alexander T. Garthwaite

发明人： David L. Detlefs ,  Alexander T. Garthwaite

IPC分类号： G06F12/00

CPC分类号： G06F12/0269 ,  G06F12/0276

摘要： An incremental collector that employs remembered sets to identify the locations where a mutator has modified references to objects in respective heap regions employs a thread operating concurrently with the mutator to update the remembered sets in accordance with reference mutation. Specifically, when the mutator modifies a reference in one of a plurality of “cards” into which the collector treats the heap as divided, the concurrent thread ordinarily searches the card for references in accordance with which it updates the remembered set. But it selects certain cards, in which it has observed particularly high mutation activity, as ones in which reference mutation will not cause concurrent remembered-set updating. Remembered-set updating in response to those cards' references occurs only when all mutator threads have been suspended.

摘要翻译： 使用记忆集合来标识突变体已修改对相应堆区域中的对象的引用的位置的增量收集器采用与变异器同时操作的线程，以根据参考突变来更新记忆集合。 具体地说，当突变体修改收集器将堆分解成多个的“卡”中的一个引用时，并发线程通常在卡中搜索引用，根据该引用更新记忆集。 但是，它选择某些特别高的突变活性的卡，其中参考突变不会引起并发的记忆集更新。 只有当所有突变体线程已被暂停时，才会对这些卡的引用进行记忆集更新。

公开(公告)号：US07136887B2

公开(公告)日：2006-11-14

申请号：US10309503

申请日：2002-12-04

申请人： Alexander T. Garthwaite ,  David L. Detlefs ,  Antonios Printezis ,  Y. Srinivas Ramakrishna

发明人： Alexander T. Garthwaite ,  David L. Detlefs ,  Antonios Printezis ,  Y. Srinivas Ramakrishna

IPC分类号： G06F12/12

CPC分类号： G06F12/0269 ,  G06F12/0276 ,  Y10S707/955 ,  Y10S707/99957

摘要： A garbage collector divides the garbage-collected heap into “cards.” It maintains a table containing a card-object table entry for each card. A card's entry contains information from which the collector can determine where any references in the card are located and thereby identify objects that may be reachable. The encoding of a card's table entry is not restricted to values that indicate the location of the object in which the card begins. Instead, its possible values additionally include ones that indicate that the card begins with a certain number of references or that an object begins at a given location in the middle of the card. The collector thereby avoids consulting object's class information unnecessarily.

摘要翻译： 垃圾收集器将垃圾收集堆分成“卡”。 它维护一个包含每个卡的卡对象表条目的表。 卡的条目包含收集者可以确定卡中的任何引用位置的信息，从而识别可达到的对象。 卡的表项的编码不限于指示卡开始的对象的位置的值。 相反，其可能的值还包括指示卡以特定数量的引用开始的对象或者对象在卡的中间的给定位置开始的值。 收集器避免了不必要地查询对象的类信息。

公开(公告)号：US06826583B1

公开(公告)日：2004-11-30

申请号：US09697228

申请日：2000-10-25

申请人： Christine H. Flood ,  David L. Detlefs ,  Alexander T. Garthwaite

发明人： Christine H. Flood ,  David L. Detlefs ,  Alexander T. Garthwaite

IPC分类号： G06F1730

CPC分类号： G06F12/0269 ,  G06F12/0276 ,  Y10S707/99957

摘要： A multiprocessor, multiprogram, 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 atomic instructions. The heap is broken into a young and an old generation where semi-space copying employing local allocation buffers is used to collect the reachable objects in the young section, and for promoting objects from the young to the old generations, and parallel mark-compacting is used for collecting the old generation. Efficiency of collection is enhanced by use of card tables and linking objects, and overflow conditions are efficiently handled by linking using class pointers. The garbage collection termination using a global status word is employed.

摘要翻译： 描述了一个多处理器，多路程序，世界垃圾收集程序。 系统最初对根源进行分区，然后迭代地采用静态和动态的工作平衡。 垃圾收集线程可以动态竞争初始分区。 被描述为在线程之间提供动态负载平衡的工作窃取双端队列，其中争用减少。 竞争由原子指令解决。 堆被打破成一个年轻的老一代，使用本地分配缓冲区的半空间复制来收集年轻部分中可达到的对象，并且用于促进从年轻到老一代的对象，并行标记压缩是 用于收集老一代。 通过使用卡表和链接对象来增强收集的效率，并且通过使用类指针链接来有效地处理溢出条件。 使用全局状态字的垃圾回收终止。

公开(公告)号：US07389395B1

公开(公告)日：2008-06-17

申请号：US11169983

申请日：2005-06-26

申请人： Alexander T. Garthwaite ,  David P. Stoutamire ,  Peter B. Kessler ,  Y Srinivas Ramakrisha ,  David L. Detlefs ,  Antonios Printezis ,  Jon A. Masamitsu ,  John W. Coomes

发明人： Alexander T. Garthwaite ,  David P. Stoutamire ,  Peter B. Kessler ,  Y Srinivas Ramakrisha ,  David L. Detlefs ,  Antonios Printezis ,  Jon A. Masamitsu ,  John W. Coomes

IPC分类号： G06F12/00

CPC分类号： G06F12/0269 ,  G06F12/0253 ,  Y10S707/99953 ,  Y10S707/99957

摘要： A heap may be marked and compacted while performing only two passes over the objects and object references in the heap. Specifically, objects and object references are traversed once during a marking phase and again during a compaction phase of split-reference, two-pass mark-compaction. Object references are updated in two steps. First, during marking, each object reference may be updated to include the relative offset within its block of the referenced object and-during compaction that offset may be added to the block's destination address resulting in a reference that points to the actual post-compaction location for the referenced object. Objects of a particular block may be rearranged, or permuted, with respect to each other within the block. However, the order between groups of objects in different blocks may be preserved across compaction.

摘要翻译： 堆可以被标记和压缩，同时仅在堆中的对象和对象引用执行两次传递。 具体来说，在标记阶段期间遍历一次对象和对象引用，并在分割参考，二次标记压缩的压缩阶段再次遍历对象和对象引用。 对象引用有两个步骤更新。 首先，在标记期间，可以更新每个对象引用以包括其引用对象的块内的相对偏移量，并且 - 在压缩期间，该偏移可以被添加到块的目的地地址，导致指向实际的后压缩位置的引用 为引用的对象。 特定块的对象可以在块内相对于彼此重新布置或排列。 但是，不同块中的对象组之间的顺序可以在压缩之间保留。

公开(公告)号：US07089272B1

公开(公告)日：2006-08-08

申请号：US10464371

申请日：2003-06-18

申请人： Alexander T. Garthwaite ,  David L. Detlefs

发明人： Alexander T. Garthwaite ,  David L. Detlefs

IPC分类号： G06F17/30

CPC分类号： G06F12/0276 ,  Y10S707/99944 ,  Y10S707/99957

摘要： A technique is provided for reducing the number of write barriers executed in mutator code without compromising garbage collector performance. Advantageously, a compiler generates two forms of a mutator code—a first version with write barriers and a second version substantially without write barriers. In operation, the first version of the code may be accessed by a vtable in a “mature” near-class and the second version may be accessed by a vtable in a “nascent” near-class. According to the invention, mapping of functionally equivalent points in the first and second versions of the mutator code may be facilitated by an associated pcmap. Further, each of the first and second versions may also be associated with a respective nr_map that facilitates mapping functionally equivalent points within different branches of guard code sequences corresponding to reference-writes to non-receiver objects.

摘要翻译： 提供了一种技术，用于减少在mutator代码中执行的写入障碍的数量，而不会影响垃圾收集器的性能。 有利地，编译器生成两种形式的变异器代码 - 具有写入障碍的第一版本和基本上没有写入障碍的第二版本。 在操作中，代码的第一个版本可能被“成熟”近级的vtable访问，第二个版本可能被“新生”的近级中的vtable访问。 根据本发明，可以通过相关联的pcmap来促进变换器代码的第一和第二版本中的功能等效点的映射。 此外，第一和第二版本中的每一个也可以与相应的nr_map相关联，这些nr_map有助于将对应于对非接收器对象的引用写入的保护码序列的不同分支内的功能等效点进行映射。

公开(公告)号：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

IPC分类号： G06F9/44 ,  G06F9/54

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端的无限数量的推送和弹出进行，而不需要调用内存分配或回收，只要推送次数和流量数之间的差异保持不变 在给定范围内。 描述垃圾收集相关和显式回收实现。

公开(公告)号：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实现的一个有趣的特征是，处理器可以检测这些边界情况，例如，确定阵列是空还是满，而不检查原子操作中两个终端指针的相对位置。

公开(公告)号：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的两端的并发性。 在根据本发明的各种实现中，可以推送到共享对象上的值集合不受使用区分值的约束。 此外，显式的回收实施例有利于在存储器的自动回收不可用或不切实际的环境或应用中使用。

公开(公告)号：US07404182B1

公开(公告)日：2008-07-22

申请号：US10679183

申请日：2003-10-03

申请人： Alexander T. Garthwaite ,  Steven K. Heller

发明人： Alexander T. Garthwaite ,  Steven K. Heller

IPC分类号： G06F9/44 ,  G06F17/30

CPC分类号： G06F12/0269 ,  Y10S707/99953 ,  Y10S707/99957

摘要： The present invention provides a technique for reducing the number of write barriers without compromising garbage collector performance or correctness. To that end, a compiler defers emitting write barriers until it reaches a subsequent instruction in the mutator code. At this point, the compiler may elide repeated or unnecessary write-barrier code so as to emit only those write barriers that provide useful information to the garbage collector. By eliminating write-barrier code in this manner, the amount of write-barrier overhead in the mutator can be minimized, consequently enabling the mutator to execute faster and more efficiently. Further, collocating write barriers after the predetermined instruction also enables the compiler to generate object code having better cache performance and more efficient use of guard code than is possible using conventional write-barrier implementations.

摘要翻译： 本发明提供了一种用于在不损害垃圾收集器性能或正确性的情况下减少写入屏障的数量的技术。 为此，编译器会延迟发出写入障碍，直到到达mutator代码中的后续指令为止。 此时，编译器可能会删除重复的或不必要的写屏障代码，以便仅发出那些向垃圾收集器提供有用信息的写入障碍。 通过以这种方式消除写屏障代码，可以使突变器中的写屏障开销的量最小化，从而使得变异器能够更快更有效地执行。 此外，在预定指令之后并置写入障碍还使得编译器能够生成具有比使用常规写屏障实现可能的更高的缓存性能和更有效地使用保护代码的目标代码。