公开(公告)号：US07016923B2

公开(公告)日：2006-03-21

申请号：US10287851

申请日：2002-11-05

申请人： Alexander T. Garthwaite ,  Christine H. Flood ,  David Dice

发明人： Alexander T. Garthwaite ,  Christine H. Flood ,  David Dice

IPC分类号： G06F12/00

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

摘要： A computer system employing a plurality of concurrent threads to perform tasks that dynamically identify further similar tasks employs a double-ended queue (“deque”) to list the dynamically identified tasks. If a thread's deque runs out of tasks while other threads' deques have tasks remaining, the thread whose deque has become empty will remove one or more entries from another thread's deque and perform the tasks thereby identified. When a thread's deque becomes too full, it may allocate space for another deque, transfer entries from its existing deque, place an identifier of the existing deque into the new deque, and adopt the new deque as the one that it uses for storing and retrieving task identifiers. Alternatively, it may transfer some of the existing deque's entries into a newly allocated array and place an identifier of that array into the existing deque. The thread thereby deals with deque overflows without introducing additional synchronization requirements or restricting the deque's range of use.

摘要翻译： 采用多个并行线程来执行动态地识别进一步类似任务的任务的计算机系统采用双端队列（“deque”）列出动态识别的任务。 如果一个线程的deque用完了任务，而其他线程的deques有剩余的任务，则其deque已经变空的线程将从另一个线程的deque中删除一个或多个条目，然后执行这样识别的任务。 当一个线程的deque变得太满时，它可以为另一个deque分配空间，从现有deque传输条目，将现有deque的标识符放置到新deque中，并采用新的deque作为它用于存储和检索的deque 任务标识符。 或者，它可以将一些现有deque的条目转移到新分配的数组中，并将该数组的标识符放置到现有deque中。 因此，线程处理德克尔溢出，而不引入额外的同步要求或限制德克的使用范围。

公开(公告)号：US06862674B2

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

申请号：US10163677

申请日：2002-06-06

申请人： David Dice ,  Alexander T. Garthwaite

发明人： David Dice ,  Alexander T. Garthwaite

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

CPC分类号： G06F12/0269 ,  G06F12/0261 ,  Y10S707/99953 ,  Y10S707/99956

摘要： Mechanisms and techniques operate in a computerized device to perform a memory management technique such as garbage collection. The mechanisms and techniques operate to detect, within a storage structure associated with a thread, general memory references that reference storage locations in a general memory area such as a heap. The storage structure may be a stack utilized by the thread, which may be, for example, a Java thread, during operation of the thread in the computerized device. The system maintains a reference structure containing an association to the general memory area for each detected general memory reference within the storage structure. The system then operates a memory management technique on the general memory area for locations in the general memory area other than those for which an association to the general memory area is maintained in the reference structure, thus increasing the performance of the memory management technique.

摘要翻译： 机制和技术在计算机化设备中运行，以执行诸如垃圾收集之类的存储器管理技术。 机制和技术操作以在与线程相关联的存储结构内检测引用诸如堆的通用存储器区域中的存储位置的一般存储器引用。 存储结构可以是在计算机化设备中的线程的操作期间由线程使用的栈，其可以是例如Java线程。 系统维护包含与存储结构内的每个检测到的通用存储器引用的一般存储器区域的关联的参考结构。 然后，系统在通用存储器区域中对存储器管理技术中的存储器管理技术进行操作，该存储器管理技术在通用存储器区域中的位置之外，而与在一般存储器区域的关联保持在参考结构中的位置不同，从而增加了存储器管理技术的

公开(公告)号：US07475397B1

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

申请号：US10900636

申请日：2004-07-28

申请人： Alexander T. Garthwaite ,  David Dice

发明人： Alexander T. Garthwaite ,  David Dice

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

CPC分类号： G06F9/52 ,  G06F9/30087 ,  G06F9/3009 ,  G06F9/522

摘要： A technique provides a remote serialization guarantee within a computerized system. The technique involves (i) receiving a serialization command from a first thread running on a first processor of the computerized system; (ii) running, on a second processor, a second thread up to a serialization point; and (iii) outputting a serialization result to the first thread in response to the serialization command. The serialization result indicates that the second thread has run up to the serialization point. Such operation enables the first and second threads to robustly coordinate access to a shared resource by the first thread incurring both the burden of employing a MEMBAR instruction and the burden of providing the remote serialization command when attempting to access the shared resource, and the second thread not running any MEMBAR instruction when attempting to access the shared resource to enable the second thread to run more efficiently.

摘要翻译： 一种技术在计算机化系统中提供远程串行化保证。 该技术涉及（i）从在计算机化系统的第一处理器上运行的第一线程接收序列化命令; （ii）在第二处理器上运行直到序列化点的第二线程; 和（iii）响应于序列化命令向第一线程输出序列化结果。 序列化结果表明第二个线程已经运行到序列化点。 这样的操作使得第一和第二线程能够稳健地协调由第一线程访问共享资源，同时引起使用MEMBAR指令的负担和在尝试访问共享资源时提供远程串行化命令的负担，第二线程 尝试访问共享资源时不运行任何MEMBAR指令，以使第二个线程更有效地运行。

公开(公告)号：US06799236B1

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

申请号：US10044214

申请日：2001-11-20

申请人： David Dice ,  Alexander T. Garthwaite

发明人： David Dice ,  Alexander T. Garthwaite

IPC分类号： G06F1214

CPC分类号： G06F9/52 ,  G06F9/3004 ,  G06F9/30087

摘要： Mechanisms and techniques operate in a computerized device to execute critical code without interference from interruptions. Critical code is registered for invocation of a critical execution manager in the event of an interruption to the critical code. The critical code is then executed until an interruption to the critical code occurs. After handling the interruption, a critical execution manager is invoked and the critical execution manager detects if an interference signal indicates a reset value. If the interference signal indicates the reset value, the critical execution manager performs a reset operation on the critical code to reset a current state of the critical code to allow execution of the critical code while avoiding interference from handling the interruption and returns to execution of the critical code using the current state of the critical code.

摘要翻译： 机制和技术在计算机化设备中运行，以执行关键代码，而不受中断的干扰。 在关键代码中断的情况下，注册关键代码用于调用关键执行管理器。 然后执行关键代码，直到出现关键代码的中断。 处理中断后，调用关键执行管理器，关键执行管理器检测干扰信号是否指示复位值。 如果干扰信号指示复位值，则关键执行管理器对关键代码执行复位操作，以重置关键代码的当前状态，以允许执行关键代码，同时避免干扰来处理中断并返回执行 关键代码使用关键代码的当前状态。

公开(公告)号：US20080250088A1

公开(公告)日：2008-10-09

申请号：US11732785

申请日：2007-04-03

申请人： Antonios Printezis ,  Alexander T. Garthwaite

发明人： Antonios Printezis ,  Alexander T. Garthwaite

IPC分类号： G06F12/00

CPC分类号： G06F12/0276

摘要： The invention relates to a method for performing generational garbage collection on a heap comprising a plurality of generations. The method involves dividing a young generation of the heap into a first young generation and a second young generation, evacuating the first young generation concurrently with allocating the second young generation, and evacuating the second young generation concurrently with allocating the first young generation and subsequent to fully evacuating the first young generation.

摘要翻译： 本发明涉及一种在包含多代的堆上执行代数垃圾收集的方法。 这种方法包括将年轻一代的小朋友分成第一个年轻一代和第二个年轻一代，同时分配第一个年轻一代，分配第二个年轻一代，同时分配第二个年轻一代，分配第一个年轻一代， 全面撤离第一批年轻一代。

公开(公告)号：US07412580B1

公开(公告)日：2008-08-12

申请号：US10679559

申请日：2003-10-06

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F12/02

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

摘要： A concurrent incremental garbage collector where tracking and summarization of modified references is concurrent with application operations. A card table is arranged with write barriers so that an application's modification of objects in memory cards are memorialized in the card table. The collector performs an atomic operation, e.g., a compare-and-swap (CAS), on the card table to detect modified or written to objects. Card table indicators of dirtied cards are reset or emptied and the corresponding dirtied cards are scanned for the modifications and the remembered sets updated. Another CAS is performed on the same card table and if any dirtied cards are indicated the collector preserves the card table with the dirtied indicators and operates on a distant card table. If the CAS succeeds no modifications were made and the collector operates on the next scheduled card table group.

摘要翻译： 并行增量垃圾回收器，其中跟踪和汇总修改后的引用与应用程序操作并发。 一张卡片表装有写入障碍物，使得应用程序对存储卡中对象的修改被记录在卡片表中。 收集器在卡表上执行原子操作，例如比较和交换（CAS），以检测修改或写入对象。 脏卡的卡片表指示器被复位或清空，并且扫描相应的脏卡以进行修改并更新记忆集。 另一个CAS在相同的卡片表上执行，并且如果指示了任何脏的卡片，则收集器保留具有脏污指示器的卡片表，并在远程卡片表上操作。 如果CAS成功，则不进行修改，并且收集器在下一个预定的卡表组上运行。

公开(公告)号：US07072918B2

公开(公告)日：2006-07-04

申请号：US10395449

申请日：2003-03-24

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F17/30

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

摘要： A computer system, method and software for detecting and purging stale entries from remembered sets associated with incrementally collectible regions used in an incremental garbage collection technique like the Trains algorithm is described. Stale entries are detected by a number of techniques, and then purged, eliminated, or scrubbed. These techniques make use of the summarized information about regions such as cards or incrementally collectible regions that indicate age of allocation, time a region was last scanned, last time an entry was inserted into a remembered set, as well as how far forward or backward objects in a given region refer in a generation.

摘要翻译： 描述了一种计算机系统，方法和软件，用于检测和清除与诸如列车算法之类的增量垃圾收集技术中使用的增量收集区域相关联的记忆集的陈旧条目。 通过多种技术检测陈旧的条目，然后清除，消除或擦洗。 这些技术利用关于诸如卡或递增可收集区域的区域的汇总信息，这些区域指示分配的年龄，上次扫描的时间，上次将记录插入到记忆集中的时间，以及前进或后退的对象 在一个给定的地区，在一代人中引用。

公开(公告)号：US07072905B2

公开(公告)日：2006-07-04

申请号：US10313657

申请日：2002-12-06

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F17/30

CPC分类号： G06F12/0276 ,  Y10S707/99944 ,  Y10S707/99945 ,  Y10S707/99953

摘要： A garbage collector for more efficient placement of objects referenced from external references. The expected life times of these objects is measured by trial and error, by the class or type, by how often the object has been evacuated or the external reference processed, by the stability and longevity of the root source, or by the prolificness of the class or type of object. The measured value is held in the header of each object in an AGE field available for this purpose. These objects may be evacuated into existing trains or into new trains, or into a combination of existing and new trains. When new trains are created the trains are distributed among the existing trains according to a distribution contour that may be linear, normal, gamma or any other contour that might be found useful. Also, when new trains are created the youngest train must be a new train. When objects are evacuated into existing trains the objects are placed in trains according the survivability of the objects with the longer-lived objects placed proportionally in the younger trains. The objects are evacuated into the new trains from oldest to youngest trains according to the value in the AGE field. The higher the value the younger the train. A threshold on the AGE value may be established such that when the threshold is reached, the objects are evacuated into the youngest new train.

摘要翻译： 一个垃圾回收器，用于更有效地放置从外部引用引用的对象。 这些物体的预期寿命是通过试验和误差，类别或类型，物体被疏散或外部参考物处理的频率，根源的稳定性和寿命，或由 类或类型的对象。 测量值保存在可用于此目的的AGE字段中的每个对象的标题中。 这些物体可能被撤离到现有的火车或新列车中，或者组合到现有的和新的列车中。 当新列车被创建时，根据可能是线性，正常，伽马或任何其他可能被发现有用的轮廓的分布轮廓，在现有列车之间分配列车。 此外，当新列车创建时，最小的火车必须是新的列车。 当物体撤离到现有火车中时，物体按照物体的生存能力放置在列车中，而较长寿命的物体按比例放置在较小的火车上。 这些物品根据AGE领域的价值从最旧到最早的列车撤离到新列车中。 火车越小越贵。 可以建立AGE值的阈值，使得当达到阈值时，物体被排空到最年轻的新列车中。

公开(公告)号：US07069280B2

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

申请号：US10313768

申请日：2002-12-06

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F17/30

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

摘要： A garbage collector employs the train algorithm to collect a generation in a dynamically allocated heap. When direct allocation of an object into the generation results in the need to allocate a new car section, the collector makes a determination of whether a new collection increment or interval needs to be initiated. It makes this determination by comparing the amount of new allocation in that generation with a threshold value. During each collection increment, it updates the threshold value by determining how much can occur during the next collection increment without exceeding an allowable pause time. It then projects from that value how much memory-space reclamation is likely to occur. From that likely amount of reclamation, it arrives at a limit on the permitted amount of allocation.

摘要翻译： 垃圾收集器采用列车算法在动态分配的堆中收集一代。 当将对象直接分配到生成中导致需要分配新的汽车部分时，收集器确定是否需要启动新的收集增量或间隔。 它通过将该代中的新分配量与阈值进行比较来确定。 在每次收集增量期间，它通过确定在下一次收集增加期间可以发生多少，而不超过允许的暂停时间来更新阈值。 然后从该值预测可能发生多少内存空间回收。 从可能的填海量来看，这是允许的分配数量的限制。

公开(公告)号：US07035884B2

公开(公告)日：2006-04-25

申请号：US10288008

申请日：2002-11-05

申请人： Alexander T. Garthwaite

发明人： Alexander T. Garthwaite

IPC分类号： G06F12/12

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

摘要： A garbage collector collects a dynamically allocated heap by employing the train algorithm, in which “car” sections of a heap generation are organized in groups, or “trains.” When a car section comes up for collection, objects that it contains are evacuated if they are referred to by references located in cars not currently being collected. The cars to which they are evacuated belong to the trains that contain the references. The trains form a sequence in which their constituent cars are to be collected, and objects that are directly allocated in the generation are placed into trains that precede some existing train in the collection sequence.

摘要翻译： 垃圾收集器通过采用列车算法收集动态分配的堆，其中堆生成的“汽车”部分被组织成“火车”。 当汽车部分出现收集时，如果通过目前正在收集的汽车中的参考文献提及其所包含的物体，则将其撤回。 他们撤离的汽车属于包含参考文件的列车。 火车形成其组成汽车要被收集的序列，在一代中直接分配的物体被放置在收集序列中先于一些现有列车之前的列车中。