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

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

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

公开(公告)号：US07890722B1

公开(公告)日：2011-02-15

申请号：US11099720

申请日：2005-04-06

申请人： Guy L. Steele, Jr. ,  Ole Agesen ,  Nir N. Shavit

发明人： Guy L. Steele, Jr. ,  Ole Agesen ,  Nir N. Shavit

IPC分类号： G06F12/14

CPC分类号： G06F9/524 ,  G06F9/30021 ,  G06F9/3004 ,  G06F9/30087

摘要： A sequentially performed implementation of a compound compare-and-swap (nCAS) operation has been developed. In one implementation, a double compare-and-swap (DCAS) operation does not result in a fault, interrupt, or trap in the situation where memory address A2 is invalid and the contents of memory address A1 are unequal to C1. In some realizations, memory locations addressed by a sequentially performed nCAS or DCAS instruction are reserved (e.g., locked) in a predefined order in accordance with a fixed total order of memory locations. In this way, deadlock between concurrently executed instances of sequentially performed nCAS instructions can be avoided. Other realizations defer responsibility for deadlock avoidance to the programmer.

摘要翻译： 已经开发了顺序执行的复合比较和交换（nCAS）操作。 在一个实现中，在存储器地址A2无效并且存储器地址A1的内容不等于C1的情况下，双重比较和交换（DCAS）操作不会导致故障，中断或陷阱。 在一些实现中，依次执行的nCAS或DCAS指令寻址的存储器单元根据存储单元的固定总顺序以预定义的顺序被保留（例如锁定）。 以这种方式，可以避免顺序执行的nCAS指令的同时执行的实例之间的死锁。 其他实现方式将程序员的死锁责任推迟。

公开(公告)号：US06880071B2

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

申请号：US09829207

申请日：2001-04-09

申请人： Guy L. Steele, Jr. ,  Ole Agesen ,  Nir N. Shavit

发明人： Guy L. Steele, Jr. ,  Ole Agesen ,  Nir N. Shavit

IPC分类号： G06F9/30 ,  G06F9/312 ,  G06F9/46

CPC分类号： G06F9/524 ,  G06F9/30021 ,  G06F9/3004 ,  G06F9/30087

摘要： A sequentially performed implementation of a compound compare-and-swap (nCAS) operation has been developed. In one implementation, a double compare-and-swap (DCAS) operation does not result in a fault, interrupt, or trap in the situation where memory address A2 is invalid and the contents of memory address A1 are unequal to C1. In some realizations, memory locations addressed by a sequentially performed nCAS or DCAS instruction are reserved (e.g., locked) in a predefined order in accordance with a fixed total order of memory locations. In this way, deadlock between concurrently executed instances of sequentially performed nCAS instructions can be avoided. Other realizations defer responsibility for deadlock avoidance to the programmer.

摘要翻译： 已经开发了顺序执行的复合比较和交换（nCAS）操作。 在一个实现中，在存储器地址A2无效并且存储器地址A1的内容不等于C1的情况下，双重比较和交换（DCAS）操作不会导致故障，中断或陷阱。 在一些实现中，依次执行的nCAS或DCAS指令寻址的存储器单元根据存储单元的固定总顺序以预定义的顺序被保留（例如锁定）。 以这种方式，可以避免顺序执行的nCAS指令的同时执行的实例之间的死锁。 其他实现方式将程序员的死锁责任推迟。

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

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

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

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

公开(公告)号：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）根据确定修改消除冲突的指令序列。

公开(公告)号：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）或其标识符之前包含对象标题的线程获得该信息。 当线程完成其同步操作时，如果该头仍然包含线程最初在那里写入的线程标识符，它将使用原子比较和交换操作将结果写入对象的头。 否则，如果线程标识符不同，则将该信息传递给其后续线程，从而指示至少一个后继者正在竞争访问链表。