公开(公告)号：US07321908B2

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

申请号：US10625048

申请日：2003-07-23

申请人： Katherine Barabash ,  Yoav Ossia ,  Erez Petrank

发明人： Katherine Barabash ,  Yoav Ossia ,  Erez Petrank

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

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

摘要： A method for collecting garbage in a computing environment, the method including tracing root objects to their reachable objects in a population of objects, marking the traced objects, unmarking a marked card including any of the objects, tracing any marked object on the unmarked card to an unmarked referent object of the marked object, marking the unmarked referent object, and tracing the marked referent object to its reachable objects, concurrently with the operation of a mutator upon the population of objects within the computing environment, and, while no mutator operates upon the population of objects within the computing environment, marking the traced objects, tracing unmarked root object referents to their reachable objects, marking any of the objects, and designating any unmarked object in the population of objects as available for reallocation.

摘要翻译： 一种用于在计算环境中收集垃圾的方法，所述方法包括将根对象追溯到对象群体中的可达对象，标记所追踪对象，取消标记包括任何对象的标记卡，跟踪未标记卡上的任何标记对象， 标记未标记对象的未标记的指示对象，标记未标记的指示对象，以及将标记的对象对象追溯到其可达到的对象，与计算环境中的对象群体上的变异器的操作同时，并且在没有变异器操作的情况下 计算环境中对象的总体，标记跟踪对象，跟踪未标记的根对象指向其可到达对象，标记任何对象，以及指定可用于重新分配的对象群体中的任何未标记对象。

公开(公告)号：US20050021576A1

公开(公告)日：2005-01-27

申请号：US10625048

申请日：2003-07-23

申请人： Katherine Barabash ,  Yoav Ossia ,  Erez Petrank

发明人： Katherine Barabash ,  Yoav Ossia ,  Erez Petrank

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

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

摘要： A method for collecting garbage in a computing environment, the method including tracing root objects to their reachable objects in a population of objects, marking the traced objects, unmarking a marked card including any of the objects, tracing any marked object on the unmarked card to an unmarked referent object of the marked object, marking the unmarked referent object, and tracing the marked referent object to its reachable objects, concurrently with the operation of a mutator upon the population of objects within the computing environment, and, while no mutator operates upon the population of objects within the computing environment, marking the traced objects, tracing unmarked root object referents to their reachable objects, marking any of the objects, and designating any unmarked object in the population of objects as available for reallocation.

摘要翻译： 一种用于在计算环境中收集垃圾的方法，所述方法包括将根对象追溯到对象群体中的可达对象，标记所追踪对象，取消标记包括任何对象的标记卡，跟踪未标记卡上的任何标记对象， 标记未标记对象的未标记的指示对象，标记未标记的指示对象，以及将标记的对象对象追溯到其可达到的对象，与计算环境中的对象群体上的变异器的操作同时，并且在没有变异器操作的情况下 计算环境中对象的总体，标记跟踪对象，跟踪未标记的根对象指向其可到达对象，标记任何对象，以及指定对象群体中可用于重新分配的任何未标记对象。

公开(公告)号：US08825719B2

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

申请号：US12261920

申请日：2008-10-30

申请人： Bjarne Steensgaard ,  Erez Petrank ,  Gabriel Kliot

发明人： Bjarne Steensgaard ,  Erez Petrank ,  Gabriel Kliot

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

CPC分类号： G06F12/0269

摘要： Concurrent, incremental, and lock-free stack scanning for garbage collectors is disclosed. This method uses a summary table and return barriers to allow high responsiveness. The method also supports programs that employ fine-synchronization to avoid locks, imposes negligible overhead on program execution, can be used with existing concurrent collectors, and supports the special in-stack references existing in languages such as C#.

摘要翻译： 披露了垃圾收集器的并发，增量和无锁堆栈扫描。 该方法使用汇总表和返回障碍以允许高响应性。 该方法还支持使用精细同步来避免锁定的程序，对程序执行造成可忽略的开销，可以与现有的并发收集器一起使用，并支持以C语言编写的特殊堆栈内参考。

公开(公告)号：US08041752B2

公开(公告)日：2011-10-18

申请号：US12731018

申请日：2010-03-24

申请人： Erez Petrank ,  Filip Jerzy Pizlo ,  Bjarne Steensgaard

发明人： Erez Petrank ,  Filip Jerzy Pizlo ,  Bjarne Steensgaard

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

CPC分类号： G06F12/0269

摘要： Described is a technology by which a real-time data relocating mechanism is provided for multiprocessing environments, including supporting lock-free programs that run in parallel. The relocating mechanism moves an object by using a status field related to the data field, possibly in an interim (wide) object space, which is then copied to a to-space object. The status information for each data field of the original object contains information indicating where a current version of the data for each field is present, that is, in the original, wide or to-space object. In one example, a handshake mechanism of a garbage collector establishes preparation and copy phases between the mechanism and other threads that determine where memory accesses occur. Also described is support for program thread compare-and-swap (CAS) operations and/or multi-word atomic operations.

摘要翻译： 描述了一种为多处理环境提供实时数据重定位机制的技术，包括支持并行运行的无锁程序。 重新定位机制可以通过使用与数据字段相关的状态字段来移动对象，可能在临时（宽）对象空间中，然后将其复制到空间对象。 原始对象的每个数据字段的状态信息包含指示每个字段的数据的当前版本在哪里的信息，即原始，宽或空间对象中的信息。 在一个示例中，垃圾收集器的握手机制在机制和确定存储器访问发生的其他线程之间建立准备和复制阶段。 还描述了对程序线程比较和交换（CAS）操作和/或多字原子操作的支持。

公开(公告)号：US20100179971A1

公开(公告)日：2010-07-15

申请号：US12731018

申请日：2010-03-24

申请人： Erez Petrank ,  Filip Jerzy Pizlo ,  Bjarne Steensgaard

发明人： Erez Petrank ,  Filip Jerzy Pizlo ,  Bjarne Steensgaard

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

CPC分类号： G06F12/0269

摘要： Described is a technology by which a real-time data relocating mechanism is provided for multiprocessing environments, including supporting lock-free programs that run in parallel. The relocating mechanism moves an object by using a status field related to the data field, possibly in an interim (wide) object space, which is then copied to a to-space object. The status information for each data field of the original object contains information indicating where a current version of the data for each field is present, that is, in the original, wide or to-space object. In one example, a handshake mechanism of a garbage collector establishes preparation and copy phases between the mechanism and other threads that determine where memory accesses occur. Also described is support for program thread compare-and-swap (CAS) operations and/or multi-word atomic operations.

摘要翻译： 描述了一种为多处理环境提供实时数据重定位机制的技术，包括支持并行运行的无锁程序。 重新定位机制可以通过使用与数据字段相关的状态字段来移动对象，可能在临时（宽）对象空间中，然后将其复制到空间对象。 原始对象的每个数据字段的状态信息包含指示每个字段的数据的当前版本在哪里的信息，即原始，宽或空间对象中的信息。 在一个示例中，垃圾收集器的握手机制在机制和确定存储器访问发生的其他线程之间建立准备和复制阶段。 还描述了对程序线程比较和交换（CAS）操作和/或多字原子操作的支持。

公开(公告)号：US06490599B2

公开(公告)日：2002-12-03

申请号：US09733085

申请日：2000-12-11

申请人： Elliot K. Kolodner ,  Erez Petrank

发明人： Elliot K. Kolodner ,  Erez Petrank

IPC分类号： G06F1730

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

摘要： A method for performing garbage collection of memory objects in a memory heap, the method includes the steps of partitioning the heap into old and new generations. There follows the step of applying an on-the-fly garbage collection to memory objects in the young generation, whilst running simultaneously a program thread.

摘要翻译： 一种用于执行存储器堆中的存储器对象的垃圾收集的方法，所述方法包括以下步骤：将堆分成新旧代。 随后，在同时运行程序线程的同时，将一个即时的垃圾收集应用于年轻一代的内存对象。

公开(公告)号：US06430580B1

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

申请号：US09344721

申请日：1999-06-25

申请人： Alain Azagury ,  Elliot Karl Kolodner ,  Erez Petrank

发明人： Alain Azagury ,  Elliot Karl Kolodner ,  Erez Petrank

IPC分类号： G06F1700

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

摘要： Improved method of replication-based garbage collection in a multiprocessing system comprising a plurality of processors, a memory divided into a current area (from-space) used by the processors during current program execution and a reserved area (to-space), and at least a garbage collector for performing, when necessary, a garbage collection consisting in flipping the roles of the current area and reserved area after all the live objects stored in current area have been copied into the reserved area and for reclaiming the current area after the flipping operation. Several program threads (mutators) are currently running in parallel and the garbage collector performs the garbage collection in parallel with the program threads, the flipping operation being performed after the program threads have been stopped and the garbage collection has been completed. The method comprises the steps of storing, during normal program execution, a record in a local buffer allocated to each program thread each time this one updates a memory location, and adding this local buffer when full to a global list of buffers using a first wait-free synchronization operation, and, during garbage collection, removing the local buffers one by one from the global list of buffers using a second wait-free synchronization operation, and looping over records in each removed local buffer and copying the updated memory locations into the reserved area until the global list is empty.

摘要翻译： 改进的在多处理系统中的基于复制的垃圾收集方法，包括多个处理器，分配为当前程序执行期间由处理器使用的当前区域（从空间）的存储器和保留区域（空间）） 至少一个垃圾收集器，用于在必要时执行一个垃圾回收，该垃圾收集包括在当前区域中存储的所有活动对象已被复制到保留区域之后翻转当前区域和保留区域的角色，并且在翻转之后回收当前区域 操作。 几个程序线程（mutator）当前并行运行，垃圾收集器与程序线程并行执行垃圾回收，在程序线程停止并且垃圾收集完成后执行翻转操作。 该方法包括以下步骤：在正常程序执行期间，在每次更新存储器位置时，将分配给每个程序线程的本地缓冲器中的记录存储在存储器位置，并且使用第一等待将该本地缓冲器添加到全局缓冲器列表时 并且在垃圾收集期间，使用第二无等待同步操作从缓冲器的全局列表逐个地移除本地缓冲器，并且循环遍历每个移除的本地缓冲器中的记录，并将更新的存储器位置复制到 保留区域，直到全局列表为空。

公开(公告)号：US07716192B2

公开(公告)日：2010-05-11

申请号：US11801039

申请日：2007-05-08

申请人： Erez Petrank ,  Filip Jerzy Pizlo ,  Bjarne Steensgaard

发明人： Erez Petrank ,  Filip Jerzy Pizlo ,  Bjarne Steensgaard

IPC分类号： G06F7/00

CPC分类号： G06F12/0269

摘要： Described is a technology by which a real-time data relocating mechanism is provided for multiprocessing environments, including supporting lock-free programs that run in parallel. The relocating mechanism moves an object by using a status field related to the data field, possibly in an interim (wide) object space, which is then copied to a to-space object. The status information for each data field of the original object contains information indicating where a current version of the data for each field is present, that is, in the original, wide or to-space object. In one example, a handshake mechanism of a garbage collector establishes preparation and copy phases between the mechanism and other threads that determine where memory accesses occur. Also described is support for program thread compare-and-swap (CAS) operations and/or multi-word atomic operations.

摘要翻译： 描述了一种为多处理环境提供实时数据重定位机制的技术，包括支持并行运行的无锁程序。 重新定位机制可以通过使用与数据字段相关的状态字段来移动对象，可能在临时（宽）对象空间中，然后将其复制到空间对象。 原始对象的每个数据字段的状态信息包含指示每个字段的数据的当前版本在哪里的信息，即原始，宽或空间对象中的信息。 在一个示例中，垃圾收集器的握手机制在机制和确定存储器访问发生的其他线程之间建立准备和复制阶段。 还描述了对程序线程比较和交换（CAS）操作和/或多字原子操作的支持。

公开(公告)号：US20090144712A1

公开(公告)日：2009-06-04

申请号：US11947031

申请日：2007-11-29

申请人： Bjarne Steensgaard ,  Erez Petrank ,  Filip Pizlo

发明人： Bjarne Steensgaard ,  Erez Petrank ,  Filip Pizlo

IPC分类号： G06F9/45

CPC分类号： G06F8/4441

摘要： Mechanism that employs code cloning and specialized code execution for barriers to minimize runtime overhead. This is facilitated by duplicating code and inserting specializations of the barriers in the code copies. The mechanism is effective for garbage collection when the garbage collection executes through different phases, and the barrier behavior and overheads depend on these phases. The duplicated and specialized code enables the program to run efficiently by reducing the dynamic count of a phase check when the phase is well-known and phase checks can be avoided.

摘要翻译： 机制采用代码克隆和专门的代码执行障碍来最小化运行时开销。 这通过复制代码并在代码副本中插入障碍的专门化来实现。 当垃圾收集通过不同阶段执行时，该机制对于垃圾收集是有效的，并且屏障行为和开销取决于这些阶段。 复制和专用的代码使程序能够有效地运行，当相位是众所周知的时候减少相位检查的动态计数，并且可以避免相位检查。

公开(公告)号：US06920541B2

公开(公告)日：2005-07-19

申请号：US10021424

申请日：2001-12-19

申请人： Elliot K. Kolodner ,  Ethan Lewis ,  Erez Petrank

发明人： Elliot K. Kolodner ,  Ethan Lewis ,  Erez Petrank

IPC分类号： G06F11/34 ,  G06F12/02 ,  G06F12/00

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

摘要： A method for memory management in execution of a program by a computer having a memory includes allocating respective portions of the memory to data objects using mutator threads of the program, whereby the objects are held in a heap created by the program. The data objects in the heap are traced so as to mark the data objects that are reachable at a given stage in the program. The computer loops over the mutator threads so as to verify for each of the mutator threads that every update to the allocated portions of the memory in progress by the mutator thread has been completed. The heap is then swept so as to free the memory that is allocated to the data objects that are not marked as reachable, for reallocation to new data objects.

摘要翻译： 一种用于通过具有存储器的计算机执行程序的存储器管理的方法包括使用所述程序的变形器线程将所述存储器的各个部分分配给数据对象，由此将所述对象保存在由所述程序创建的堆中。 跟踪堆中的数据对象，以便标记程序中给定阶段可访问的数据对象。 计算机循环通过变异器线程，以便为每个更改器线程验证每个更新到由扩展器线程正在进行的内存的已分配部分的每个更新已经完成。 然后扫描堆，以释放分配给未标记为可达的数据对象的内存，以重新分配给新的数据对象。