公开(公告)号：US20240378242A1

公开(公告)日：2024-11-14

申请号：US18780266

申请日：2024-07-22

Applicant: Oracle International Corporation

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

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

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.

公开(公告)号：US20240345901A1

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

申请号：US18757299

申请日：2024-06-27

Applicant: Oracle International Corporation

Inventor： David Dice ,  Alex Kogan

IPC: G06F9/52 ,  G06F9/50

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

Abstract: Generic Concurrency Restriction (GCR) may divide a set of threads waiting to acquire a lock into two sets: an active set currently able to contend for the lock, and a passive set waiting for an opportunity to join the active set and contend for the lock. The number of threads in the active set may be limited to a predefined maximum or even a single thread. Generic Concurrency Restriction may be implemented as a wrapper around an existing lock implementation. Generic Concurrency Restriction may, in some embodiments, be unfair (e.g., to some threads) over the short term, but may improve the overall throughput of the underlying multithreaded application via passivation of a portion of the waiting threads.

公开(公告)号：US11972777B2

公开(公告)日：2024-04-30

申请号：US18174520

申请日：2023-02-24

Applicant: Oracle International Corporation

Inventor： David Dice ,  Alex Kogan

IPC: G11B20/10 ,  G06F9/52 ,  G06F16/23 ,  G11B20/18 ,  G11C16/26

CPC classification number: G11B20/10268 ,  G06F9/526 ,  G06F16/2343 ,  G06F16/2365 ,  G11B20/105 ,  G11C16/26

Abstract: A data object has a lock and a condition indicator associated with it. Based at least partly on detecting a first setting of the condition indicator, a reader stores an indication that the reader has obtained read access to the data object in an element of a readers structure and reads the data object without acquiring the lock. A writer detects the first setting and replaces it with a second setting, indicating that the lock is to be acquired by readers before reading the data object. Prior to performing a write on the data object, the writer verifies that one or more elements of the readers structure have been cleared.

公开(公告)号：US20230333916A1

公开(公告)日：2023-10-19

申请号：US18341588

申请日：2023-06-26

Applicant: Oracle International Corporation

Inventor： David Dice ,  Alex Kogan

IPC: G06F9/52 ,  G06F9/50

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

Abstract: Generic Concurrency Restriction (GCR) may divide a set of threads waiting to acquire a lock into two sets: an active set currently able to contend for the lock, and a passive set waiting for an opportunity to join the active set and contend for the lock. The number of threads in the active set may be limited to a predefined maximum or even a single thread. Generic Concurrency Restriction may be implemented as a wrapper around an existing lock implementation. Generic Concurrency Restriction may, in some embodiments, be unfair (e.g., to some threads) over the short term, but may improve the overall throughput of the underlying multithreaded application via passivation of a portion of the waiting threads.

公开(公告)号：US11594252B2

公开(公告)日：2023-02-28

申请号：US17507714

申请日：2021-10-21

Applicant: Oracle International Corporation

Inventor： David Dice ,  Alex Kogan

IPC: G11B20/18 ,  G11B20/10 ,  G11C16/26 ,  G06F16/23 ,  G06F9/52

Abstract: A data object has a lock and a condition indicator associated with it. Based at least partly on detecting a first setting of the condition indicator, a reader stores an indication that the reader has obtained read access to the data object in an element of a readers structure and reads the data object without acquiring the lock. A writer detects the first setting and replaces it with a second setting, indicating that the lock is to be acquired by readers before reading the data object. Prior to performing a write on the data object, the writer verifies that one or more elements of the readers structure have been cleared.

公开(公告)号：US20220374287A1

公开(公告)日：2022-11-24

申请号：US17817854

申请日：2022-08-05

Applicant: Oracle International Corporation

Inventor： David Dice ,  Alex Kogan

IPC: G06F9/52 ,  G06F9/38

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.

公开(公告)号：US20220253339A1

公开(公告)日：2022-08-11

申请号：US17169246

申请日：2021-02-05

Applicant: Oracle International Corporation

Inventor： David Dice ,  Alex Kogan

IPC: G06F9/50 ,  G06F9/30

Abstract: Compact and scalable mutual exclusion techniques are implemented for multiple executing threads. A thread may acquire a lock by swapping a pointer to the thread into a tail field of a lock data structure. If the swap operation returned a null value, then the lock is acquired. If the swap operation does not return a null value, then the thread may wait to obtain the lock from a predecessor thread. The thread may wait until a grant field in a data structure for the predecessor thread stores a pointer to the lock, signaling to the thread that the thread may acquire the lock.

公开(公告)号：US11170816B2

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

申请号：US17020655

申请日：2020-09-14

Applicant: Oracle International Corporation

Inventor： David Dice ,  Alex Kogan

IPC: G11B27/36 ,  G11B20/10 ,  G11C16/26 ,  G06F16/23 ,  G06F9/52 ,  G06F16/43

Abstract: A data object has a lock and a condition indicator associated with it. Based at least partly on detecting a first setting of the condition indicator, a reader stores an indication that the reader has obtained read access to the data object in an element of a readers structure and reads the data object without acquiring the lock. A writer detects the first setting and replaces it with a second setting, indicating that the lock is to be acquired by readers before reading the data object. Prior to performing a write on the data object, the writer verifies that one or more elements of the readers structure have been cleared.

公开(公告)号：US20210342202A1

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

申请号：US17378488

申请日：2021-07-16

Applicant: Oracle International Corporation

Inventor： Yosef Lev ,  Victor M. Luchangco ,  David Dice ,  Alex Kogan ,  Timothy L. Harris ,  Pantea Zardoshti

IPC: G06F9/52 ,  G06F9/54

Abstract: A first data accessor acquires a lock associated with a critical section. The first data accessor initiates a help session associated with a first operation of the critical section. In the help session, a second data accessor (which has not acquired the first lock) performs one or more sub-operations of the first operation. The first data accessor releases the lock after at least the first operation has been completed.

公开(公告)号：US20210049010A1

公开(公告)日：2021-02-18

申请号：US17086065

申请日：2020-10-30

Applicant: Oracle International Corporation

Inventor： Virendra J. Marathe ,  Alex Kogan ,  Mihail-Igor Zablotchi

IPC: G06F9/30 ,  G06F12/0804

Abstract: A computer comprising one or more processors and memory may implement an atomic compare and swap (CAS) operation on multiple data elements. Each data element has a corresponding descriptor which includes a new value and a reference to a controlling descriptor for the CAS operation. The controlling descriptor includes a status value which indicates whether the CAS operation is in progress or has completed. The operation first allocates memory locations of the data elements by writing addresses of respective descriptors to the memory locations using CAS instructions. The operation then writes successful status to the status value of the controlling descriptor to indicate that the respective memory locations are no longer allocated. The operation then returns an indicator of successful completion without atomically updating the memory locations with the new values. Extensions are further described to implement CAS operations in non-volatile random access memories.