公开(公告)号：US08973004B2

公开(公告)日：2015-03-03

申请号：US12492654

申请日：2009-06-26

Applicant: David Dice ,  Nir N. Shavit

Inventor： David Dice ,  Nir N. Shavit

IPC: G06F9/46 ,  G06F13/00 ,  G06F12/00 ,  G06F12/14

CPC classification number: G06F9/467 ,  G06F12/00 ,  G06F12/14 ,  G06F2209/523

Abstract: A system and method for transactional memory using read-write locks is disclosed. Each of a plurality of shared memory areas is associated with a respective read-write lock, which includes a read-lock portion indicating whether any thread has a read-lock for read-only access to the memory area and a write-lock portion indicating whether any thread has a write-lock for write access to the memory area. A thread executing a group of memory access operations as an atomic transaction acquires the proper read or write permissions before performing a memory operation. To perform a read access, the thread attempts to obtain the corresponding read-lock and succeeds if no other thread holds a write-lock for the memory area. To perform a write-access, the thread attempts to obtain the corresponding write-lock and succeeds if no other thread holds a write-lock or read-lock for the memory area.

Abstract translation: 公开了一种使用读写锁的事务性存储器的系统和方法。 多个共享存储器区域中的每一个与相应的读写锁定相关联，读锁定包括指示是否任何线程具有用于对存储区域的只读访问的读锁定的读锁定部分和指示 任何线程是否具有写入对存储区域的访问权限的写锁定。 作为原子事务执行一组内存访问操作的线程在执行内存操作之前获取正确的读取或写入权限。 要执行读取访问，线程尝试获取相应的读取锁定，并且如果没有其他线程持有内存区域的写入锁定，该线程将成功执行。 要执行写入访问，线程尝试获取相应的写入锁定，并且如果其他线程不存在用于存储器区域的写锁定或读锁定，则该线程成功执行。

公开(公告)号：US08909601B2

公开(公告)日：2014-12-09

申请号：US11939372

申请日：2007-11-13

Applicant: Mark S. Moir ,  Yosef Lev ,  Victor M. Luchangco ,  David Dice

Inventor： Mark S. Moir ,  Yosef Lev ,  Victor M. Luchangco ,  David Dice

IPC: G06F9/52 ,  G06F13/14

CPC classification number: G06F9/52

Abstract: A Scalable NonZero Indicator (SNZI) object in a concurrent computing application may include a shared data portion (e.g., a counter portion) and a shared nonzero indicator portion, and/or may be an element in a hierarchy of SNZI objects that filters changes in non-root nodes to a root node. SNZI objects may be accessed by software applications through an API that includes a query operation to return the value of the nonzero indicator, and arrive (increment) and depart (decrement) operations. Modifications of the data portion and/or the indicator portion may be performed using atomic read-modify-write type operations. Some SNZI objects may support a reset operation. A shared data object may be set to an intermediate value, or an announce bit may be set, to indicate that a modification is in progress that affects its corresponding indicator value. Another process or thread seeing this indication may “help” complete the modification before proceeding.

Abstract translation: 并发计算应用中的可扩展非零指示符（SNZI）对象可以包括共享数据部分（例如，计数器部分）和共享非零指示符部分，和/或可以是SNZI对象的层次结构中的元素， 非根节点到根节点。 软件应用程序可以通过API来访问SNZI对象，该API包括返回非零指示符值的查询操作，以及到达（递增）和离开（递减）操作。 可以使用原子读取 - 修改 - 写入类型操作来执行数据部分和/或指示符部分的修改。 一些SNZI对象可能支持复位操作。 可以将共享数据对象设置为中间值，或者可以设置通告位，以指示正在进行的修改影响其对应的指示符值。 看到此指示的另一个进程或线程可能会在进行之前“帮助”完成修改。

公开(公告)号：US08732682B2

公开(公告)日：2014-05-20

申请号：US13213830

申请日：2011-08-19

Applicant: Virendra J. Marathe ,  David Dice

Inventor： Virendra J. Marathe ,  David Dice

IPC: G06F9/45

CPC classification number: G06F9/524 ,  G06F8/458 ,  G06F11/3608 ,  G06F11/3612

Abstract: The system and methods described herein may be used to detect and tolerate atomicity violations between concurrent code blocks and/or to generate code that is executable to detect and tolerate such violations. A compiler may transform program code in which the potential for atomicity violations exists into alternate code that tolerates these potential violations. For example, the compiler may inflate critical sections, transform non-critical sections into critical sections, or coalesce multiple critical sections into a single critical section. The techniques described herein may utilize an auxiliary lock state for locks on critical sections to enable detection of atomicity violations in program code by enabling the system to distinguish between program points at which lock acquisition and release operations appeared in the original program, and the points at which these operations actually occur when executing the transformed program code. Filtering and analysis techniques may reduce false positives induced by the transformations.

Abstract translation: 本文描述的系统和方法可以用于检测和容忍并发代码块之间的原子性违规和/或生成可执行以检测和容忍这种违规的代码。 编译器可以将存在原子性冲突的可能性的程序代码转换为容许这些潜在违规的备用代码。 例如，编译器可能会膨胀关键部分，将非关键部分转换为关键部分，或将多个关键部分合并到单个关键部分中。 本文描述的技术可以利用关键部分上的锁的辅助锁定状态来使得能够通过使得系统能够区分在原始程序中出现锁定获取和释放操作的程序点和在原始程序中出现的点，来检测程序代码中的原子性违反 这些操作在执行转换的程序代码时实际发生。 过滤和分析技术可以减少由转化引起的假阳性。

公开(公告)号：US08725974B2

公开(公告)日：2014-05-13

申请号：US11654456

申请日：2007-01-17

Applicant: David Dice ,  Antonios Printezis

Inventor： David Dice ,  Antonios Printezis

IPC: G06F12/00 ,  G06F13/00

CPC classification number: G06F12/0253

Abstract: A method, apparatus and computer program product for providing page-protection based memory access barrier traps is presented. A value for a user-mode bit (u-bit) is computed for each extant virtual page in an address space, the u-bit indicative that an object on the virtual page is being moved by a Garbage Collector process. An instruction is executed which causes an access protection fault. The state of the u-bit for the virtual page associated with the access protection fault is consulted when the access protection fault is encountered. Additionally, the access protection fault is translated into a user-trap (utrap) and the utrap is serviced when the u-bit is set.

Abstract translation: 提出了一种用于提供基于页面保护的存储器访问障碍阱的方法，装置和计算机程序产品。 为地址空间中的每个现有虚拟页面计算用户模式位（u位）的值，表示虚拟页面上的对象正由垃圾收集器进程移动的u位。 执行导致访问保护故障的指令。 当遇到访问保护故障时，将查阅与访问保护故障相关联的虚拟页面的u位状态。 另外，访问保护故障被转换为用户陷阱（utrap），并且当u位置1时，接口保护故障被服务。

公开(公告)号：US08707006B2

公开(公告)日：2014-04-22

申请号：US12899493

申请日：2010-10-06

Applicant: David Dice

Inventor： David Dice

IPC: G06F12/00 ,  G06F13/00 ,  G06F13/28

CPC classification number: G06F12/0223 ,  G06F12/023 ,  G06F12/0802 ,  G06F12/10 ,  G06F2212/653 ,  G06F2212/657

Abstract: A method for managing a memory, including obtaining a number of indices and a cache line size of a cache memory, computing a cache page size by multiplying the number of indices by the cache line size, calculating a greatest common denominator (GCD) of the cache page size and a first size class, incrementing, in response to the GCD of the cache page size and the first size class exceeding the cache line size, the first size class to generate an updated first size class, calculating a GCD of the cache page size and the updated first size class, creating, in response to the GCD of the cache page size and the updated first size class being less than the cache line size, a first superblock in the memory including a first plurality of blocks of the updated first size class, and creating a second superblock in the memory.

Abstract translation: 一种用于管理存储器的方法，包括获得多个索引和高速缓存存储器的高速缓存行大小，通过将索引数乘以高速缓存行大小来计算高速缓存页大小，计算最大公分母（GCD） 缓存页面大小和第一大小类别，响应于高速缓存页大小的GCD和超过高速缓存行大小的第一大小类而递增，生成更新的第一大小类的第一大小类，计算高速缓存的GCD 页面大小和更新的第一大小类别，响应于缓存页面大小的GCD和更新的第一大小类别小于高速缓存行大小，创建存储器中的第一超级块，其包括更新的第一大小块 第一大小类，并在内存中创建第二个超级块。

公开(公告)号：US08539168B2

公开(公告)日：2013-09-17

申请号：US12492613

申请日：2009-06-26

Applicant: David Dice ,  Nir N. Shavit

Inventor： David Dice ,  Nir N. Shavit

IPC: G06F12/14

CPC classification number: G06F9/526 ,  G06F2209/523

Abstract: A system and method for concurrency control may use slotted read-write locks. A slotted read-write lock is a lock data structure associated with a shared memory area, wherein the slotted read-write lock indicates whether any thread has a read-lock and/or a write-lock for the shared memory area. Multiple threads may concurrently have the read-lock but only one thread can have the write-lock at any given time. The slotted read-write lock comprises multiple slots, each associated with a single thread. To acquire the slotted read-write lock for reading, a thread assigned to a slot performs a store operation to the slot and then attempts to determine that no other thread holds the slotted read-write lock for writing. To acquire the slotted read-write lock for writing, a thread assigned to a slot sets its write-bit and then attempts to determine that the write-lock is not held.

Abstract translation: 用于并发控制的系统和方法可以使用时隙读写锁。 时隙读写锁是与共享存储器区域相关联的锁定数据结构，其中，时隙读写锁定指示任何线程是否具有针对共享存储器区域的读锁定和/或写锁定。 多个线程可以同时具有读锁定，但只有一个线程可以在任何给定时间具有写锁定。 时隙读写锁定包括多个时隙，每个时隙与单个线程相关联。 为了获取读取时隙读写锁，分配给时隙的线程对该时隙执行存储操作，然后尝试确定没有其他线程保持用于写入的时隙读写锁。 要获取用于写入的时隙读写锁，分配给时隙的线程设置其写入位，然后尝试确定写锁定不被保持。

公开(公告)号：US08473772B2

公开(公告)日：2013-06-25

申请号：US12898371

申请日：2010-10-05

Applicant: David Dice ,  Timothy Paul Marsland

Inventor： David Dice ,  Timothy Paul Marsland

IPC: G06F1/14

CPC classification number: G06F1/14

Abstract: A method for providing applications with a current time value includes receiving a trap for an application to access a time memory page, creating, in a memory map corresponding to the application, a mapping between an address space of the application and the time memory page in response to the trap, accessing, based on the trap, a hardware clock to obtain a time value, and updating the time memory page with the time value. The application reads the time value from the time memory page using the memory map.

Abstract translation: 用于向当前时间值提供应用的方法包括接收应用程序访问时间存储器页面的陷阱，在与应用程序相对应的存储器映射中创建应用程序的地址空间与时间存储器页面之间的映射 响应陷阱，根据陷阱访问硬件时钟以获取时间值，并使用时间值更新时间存储器页面。 应用程序使用存储器映射从时间存储器页面读取时间值。

公开(公告)号：US20130047011A1

公开(公告)日：2013-02-21

申请号：US13213833

申请日：2011-08-19

Applicant: David Dice ,  Nir N. Shavit ,  Virendra J. Marathe

Inventor： David Dice ,  Nir N. Shavit ,  Virendra J. Marathe

IPC: G06F9/46 ,  G06F1/32

CPC classification number: G06F9/526 ,  G06F1/3228 ,  G06F1/324 ,  G06F9/485 ,  Y02D10/126

Abstract: The systems and methods described herein may enable a processor core to run at higher speeds than other processor cores in the same package. A thread executing on one processor core may begin waiting for another thread to complete a particular action (e.g., to release a lock). In response to determining that other threads are waiting, the thread/core may enter an inactive state. A data structure may store information indicating which threads are waiting on which other threads. In response to determining that a quorum of threads/cores are in an inactive state, one of the threads/cores may enter a turbo mode in which it executes at a higher speed than the baseline speed for the cores. A thread holding a lock and executing in turbo mode may perform work delegated by waiting threads at the higher speed. A thread may exit the inactive state when the waited-for action is completed.

Abstract translation: 本文描述的系统和方法可以使处理器核心以比同一封装中的其它处理器核心更高的速度运行。 在一个处理器核心上执行的线程可以开始等待另一个线程来完成特定动作（例如，释放锁定）。 响应于确定其他线程正在等待，线程/内核可能进入非活动状态。 数据结构可以存储指示哪些线程在哪个其他线程上等待的信息。 响应于确定线程/核心的法定数量处于非活动状态，线程/内核中的一个可以进入turbo模式，在该模式下，该模式以比核心的基线速度更高的速度执行。 持有锁并以turbo模式执行的线程可以执行以较高速度等待线程委托的工作。 等待操作完成时，线程可能会退出非活动状态。

公开(公告)号：US20110246727A1

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

申请号：US12750455

申请日：2010-03-30

Applicant: David Dice ,  Nir N. Shavit

Inventor： David Dice ,  Nir N. Shavit

IPC: G06F12/02 ,  G06F12/06

CPC classification number: G06F12/0261

Abstract: The system described herein may track references to a shared object by concurrently executing threads using a reference tracking data structure that includes an owner field and an array of byte-addressable per-thread entries, each including a per-thread reference counter and a per-thread counter lock. Slotted threads assigned to a given array entry may increment or decrement the per-thread reference counter in that entry in response to referencing or dereferencing the shared object. Unslotted threads may increment or decrement a shared unslotted reference counter. A thread may update the data structure and/or examine it to determine whether the number of references to the shared object is zero or non-zero using a blocking-optimistic or a non-blocking mechanism. A checking thread may acquire ownership of the data structure, obtain an instantaneous snapshot of all counters, and return a value indicating whether the number of references to the shared object is zero or non-zero.

Abstract translation: 本文描述的系统可以通过使用包括所有者字段和字节可寻址每个线程条目的数组的参考跟踪数据结构并行执行线程来跟踪对共享对象的引用，每个线程项包括每线程参考计数器和每线程参考计数器， 螺纹计数器锁。 分配给给定阵列条目的时隙线程可以增加或减少该条目中的每个线程引用计数器，以响应引用或取消引用共享对象。 未分配的线程可以递增或递减共享的未引用的引用计数器。 线程可以更新数据结构和/或检查它，以使用阻塞乐观或非阻塞机制来确定对共享对象的引用数量是零还是非零。 检查线程可以获取数据结构的所有权，获得所有计数器的瞬时快照，并返回一个值，该值指示对共享对象的引用数是零还是非零。

公开(公告)号：US08028133B2

公开(公告)日：2011-09-27

申请号：US11699802

申请日：2007-01-30

Applicant: David Dice ,  Nir N. Shavit ,  Ori Shalev ,  Mark Moir

Inventor： David Dice ,  Nir N. Shavit ,  Ori Shalev ,  Mark Moir

IPC: G06F13/00

CPC classification number: G06F9/466

Abstract: The present disclosure describes a unique way for each of multiple processes to operate in parallel and use the same shared data without causing corruption to the shared data. For example, during a commit phase, a corresponding transaction can attempt to increment a globally accessible version information variable and store a current value of the globally accessible version information variable for updating version information associated with modified data regardless of whether an associated attempt by the corresponding transaction to modify the globally accessible version information variable was successful. As an alternative mode, a corresponding transaction can merely read and store a current value of the globally accessible version information variable without attempting to update the globally accessible version information variable before such use. In yet another application, a parallel processing environment implements a combination of both aforementioned modes depending on a self-abort rate of the transaction.

Abstract translation: 本公开描述了多个进程中的每一个并行操作并使用相同的共享数据而不会对共享数据造成损坏的唯一方式。 例如，在提交阶段期间，相应的事务可以尝试增加全局可访问的版本信息变量并存储全局可访问版本信息变量的当前值，用于更新与经修改的数据相关联的版本信息，而不管相关联的尝试是否相应 修改全局可访问版本信息变量的事务成功。 作为替代模式，相应的事务只能读取和存储全局可访问版本信息变量的当前值，而不尝试在此类使用之前更新全局可访问版本信息变量。 在另一个应用中，并行处理环境根据交易的自我中止率实现两种上述模式的组合。