Systems and methods for performing concurrency restriction and throttling over contended locks
First Claim
1. A method, comprising:
- performing by a computer;
beginning execution of a multithreaded application that comprises a plurality of requests to acquire a concurrency-restricting lock associated with a critical section of code or a shared resource;
arriving, by a given thread of the application, at the concurrency restricting lock;
determining, whether the given thread is to be placed in an active circulation set associated with the concurrency-restricting lock or in a passive set associated with the concurrency-restricting lock, wherein threads in the active circulation set are able to contend for the concurrency-restricting lock, and wherein one thread in the passive set is able to contend for the concurrency-restricting lock;
placing the given thread in the determined one of the active circulation set or the passive set; and
subsequent to said placing;
determining, based on a predetermined saturation threshold associated with the active circulation set, to apply a culling policy, wherein applying the culling policy comprises;
controlling movement of threads to and from the active circulation set and passive set to cause a reduction in a number of threads in the active circulation set based at least in part on the saturation threshold of the concurrency-restricting lock dependent on a size of the active circulation set that is eligible to contend for the concurrency-restricting lock, andmoving a thread from the active circulation set to the passive set; and
determining to apply a fairness policy to the passive set, wherein applying the fairness policy comprises;
moving another thread from the passive set to the active circulation set.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
20 Claims
-
1. A method, comprising:
- performing by a computer;
beginning execution of a multithreaded application that comprises a plurality of requests to acquire a concurrency-restricting lock associated with a critical section of code or a shared resource; arriving, by a given thread of the application, at the concurrency restricting lock; determining, whether the given thread is to be placed in an active circulation set associated with the concurrency-restricting lock or in a passive set associated with the concurrency-restricting lock, wherein threads in the active circulation set are able to contend for the concurrency-restricting lock, and wherein one thread in the passive set is able to contend for the concurrency-restricting lock; placing the given thread in the determined one of the active circulation set or the passive set; and subsequent to said placing; determining, based on a predetermined saturation threshold associated with the active circulation set, to apply a culling policy, wherein applying the culling policy comprises; controlling movement of threads to and from the active circulation set and passive set to cause a reduction in a number of threads in the active circulation set based at least in part on the saturation threshold of the concurrency-restricting lock dependent on a size of the active circulation set that is eligible to contend for the concurrency-restricting lock, and moving a thread from the active circulation set to the passive set; and determining to apply a fairness policy to the passive set, wherein applying the fairness policy comprises; moving another thread from the passive set to the active circulation set. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
- performing by a computer;
-
9. A system, comprising:
-
a plurality of nodes, each of which comprises at least one processor core and supports multithreading; and a memory coupled to the plurality of nodes; wherein the memory stores program instructions that when executed on one or more processor cores in the plurality of nodes cause the one or more processor cores to perform; beginning execution of a multithreaded application that comprises a plurality of requests to acquire a concurrency-restricting lock associated with a critical section of code or a shared resource; arriving, by a given thread of the application, at the concurrency restricting lock; determining whether the given thread is to be placed in an active circulation set associated with the concurrency-restricting lock or in a passive set associated with the concurrency-restricting lock, wherein all threads in the active circulation set are able to contend for the concurrency-restricting lock, and wherein at most one thread in the passive set is able to contend for the concurrency restricting lock; placing the given thread in the determined one of the active circulation set or the passive set; and subsequent to said placing; determining, based on a predetermined saturation threshold associated with the active circulation set, to apply a culling policy, wherein applying the culling policy comprises; controlling movement of threads to and from the active circulation set and passive set to cause a reduction in a number of threads in the active circulation set based at least in part on the saturation threshold of the concurrency-restricting lock dependent on a size of the active circulation set that is eligible to contend for the concurrency-restricting lock, and moving a thread from the active circulation set to the passive set; and determining to apply a fairness policy to the passive set, wherein applying the fairness policy comprises; moving another thread from the passive set to the active circulation set. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
-
17. 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 a plurality of requests to acquire a concurrency-restricting lock associated with a critical section of code or a shared resource; arriving, by a given thread of the application, at the concurrency-restricting lock; determining whether the given thread is to be placed in an active circulation set associated with the concurrency-restricting lock or in a passive set associated with the concurrency-restricting lock, wherein all threads in the active circulation set are able to contend for the concurrency-restricting lock, and wherein at most one thread in the passive set is able to contend for the concurrency-restricting lock; placing the given thread in the determined one of the active circulation set or the passive set; and subsequent to said placing; determining, based on a predetermined saturation threshold associated with the active circulation set, to apply a culling policy, wherein applying the culling policy comprises; controlling movement of threads to and from the active circulation set and passive set to cause to the active circulation set that specifies a reduction in a number of threads in the active circulation set based at least in part on the saturation threshold of the concurrency-restricting lock dependent on a size of the active circulation set that is eligible to contend for the concurrency-restricting lock, and moving a thread from the active circulation set to the passive set; and determining to apply a fairness policy to the passive set, wherein applying the fairness policy comprises; moving another thread from the passive set to the active circulation set. - View Dependent Claims (18, 19, 20)
-
Specification