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

公开(公告)号：US06560619B1

公开(公告)日：2003-05-06

申请号：US09704141

申请日：2000-11-01

申请人： Christine H. Flood ,  Ole Agesen

发明人： Christine H. Flood ,  Ole Agesen

IPC分类号： G06F1200

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

摘要： A multiprocessor, multi-program, stop-the-world garbage collection program is described. The system initially over partitions the root sources, and then iteratively employs static and dynamic work balancing. Garbage collection threads compete dynamically for the initial partitions. Work stealing double-ended queues, where contention is reduced, are described to provide dynamic load balancing among the threads. Contention is resolved by using atomic instructions. The heap is broken into a young and an old generation where parallel semi-space copying is used to collect the young generation and parallel mark-compacting the old generation. Speed and efficiency of collection is enhanced by use of card tables and linking objects, and overflow conditions are efficiently handled by linking using class pointers. The garbage collection termination employs a global status word.

摘要翻译： 描述了一个多处理器，多程序，停止世界的垃圾收集程序。 系统最初对根源进行分区，然后迭代地采用静态和动态的工作平衡。 垃圾收集线程可以动态竞争初始分区。 被描述为在线程之间提供动态负载平衡的工作窃取双端队列，其中争用减少。 竞争通过使用原子指令来解决。 堆被打破成一个年轻和老一代，平行的半空间复制用于收集年轻一代和平行的标记压实老一代。 通过使用卡表和链接对象来增强收集的速度和效率，并且通过使用类指针进行链接来有效地处理溢出条件。 垃圾回收终止使用全局状态字。

公开(公告)号：US07640544B2

公开(公告)日：2009-12-29

申请号：US10996508

申请日：2004-11-23

申请人： Christine H. Flood ,  David L. Detlefs ,  Nir N. Shavit ,  Xiaolan Zhang ,  Ole Agesen

发明人： Christine H. Flood ,  David L. Detlefs ,  Nir N. Shavit ,  Xiaolan Zhang ,  Ole Agesen

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

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

摘要： A multiprocessor, multi-program, stop-the-world garbage collection program is described. The system initially over partitions the root sources, and then iteratively employs static and dynamic work balancing. Garbage collection threads compete dynamically for the initial partitions. Work stealing double-ended queues, where contention is reduced, are described to provide dynamic load balancing among the threads. Contention is resolved by using atomic instructions. The heap is broken into a young and an old generation where parallel semi-space copying is used to collect the young generation and parallel mark-compacting the old generation. Speed and efficiency of collection is enhanced by use of card tables and linking objects, and overflow conditions are efficiently handled by linking using class pointers. A garbage collection termination employs a global status word.

摘要翻译： 描述了一个多处理器，多程序，停止世界的垃圾收集程序。 系统最初对根源进行分区，然后迭代地采用静态和动态的工作平衡。 垃圾收集线程可以动态竞争初始分区。 被描述为在线程之间提供动态负载平衡的工作窃取双端队列，其中争用减少。 竞争通过使用原子指令来解决。 堆被打破成一个年轻和老一代，平行的半空间复制用于收集年轻一代和平行的标记压实老一代。 通过使用卡表和链接对象来增强收集的速度和效率，并且通过使用类指针进行链接来有效地处理溢出条件。 垃圾收集终端采用全局状态字。

公开(公告)号：US06823351B1

公开(公告)日：2004-11-23

申请号：US09697729

申请日：2000-10-26

申请人： Christine H. Flood ,  David L. Detlefs ,  Nir N. Shavit ,  Xiaolan Zhang ,  Ole Agesen

发明人： Christine H. Flood ,  David L. Detlefs ,  Nir N. Shavit ,  Xiaolan Zhang ,  Ole Agesen

IPC分类号： G06F1730

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

摘要： A multiprocessor, multi-program, stop-the-world garbage collection program is described. The system initially over partitions the root sources, and then iteratively employs static and dynamic work balancing. Garbage collection threads compete dynamically for the initial partitions. Work stealing double-ended queues, where contention is reduced, are described to provide dynamic load balancing among the threads. Contention is resolved by using atomic instructions. The heap is broken into a young and an old generation where parallel semi-space copying is used to collect the young generation and parallel mark-compacting the old generation. Speed and efficiency of collection is enhanced by use of card tables and linking objects, and overflow conditions are efficiently handled by linking using class pointers. A garbage collection termination employs a global status word.

摘要翻译： 描述了一个多处理器，多程序，停止世界的垃圾收集程序。 系统最初对根源进行分区，然后迭代地采用静态和动态的工作平衡。 垃圾收集线程可以动态竞争初始分区。 被描述为在线程之间提供动态负载平衡的工作窃取双端队列，其中争用减少。 竞争通过使用原子指令来解决。 堆被打破成一个年轻和老一代，平行的半空间复制用于收集年轻一代和平行的标记压实老一代。 通过使用卡表和链接对象来增强收集的速度和效率，并且通过使用类指针进行链接来有效地处理溢出条件。 垃圾收集终端采用全局状态字。

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

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

公开(公告)号：US06711672B1

公开(公告)日：2004-03-23

申请号：US09668091

申请日：2000-09-22

申请人： Ole Agesen

发明人： Ole Agesen

IPC分类号： G06F9455

CPC分类号： G06F8/52 ,  G06F9/4484 ,  G06F2212/451

摘要： A sequence of input language (IL) instructions of a guest system is converted, for example by binary translation, into a corresponding sequence of output language (OL) instructions of a host system, which executes the OL instructions. In order to determine the correct return address after any IL call to a subroutine, the corresponding OL return address is stored in an array at a location determined by a hash function. After completion of execution of the OL translation of the IL subroutine, execution is transferred to the address stored in the array at the location where the correct OL return address was previously stored. This location may have been overwritten by some other OL return address. This transfer will therefore be to one of three places: 1) either back to the correct OL call site, in which case execution may continue as normal; 2) directly to a back-up return address recovery module; or 3) to an incorrect OL call site (created upon translation of some other IL subroutine call), in which case execution is transferred to the back-up recovery module. A confirmation instruction block is included in each OL call site to determine whether the transfer was to the correct or incorrect call site.

摘要翻译： 访客系统的输入语言（IL）指令的序列例如通过二进制转换被转换成执行OL指令的主机系统的输出语言（OL）指令的相应序列。 为了在任何IL调用子程序后确定正确的返回地址，相应的OL返回地址存储在由散列函数确定的位置的数组中。 在执行IL子程序的OL转换完成后，执行将被转移到阵列中存储了正确OL返回地址的位置的地址。 该位置可能已被其他一些OL返回地址覆盖。 因此，这种转移将是三个地方之一：1）返回正确的OL呼叫站点，在这种情况下执行可能正常; 2）直接到备份返回地址恢复模块; 或3）到不正确的OL调用站点（在其他IL子程序调用的转换时创建），在这种情况下，执行将传输到备份恢复模块。 每个OL呼叫站点中都包含确认指令块，以确定传输是否是正确或不正确的呼叫站点。

公开(公告)号：US5909579A

公开(公告)日：1999-06-01

申请号：US847770

申请日：1997-04-23

申请人： Ole Agesen ,  David Ungar

发明人： Ole Agesen ,  David Ungar

IPC分类号： G06F12/02 ,  H03M3/02 ,  G06B9/44

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

摘要： Live pointer information for a stream of bytecodes is precomputed for each bytecode. The precomputed full live pointer information is stored only for bytecodes at predetermined intervals in the stream. Between the bytecodes for which full live pointer information is stored, changes in the live pointer information produced by each bytecode are encoded using a suitable compressive coding and stored. Later, when a program which needs the live pointer information, such as garbage collection, is initiated, the full live pointer information for the nearest bytecode preceding the desired bytecode boundary is retrieved along with the intervening coded changes. The changes are decoded and applied to the retrieved live pointer information to generate the live pointer information at the desired bytecode boundary. In one embodiment of the invention, the live pointer changes are delta encoded so that each code contains information relating to the live pointer changes produced by a bytecode from the live pointer information as modified by the previous delta code. In another embodiment of the invention, the delta coded changes are encoded with a Huffman encoding scheme.

摘要翻译： 每个字节码预先计算字节码流的实时指针信息。 预计算的完整实况指针信息仅在流中以预定间隔存储在字节码中。 在存储完整的实时指针信息的字节码之间，使用适当的压缩编码对每个字节码产生的实况指针信息进行改变并进行存储。 之后，当开始需要诸如垃圾收集之类的活动指针信息的程序时，将检索所需字节码边界之前的最近字节码的完整实况指针信息以及中间编码的变化。 这些改变被解码并应用于检索到的实时指针信息以在期望的字节码边界处生成实时指针信息。 在本发明的一个实施例中，实时指针变化被增量编码，使得每个代码包含与由先前的增量代码修改的来自实时指针信息的字节码产生的实况指针变化相关的信息。 在本发明的另一个实施例中，Δ编码改变用霍夫曼编码方案编码。