公开(公告)号：US20200265091A1

公开(公告)日：2020-08-20

申请号：US16407007

申请日：2019-05-08

Applicant: Oracle International Corporation

Inventor： Alex Kogan ,  David Dice ,  Shady Alaaeldin Mohamed Abdelkader Rabie Issa

IPC: G06F16/901 ,  G06F16/176 ,  G06F11/30

Abstract: A computer comprising one or more processors and memory may implement multiple threads performing mutually exclusive lock acquisition operations on disjoint ranges of a shared resource each using atomic compare and swap (CAS) operations. A linked list of currently locked ranges is maintained and, upon entry to a lock acquisition operation, a thread waits for all locked ranges overlapping the desired range to be released then inserts a descriptor for the desired range into the linked list using a single CAS operation. To release a locked range, a thread executes a single fetch and add (FAA) operation. The operation may be extended to support simultaneous exclusive and non-exclusive access by allowing overlapping ranges to be locked for non-exclusive access and by performing an additional validation after locking to provide conflict resolution should a conflict be detected.

公开(公告)号：US20200150869A1

公开(公告)日：2020-05-14

申请号：US16739839

申请日：2020-01-10

Applicant: Oracle International Corporation

Inventor： Alex Kogan ,  David Dice ,  Virendra J. Marathe

IPC: G06F3/06 ,  G06F9/46 ,  G06F9/52 ,  G06F9/50

Abstract: Concurrent threads may be synchronized at the level of the memory words they access rather than at the level of the lock that protects the execution of critical sections. Each lock may be associated with an array of flags and each flag may indicate ownership of certain memory words. A pessimistic thread may set flags corresponding to memory words it is accessing in the critical section, while an optimistic thread may read the corresponding flag before any memory access to ensure that the flag is not set and that therefore the associated memory word is not being accessed by the other thread. Thus, optimistic threads that do not have conflicts with the pessimistic thread may not have to wait for the pessimistic thread to release the lock before proceeding.

公开(公告)号：US20170046182A1

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

申请号：US15221428

申请日：2016-07-27

Applicant: Oracle International Corporation

Inventor： Alex Kogan ,  David Dice ,  Maurice P. Herlihy

IPC: G06F9/445

CPC classification number: G06F9/466 ,  G06F8/458 ,  G06F9/3836 ,  G06F9/3842 ,  G06F9/3851 ,  G06F9/44552 ,  G06F9/46 ,  G06F9/467 ,  G06F9/48 ,  G06F9/4806 ,  G06F9/4812 ,  G06F9/4831 ,  G06F9/4843 ,  G06F9/485 ,  G06F9/4881 ,  G06F9/50 ,  G06F9/5005 ,  G06F9/5027 ,  G06F9/5038 ,  G06F9/52 ,  G06F9/526

Abstract: Hardware transactional memory (HTM) systems may guarantee that transactions commit without falling back to non-speculative code paths. A transaction that fails to progress may enter a power mode, giving the transaction priority when it conflicts with non-power-mode transactions. If, during execution of a power-mode transaction, another thread attempts, using a non-power-mode transaction, to access a shared resource being accessed by the power-mode transaction, it may be determined whether any actual data conflict occurs between the two transactions. If no data conflict exists, both transactions may continue to completion. If, however, a data conflict does exist, the power-mode transaction may deny the other transaction access to the shared resource. HTM systems may, in some embodiments, ensure that only one power-mode transaction exists at a time. In other embodiments, multiple, concurrent, power-mode transactions may be supported while ensuring that they access disjoint data sets.

Abstract translation: 硬件事务存储器（HTM）系统可以保证事务提交而不会退回到非推测性代码路径。 无法进行的事务可能进入电源模式，当与非电源模式事务冲突时，优先处理事务。 如果在执行功率模式事务期间，另一线程使用非功率模式事务尝试访问由功率模式事务访问的共享资源，则可以确定是否在任何实际的数据冲突之间发生任何实际的数据冲突 两笔交易。 如果不存在数据冲突，则两个事务都可能继续完成。 然而，如果确实存在数据冲突，则功率模式事务可以拒绝其他事务对共享资源的访问。 在一些实施例中，HTM系统可以确保一次只存在一个功率模式事务。 在其他实施例中，可以支持多个并发的功率模式事务，同时确保它们访问不相交的数据集。

公开(公告)号：US20160246641A1

公开(公告)日：2016-08-25

申请号：US15050393

申请日：2016-02-22

Applicant: Oracle International Corporation

Inventor： Alex Kogan ,  David Dice ,  Virendra J. Marathe

IPC: G06F9/46 ,  G06F9/52 ,  G06F9/50 ,  G06F3/06

Abstract: Concurrent threads may be synchronized at the level of the memory words they access rather than at the level of the lock that protects the execution of critical sections. Each lock may be associated with an array of flags and each flag may indicate ownership of certain memory words. A pessimistic thread may set flags corresponding to memory words it is accessing in the critical section, while an optimistic thread may read the corresponding flag before any memory access to ensure that the flag is not and that therefore the associated memory word is not being accessed by the other thread. Thus, optimistic threads that do not have conflicts with the pessimistic thread may not have to wait for the pessimistic thread to release the lock before proceeding.

Abstract translation: 并发线程可以在其访问的存储器字的级别上同步，而不是在保护关键段的执行的锁的级别。 每个锁可以与一组标志相关联，并且每个标志可以指示某些存储器字的所有权。 悲观的线程可以设置对应于它在关键部分中访问的存储器字的标志，而乐观线程可以在任何存储器访问之前读取相应的标志，以确保该标志不是，并且因此关联的存储器字不被 另一个线程。 因此，与悲观线程没有冲突的乐观线程可能不必等待悲观线程在继续之前释放锁。

公开(公告)号：US20160216966A1

公开(公告)日：2016-07-28

申请号：US15090554

申请日：2016-04-04

Applicant: Oracle International Corporation

Inventor： David Dice ,  Mark S. Moir

IPC: G06F9/30

CPC classification number: G06F9/30058 ,  G06F9/30079 ,  G06F9/325 ,  G06F9/3846 ,  G06F9/3848

Abstract: A computer system may recognize a busy-wait loop in program instructions at compile time and/or may recognize busy-wait looping behavior during execution of program instructions. The system may recognize that an exit condition for a busy-wait loop is specified by a conditional branch type instruction in the program instructions. In response to identifying the loop and the conditional branch type instruction that specifies its exit condition, the system may influence or override a prediction made by a dynamic branch predictor, resulting in a prediction that the exit condition will be met and that the loop will be exited regardless of any observed branch behavior for the conditional branch type instruction. The looping instructions may implement waiting for an inter-thread communication event to occur or for a lock to become available. When the exit condition is met, the loop may be exited without incurring a misprediction delay.

公开(公告)号：US20160062796A1

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

申请号：US14936619

申请日：2015-11-09

Applicant: Oracle International Corporation

Inventor： David Dice ,  Alex Kogan ,  Yosef Lev ,  Timothy M. Merrifield ,  Mark S. Moir

IPC: G06F9/48 ,  G06F9/46

CPC classification number: G06F9/4843 ,  G06F9/467 ,  G06F9/468 ,  G06F9/4881 ,  G06F9/5022 ,  G06F9/528

Abstract: Particular techniques for improving the scalability of concurrent programs (e.g., lock-based applications) may be effective in some environments and for some workloads, but not others. The systems described herein may automatically choose appropriate ones of these techniques to apply when executing lock-based applications at runtime, based on observations of the application in the current environment and with the current workload. In one example, two techniques for improving lock scalability (e.g., transactional lock elision using hardware transactional memory, and optimistic software techniques) may be integrated together. A lightweight runtime library built for this purpose may adapt its approach to managing concurrency by dynamically selecting one or more of these techniques (at different times) during execution of a given application. In this Adaptive Lock Elision approach, the techniques may be selected (based on pluggable policies) at runtime to achieve good performance on different platforms and for different workloads.

公开(公告)号：US20140181473A1

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

申请号：US13722839

申请日：2012-12-20

Applicant: ORACLE INTERNATIONAL CORPORATION

Inventor： David Dice ,  Yosef Lev ,  Mark S. Moir

IPC: G06F9/48

CPC classification number: G06F9/4881 ,  G06F9/52 ,  G06F9/524

Abstract: The systems and methods described herein may implement probabilistic counters and/or update mechanisms for those counters such that they are dependent on the value of a configurable accuracy parameter. The accuracy parameter value may be adjusted to provide fine-grained control over the tradeoff between the accuracy of the counters and the performance of applications that access them. The counters may be implemented as data structures that include a mantissa portion and an exponent portion that collectively represent an update probability value. When updating the counters, the value of the configurable accuracy parameter may affect whether, when, how often, or by what amount the mantissa portion and/or the exponent portion are updated. Updating a probabilistic counter may include multiplying its value by a constant that is dependent on the value of a configurable accuracy parameter. The counters may be accessible within transactions. The counters may have deterministic update policies.

Abstract translation: 这里描述的系统和方法可以为这些计数器实现概率计数器和/或更新机制，使得它们取决于可配置精度参数的值。 可以调整精度参数值，以便在计数器的准确性和访问它们的应用程序的性能之间进行权衡，以提供细粒度的控制。 计数器可以被实现为数据结构，其包括总体表示更新概率值的尾数部分和指数部分。 当更新计数器时，可配置的精度参数的值可能会影响是否，何时，多长时间还是影响尾数部分和/或指数部分的更新量。 更新概率计数器可以包括将其值乘以一个取决于可配置精度参数的值的常数。 柜台可能在交易中可访问。 计数器可能具有确定性的更新策略。

公开(公告)号：US12182636B2

公开(公告)日：2024-12-31

申请号：US17701302

申请日：2022-03-22

Applicant: Oracle International Corporation

Inventor： David Dice

IPC: G06F9/52

Abstract: A concurrency-restricting lock may divide a set of threads waiting to acquire the lock into an active circulating set (ACS) that contends for the lock, and a passive set (PS) that awaits an opportunity to contend for the lock. The lock, which may include multiple constituent lock types, lists, or queues, may be unfair over the short term, but improve throughput of the underlying multithreaded application. Culling and long-term fairness policies may be applied to the lock to move excess threads from the ACS to the PS or promote threads from the PS to the ACS. These policies may constraint the size or distribution of threads in the ACS (which may be NUMA-aware). A waiting policy may avoid aggressive promotion from the PS to the ACS, and a short-term fairness policy may move a thread from the tail of a list or queue to its head.

公开(公告)号：US20240338259A1

公开(公告)日：2024-10-10

申请号：US18747956

申请日：2024-06-19

Applicant: Oracle International Corporation

Inventor： David Dice ,  Alex Kogan

IPC: G06F9/52 ,  G06F9/30 ,  G06F9/50 ,  G06F9/54

CPC classification number: G06F9/526 ,  G06F9/30087 ,  G06F9/5016 ,  G06F9/541 ,  G06F9/542

Abstract: A computer including multiple processors and memory implements a managed runtime providing a synchronization application programming interface (API) for threads that perform synchronized accesses to shared objects. A standardized header of objects includes a memory word storing an object identifier. To lock the object for synchronized access, the memory word may be converted to store the tail of a linked list of a first-in-first-out synchronization structures for threads waiting to acquire the lock, with the object identifier relocated to the list structure. The list structure may further include a stack of threads waiting on events related to the object, with the synchronization API additionally providing wait, notify and related synchronization operations. Upon determining that no threads hold or desire to hold the lock for the object and that no threads are waiting on events related to the object, the memory word may be restored to contain the object identifier.

公开(公告)号：US20240160447A1

公开(公告)日：2024-05-16

申请号：US18418980

申请日：2024-01-22

Applicant: Oracle International Corporation

Inventor： David Dice ,  Alex Kogan

IPC: G06F9/30 ,  G06F9/38 ,  G06F9/52 ,  G06F12/0802 ,  G06F13/16

CPC classification number: G06F9/3009 ,  G06F9/3802 ,  G06F9/52 ,  G06F9/526 ,  G06F12/0802 ,  G06F13/1663 ,  G06F13/1689 ,  G06F2212/60

Abstract: A computer comprising one or more processors and memory may implement multiple threads that perform a lock operation using a data structure comprising an allocation field and a grant field. Upon entry to a lock operation, a thread allocates a ticket by atomically copying a ticket value contained in the allocation field and incrementing the allocation field. The thread compares the allocated ticket to the grant field. If they are unequal, the thread determines a number of waiting threads. If the number is above the threshold, the thread enters a long term wait operation comprising determining a location for long term wait value and waiting on changes to that value. If the number is below the threshold or the long term wait operation is complete, the thread waits for the grant value to equal the ticket to indicate that the lock is allocated.