公开(公告)号：US06253215B1

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

申请号：US09134548

申请日：1998-08-17

申请人： Ole Agesen ,  David L. Detlefs ,  Derek R. White

发明人： Ole Agesen ,  David L. Detlefs ,  Derek R. White

IPC分类号： G06F1730

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

摘要： Methods, systems, and articles of manufacture consistent with the present invention provide a program component including a set of instructions native to the system, include in the set of native instructions an instruction to maintain information on use of a particular object, and permit reuse of memory resources corresponding to the particular object based on an indication from a source that the particular object is no longer being used, the source being different from any source used to provide information on use of objects associated with non-native instructions of the program component. Additionally, garbage collection is not permitted during native code operations to read or write data in object fields because during such operations an indication exists that such collection may be inaccurate and could possibly reclaim or relocate objects referenced by native code though not specified as such in the native code stack and global variables.

摘要翻译： 与本发明一致的方法，系统和制品提供了包括本系统的一组指令的程序组件，在本组指令中包括维护关于使用特定对象的信息的指令，并允许重用 基于来自源的指示，特定对象不再被使用的指示，所述源与用于提供关于与所述程序组件的非本地指令相关联的对象的使用的信息的任何源不同。 此外，在本地代码操作期间，不允许在本地代码操作中读取或写入对象字段中的数据，因为在此类操作中存在这样的指示，即这样的集合可能不准确，并且可能会回收或重新定位由本机代码引用的对象，但在 本地代码堆栈和全局变量。

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

公开(公告)号：US6047125A

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

申请号：US942292

申请日：1997-10-01

申请人： Ole Agesen ,  David L. Detlefs

发明人： Ole Agesen ,  David L. Detlefs

IPC分类号： G06F9/45 ,  G06F12/02 ,  G06F9/44

CPC分类号： G06F8/443 ,  G06F12/023 ,  G06F12/0253 ,  Y10S707/99952 ,  Y10S707/99953

摘要： In accordance with the present invention a method for modifying a sequence of instructions to improve memory management within a storage device during execution of the instructions, comprises the steps, performed by a processor, of (a) analyzing the sequence of instructions for a conflict indicating an undeterminable variable type, (b) determining the type of conflict, and (c) modifying the sequence of instructions to eliminate the conflict based on the determination.

摘要翻译： 根据本发明，一种用于在执行指令期间修改指令序列以改善存储设备内的存储器管理的方法包括由处理器执行的步骤（a）分析用于冲突的冲突指令序列 不确定的变量类型，（b）确定冲突的类型，以及（c）根据确定修改消除冲突的指令序列。

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

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

公开(公告)号：US06314563B1

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

申请号：US09283136

申请日：1999-03-31

申请人： Ole Agesen ,  David L. Detlefs ,  Alex Garthwaite

发明人： Ole Agesen ,  David L. Detlefs ,  Alex Garthwaite

IPC分类号： G06F965

CPC分类号： G06F9/52 ,  Y10S707/99938

摘要： An object structure's header (40) allocates a two-bit synchronization-state field (42) solely to monitor data for implementing synchronization on that object. When the object is locked by a particular execution thread, or when one or more execution threads are waiting for a lock or notification on that object, its header contains a pointer to monitor resources in the form of a linked list of lock records (50, 52, 54) associated with the threads involved. The synchronization-state field (42) ordinarily contains an indication of whether such a linked list exists and, if so, whether its first member is associated with a thread that has a lock on the object. When a thread attempts to gain access to that linked list, it employs an atomic swap operation to place a special busy value in that lock-state field (42) and write its execution-environment pointer into the object's header (40). If the previous value of that field was not the special busy value, the thread uses the header's previous contents to perform its intended synchronization operation. Otherwise, it obtains that information through its own execution environment (44, 46, or 48) or that of the thread whose identifier the object header previously contained. When the thread completes its synchronization operation, it employs an atomic compare-and-swap operation to write the results into the object's header if that header still contains the thread identifier that the thread originally wrote there. Otherwise, it communicates that information to its successor thread if the thread identifier is different and thereby indicates that at least one successor is contending for access to the linked list.

摘要翻译： 对象结构的头部（40）仅分配两位同步状态字段（42）来监视用于实现该对象上的同步的数据。 当对象被特定执行线程锁定时，或者当一个或多个执行线程等待该对象上的锁定或通知时，其头包含指向监视资源的指针，该指针以锁定记录的链表的形式（50， 52,54）与所涉及的线程相关联。 同步状态字段（42）通常包含这样的链表是否存在的指示，如果是，则其第一个成员是否与对象上具有锁定的线程相关联。 当一个线程尝试访问该链表时，它采用原子交换操作在该锁状态字段（42）中放置一个特殊的忙值，并将其执行环境指针写入对象的头（40）。 如果该字段的先前值不是特殊忙值，线程将使用头部的以前内容来执行其预期的同步操作。 否则，它通过其自己的执行环境（44,46或48）或其标识符之前包含对象标题的线程获得该信息。 当线程完成其同步操作时，如果该头仍然包含线程最初在那里写入的线程标识符，它将使用原子比较和交换操作将结果写入对象的头。 否则，如果线程标识符不同，则将该信息传递给其后续线程，从而指示至少一个后继者正在竞争访问链表。

公开(公告)号：US06173442B2

公开(公告)日：2001-01-09

申请号：US09245778

申请日：1999-02-05

申请人： Ole Agesen ,  David L. Detlefs ,  Alex Garthwaite ,  Ross C. Knippel ,  Y. Srinivas Ramakrishna ,  Derek White

发明人： Ole Agesen ,  David L. Detlefs ,  Alex Garthwaite ,  Ross C. Knippel ,  Y. Srinivas Ramakrishna ,  Derek White

IPC分类号： G06F945

CPC分类号： G06F9/52 ,  Y10S707/99938

摘要： An object structure's header (40) allocates a two-bit synchronization-state field (42) solely to monitor data for implementing synchronization on that object. When the object is locked by a particular execution thread, or when one or more execution threads are waiting for a lock or notification on that object, its header contains a pointer to monitor resources in the form of a linked list of lock records (50, 52, 54) associated with the threads involved. The synchronization-state field (42) ordinarily contains an indication of whether such a linked list exists and, if so, whether its first member is associated with a thread that has a lock on the object. When a thread attempts to gain access to that linked list, it employs an atomic swap operation to place a special busy value in that lock-state field (42) and write its execution-environment pointer into the object's header (40). If the previous value of that field was not the special busy value, the thread uses the header's previous contents to perform its intended synchronization operation. Otherwise, it obtains that information through its own execution environment (44, 46, or 48) or that of the thread whose identifier the object header previously contained. When the thread completes its synchronization operation, it employs an atomic compare-and-swap operation to write the results into the object's header if that header still contains the thread identifier that the thread originally wrote there. Otherwise, it communicates that information to its successor thread if the thread identifier is different and thereby indicates that at least one successor is contending for access to the linked list.

摘要翻译： 对象结构的头部（40）仅分配两位同步状态字段（42）来监视用于实现该对象上的同步的数据。 当对象被特定执行线程锁定时，或者当一个或多个执行线程等待该对象上的锁定或通知时，其头包含指向监视资源的指针，该指针以锁定记录的链表的形式（50， 52,54）与所涉及的线程相关联。 同步状态字段（42）通常包含这样的链表是否存在的指示，如果是，则其第一个成员是否与对象上具有锁定的线程相关联。 当一个线程尝试访问该链表时，它采用原子交换操作在该锁状态字段（42）中放置一个特殊的忙值，并将其执行环境指针写入对象的头（40）。 如果该字段的先前值不是特殊忙值，线程将使用头部的以前内容来执行其预期的同步操作。 否则，它通过其自己的执行环境（44,46或48）或其标识符之前包含对象标题的线程获得该信息。 当线程完成其同步操作时，如果该头仍然包含线程最初在那里写入的线程标识符，它将使用原子比较和交换操作将结果写入对象的头。 否则，如果线程标识符不同，则将该信息传递给其后续线程，从而指示至少一个后继者正在竞争访问链表。

公开(公告)号：US6161217A

公开(公告)日：2000-12-12

申请号：US152735

申请日：1998-09-14

申请人： David L. Detlefs ,  Ole Agesen

发明人： David L. Detlefs ,  Ole Agesen

IPC分类号： G06F9/42 ,  G06F9/45 ,  G06N9/45

CPC分类号： G06F9/4491

摘要： A computer system (10) is configured as a compiler to translate source code (FIG. 4) into object code (FIG. 6). The source code calls a polymorphic method on a receiver object. The compiler inlines the polymorphic method and guards the inlining with guard code that causes the executing microprocessor to skip the inlining in favor of a virtual method call when it determines that the inlined code is not appropriate for the receiver object. To make that determination, the guard code compares the address of the method version that has been inlined with the receiver object's pointer to its version of the polymorphic method.

摘要翻译： 计算机系统（10）被配置为将源代码（图4）转换为目标代码（图6）的编译器。 源代码调用接收器对象上的多态方法。 编译器内联多态方法，并使用保护代码来保护内联，使得执行的微处理器在确定内联代码不适合接收器对象时跳过内联，以利于虚拟方法调用。 为了做出这个确定，保护代码将已经被内联的方法版本的地址与接收器对象的指针对应于其多态方法的版本进行比较。

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

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

公开(公告)号：US06192517B1

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

申请号：US09436636

申请日：1999-11-09

申请人： Ole Agesen ,  David L. Detlefs

发明人： Ole Agesen ,  David L. Detlefs

IPC分类号： G06F945

CPC分类号： G06F8/443 ,  G06F12/023 ,  G06F12/0253 ,  Y10S707/99952 ,  Y10S707/99953

摘要： In accordance with the present invention a method for modifying a sequence of instructions to improve memory management within a storage device during execution of the instructions, comprises the steps, performed by a processor, of (a) analyzing the sequence of instructions for a conflict indicating an undeterminable variable type, (b) determining the type of conflict, and (c) modifying the sequence of instructions to eliminate the conflict based on the determination.

摘要翻译： 根据本发明，一种用于在执行指令期间修改指令序列以改善存储设备内的存储器管理的方法包括由处理器执行的步骤（a）分析用于冲突的冲突指令序列 不确定的变量类型，（b）确定冲突的类型，以及（c）根据确定修改消除冲突的指令序列。

公开(公告)号：US5873105A

公开(公告)日：1999-02-16

申请号：US883291

申请日：1997-06-26

申请人： Marc Tremblay ,  James Michael O'Connor ,  Guy L. Steele, Jr. ,  Sanjay Vishin ,  Ole Agesen ,  Steven Heller ,  Derek R. White

发明人： Marc Tremblay ,  James Michael O'Connor ,  Guy L. Steele, Jr. ,  Sanjay Vishin ,  Ole Agesen ,  Steven Heller ,  Derek R. White

IPC分类号： G06F12/00 ,  G06F9/44 ,  G06F12/02 ,  G06F17/30

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

摘要： A write barrier to stores into a partially relocated large or popular memory object facilitates bounded pause time implementations of relocating garbage collectors, including e.g., copying collectors, generational collectors, and collectors providing compaction. Such a write barrier allows a garbage collector implementation to interrupt relocation of large or popular memory objects so as to meet bounded pause time guarantees. A partially relocated object identifier store including "copy from" identifier storage accessible to write barrier logic allows the write barrier logic to maintain consistency between FromSpace and ToSpace instances of a partially relocated memory object. "Copy from" identifier storage allows the write barrier logic, or a trap handler responsive thereto, to broadcast a store-oriented memory access targeting the FromSpace instance to both FromSpace and ToSpace instances. Optional "How far" indication storage facilitates differentiation by the write barrier logic between a copied portion and an uncopied portion of the partially relocated memory object.

摘要翻译： 将存储到部分重定位的大型或流行的存储器对象中的写入屏障有助于重新定位垃圾收集器的有限暂停时间实现，包括例如复制收集器，代人收集器和提供压缩的收集器。 这样的写屏障允许垃圾回收器实现中断大型或流行的存储器对象的重新定位，以便满足有限的暂停时间保证。 包含写入屏障逻辑可访问的“复制”标识符存储的部分重新定位的对象标识符存储允许写入屏障逻辑保持部分重新定位的存储器对象的FromSpace和ToSpace实例之间的一致性。 从“标识符存储器复制”允许写屏障逻辑或响应于此的陷阱处理器将针对FromSpace实例的面向存储器的存储器访问广播到FromSpace和ToSpace实例。 可选的“多远”指示存储有助于通过写入屏障逻辑在部分重定位的存储器对象的复制部分和未遮盖部分之间进行区分。