Systems and methods for performing concurrency restriction and throttling over contended locks

• US 10,417,056 B2
• Filed: 08/04/2015
• Issued: 09/17/2019
• Est. Priority Date: 08/04/2015
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Dice, David
• Primary Examiner(s): Aquino, Wynuel S
• Assistant Examiner(s): Headly, Melissa A
• Application Number:
  US14/818,213
• Publication Number:
  US 20170039094A1
• Time in Patent Office: 1,505 Days
• Field of Search: None
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

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.

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.

2. The method of claim 1,

wherein the method further comprises determining that the concurrency restricting lock is saturated;

and

wherein determining whether the given thread is to be placed in the active circulation set or in the passive set comprises determining, in response to determining that the concurrency-restricting lock is saturated, that the given thread is to be placed in the passive set.

3. The method of claim 1, wherein determining whether the given thread is to be placed in the active circulation set or in the passive set is dependent on which of a plurality of computing nodes the given thread is executing on.

4. The method of claim 1,

wherein the method further comprises:

initiating, by a thread that holds the concurrency-restricting lock, an operation to release the concurrency-restricting lock; and

wherein one or more of said applying the culling policy or said applying the fairness policy is performed in response to said initiating.

5. The method of claim 1, wherein the fairness policy is dependent on one or more of:

an amount of time since an individual thread was moved from the passive set to the active circulation set;

a value of a counter;

or

a value returned by a randomization function.

6. The method of claim 1,

wherein one of a plurality of computing nodes on which the multithreaded application is executing is a currently preferred node of the concurrency restricting lock;

wherein the fairness policy is dependent on which of the plurality of computing nodes each of the threads in the passive set is executing on; and

wherein applying the fairness policy comprises moving a thread that is executing on a computing node other than the currently preferred node from the passive set to the active circulation set.

7. The method of claim 1,

wherein the multithreaded application is executing on a plurality of computing nodes;

and

wherein the culling policy is dependent on one or more of;

a lock saturation threshold of the concurrency-restricting lock;

a value of a performance metric associated with the concurrency restricting lock;

or

which of the plurality of computing nodes each of the threads in the active circulation set is executing on.

8. The method of claim 1, further comprising:

accessing, by a first thread in the active circulation set that holds the concurrency restricting lock, the critical section of code or a shared resource; and

subsequent to said accessing;

passing ownership of the concurrency-restricting lock to a second thread in the active circulation set; and

releasing the concurrency-restricting lock.

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.

10. The system of claim 9, wherein data representing the active circulation set and data representing the passive set are maintained in different queues or lists of threads or are maintained in different portions of a single queue or list of threads.

11. The system of claim 9,

wherein the concurrency-restricting lock comprises:

a list-based queuing lock in which threads contending for the list-based queuing lock are maintained in a linked list and spin on local variables; and

an excess threads list;

wherein data representing the active circulation set is maintained in the linked list; and

wherein data representing the passive set is maintained in the excess threads list.

12. The system of claim 9,

wherein the concurrency-restricting lock comprises a last-in-first-out stack in which data stored at the head of the stack represents a thread in the active circulation set that holds the concurrency-restricting lock or that is contending for the concurrency-restricting lock;

and

wherein the method further comprises applying, in response to a fairness condition being met, another fairness policy, wherein applying the other fairness policy comprises moving an element from the tail of the stack to the head of the stack.

13. The system of claim 9,

wherein one of the plurality of nodes is a currently preferred node of the concurrency-restricting lock;

wherein the concurrency-restricting lock comprises;

a last-in-first-out (LIFO) stack in which data stored at the head of the LIFO stack represents a thread in the active circulation set that is executing on the currently preferred node and that holds the concurrency-restricting lock or that is contending for the concurrency-restricting lock; and

a list in which data representing threads in the passive set is maintained, wherein at least one of the threads in the passive set is executing on a node other than the currently preferred node; and

wherein said applying the fairness policy comprises moving an element representing one of the at least one of the threads that is executing on a node other than the currently preferred node from passive list to the active circulation set.

14. The system of claim 13,

wherein when executed on the one or more processor cores in the plurality of nodes, the program instructions further cause the one or more processor cores to perform:

accessing, by a thread in the active circulation set that holds the concurrency-restricting lock, the critical section of code or shared resource;

passing ownership of the concurrency-restricting lock to the one of the at least one of the threads that is executing on a node other than the currently preferred node; and

updating data representing the currently preferred node to indicate that the other node is the currently preferred node.

15. The system of claim 9,

wherein the concurrency-restricting lock comprises:

an outer lock over which threads in the active circulation set circulate; and

an inner lock on which threads in the passive set wait;

wherein the concurrency-restricting lock is considered to be held only when the outer lock is held;

wherein threads in the passive set are able to contend for the outer lock subsequent to acquiring the inner lock; and

wherein 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 comprises;

attempting, by the given thread, to acquire the outer lock; and

determining that the given thread is to be placed in the active circulation set in response to the given thread acquiring the outer lock;

or

determining that the given thread is to be placed in the passive set in response to the given thread failing to acquire the outer lock.

16. The system of claim 15,

wherein when executed on the one or more processor cores in the plurality of nodes, the program instructions further cause the one or more processor cores to perform:

acquiring, by a thread in the passive set, the inner lock;

determining, by the thread that acquired the inner lock, that the outer lock is not currently held;

delaying, by the thread that acquired the inner lock, an attempt to acquire the outer lock;

attempting, by the thread that acquired the inner lock and subsequent to said delaying, to acquire the outer lock; and

wherein applying the fairness policy comprises moving the thread that acquired the inner lock from the passive set to the active circulation set in response to the thread that acquired the inner lock acquiring the outer lock.

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.

18. The non-transitory, computer-readable storage medium of claim 17, wherein when executed on one or more computers, the program instructions further cause the one or more computers to perform:

releasing, by a thread in the active circulation set that holds the concurrency restricting lock, the concurrency-restricting lock, wherein said releasing comprises one or more of;

applying the culling policy to the active circulation set;

applying the fairness policy to the passive set;

or

determining which of a plurality of threads in the active circulation set or the passive set to pass ownership of the concurrency-restricting lock to.

19. The non-transitory, computer-readable storage medium of claim 17, wherein applying the culling policy comprises one or more of:

determining that a lock saturation threshold of the concurrency-restricting lock has been met;

determining a value of a performance metric associated with the concurrency restricting lock;

or

determining which of a plurality of computing nodes on which the multithreaded application is executing each of the threads in the active circulation set is executing on.

20. The non-transitory, computer-readable storage medium of claim 17, wherein applying the fairness policy comprises one or more of:

determining an amount of time since any thread was moved from the passive set to the active circulation set;

determining a value of a counter;

determining which of a plurality of computing nodes on which the multithreaded application is executing each of the threads in the passive set is executing on;

or

determining a value returned by a randomization function.