公开(公告)号：US06839725B2

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

申请号：US09855453

申请日：2001-05-15

申请人： Ole Agesen ,  Alexander T. Garthwaite ,  Timothy L. Harris

发明人： Ole Agesen ,  Alexander T. Garthwaite ,  Timothy L. Harris

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

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

摘要： Run time sampling techniques have been developed whereby representative object lifetime statistics may be obtained and employed to adaptively affect tenuring decisions, memory object promotion and/or storage location selection. In some realizations, object allocation functionality is dynamically varied to achieve desired behavior on an object category-by-category basis. In some realizations, phase behavior affects sampled lifetimes e.g., for objects allocated at different phases of program execution, and the dynamic facilities described herein provide phase-specific adaptation tenuring decisions, memory object promotion and/or storage location selection. In some realizations, reversal of such decisions is provided.

公开(公告)号：US06799191B2

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

申请号：US09855454

申请日：2001-05-15

申请人： Ole Agesen ,  Alexander T. Garthwaite ,  Timothy L. Harris

发明人： Ole Agesen ,  Alexander T. Garthwaite ,  Timothy L. Harris

IPC分类号： G06F1200

CPC分类号： G06F12/0276 ,  G06F11/3447 ,  G06F11/3466 ,  Y10S707/99957

摘要： With better knowledge of the behavior of objects in a running application, it is possible to improve execution environment decisions that affect management of such objects. For example, if available, object lifetime statistics could be employed in decisions that affect how and where objects are placed, e.g., on allocation or during operation of automatic dynamic memory management facilities such as a garbage collector. Typically, instrumenting all objects to sample lifetimes or other characteristics would impose an impractical level of overhead. We present a technique for dynamic sampling of a subset of allocated objects that incurs low runtime overheads. Coupled with automatic memory management or collection facilities, this technique allows us to improve the efficiency of a collector by segregating objects, sampled and non-sampled alike, based on observed characteristics such as object lifetime. The sampling techniques facilitate tracking of many kinds of object information. For purposes of illustration, an exemplary implementation is described in which such sampling techniques are exploited to improve performance of generational garbage collectors.

摘要翻译： 通过更好地了解正在运行的应用程序中对象的行为，可以改进影响这些对象管理的执行环境决策。 例如，如果可用，则可以在影响如何以及在何处放置对象的决策中使用对象生命周期统计，例如在诸如垃圾收集器的自动动态存储器管理设备的分配或操作期间。 通常，将所有对象检测到样本生命周期或其他特征将会产生不切实际的开销级别。 我们提出了一种用于动态采样分配对象的子集的技术，从而导致低运行时开销。 结合自动记忆管理或收集设备，这种技术使我们能够根据诸如对象寿命等观察特征，通过分离对象，采样和非抽样等来提高收集器的效率。 采样技术有助于跟踪多种物体信息。 为了说明的目的，描述了一种示例性实现，其中利用这种采样技术来改善代代垃圾收集器的性能。

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

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

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

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

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

公开(公告)号：US08006043B2

公开(公告)日：2011-08-23

申请号：US12246402

申请日：2008-10-06

申请人： Ole Agesen

发明人： Ole Agesen

IPC分类号： G06F12/08

CPC分类号： G06F12/08 ,  G06F9/45537 ,  G06F9/544 ,  G06F2209/542

摘要： In a virtualized system using memory page sharing, a method is provided for maintaining sharing when Guest code attempts to write to the shared memory. In one embodiment, virtualization logic uses a pattern matcher to recognize and intercept page zeroing code in the Guest OS. When the page zeroing code is about to run against a page that is already zeroed, i.e., contains all zeros, and is being shared, the memory writes in the page zeroing code have no effect. The virtualization logic skips over the writes, providing an appearance that the Guest OS page zeroing code has run to completion but without performing any of the writes that would have caused a loss of page sharing. The pattern matcher can be part of a binary translator that inspects code before it executes.

摘要翻译： 在使用内存页面共享的虚拟化系统中，提供了一种方法，用于在访客代码尝试写入共享内存时保持共享。 在一个实施例中，虚拟化逻辑使用模式匹配器来识别和拦截访客操作系统中的页面归零代码。 当页面归零代码即将针对已经归零的页面运行时，即包含全部零，并且正在共享时，页面调零代码中的内存写入不起作用。 虚拟化逻辑跳过写入，提供Guest OS页面调零代码已经运行到完成的外观，但不执行会导致页面共享丢失的任何写入。 模式匹配器可以是在执行代码之前检查代码的二进制转换器的一部分。

公开(公告)号：US07487313B1

公开(公告)日：2009-02-03

申请号：US11865635

申请日：2007-10-01

申请人： Ole Agesen ,  Jeffrey W. Sheldon

发明人： Ole Agesen ,  Jeffrey W. Sheldon

IPC分类号： G06F12/00

CPC分类号： G06F12/1036 ,  G06F12/1475 ,  G06F2212/656

摘要： A first software entity occupies a portion of a linear address space of a second software entity and prevents the second software entity from accessing the memory of the first software entity. For example, in one embodiment of the invention, the first software entity is a virtual machine monitor (VMM), which supports a virtual machine (VM), the second software entity. The VMM sometimes directly executes guest instructions from the VM and, at other times, the VMM executes binary translated instructions derived from guest instructions. When executing binary translated instructions, the VMM uses memory segmentation to protect its memory. When directly executing guest instructions, the VMM may use either memory segmentation or a memory paging mechanism to protect its memory. When the memory paging mechanism is active during direct execution, the protection from the memory segmentation mechanism may be selectively deactivated to improve the efficiency of the virtual computer system.

公开(公告)号：US07277998B1

公开(公告)日：2007-10-02

申请号：US10917732

申请日：2004-08-12

申请人： Ole Agesen ,  Jeffrey W. Sheldon

发明人： Ole Agesen ,  Jeffrey W. Sheldon

IPC分类号： G06F12/00

CPC分类号： G06F12/1036 ,  G06F12/1475 ,  G06F2212/656

摘要： A first software entity occupies a portion of a linear address space of a second software entity and prevents the second software entity from accessing the memory of the first software entity. For example, in one embodiment of the invention, the first software entity is a virtual machine monitor (VMM), which supports a virtual machine (VM), the second software entity. The VMM sometimes directly executes guest instructions from the VM and, at other times, the VMM executes binary translated instructions derived from guest instructions. When executing binary translated instructions, the VMM uses memory segmentation to protect its memory. When directly executing guest instructions, the VMM may use either memory segmentation or a memory paging mechanism to protect its memory. When the memory paging mechanism is active during direct execution, the protection from the memory segmentation mechanism may be selectively deactivated to improve the efficiency of the virtual computer system.

摘要翻译： 第一软件实体占用第二软件实体的线性地址空间的一部分，并且防止第二软件实体访问第一软件实体的存储器。 例如，在本发明的一个实施例中，第一软件实体是支持虚拟机（VM）的第二软件实体的虚拟机监视器（VMM）。 VMM有时直接从VM执行访客指令，而在其他时候，VMM执行从访客指令导出的二进制翻译指令。 当执行二进制转换指令时，VMM使用存储器分段来保护其内存。 当直接执行访客指令时，VMM可以使用存储器分段或存储器寻呼机制来保护其存储器。 当存储器分页机制在直接执行期间有效时，可以选择性地停止对存储器分段机制的保护，以提高虚拟计算机系统的效率。

公开(公告)号：US07069413B1

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

申请号：US10354556

申请日：2003-01-29

申请人： Ole Agesen ,  Pratap Subrahmanyam

发明人： Ole Agesen ,  Pratap Subrahmanyam

IPC分类号： G06F12/00

CPC分类号： G06F12/1072 ,  G06F12/1036 ,  G06F2212/682

摘要： The invention is used in a virtual machine monitor for a multiprocessing system that includes a virtual memory system. During a software-based processing of a guest instruction, including translating or interpreting a guest instruction, mappings between virtual addresses and physical addresses are retained in memory until processing of the guest instruction is completed. The retained mappings may be cleared after each guest instruction has been processed, or after multiple guest instructions have been processed. Information may also be stored to indicate that an attempt to map a virtual address to a physical address was not successful. The invention may be extended beyond virtual machine monitors to other systems involving the software-based processing of instructions, and beyond multiprocessing systems to other systems involving concurrent access to virtual memory management data.

摘要翻译： 本发明用于包括虚拟存储器系统的多处理系统的虚拟机监视器中。 在访客指令的基于软件的处理中，包括翻译或解释访客指令，虚拟地址和物理地址之间的映射被保留在存储器中，直到访客指令的处理完成。 保留的映射可以在每个客户指令被处理之后或在多个客户指令被处理之后被清除。 还可以存储信息以指示将虚拟地址映射到物理地址的尝试不成功。 本发明可以扩展到虚拟机监视器以外的其他系统，涉及指令的基于软件的处理，并且超出多处理系统到涉及对虚拟存储器管理数据的并发访问的其他系统。