公开(公告)号：US12217083B2

公开(公告)日：2025-02-04

申请号：US17308502

申请日：2021-05-05

Applicant: Oracle International Corporation

Inventor： Alex Kogan ,  Yosef Lev

IPC: G06F9/46

Abstract: An HTM-assisted Combining Framework (HCF) may enable multiple (combiner and non-combiner) threads to access a shared data structure concurrently using hardware transactional memory (HTM). As long as a combiner executes in a hardware transaction and ensures that the lock associated with the data structure is available, it may execute concurrently with other threads operating on the data structure. HCF may include attempting to apply operations to a concurrent data structure utilizing HTM and if the HTM attempt fails, utilizing flat combining within HTM transactions. Publication lists may be used to announce operations to be applied to a concurrent data structure. A combiner thread may select a subset of the operations in the publication list and attempt to apply the selected operations using HTM. If the thread fails in these HTM attempts, it may acquire a lock associated with the data structure and apply the selected operations without HTM.

公开(公告)号：US20240028424A1

公开(公告)日：2024-01-25

申请号：US18478820

申请日：2023-09-29

Applicant: Oracle International Corporation

Inventor： David Dice ,  Timothy L. Harris ,  Alex Kogan ,  Yosef Lev ,  Mark S. Moir

IPC: G06F9/52 ,  G06F9/46 ,  G06F9/38 ,  G06F9/30

CPC classification number: G06F9/526 ,  G06F9/467 ,  G06F9/3851 ,  G06F9/30087

Abstract: Transactional Lock Elision allows hardware transactions to execute unmodified critical sections protected by the same lock concurrently, by subscribing to the lock and verifying that it is available before committing the transaction. A “lazy subscription” optimization, which delays lock subscription, can potentially cause behavior that cannot occur when the critical sections are executed under the lock. Hardware extensions may provide mechanisms to ensure that lazy subscriptions are safe (e.g., that they result in correct behavior). Prior to executing a critical section transactionally, its lock and subscription code may be identified (e.g., by writing their locations to special registers). Prior to committing the transaction, the thread executing the critical section may verify that the correct lock was correctly subscribed to. If not, or if locations identified by the special registers have been modified, the transaction may be aborted. Nested critical sections associated with different lock types may invoke different subscription code.

公开(公告)号：US09727369B2

公开(公告)日：2017-08-08

申请号：US15156110

申请日：2016-05-16

Applicant: Oracle International Corporation

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

IPC: G06F12/00 ,  G06F9/46 ,  G06F9/52 ,  G06F9/50

CPC classification number: G06F9/467 ,  G06F9/5027 ,  G06F9/528 ,  G06F2209/523

Abstract: Transactional reader-writer locks may leverage available hardware transactional memory (HTM) to simplify the procedures of the reader-writer lock algorithm and to eliminate a requirement for type stable memory An HTM-based reader-writer lock may include an ordered list of client-provided nodes, each of which represents a thread that holds (or desires to acquire) the lock, and a tail pointer. The locking and unlocking procedures invoked by readers and writers may access the tail pointer or particular ones of the nodes in the list using various combinations of transactions and non-transactional accesses to insert nodes into the list or to remove nodes from the list. A reader or writer that owns a node at the head of the list (or a reader whose node is preceded in the list only by other readers' nodes) may access a critical section of code or shared resource.

公开(公告)号：US09619281B2

公开(公告)日：2017-04-11

申请号：US14936619

申请日：2015-11-09

Applicant: Oracle International Corporation

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

IPC: G06F9/46 ,  G06F9/48 ,  G06F9/50 ,  G06F9/52

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.

公开(公告)号：US20170075720A1

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

申请号：US15263123

申请日：2016-09-12

Applicant: Oracle International Corporation

Inventor： Alex Kogan ,  Victor M. Luchangco ,  Yosef Lev ,  Trevor Brown

IPC: G06F9/46 ,  G06F9/50 ,  G06F9/48

CPC classification number: G06F9/528 ,  G06F9/5027 ,  H04Q3/54541

Abstract: Socket scheduling modes may prevent non-uniform memory access effects from negatively affecting performance of synchronization mechanisms utilizing hardware transactional memory. Each mode may indicate whether a thread may execute a critical section on a particular socket. For example, under transitional lock elision, locks may include a mode indicating whether threads may acquire or elide the lock on a particular socket. Different modes may be used alternately to prevent threads from starving. A thread may only execute a critical section on a particular socket if allowed by the current mode. Otherwise, threads may block until allowed to execute the critical section, such as after the current mode changes. A profiling session may, for a running workload, iterate over all possible modes, measuring statistics pertaining to the execution of critical sections (e.g., the number of lock acquisitions and/or elisions), to determine the best performing modes for the particular workload.

Abstract translation: 套接字调度模式可以防止不均匀的存储器访问效应不利地影响利用硬件事务存储器的同步机制的性能。 每个模式可以指示线程是否可以在特定的套接字上执行关键部分。 例如，在过渡锁定检测下，锁可以包括指示线程是否可以获取或删除特定套接字上的锁的模式。 可以交替使用不同的模式来防止线程饥饿。 线程只能在当前模式允许的情况下执行特定套接字上的关键部分。 否则，线程可能会阻塞，直到允许执行关键部分，例如当前模式更改后。 对于运行的工作负载，分析会话可以迭代所有可能的模式，测量关于关键部分的执行的统计数据（例如，锁获取和/或删除的数量），以确定特定工作负载的最佳执行模式。

公开(公告)号：US20160259663A1

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

申请号：US15156110

申请日：2016-05-16

Applicant: Oracle International Corporation

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

IPC: G06F9/46 ,  G06F9/50

CPC classification number: G06F9/467 ,  G06F9/5027 ,  G06F9/528 ,  G06F2209/523

Abstract: Transactional reader-writer locks may leverage available hardware transactional memory (HTM) to simplify the procedures of the reader-writer lock algorithm and to eliminate a requirement for type stable memory An HTM-based reader-writer lock may include an ordered list of client-provided nodes, each of which represents a thread that holds (or desires to acquire) the lock, and a tail pointer. The locking and unlocking procedures invoked by readers and writers may access the tail pointer or particular ones of the nodes in the list using various combinations of transactions and non-transactional accesses to insert nodes into the list or to remove nodes from the list. A reader or writer that owns a node at the head of the list (or a reader whose node is preceded in the list only by other readers' nodes) may access a critical section of code or shared resource.

Abstract translation: 事务读写器锁可以利用可用的硬件事务存储器（HTM）来简化读写器锁定算法的过程，并消除对类型稳定存储器的要求基于HTM的读写器锁可以包括客户端 - 提供的节点，每个节点表示一个保存（或希望获取）锁的线程和一个尾部指针。 读者和作者调用的锁定和解锁过程可以使用事务和非事务性访问的各种组合来访问列表中的尾部指针或特定节点，以将节点插入到列表中或从列表中删除节点。 在列表头部拥有一个节点的阅读器或写入器（或者只有其他读取器节点在其列表中的节点之前的读取器）可以访问代码或共享资源的关键部分。

公开(公告)号：US20160246527A1

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

申请号：US15050396

申请日：2016-02-22

Applicant: Oracle International Corporation

Inventor： Alex Kogan ,  Yosef Lev

IPC: G06F3/06 ,  G06F9/46

CPC classification number: G06F3/0604 ,  G06F3/0629 ,  G06F9/467 ,  G06F9/5016 ,  G06F9/52 ,  G06F9/524

Abstract: Threads using hardware transactions and executing instrumented critical sections that do not perform any writes may complete as long as the thread holding the lock has not yet executed its first write operation. If the thread executing the instrumented critical section performs any writes, or if the thread holding the lock performs any writes during its critical section, the hardware transaction may be aborted. A write flag may be used to determine whether the thread holding the lock performs any writes. The thread holding the lock may set the flag before performing any write operation. The thread executing the hardware transaction may subscribe to that flag and abort the transaction if the flag is set to true, indicating that the thread holding the lock performed a write operation.

Abstract translation: 只要持有锁的线程尚未执行其第一次写入操作，使用硬件事务和执行不执行任何写入的仪表化关键部分的线程就可以完成。 如果执行检测的关键部分的线程执行任何写入，或者如果持有锁的线程在其关键部分期间执行任何写操作，则可能会中止硬件事务。 可以使用写标志来确定持有锁的线程是否执行任何写入。 持有锁的线程可以在执行任何写操作之前设置该标志。 执行硬件事务的线程可以订阅该标志，并且如果标志被设置为真，则中止该事务，指示保持锁定的线程执行写入操作。

公开(公告)号：US08918596B2

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

申请号：US13722817

申请日：2012-12-20

Applicant: Oracle International Corporation

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

IPC: G06F13/18 ,  G06F9/50 ,  G06F9/52

CPC classification number: G06F13/18 ,  G06F9/5027 ,  G06F9/52 ,  G06F9/526

Abstract: The systems and methods described herein may be used to implement scalable statistics counters suitable for use in systems that employ a NUMA style memory architecture. The counters may be implemented as data structures that include a count value portion and a node identifier portion. The counters may be accessible within transactions. The node identifier portion may identify a node on which a thread that most recently incremented the counter was executing or one on which a thread that has requested priority to increment the shared counter was executing. Threads executing on identified nodes may have higher priority to increment the counter than other threads. Threads executing on other nodes may delay their attempts to increment the counter, thus encouraging consecutive updates from threads on a single node. Impatient threads may attempt to update the node identifier portion or may update an anti-starvation variable to indicate a request for priority.

Abstract translation: 本文描述的系统和方法可以用于实现适用于采用NUMA风格存储器架构的系统中的可伸缩统计计数器。 计数器可以被实现为包括计数值部分和节点标识符部分的数据结构。 柜台可能在交易中可访问。 节点标识符部分可以标识正在执行计数器最近递增的线程的节点，或者正在执行已经请求优先级以增加共享计数器的线程的节点。 在标识节点上执行的线程可能比其他线程具有更高的优先级来增加计数器。 在其他节点上执行的线程可能会延迟其增加计数器的尝试，从而鼓励单个节点上线程的连续更新。 不耐烦的线程可以尝试更新节点标识符部分，或者可以更新反饥饿变量以指示优先级请求。

公开(公告)号：US20140282595A1

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

申请号：US13800097

申请日：2013-03-13

Applicant: ORACLE INTERNATIONAL CORPORATION

Inventor： Yosef Lev ,  Guy L. Steele, JR.

IPC: G06F9/48

CPC classification number: G06F9/505 ,  G06F9/5083 ,  G06F2209/5011

Abstract: A system may perform work stealing using a dynamically configurable separation between stealable and non-stealable work items. The work items may be held in a double-ended queue (deque), and the value of a variable (index) may indicate the position of the last stealable work item or the first non-stealable work item in the deque. A thread may steal a work item only from the portion of another thread's deque that holds stealable items. The owner of a deque may add work items to the deque and may modify the number or percentage of stealable work items, the number or percentage of non-stealable work items, and/or the ratio between stealable and non-stealable work items in the deque during execution. For example, the owner may convert stealable work items to non-stealable work items, or vice versa, in response to changing conditions and/or according to various work-stealing policies.

Abstract translation: 系统可以使用在可偷窃和非偷窃工作项之间的可动态配置分隔来执行工作窃取。 工作项目可以保存在双端队列（deque）中，变量（索引）的值可以指示最后一个可窃取的工作项或位于第一个非可窃取工作项的位置。 一个线程只能从另一个线程的持有可窃取物品的deque的部分窃取工作项。 德行的业主可以向工作单位增加工作项目，并可能修改可偷工作项目的数量或百分比，非可偷工作项目的数量或百分比，和/或可偷窃工作项目与非可偷工作项目之间的比例 执行期间deque。 例如，业主可以根据不断变化的条件和/或根据各种工作窃取政策将可转让的工作项目转换为非可窃取的工作项目，反之亦然。

公开(公告)号：US20140258645A1

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

申请号：US13784965

申请日：2013-03-05

Applicant: ORACLE INTERNATIONAL CORPORATION

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

IPC: G06F12/14

CPC classification number: G06F9/467 ,  G06F9/5027 ,  G06F9/528 ,  G06F2209/523

Abstract: Transactional reader-writer locks may leverage available hardware transactional memory (HTM) to simplify the procedures of the reader-writer lock algorithm and to eliminate a requirement for type stable memory An HTM-based reader-writer lock may include an ordered list of client-provided nodes, each of which represents a thread that holds (or desires to acquire) the lock, and a tail pointer. The locking and unlocking procedures invoked by readers and writers may access the tail pointer or particular ones of the nodes in the list using various combinations of transactions and non-transactional accesses to insert nodes into the list or to remove nodes from the list. A reader or writer that owns a node at the head of the list (or a reader whose node is preceded in the list only by other readers' nodes) may access a critical section of code or shared resource.

Abstract translation: 事务读写器锁可以利用可用的硬件事务存储器（HTM）来简化读写器锁定算法的过程，并消除对类型稳定存储器的要求基于HTM的读写器锁可以包括客户端 - 提供的节点，每个节点表示一个保存（或希望获取）锁的线程和一个尾部指针。 读者和作者调用的锁定和解锁过程可以使用事务和非事务性访问的各种组合来访问列表中的尾部指针或特定节点，以将节点插入到列表中或从列表中删除节点。 在列表头部拥有一个节点的阅读器或写入器（或者只有其他读取器节点在其列表中的节点之前的读取器）可以访问代码或共享资源的关键部分。