公开(公告)号：US20080250088A1

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

申请号：US11732785

申请日：2007-04-03

申请人： Antonios Printezis ,  Alexander T. Garthwaite

发明人： Antonios Printezis ,  Alexander T. Garthwaite

IPC分类号： G06F12/00

CPC分类号： G06F12/0276

摘要： The invention relates to a method for performing generational garbage collection on a heap comprising a plurality of generations. The method involves dividing a young generation of the heap into a first young generation and a second young generation, evacuating the first young generation concurrently with allocating the second young generation, and evacuating the second young generation concurrently with allocating the first young generation and subsequent to fully evacuating the first young generation.

摘要翻译： 本发明涉及一种在包含多代的堆上执行代数垃圾收集的方法。 这种方法包括将年轻一代的小朋友分成第一个年轻一代和第二个年轻一代，同时分配第一个年轻一代，分配第二个年轻一代，同时分配第二个年轻一代，分配第一个年轻一代， 全面撤离第一批年轻一代。

公开(公告)号：US07412580B1

公开(公告)日：2008-08-12

申请号：US10679559

申请日：2003-10-06

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F12/02

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

摘要： A concurrent incremental garbage collector where tracking and summarization of modified references is concurrent with application operations. A card table is arranged with write barriers so that an application's modification of objects in memory cards are memorialized in the card table. The collector performs an atomic operation, e.g., a compare-and-swap (CAS), on the card table to detect modified or written to objects. Card table indicators of dirtied cards are reset or emptied and the corresponding dirtied cards are scanned for the modifications and the remembered sets updated. Another CAS is performed on the same card table and if any dirtied cards are indicated the collector preserves the card table with the dirtied indicators and operates on a distant card table. If the CAS succeeds no modifications were made and the collector operates on the next scheduled card table group.

摘要翻译： 并行增量垃圾回收器，其中跟踪和汇总修改后的引用与应用程序操作并发。 一张卡片表装有写入障碍物，使得应用程序对存储卡中对象的修改被记录在卡片表中。 收集器在卡表上执行原子操作，例如比较和交换（CAS），以检测修改或写入对象。 脏卡的卡片表指示器被复位或清空，并且扫描相应的脏卡以进行修改并更新记忆集。 另一个CAS在相同的卡片表上执行，并且如果指示了任何脏的卡片，则收集器保留具有脏污指示器的卡片表，并在远程卡片表上操作。 如果CAS成功，则不进行修改，并且收集器在下一个预定的卡表组上运行。

公开(公告)号：US07072918B2

公开(公告)日：2006-07-04

申请号：US10395449

申请日：2003-03-24

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F17/30

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

摘要： A computer system, method and software for detecting and purging stale entries from remembered sets associated with incrementally collectible regions used in an incremental garbage collection technique like the Trains algorithm is described. Stale entries are detected by a number of techniques, and then purged, eliminated, or scrubbed. These techniques make use of the summarized information about regions such as cards or incrementally collectible regions that indicate age of allocation, time a region was last scanned, last time an entry was inserted into a remembered set, as well as how far forward or backward objects in a given region refer in a generation.

摘要翻译： 描述了一种计算机系统，方法和软件，用于检测和清除与诸如列车算法之类的增量垃圾收集技术中使用的增量收集区域相关联的记忆集的陈旧条目。 通过多种技术检测陈旧的条目，然后清除，消除或擦洗。 这些技术利用关于诸如卡或递增可收集区域的区域的汇总信息，这些区域指示分配的年龄，上次扫描的时间，上次将记录插入到记忆集中的时间，以及前进或后退的对象 在一个给定的地区，在一代人中引用。

公开(公告)号：US07072905B2

公开(公告)日：2006-07-04

申请号：US10313657

申请日：2002-12-06

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F17/30

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

摘要： A garbage collector for more efficient placement of objects referenced from external references. The expected life times of these objects is measured by trial and error, by the class or type, by how often the object has been evacuated or the external reference processed, by the stability and longevity of the root source, or by the prolificness of the class or type of object. The measured value is held in the header of each object in an AGE field available for this purpose. These objects may be evacuated into existing trains or into new trains, or into a combination of existing and new trains. When new trains are created the trains are distributed among the existing trains according to a distribution contour that may be linear, normal, gamma or any other contour that might be found useful. Also, when new trains are created the youngest train must be a new train. When objects are evacuated into existing trains the objects are placed in trains according the survivability of the objects with the longer-lived objects placed proportionally in the younger trains. The objects are evacuated into the new trains from oldest to youngest trains according to the value in the AGE field. The higher the value the younger the train. A threshold on the AGE value may be established such that when the threshold is reached, the objects are evacuated into the youngest new train.

摘要翻译： 一个垃圾回收器，用于更有效地放置从外部引用引用的对象。 这些物体的预期寿命是通过试验和误差，类别或类型，物体被疏散或外部参考物处理的频率，根源的稳定性和寿命，或由 类或类型的对象。 测量值保存在可用于此目的的AGE字段中的每个对象的标题中。 这些物体可能被撤离到现有的火车或新列车中，或者组合到现有的和新的列车中。 当新列车被创建时，根据可能是线性，正常，伽马或任何其他可能被发现有用的轮廓的分布轮廓，在现有列车之间分配列车。 此外，当新列车创建时，最小的火车必须是新的列车。 当物体撤离到现有火车中时，物体按照物体的生存能力放置在列车中，而较长寿命的物体按比例放置在较小的火车上。 这些物品根据AGE领域的价值从最旧到最早的列车撤离到新列车中。 火车越小越贵。 可以建立AGE值的阈值，使得当达到阈值时，物体被排空到最年轻的新列车中。

公开(公告)号：US07069280B2

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

申请号：US10313768

申请日：2002-12-06

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F17/30

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

摘要： A garbage collector employs the train algorithm to collect a generation in a dynamically allocated heap. When direct allocation of an object into the generation results in the need to allocate a new car section, the collector makes a determination of whether a new collection increment or interval needs to be initiated. It makes this determination by comparing the amount of new allocation in that generation with a threshold value. During each collection increment, it updates the threshold value by determining how much can occur during the next collection increment without exceeding an allowable pause time. It then projects from that value how much memory-space reclamation is likely to occur. From that likely amount of reclamation, it arrives at a limit on the permitted amount of allocation.

摘要翻译： 垃圾收集器采用列车算法在动态分配的堆中收集一代。 当将对象直接分配到生成中导致需要分配新的汽车部分时，收集器确定是否需要启动新的收集增量或间隔。 它通过将该代中的新分配量与阈值进行比较来确定。 在每次收集增量期间，它通过确定在下一次收集增加期间可以发生多少，而不超过允许的暂停时间来更新阈值。 然后从该值预测可能发生多少内存空间回收。 从可能的填海量来看，这是允许的分配数量的限制。

公开(公告)号：US07035884B2

公开(公告)日：2006-04-25

申请号：US10288008

申请日：2002-11-05

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F12/12

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

摘要： A garbage collector collects a dynamically allocated heap by employing the train algorithm, in which “car” sections of a heap generation are organized in groups, or “trains.” When a car section comes up for collection, objects that it contains are evacuated if they are referred to by references located in cars not currently being collected. The cars to which they are evacuated belong to the trains that contain the references. The trains form a sequence in which their constituent cars are to be collected, and objects that are directly allocated in the generation are placed into trains that precede some existing train in the collection sequence.

摘要翻译： 垃圾收集器通过采用列车算法收集动态分配的堆，其中堆生成的“汽车”部分被组织成“火车”。 当汽车部分出现收集时，如果通过目前正在收集的汽车中的参考文献提及其所包含的物体，则将其撤回。 他们撤离的汽车属于包含参考文件的列车。 火车形成其组成汽车要被收集的序列，在一代中直接分配的物体被放置在收集序列中先于一些现有列车之前的列车中。

公开(公告)号：US07660961B2

公开(公告)日：2010-02-09

申请号：US11732785

申请日：2007-04-03

申请人： Antonios Printezis ,  Alexander T. Garthwaite

发明人： Antonios Printezis ,  Alexander T. Garthwaite

IPC分类号： G06F12/00

CPC分类号： G06F12/0276

摘要： The invention relates to a method for performing generational garbage collection on a heap comprising a plurality of generations. The method involves dividing a young generation of the heap into a first young generation and a second young generation, evacuating the first young generation concurrently with allocating the second young generation, and evacuating the second young generation concurrently with allocating the first young generation and subsequent to fully evacuating the first young generation.

摘要翻译： 本发明涉及一种在包含多代的堆上执行代数垃圾收集的方法。 这种方法包括将年轻一代的小朋友分成第一个年轻一代和第二个年轻一代，同时分配第一个年轻一代，分配第二个年轻一代，同时分配第二个年轻一代，分配第一个年轻一代， 完全疏散第一代青年。

公开(公告)号：US07539713B2

公开(公告)日：2009-05-26

申请号：US10287930

申请日：2002-11-05

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

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

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

摘要： A garbage collector for reclaiming computer-memory space occupied by unreachable data objects operates incrementally in accordance with the train algorithm. Although most objects share car sections with other objects, objects found to be referred to by a large number of references are placed in their own individual car sections so that the “popular” object's train membership can be changed without relocating the object and thus requiring the numerous references to it to be updated. The collector keeps track of different object classes to have instances that are popular. If a class exhibits a strong tendency to have popular instances, the collector initially places instances of that class into respective single-object cars even if those objects have not yet been identified as popular.

摘要翻译： 用于回收由不可达数据对象占用的计算机存储器空间的垃圾收集器根据列车算法递增地进行操作。 虽然大多数对象与其他对象共享汽车部分，但是由大量参考文献发现的对象被放置在其各自的车辆部分中，使得可以改变“流行”对象的列车成员资格而不重新定位对象，因此需要 许多参考它被更新。 收集器跟踪不同的对象类以具有受欢迎的实例。 如果一个班级表现出很受欢迎的实例倾向，那么收藏家最初会把这个类别的实例放在相应的单一物体汽车中，即使这些物体尚未被识别为受欢迎的。

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

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

公开(公告)号：US20070294499A1

公开(公告)日：2007-12-20

申请号：US11452533

申请日：2006-06-14

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F12/00

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

摘要： Reference updating in a sliding compaction garbage collector may involve maintaining, for each logical region of the heap to be compacted, values that represent the range of addresses referenced by individual regions of the heap. For example, a highest-referenced address (HRA) represents the maximum address referenced by any object references in the respective region. Similarly, a lowest-reference address (LRA) represents the minimum address referenced by a region. When updating references during compaction, if the HRA and/or LRA for a particular region indicate that all references within the region point to addresses within a region of memory that will not be relocated during compaction, such as a dense prefix, the references with the particular region need not be updated. Maintaining HRAs and/or LRAs for region of heap memory may simplify determining whether or not references within individual regions require updating.

摘要翻译： 滑动式压缩垃圾回收器中的参考更新可能涉及为堆的每个逻辑区域维护代表堆的各个区域引用的地址范围的值。 例如，最高参考地址（HRA）表示相应区域中任何对象引用引用的最大地址。 类似地，最低参考地址（LRA）表示由一个区域引用的最小地址。 在压缩期间更新引用时，如果特定区域的HRA和/或LRA指示区域内的所有引用指向在压缩期间将不会重定位的内存区域内的地址（例如密集前缀），则引用具有 特定区域不需要更新。 维护堆存储区域的HRAs和/或LRA可以简化确定各个区域内的引用是否需要更新。