公开(公告)号：US07146390B2

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

申请号：US10372905

申请日：2003-02-24

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F12/00

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

摘要： A garbage collector that reclaims memory space no longer needed by a mutator treats a generation of a dynamically allocated heap as being divided into “car” sections. For each car section, the collector maintains a remembered-set structure in which it keeps a record of the locations in the generation where the collector has previously found references to locations in that car section. The collector operates in increments in each of which it collects a respective collection set consisting of one or more of the generation's car sections. From the remembered sets associated with a collection set's car sections, it generates scratch-pad lists whose entries tell where locations identified by those remembered sets still contain references to collection-set locations. In situations in which the remembered sets are particularly large, the collector divides the operation of generating the scratch-pad lists into a plurality of collection intervals separated by mutator intervals. The collector bases its identification of reachable collection-set objects on the scratch-pad-list entries. By dividing the scratch-pad-list generation into multiple collection intervals, the collector can keep pause times low while employing relatively large collection sets.

摘要翻译： 一个垃圾收集器回收不再需要的内存空间，将动态分配的堆的一代分为“车”部分。 对于每个汽车部分，收集器维护一个记忆集结构，其中保存了收集器先前已经找到对该汽车部分中的位置的引用的生成中的位置的记录。 收集器以增量运行，其中每个收集由一代或多代的汽车部分组成的相应收集集。 从与集合集合的汽车部分相关联的记忆集中，它生成暂存列表，其条目告诉那些记住集合识别的位置仍然包含对集合集合位置的引用。 在记忆集特别大的情况下，收集器将生成暂存列表的操作划分为由变异器间隔分隔的多个收集间隔。 收集器将其可达到的收集集对象的标识符放在便笺簿列表条目上。 通过将暂存列表生成除以多个收集间隔，收集器可以在采用相对较大的收集集合时保持暂停时间低。

公开(公告)号：US07096329B2

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

申请号：US10375452

申请日：2003-02-27

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F12/00

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

摘要： In a garbage collector that more efficiently places newly promoted objects into a generation managed by the train algorithm, a promotion train is established near the oldest train and the objects are placed therein. If some objects are referenced from existing trains in the generation those objects are placed into those trains, and if any such objects are referenced from several existing trains, the objects are placed at the end of the youngest referencing train. The promotion train may be a new train that is placed, or a existing train that is selected, between the oldest train and the youngest train at a position based on the amount of memory compared to the size of a collection set. In the case of multiple collector threads, multiple cars in a promotion train or multiple promotion trains may be formed.

摘要翻译： 在更有效地将新推进的对象放置在由列车算法管理的一代的垃圾收集器中，在最古老的列车附近建立一个升降机列，并将物体放在其中。 如果某些物体在生成中从现有列车中引用，则将这些物体放置在这些列车中，并且如果从几个现有列车引用了任何此类物体，则将物体放置在最小的引用列车的末尾。 升降机列车可以是根据与收集集的大小相比，基于记忆体量，在最早的火车和最年轻的列车之间放置的新列车或选择的现有列车。 在多个收集器线程的情况下，可以形成升级列车中的多个轿厢或多个促销列车。

公开(公告)号：US07092978B2

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

申请号：US10373147

申请日：2003-02-24

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F17/30

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

摘要： A copying-type garbage collector operates in multiple concurrent threads. Each thread evacuates potentially reachable objects from the from space to the to space in a depth-first manner: if a thread has evacuated an object containing references to any from-space objects, it evacuates all of that object's descendants before it evacuates any other reachable objects. To keep track of descendants that must be evacuated before non-descendants can be, the thread places objects containing references to non-evacuated objects into a linked list maintained by pointers that it installs in the from-space locations from which the objects on the list were evacuated. Additionally, it divides the to space into local-allocation buffers (“LABs”) to which respective threads exclusively evacuate objects, and each thread maintains a LAB stack representing all the LABs it has filled that still contain references to unevacuated from-space objects. When a thread has completed evacuating the descendants of evacuees in all of its LABs, it “steals” work from other threads. It may do so, for instance, by processing a reference in an object belonging to another thread's list, by transferring to its own list one or more objects from another thread's list, or by transferring to its own LAB stack one or more LABs from another thread's LAB stack.

摘要翻译： 复制型垃圾收集器在多个并发线程中运行。 每个线程以深度优先的方式将潜在可达的对象从空间抽空到空间：如果线程已经抽空了包含对任何空间对象的引用的对象，则在撤销所有对象的后代之前，将其撤回所有其他可访问的对象 对象 为了跟踪在非后代之前必须撤离的后代，该线程将包含未撤离对象的引用的对象放置在由安装在列表中的对象的空间位置的指针所维护的链表中 被疏散。 此外，它将空间划分为本地分配缓冲区（“LAB”），各个线程专门排除对象，并且每个线程都维护一个LAB堆栈，代表其所填充的所有仍然包含对未完成的空间对象的引用的LAB。 当一个线程已完成撤离所有LAB中撤离人员的后代时，它从其他线程“窃取”工作。 它可以这样做，例如，通过处理属于另一个线程列表的对象中的引用，通过将自己的列表中的一个或多个对象从另一个线程的列表传输到其自身的LAB堆栈，从另一个线程列表中传递一个或多个LAB 线程的LAB堆栈。

公开(公告)号：US07062519B2

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

申请号：US10375285

申请日：2003-02-27

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F17/30

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

摘要： A technique for incrementally collecting enormous objects including scanning portions of the enormous objects on different collection steps. The scanning can be accomplished with a number of collection sets where the enormous object is re-linked and older cars remembered sets are updated on subsequent collection steps. Unscanned portions of the enormous object are scanned on subsequent collection cycles until the enormous object has been fully scanned. This incremental collection can be performed concurrently with collections of other generations and applications.

摘要翻译： 一种用于逐渐收集巨大物体的技术，包括扫描不同收集步骤上巨大物体的部分。 扫描可以通过多个收集集来实现，其中重要的对象被重新链接，并且在随后的收集步骤中更新旧的汽车记住集合。 在随后的收集循环中扫描巨大物体的未扫描部分，直到巨大的物体被完全扫描。 此增量集合可以与其他代和集合的应用程序同时执行。

公开(公告)号：US07058670B2

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

申请号：US10325049

申请日：2002-12-20

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F17/30

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

摘要： A garbage collector operates in increments in which it collects a collection set consisting of one or more segments of a dynamically allocated heap. For each of those segments it maintains a remembered set of locations in which it has previously found references to objects in that associated segment. Each remembered set is stored in a plurality of remembered-set structures, each of which is associated with a separate one of a corresponding plurality of “stripes” into which at least a portion of the heap is divided. The garbage collector executes its remembered-set-updating operations in a plurality of concurrently executing threads, each of which claims exclusive access to a subset of the constituent remembered-set structures. By restricting its access only to that subset of the remembered-set structures that it has claimed, an individual thread is able to perform its portion of the updating operation without the need for synchronization with other threads.

摘要翻译： 垃圾收集器以增量方式运行，其中收集由动态分配的堆的一个或多个段组成的集合集。 对于每个这些段，它维护一个记住的位置集合，其中它先前已经发现对该关联段中的对象的引用。 每个记忆集存储在多个记忆集合结构中，每个记忆集合结构与相应的多个“条纹”中的单独的一个相关联，其中堆的至少一部分被划分到该结构中。 垃圾收集器在多个并发执行的线程中执行其记忆集更新操作，每个线程要求对组成的记忆集结构的子集的独占访问。 通过限制其仅访问其所要求的记忆集结构的子集，单个线程能够执行其更新操作的部分，而不需要与其他线程同步。

公开(公告)号：US07024437B2

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

申请号：US10313831

申请日：2002-12-06

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

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

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

摘要： A garbage collector that operates in accordance with the train algorithm designates some cars as “special” cars into each of which at most a single object is allowed. When an object in a car being collected is referred to by a reference located in such a special car, the collector may depart from the conventional evacuation approach of placing the evacuated object into the train containing the reference referring to it. If the reference is located in an object referred to from a train younger than the train in which the reference is located, the referred-to object in the car being collected is not evacuated to the train that contains the reference to it. Instead, it is evacuated to the train from which the object containing that reference is referred to.

摘要翻译： 根据火车算法运行的垃圾收集器将一些汽车称为“特殊”轿厢，其中最多允许单个对象。 当被收集的汽车中的物体被称为位于这样一辆专用轿厢中的参考物时，收集器可以偏离常规撤离方式将撤离物体放入列入参考的列车中。 如果参考文献位于比参考文献所列火车更小的列车的对象中，则被收集的汽车中的被引用对象不被撤回到包含其引用的列车。 相反，它被撤离到包含该引用的对象所参照的列车。

公开(公告)号：US06415302B1

公开(公告)日：2002-07-02

申请号：US09377654

申请日：1999-08-19

申请人： Alexander T. Garthwaite ,  Ole Agesen

发明人： Alexander T. Garthwaite ,  Ole Agesen

IPC分类号： G06F1730

CPC分类号： G06F12/0276 ,  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. When the collector collects a car section, it reclaims the car section's objects for which there are no references, looking only in regions that the car section's remembered set specifies. Additionally, the collector treats the generation as divided into segments, for each of which it maintains a farthest-forward-car value that identifies which, among the car sections into which the respective segment contains a reference, is closest to collection. When the collector looks for references in a region that the remembered set specifies, it searches only that region's segments whose farthest-forward-car values identify car sections in the remembered set.

摘要翻译： 垃圾收集器根据列车算法收集一代收集的堆。 它使用与相应轿厢部分相关联的记忆集合来跟踪到相关联的轿厢部分的参考。 每个记住的集合包含标识生成中包含对相关联的汽车部分的引用的各个区域的条目。 当收集者收集汽车部分时，它回收汽车部分没有引用的对象，仅查看汽车部分记忆集指定的区域。 另外，收集器将生成器视为分割段，其中每个区段保持最前进的车辆值，该车辆值识别相应段中包含参考的轿厢区段中哪一个最接近于集合。 当收集器在记忆集指定的区域中查找引用时，它只搜索最远的车辆值识别记忆集中的车辆部分的区域。

公开(公告)号：US06185581B2

公开(公告)日：2001-02-06

申请号：US09377555

申请日：1999-08-19

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

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. A limit is imposed on the number of entries in the remembered sets used to keep track of references to objects in certain car sections that contain only a single object each. An object in any such car section whose remembered set has more than a threshold number of entries is treated as reachable and relinked into a younger train without having the memory regions that those entries identify searched for valid references.

摘要翻译： 垃圾收集器根据列车算法收集一代收集的堆。 它使用与相应轿厢部分相关联的记忆集合来跟踪到相关联的轿厢部分的参考。 每个记住的集合包含标识生成中包含对相关联的汽车部分的引用的各个区域的条目。 对于用于跟踪每个仅包含单个对象的某些汽车部分中的对象的引用的记忆集中的条目数量的限制。 任何这样的汽车部分中的记录集具有超过阈值数量的条目的对象被视为可到达并重新链接到较年轻的列车中，而没有这些条目标识的存储区域搜索有效参考。

公开(公告)号：US07945911B1

公开(公告)日：2011-05-17

申请号：US11147066

申请日：2005-06-03

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F9/46 ,  G06F12/00

CPC分类号： G06F9/52 ,  G06F9/4843 ,  G06F12/0253

摘要： Method and apparatus for barrier synchronization of threads, for example work-stealing threads. Embodiments may provide a consensus barrier synchronization mechanism that allows a “stop world” operation being performed by two or more worker threads configured to “steal” work from other threads to complete, even if one or more of the threads are not scheduled/started by the thread scheduler and thus do not rendezvous or “check in” at a consensus barrier in a timely manner. In embodiments, portions (subtasks) of the overall task which were assigned to the tardy thread may have been completed by other work-stealing threads, and one of the other threads may check in the tardy thread at the consensus barrier upon determining that the thread is dormant and does not have any more apportioned work to be performed. In one embodiment, the task being performed may be garbage collection for a process.

摘要翻译： 用于线程屏障同步的方法和装置，例如工作窃取螺纹。 实施例可以提供一致的障碍同步机制，其允许由两个或更多个工作线程执行“停止世界”操作，所述两个或更多个工作线程被配置为从其他线程“偷走”工作以完成，即使一个或多个线程未被调度/启动 线程调度器，因此不会及时地在协商一致的屏障上进行会合或“签入”。 在实施例中，被分配给迟延线程的整个任务的部分（子任务）可能已经被其他工作窃取线程完成，并且其他线程之一可以在确定线程之后以共识屏障检查迟延线程 是休眠的，没有任何更多的分配工作要执行。 在一个实施例中，正在执行的任务可以是进程的垃圾收集。

公开(公告)号：US07565499B1

公开(公告)日：2009-07-21

申请号：US11091032

申请日：2005-03-28

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F12/00

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

摘要： In a computer system with a garbage-collected heap memory, a cache of modified reference locations is associated with each application thread. The cache comprises a plurality of reference cache entries that are encoded in one of a plurality of ways. Using a write barrier that operates during a store operation, each application thread records modified references in its associated reference cache. Only when an entry must be evicted to make room for new information or when the thread is suspended is further processing of the reference cache required.

摘要翻译： 在具有垃圾回收堆存储器的计算机系统中，修改的引用位置的高速缓存与每个应用程序线程相关联。 高速缓存包括以多种方式之一编码的多个参考高速缓存条目。 使用在存储操作期间操作的写入屏障，每个应用程序线程在其关联的引用高速缓存中记录修改的引用。 只有当一个条目必须被赶出来为新信息腾出空间或者当线程被暂停时才进一步处理所需的引用缓存。