公开(公告)号：US20080034172A1

公开(公告)日：2008-02-07

申请号：US11499091

申请日：2006-08-04

申请人： John Joseph Duffy ,  Michael M. Magruder ,  Goetz Graefe ,  David Detlefs ,  Vinod K. Grover

发明人： John Joseph Duffy ,  Michael M. Magruder ,  Goetz Graefe ,  David Detlefs ,  Vinod K. Grover

IPC分类号： G06F13/28

CPC分类号： G06F9/467 ,  Y10S707/99932 ,  Y10S707/99938 ,  Y10S707/99945

摘要： Various technologies and techniques are disclosed that improve implementation of concurrency control modes in a transactional memory system. A transactional memory word is provided for each piece of data. The transactional memory word includes a version number, a reader indicator, and an exclusive writer indicator. The transactional memory word is analyzed to determine if the particular concurrency control mode is proper. Using the transactional memory word to help with concurrency control allows multiple combinations of operations to be performed against the same memory location simultaneously and/or from different transactions. For example, a pessimistic read operation and an optimistic read operation can be performed against the same memory location.

摘要翻译： 公开了改进事务存储器系统中并发控制模式的实现的各种技术和技术。 为每条数据提供事务记忆字。 事务存储器字包括版本号，读取器指示符和专用写入器指示符。 分析事务性存储器字以确定特定的并发控制模式是否合适。 使用事务存储器字来帮助并发控制允许对同一存储位置同时和/或从不同的事务执行多个操作组合。 例如，可以针对相同的存储器位置执行悲观的读取操作和乐观的读取操作。

公开(公告)号：US20070174370A1

公开(公告)日：2007-07-26

申请号：US11331376

申请日：2006-01-12

申请人： David Detlefs ,  Antonios Printezis ,  Steven Heller

发明人： David Detlefs ,  Antonios Printezis ,  Steven Heller

IPC分类号： G06F17/30

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

摘要： In a generational, copying garbage collector, young generation collection may be made more efficient by dynamically measuring object survival rates as a function of “fine-grained” allocation age, and choosing, on the basis of these survival rates, part of the young generation that will be not be collected, but instead scanned for pointers to objects in the rest of the young generation. The rest of the young generation, including objects referenced by the pointers, is then collected.

摘要翻译： 在一代人复制垃圾收集器中，年轻一代的收集可以通过动态地测量对象存活率作为“细粒度”分配年龄的函数而变得更有效率，并且基于这些存活率来选择年轻一代的一部分 这将不被收集，而是扫描指向其他年轻一代的对象的指针。 然后收集年轻一代的其余部分，包括指针引用的对象。

公开(公告)号：US20060218561A1

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

申请号：US11343678

申请日：2006-01-30

申请人： Mark Moir ,  David Detlefs ,  Simon Doherty ,  Maurice Herlihy ,  Victor Luchangco ,  Paul Martin ,  Guy Steele

发明人： Mark Moir ,  David Detlefs ,  Simon Doherty ,  Maurice Herlihy ,  Victor Luchangco ,  Paul Martin ,  Guy Steele

IPC分类号： G06F9/46

CPC分类号： G06F12/0261 ,  G06F9/46 ,  G06F9/526

摘要： A methodology has been discovered for transforming garbage collection-dependent algorithms, shared object implementations and/or concurrent software mechanisms into a form that does not presume the existence of an independent, or execution environment provided, garbage collector. Algorithms, shared object implementations and/or mechanisms designed or transformed using techniques described herein provide explicit reclamation of storage using lock-free pointer operations. Transformations can be applied to lock-free algorithms and shared object implementations and preserve lock-freedom of such algorithms and implementations. As a result, existing and future lock-free algorithms and shared object implementations that depend on a garbage-collected execution environment can be exploited in environments that do not provide garbage collection. Furthermore, algorithms and shared object implementations that employ explicit reclamation of storage using lock-free pointer operations such as described herein may be employed in the implementation of a garbage collector itself.

摘要翻译： 已经发现了一种方法，用于将垃圾回收依赖算法，共享对象实现和/或并发软件机制转换为不假定存在独立或执行环境（垃圾收集器）的形式。 使用本文描述的技术设计或变换的算法，共享对象实现和/或机制使用无锁指针操作来提供存储的显式回收。 转换可以应用于无锁算法和共享对象实现，并保持这种算法和实现的锁定自由度。 因此，依赖于垃圾回收执行环境的现有和将来的无锁算法和共享对象实现可以在不提供垃圾回收的环境中被利用。 此外，使用如本文所述的无锁定指针操作的使用显式回收存储的算法和共享对象实现可以用于实现垃圾收集器本身。

公开(公告)号：US20070162526A1

公开(公告)日：2007-07-12

申请号：US11305957

申请日：2005-12-19

申请人： Antonios Printezis ,  David Detlefs

发明人： Antonios Printezis ,  David Detlefs

IPC分类号： G06F17/30

CPC分类号： G06F9/4843 ,  G06F9/5016 ,  G06F12/0269

摘要： The time cost of collecting a region in a Garbage-First garbage collector is adjusted to account for concurrent thread activity. The overhead of a concurrent thread is tracked by dividing elapsed time into relatively short time “windows” and monitoring the system during those windows to determine how long that thread is scheduled to run during those windows. Using measurements of this type for each concurrent thread, the percentage of each elapsed time window dedicated to each concurrent thread is determined. Finally, by summing the percentages of elapsed time dedicated to concurrent thread activity, the cost of collecting a region can be increased by adding the overhead attributable to concurrent activity.

摘要翻译： 在垃圾回收垃圾回收器中收集区域的时间成本调整为兼并线程活动。 并行线程的开销通过将经过的时间划分为相对较短的时间“windows”并在这些窗口中监视系统来跟踪，以确定在这些窗口期间该线程计划运行多长时间。 对每个并发线程使用此类型的测量，确定专用于每个并发线程的每个经过时间窗口的百分比。 最后，通过将专用于并发线程活动的经过时间的百分比相加，可以通过添加归并于并发活动的开销来增加收集区域的成本。

公开(公告)号：US08032870B2

公开(公告)日：2011-10-04

申请号：US11821630

申请日：2007-06-25

申请人： David Detlefs

发明人： David Detlefs

IPC分类号： G06F9/44

CPC分类号： G06F9/467 ,  G06F8/434

摘要： Various technologies and techniques are disclosed for transacting accesses via unmanaged pointers in a transactional memory system. A transactional memory system is provided. Source code is analyzed to identify operations that create unmanaged pointers. Information is tracked about the targets of unmanaged pointer values in pointer variables. The target information is used to determine how accesses through an unmanaged pointer argument are to be transacted. When an unmanaged pointer is created, a descriptor of the target with the resulting pointer value is associated with the location. Within the method that creates the unmanaged pointer, the target can be identified using the descriptor, thereby enabling accesses to be transacted. When an unmanaged pointer is being passed as an argument, a descriptor is also passed as an argument to allow the unmanaged pointer target to be identified.

摘要翻译： 公开了用于通过事务存储器系统中的非托管指针来进行访问的各种技术和技术。 提供事务性存储系统。 分析源代码以识别创建非托管指针的操作。 跟踪指针变量中非托管指针值的目标的信息。 目标信息用于确定如何处理非托管指针参数的访问。 当创建非托管指针时，具有生成的指针值的目标的描述符与该位置相关联。 在创建非托管指针的方法中，可以使用描述符来标识目标，从而使访问能够被处理。 当非托管指针作为参数传递时，也会将描述符作为参数传递，以允许识别非托管指针。

公开(公告)号：US20070180002A1

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

申请号：US11340940

申请日：2006-01-27

申请人： Antonios Printezis ,  David Detlefs ,  Fabio Rojas

发明人： Antonios Printezis ,  David Detlefs ,  Fabio Rojas

IPC分类号： G06F17/30

CPC分类号： G06F12/0276

摘要： In some circumstances a generational garbage collector may be made more efficient by “pre-tenuring” objects or directly allocating new objects in an old generation instead of allocating them in the normal fashion in a young generation. A pre-tenuring decision is made by a two step process. In the first step, during a young-generation collection, an execution frequency is determined for each allocation site and sites with the highest execution frequency are selected as candidate sites. In the second step, during a subsequent young-generation collection, the survival rates are determined for the candidate sites. After this, objects allocated from sites with sufficiently high survival rates are allocated directly in the old generation.

摘要翻译： 在某些情况下，世代垃圾收集器可以通过“预置换”对象或直接分配新的对象，而不是以年轻一代中的正常方式分配，从而更有效率。 通过两步过程进行了一项前期终身决定。 第一步，在年轻一代的收集中，确定每个分配站点的执行频率，并选择具有最高执行频率的站点作为候选站点。 在第二步，在随后的年轻一代收集中，确定候选地点的存活率。 之后，从具有足够高存活率的地点分配的物品直接分配给老一代。

公开(公告)号：US20070174369A1

公开(公告)日：2007-07-26

申请号：US11330777

申请日：2006-01-12

申请人： David Detlefs

发明人： David Detlefs

IPC分类号： G06F17/30

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

摘要： In a space incremental garbage collector, remembered set information for a region is stored in a set of fixed-size data structures, each of which has a representation of the information and a level of precision that differs from other data structures in the set. Remembered set information for each other region is placed in a data structure based on the density of inter-region references between the region and the other region. The remembered set information for the other region is moved from one data structure to another data structure when the density of inter-region references between the region and the other changes. Some of the data structures use bit arrays to store the information and these arrays can be combined with bit arrays produced by the collector to facilitate the identification and removal of stale remembered set entries.

摘要翻译： 在空间增量垃圾回收器中，区域的记忆集信息存储在一组固定大小的数据结构中，每个固定大小的数据结构具有不同于集合中其他数据结构的信息表示和精度水平。 基于区域和其他区域之间的区域间参考的密度将彼此区域的记忆集信息放置在数据结构中。 当区域和其他区域之间的区域间参考的密度变化时，其他区域的记忆集信息从一个数据结构移动到另一个数据结构。 一些数据结构使用位数组来存储信息，这些数组可以与收集器产生的位数组合，以便识别和删除陈旧的记忆集条目。

公开(公告)号：US20060161737A1

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

申请号：US11384627

申请日：2006-03-20

申请人： Paul Martin ,  David Detlefs ,  Alexander Garthwaite ,  Guy Steele ,  Mark Moir

发明人： Paul Martin ,  David Detlefs ,  Alexander Garthwaite ,  Guy Steele ,  Mark Moir

IPC分类号： G06F13/28

CPC分类号： G06F7/785 ,  G06F9/30032 ,  G06F9/526 ,  G06F9/544 ,  G06F2205/064 ,  G06F2209/521

摘要： In some embodiments, a Hat Trick deque requires only a single DCAS for most pushes and pops. The left and right ends do not interfere with each other until there is one or fewer items in the queue, and then a DCAS adjudicates between competing pops. By choosing a granularity greater than a single node, the user can amortize the costs of adding additional storage over multiple push (and pop) operations that employ the added storage. A suitable removal strategy can provide similar amortization advantages. The technique of leaving spare nodes linked in the structure allows an indefinite number of pushes and pops at a given deque end to proceed without the need to invoke memory allocation or reclamation so long as the difference between the number of pushes and the number of pops remains within given bounds. Both garbage collection dependent and explicit reclamation implementations are described.

摘要翻译： 在一些实施例中，帽子技巧deque仅需要单个DCAS用于大多数按压和弹出。 在队列中有一个或多个项目之前，左右两端不会相互干扰，然后DCAS在竞争弹出之间进行裁决。 通过选择大于单个节点的粒度，用户可以通过使用添加的存储的多个推送（和弹出）操作来分摊添加附加存储的成本。 合适的清除策略可以提供类似的摊销优势。 在结构中链接的备用节点的技术允许在给定的deque端的无限数量的推送和弹出进行，而不需要调用内存分配或回收，只要推送次数和流量数之间的差异保持不变 在给定范围内。 描述垃圾收集相关和显式回收实现。

公开(公告)号：US08271465B2

公开(公告)日：2012-09-18

申请号：US13027938

申请日：2011-02-15

申请人： Michael M. Magruder ,  David Detlefs ,  John J. Duffy ,  Goetz Graefe ,  Vinod K. Grover

发明人： Michael M. Magruder ,  David Detlefs ,  John J. Duffy ,  Goetz Graefe ,  Vinod K. Grover

IPC分类号： G06F17/30

CPC分类号： G06F9/467 ,  G06F17/30356 ,  G06F17/30359 ,  G06F17/30362

摘要： Various technologies and techniques are disclosed for supporting parallel nested transactions in a transactional memory system. Multiple closed nested transactions are created for a single parent transaction, and the closed nested transactions are executed concurrently as parallel nested transactions. Various techniques are used to ensure effects of the parallel nested transactions are hidden from other transactions outside the parent transaction until the parent transaction commits. For example, versioned write locks are used with parallel nested transactions. When a transactional memory word changes from a write lock to a versioned write lock, an entry is made in a global versioned write lock map to store a pointer to a write log entry that the versioned write lock replaced. When the versioned write lock is encountered during transaction processing, the global versioned write lock map is consulted to translate the versioned write lock to the pointer to the write log entry.

摘要翻译： 公开了用于支持事务存储器系统中的并行嵌套事务的各种技术和技术。 为单个父事务创建多个封闭的嵌套事务，并且封闭的嵌套事务将作为并行嵌套事务并发执行。 使用各种技术来确保并行嵌套事务对父事务之外的其他事务的影响，直到父事务提交为止。 例如，版本化的写锁与并行嵌套事务一起使用。 当事务性内存单词从写入锁定更改为版本化写入锁定时，将在全局版本化写入锁定映射中创建一个条目，以存储指向版本化写入锁定替换的写入日志条目的指针。 当在事务处理期间遇到版本化的写锁时，请参考全局版本的写入锁定映射，以将版本化的写锁定转换为写入日志条目的指针。

公开(公告)号：US20080320063A1

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

申请号：US11821630

申请日：2007-06-25

申请人： David Detlefs

发明人： David Detlefs

IPC分类号： G06F17/30

CPC分类号： G06F9/467 ,  G06F8/434

摘要： Various technologies and techniques are disclosed for transacting accesses via unmanaged pointers in a transactional memory system. A transactional memory system is provided. Source code is analyzed to identify operations that create unmanaged pointers. Information is tracked about the targets of unmanaged pointer values in pointer variables. The target information is used to determine how accesses through an unmanaged pointer argument are to be transacted. When an unmanaged pointer is created, a descriptor of the target with the resulting pointer value is associated with the location. Within the method that creates the unmanaged pointer, the target can be identified using the descriptor, thereby enabling accesses to be transacted. When an unmanaged pointer is being passed as an argument, a descriptor is also passed as an argument to allow the unmanaged pointer target to be identified.

摘要翻译： 公开了用于通过事务存储器系统中的非托管指针来进行访问的各种技术和技术。 提供事务性存储系统。 分析源代码以识别创建非托管指针的操作。 跟踪指针变量中非托管指针值的目标的信息。 目标信息用于确定如何处理非托管指针参数的访问。 当创建非托管指针时，具有生成的指针值的目标的描述符与该位置相关联。 在创建非托管指针的方法中，可以使用描述符来标识目标，从而使访问能够被处理。 当非托管指针作为参数传递时，也会将描述符作为参数传递，以允许识别非托管指针。