System and Method for Implementing NUMA-Aware Reader-Writer Locks
First Claim
1. A method, comprising:
- performing by a computer;
beginning execution of a multithreaded application that comprises one or more requests to acquire a shared lock, wherein the shared lock controls write access to a critical section of code or a shared resource by concurrently executing threads of the application, wherein only one thread can hold the shared lock for writing at a time, and wherein each of the concurrently executing threads of the application executes on one of a plurality of processor cores in a cluster of processor cores that share a memory, and wherein the cluster of processor cores is one of a plurality of clusters of processor cores on which threads of the multithreaded application are executing;
a reader thread of the application;
determining that no thread holds the shared lock for writing; and
in response to determining that no thread holds the shared lock for writing;
accessing the critical section of code or shared resource in read-only mode;
subsequent to the reader thread accessing the critical section of code or shared resource in read-only mode, a writer thread of the application acquiring the shared lock for writing;
in response to acquiring the shared lock for writing, the writer thread;
accessing the critical section of code or shared resource for writing; and
subsequent to said accessing the critical section of code or shared resource for writing;
determining whether any other threads of the application executing on a processor core in the cluster of processor cores that comprises the processor core on which the writer thread is executing are waiting to acquire the shared lock for writing; and
in response to determining that at least one other thread of the application executing on a processor core in the cluster of processor cores that comprises the processor core on which the writer thread is executing is waiting to acquire the shared lock for writing, passing ownership of a cluster-specific lock for writing to another thread of the application executing on a processor core in the cluster of processor cores that comprises the processor core on which the writer thread is executing that is waiting to acquire the shared lock for writing without releasing the shared lock.
1 Assignment
0 Petitions
Accused Products
Abstract
NUMA-aware reader-writer locks may leverage lock cohorting techniques to band together writer requests from a single NUMA node. The locks may relax the order in which the lock schedules the execution of critical sections of code by reader threads and writer threads, allowing lock ownership to remain resident on a single NUMA node for long periods, while also taking advantage of parallelism between reader threads. Threads may contend on node-level structures to get permission to acquire a globally shared reader-writer lock. Writer threads may follow a lock cohorting strategy of passing ownership of the lock in write mode from one thread to a cohort writer thread without releasing the shared lock, while reader threads from multiple NUMA nodes may simultaneously acquire the shared lock in read mode. The reader-writer lock may follow a writer-preference policy, a reader-preference policy or a hybrid policy.
77 Citations
20 Claims
-
1. A method, comprising:
performing by a computer; beginning execution of a multithreaded application that comprises one or more requests to acquire a shared lock, wherein the shared lock controls write access to a critical section of code or a shared resource by concurrently executing threads of the application, wherein only one thread can hold the shared lock for writing at a time, and wherein each of the concurrently executing threads of the application executes on one of a plurality of processor cores in a cluster of processor cores that share a memory, and wherein the cluster of processor cores is one of a plurality of clusters of processor cores on which threads of the multithreaded application are executing; a reader thread of the application; determining that no thread holds the shared lock for writing; and in response to determining that no thread holds the shared lock for writing; accessing the critical section of code or shared resource in read-only mode; subsequent to the reader thread accessing the critical section of code or shared resource in read-only mode, a writer thread of the application acquiring the shared lock for writing; in response to acquiring the shared lock for writing, the writer thread; accessing the critical section of code or shared resource for writing; and subsequent to said accessing the critical section of code or shared resource for writing; determining whether any other threads of the application executing on a processor core in the cluster of processor cores that comprises the processor core on which the writer thread is executing are waiting to acquire the shared lock for writing; and in response to determining that at least one other thread of the application executing on a processor core in the cluster of processor cores that comprises the processor core on which the writer thread is executing is waiting to acquire the shared lock for writing, passing ownership of a cluster-specific lock for writing to another thread of the application executing on a processor core in the cluster of processor cores that comprises the processor core on which the writer thread is executing that is waiting to acquire the shared lock for writing without releasing the shared lock. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
15. A system, comprising:
-
a plurality of processor core clusters, each of which comprises two or more processor cores that support multithreading and that share a local memory; a system memory coupled to the plurality of processor core clusters; wherein the system memory stores program instructions that when executed on one or more processor cores in the plurality of processor core clusters cause the one or more processor cores to perform; beginning execution of a multithreaded application that comprises one or more requests to acquire a shared lock, wherein the shared lock controls write access to a critical section of code or a shared resource by concurrently executing threads of the application, wherein only one thread can hold the shared lock for writing at a time, and wherein the each of the concurrently executing threads of the application executes on one of the plurality of processor cores in the processor core clusters; a reader thread of the application; determining that no thread holds the shared lock for writing; and in response to determining that no thread holds the shared lock for writing; accessing the critical section of code or shared resource in read-only mode; subsequent to the reader thread accessing the critical section of code or shared resource in read-only mode, a writer thread of the application acquiring the shared lock for writing; in response to acquiring the shared lock for writing, the writer thread; accessing the critical section of code or shared resource for writing; and subsequent to said accessing the critical section of code or shared resource for writing; determining whether any other threads of the application executing on a processor core in the cluster of processor cores that comprises the processor core on which the writer thread is executing are waiting to acquire the shared lock for writing; and in response to determining that at least one other thread of the application executing on a processor core in the cluster of processor cores that comprises the processor core on which the writer thread is executing is waiting to acquire the shared lock for writing, passing ownership of a cluster-specific lock for writing to another thread of the application executing on a processor core in the cluster of processor cores that comprises the processor core on which the writer thread is executing that is waiting to acquire the shared lock for writing without releasing the shared lock. - View Dependent Claims (16, 17)
-
-
18. A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:
-
beginning execution of a multithreaded application that comprises one or more requests to acquire a shared lock, wherein the shared lock controls write access to a critical section of code or a shared resource by concurrently executing threads of the application, wherein only one thread can hold the shared lock for writing at a time, and wherein the each of the concurrently executing threads of the application executes on one of a plurality of processor cores in a cluster of processor cores that share a memory, and wherein the cluster of processor cores is one of a plurality of clusters of processor cores on which threads of the multithreaded application are executing; a reader thread of the application; determining that no thread holds the shared lock for writing; and in response to determining that no thread holds the shared lock for writing; accessing the critical section of code or shared resource in read-only mode; subsequent to the reader thread accessing the critical section of code or shared resource in read-only mode, a writer thread of the application acquiring the shared lock for writing; in response to acquiring the shared lock for writing, the writer thread; accessing the critical section of code or shared resource for writing; and subsequent to said accessing the critical section of code or shared resource for writing; determining whether any other threads of the application executing on a processor core in the cluster of processor cores that comprises the processor core on which the writer thread is executing are waiting to acquire the shared lock for writing; and in response to determining that at least one other thread of the application executing on a processor core in the cluster of processor cores that comprises the processor core on which the writer thread is executing is waiting to acquire the shared lock for writing, passing ownership of a cluster-specific lock for writing to another thread of the application executing on a processor core in the cluster of processor cores that comprises the processor core on which the writer thread is executing that is waiting to acquire the shared lock for writing without releasing the shared lock. - View Dependent Claims (19, 20)
-
Specification