公开(公告)号：US07069281B2

公开(公告)日：2006-06-27

申请号：US10372890

申请日：2003-02-24

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F17/30

CPC分类号： G06F12/0276 ,  G06F9/4493 ,  G06F12/0253 ,  Y10S707/99953 ,  Y10S707/99957

摘要： A copying garbage collector evacuates to a to space the objects in a from space that are referred to by references, including references in previously evacuated objects, that are located outside the from space. It divides the to space into local-allocation buffers (“LABs”), and it adopts one of these as a destination LAB, i.e., as the LAB into which it places the objects that it evacuates. When a destination LAB becomes full, the thread adopts a new LAB as its destination LAB. When a destination LAB's contents fill it to some predetermined fill threshold, that destination LAB becomes the source LAB, i.e., the LAB that the collector scans for references to the collection-set objects. If a previous source LAB's contents has not yet been completely scanned when the collector thus adopts a new source LAB, the previous source LAB is placed on a LAB stack. When no more references to unevacuated collection-set objects remain in its current source LAB, the collector then pops a LAB from its LAB stack on a last-in, first-out basis and adopts that LAB as the source LAB.

摘要翻译： 复制垃圾收集器撤离到空间中的对象，该对象在引用的参考空间中，包括位于空间外部的先前抽空物体中的引用。 它将空间划分为本地分配缓冲区（“LAB”），并将它们中的一个作为目的地LAB，即作为其放置对象的LAB作为LAB。 当目的地LAB变满时，线程采用新的LAB作为其目的地LAB。 当目的地LAB的内容将其填充到某个预定的填充阈值时，该目的地LAB成为源LAB，即收集者扫描对集合集对象的引用的LAB。 如果当收集器采用新的源LAB时，以前的源LAB的内容尚未被完全扫描，则先前的源LAB被放置在LAB堆栈上。 当没有更多的对未完成的集合集对象的引用仍保留在其当前的源LAB中时，收集器然后以先前先出的方式从其LAB堆栈中弹出LAB，并采用该LAB作为源LAB。

公开(公告)号：US07039664B2

公开(公告)日：2006-05-02

申请号：US10309909

申请日：2002-12-04

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F17/30

CPC分类号： G06F12/0276 ,  Y10S707/955 ,  Y10S707/968 ,  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. Specifically, although each entry is smaller than a memory address, it has enough possible values to give the relative location of the object in which the associated card begins or to direct the collector to another entry for that information. But the entries are additionally grouped into sequences of contiguous entries that together are large enough to contain a complete address. When every card associated with a entry in a given (address-sized) entry sequence begins in the same object, that entry sequence is together given a value that the collector can recognize as indicating that object's absolute location.

摘要翻译： 垃圾收集器将垃圾收集堆分成“卡”。 它维护一个包含每个卡的卡对象表条目的表。 卡的条目包含收集者可以确定卡中的任何引用位置的信息，从而识别可达到的对象。 具体来说，虽然每个条目都小于存储器地址，但是它具有足够的可能值来给出相关卡开始的对象的相对位置，或将收集器引导到该信息的另一条目。 但是条目另外被分组成连续条目的序列，其一起足够大以包含完整的地址。 当与给定（地址大小）条目序列中的条目相关联的每个卡片都在同一对象中开始时，该条目序列一起给出了收集器可以识别为指示对象的绝对位置的值。

公开(公告)号：US06999979B2

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

申请号：US10288608

申请日：2002-11-05

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F12/12

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

摘要： In a garbage collector that employs the train algorithm, remembered sets are employed to record the locations of references to objects in a train car in objects outside the car. During each collection, remembered set entries are processed to find the locations of references into the cars yet to be collected. The found locations are stored in scratch-pad lists, and each entry in that list includes a mode indicator that specifies whether the entry represents a single reference location or the locations of more than one reference. One possible value of the mode indicator indicates that the entry consists of two computer words rather than one, the second computer word containing a list of offsets into a region specified by the first word. Another possible mode-indicator value indicates that a region contains references, but it does not specify where within the region those references occur.

摘要翻译： 在采用列车算法的垃圾收集器中，采用记忆集来记录在汽车中的对象中的火车车厢中对象的引用位置。 在每个收集期间，处理记忆集条目以找到尚未收集的车辆中的引用位置。 找到的位置存储在便笺本列表中，该列表中的每个条目都包含一个模式指示符，用于指定条目是单个引用位置还是多于一个引用的位置。 模式指示符的一个可能的值表示条目由两个计算机词组成，而不是一个，第二个计算机单词包含偏移列表到由第一个单词指定的区域。 另一个可能的模式指标值表示一个区域包含引用，但是它没有指定这些引用出现在哪里。

公开(公告)号：US06965905B2

公开(公告)日：2005-11-15

申请号：US10325003

申请日：2002-12-20

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F12/02 ,  G06F17/30

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

摘要： A multi-threaded garbage collector operates in increments and maintains, for each of a plurality of car sections in which it has divided a portion of the heap, a respective remembered set of the locations at which it has found references to objects in those car sections. It stores the remembered sets in respective hash tables, whose contents it updates in a scanning operation, executed concurrently by multiple threads, in which it finds references and records their locations in the appropriate tables. Occasionally, one of the threads replaces the hash table for a given car section. Rather than wait for the replacement operation to be completed, a thread that has an entry to be made into that car section's remembered set accesses the old table to find out whether the entry has already been made. If so, no new entry is necessary. Otherwise, it places an entry into the old table and sometimes places an insertion record containing that entry into a linked list associated with that car section. When the reclaiming thread has finished transferring information from the old table to the new table, it transfers information from the linked list of insertion records into the new table, too. In this way, the replacement process is not a bottleneck to other threads' performing update operations.

摘要翻译： 多线程垃圾回收器以增量方式操作，并且对于其中已经分割堆的一部分的多个轿厢部分中的每一个，维护已经发现对这些轿厢部分中的对象的引用的相应的记忆集合 。 它将各个哈希表中的记忆集合存储在其扫描操作中更新的内容，多个线程并发执行，其中查找引用并将其位置记录在适当的表中。 有时候，其中一个线程将替换给定汽车部分的哈希表。 而不是等待更换操作完成，具有要进入该汽车部分的记忆集的条目的线程访问旧表，以确定该条目是否已经被创建。 如果是，则不需要新的条目。 否则，它将一个条目放入旧表中，有时将包含该条目的插入记录放置到与该车段相关联的链接列表中。 当回收线程已经将信息从旧表转移到新表时，它也将信息从插入记录的链表传输到新表中。 这样，替换过程不是其他线程执行更新操作的瓶颈。

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

公开(公告)号：US06799236B1

公开(公告)日：2004-09-28

申请号：US10044214

申请日：2001-11-20

申请人： David Dice ,  Alexander T. Garthwaite

发明人： David Dice ,  Alexander T. Garthwaite

IPC分类号： G06F1214

CPC分类号： G06F9/52 ,  G06F9/3004 ,  G06F9/30087

摘要： Mechanisms and techniques operate in a computerized device to execute critical code without interference from interruptions. Critical code is registered for invocation of a critical execution manager in the event of an interruption to the critical code. The critical code is then executed until an interruption to the critical code occurs. After handling the interruption, a critical execution manager is invoked and the critical execution manager detects if an interference signal indicates a reset value. If the interference signal indicates the reset value, the critical execution manager performs a reset operation on the critical code to reset a current state of the critical code to allow execution of the critical code while avoiding interference from handling the interruption and returns to execution of the critical code using the current state of the critical code.

摘要翻译： 机制和技术在计算机化设备中运行，以执行关键代码，而不受中断的干扰。 在关键代码中断的情况下，注册关键代码用于调用关键执行管理器。 然后执行关键代码，直到出现关键代码的中断。 处理中断后，调用关键执行管理器，关键执行管理器检测干扰信号是否指示复位值。 如果干扰信号指示复位值，则关键执行管理器对关键代码执行复位操作，以重置关键代码的当前状态，以允许执行关键代码，同时避免干扰来处理中断并返回执行 关键代码使用关键代码的当前状态。

公开(公告)号：US06529919B1

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

申请号：US09504091

申请日：2000-02-15

申请人： Ole Agesen ,  Alexander T. Garthwaite

发明人： Ole Agesen ,  Alexander T. Garthwaite

IPC分类号： G06F1200

CPC分类号： G06F9/44594 ,  G06F9/4493 ,  G06F12/0276 ,  Y10S707/99944 ,  Y10S707/99953 ,  Y10S707/99957

摘要： A garbage collector collects a train-managed heap in accordance with the train algorithm. In doing so, it concentrates into a respective train the heap-located objects that belong to garbage cycles even if those cycles additionally include certain types of objects that are outside the train-managed heap. It does so by using objects within the heap as proxies for those extra-heap objects, and it evacuates into a proxy object's train any collection-set objects referred to by the extra-heap objects for which the proxy object is a proxy. The objects in those garbage cycles containing the extra-heap objects can thereby be collected incrementally despite the extra-heap references to them.

摘要翻译： 垃圾收集器根据列车算法收集火车管理的堆。 在这样做时，它集中在各自的列车中，即属于垃圾循环的堆定位对象，即使这些周期还包括列在列车管理堆外部的某些类型的对象。 它通过使用堆内的对象作为这些超堆对象的代理，并将代理对象作为代理的额外堆对象引用的任何集合集对象撤回到代理对象的列表中。 因此，包含堆外对象的这些垃圾循环中的对象可以逐渐收集，尽管对它们进行了额外的引用。

公开(公告)号：US06449626B1

公开(公告)日：2002-09-10

申请号：US09377137

申请日：1999-08-19

申请人： Alexander T. Garthwaite ,  Ole Agesen

发明人： Alexander T. Garthwaite ,  Ole Agesen

IPC分类号： G06F1730

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

摘要： A garbage collector collects a generation of a collected heap in accordance with the train algorithm. It employs remembered sets associated with respective car sections to keep track of references into the associated car sections. Each remembered set contains entries that identify respective regions in the generation that contain references into the associated car section. In some collection cycles, the collector collects a collection set of more than one car section. When it does, it processes the remembered-set entries by searching the regions specified thereby not only for references into the associated car sections but also for references into other car sections in the collection set. The collector further treats the generation as divided into segments, for each of which it maintains a Boolean value that indicates whether the segment has been searched during the current collection cycle. If it has, the collector does not search it in response to a subsequently encountered remembered-set entry that identifies a region in which that segment is included.

摘要翻译： 垃圾收集器根据列车算法收集一代收集的堆。 它使用与相应轿厢部分相关联的记忆集合来跟踪到相关联的轿厢部分的参考。 每个记住的集合包含标识生成中包含对相关联的汽车部分的引用的各个区域的条目。 在一些收集周期中，收集器收集一组多个汽车部分。 当它是这样做时，它通过搜索指定的区域来处理记忆集条目，不仅对于相关联的轿厢部分的引用，而且还用于对集合集合中的其他轿厢部分的引用。 收集器进一步将生成分为段，每个段保持一个布尔值，该值指示在当前收集循环期间是否已搜索段。 如果有，则收集器不会响应于随后遇到的记住集合条目来搜索它，该条目标识了包含该段的区域。

公开(公告)号：US06434576B1

公开(公告)日：2002-08-13

申请号：US09377349

申请日：1999-08-19

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F1730

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

摘要： A garbage collector that employs the train algorithm identifies popular objects by a count of references to them and places such objects into special, single-object car sections that are normally smaller than the car sections employed for objects that are less popular. When such cars are part of the collection set and evacuated, the evacuation occurs by relinking, without relocating the objects and memory. References to such popular objects therefore do not need to be updated as a result of evacuation. A limit is imposed on the number of entries in the remembered sets used to keep track of references to objects and such popular-object car sections, and any popular-object car section whose remembered set has more than a threshold number of entries is treated as reachable and still popular without having the memory regions that those entries identify searched for valid references.

摘要翻译： 使用列车算法的垃圾收集器通过对它们的引用的计数来识别流行的对象，并将这些对象放置成特定的单对象汽车部分，其通常小于用于不太受欢迎的对象的汽车部分。 当这些汽车是收集集和撤离的一部分时，通过重新链接进行疏散，而不会拆卸物体和记忆。 因此，对这种受欢迎的对象的引用不需要由于撤离而被更新。 对用于跟踪对象和这种流行对象汽车部分的引用的记忆集中的条目数量进行限制，并且任何流行对象汽车部分的记忆集合具有多于阈值数量的条目被视为 可访问并仍然受欢迎，而没有这些条目标识的存储区域搜索有效的引用。