System and method for promoting reader groups for lock cohorting

• US 10,585,719 B2
• Filed: 08/06/2018
• Issued: 03/10/2020
• Est. Priority Date: 02/01/2016
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Dice, David, Marathe, Virendra J.
• Primary Examiner(s): Wu, Qing Yuan
• Application Number:
  US16/056,094
• Publication Number:
  US 20180349211A1
• Time in Patent Office: 582 Days
• Field of Search: None
• CPC Class Codes: G06F 13/1605 based on arbitration arbitration in handling access to a common bus or bus system G06F13/36
• CPC Class Codes: G06F 16/176 Support for shared access to files; File sharing support
• CPC Class Codes: G06F 16/1767 Concurrency control, e.g. optimistic or pessimistic approaches
• CPC Class Codes: G06F 16/1774 Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/468 Specific access rights for resources, e.g. using capability register
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

NUMA-aware reader-writer locks may leverage lock cohorting techniques that introduce a synthetic level into the lock hierarchy (e.g., one whose nodes do not correspond to the system topology). The synthetic level may include a global reader lock and a global writer lock. A writer thread may acquire a node-level writer lock, then the global writer lock, and then the top-level lock, after which it may access a critical section protected by the lock. The writer may release the lock (if an upper bound on consecutive writers has been met), or may pass the lock to another writer (on the same node or a different node, according to a fairness policy). A reader may acquire the global reader lock (whether or not node-level reader locks are present), and then the top-level lock. However, readers may only hold these locks long enough to increment reader counts associated with them.

Claims

1. A method, comprising:

performing, by one or more computers;

acquiring, by a writer thread of a plurality of concurrently executing threads executing on respective ones of a plurality of processor cores of a plurality of nodes that share access to a memory, a reader-writer lock having a multiple-level lock hierarchy, wherein said acquiring comprises;

acquiring a node-level writer lock for the respective node for the writer thread at a lowest level in the multiple-level lock hierarchy, wherein the node-level writer lock is one of a plurality of node-level writer locks at the lowest level in the multiple-level lock hierarchy, each of which is a writer lock for a respective one of the plurality of nodes, and wherein at most one writer thread executing on the respective node holds the node-level writer lock at a time;

acquiring a global writer lock at a different level in the multiple-level lock hierarchy, wherein the different level comprises the global writer lock and a global reader lock, and wherein at most one writer thread holds the global writer lock at a time; and

acquiring a top-level lock in the lock hierarchy, wherein at most one writer thread or one reader thread holds the top-level lock at a time.

2. The method of claim 1, further comprising:

accessing, by the writer thread while the writer thread holds the reader-writer lock, a critical section of code protected by the reader-writer lock.

3. The method of claim 2,

wherein the method further comprises determining, subsequent to said accessing, that ownership of the reader-writer lock is to be passed to another writer thread;

and

wherein said determining that ownership of the reader-writer lock is to be passed to the other writer thread comprises;

determining that an upper bound on the number of consecutive writer threads that hold the reader-writer lock has not yet been met.

4. The method of claim 3,

wherein said determining that ownership of the reader-writer lock is to be passed to the other writer thread further comprises determining that an upper bound on the number of consecutive writer threads executing on a single node that hold the global writer lock has not yet been met;

and

wherein the method further comprises passing ownership of the reader-writer lock to another writer thread executing on the given node, wherein passing ownership of the reader-writer lock to another writer thread executing on the given node comprises;

passing ownership of the top-level lock to the other writer thread;

passing ownership of the global writer lock to the other writer thread; and

passing ownership of the node-level writer lock for the given node to the other writer thread.

5. The method of claim 3,

wherein said determining that ownership of the reader-writer lock is to be passed to the other writer thread comprises determining that an upper bound on the number of consecutive writer threads executing on a single node that hold the global writer lock has been met;

and

wherein the method further comprises passing ownership of the reader-writer lock to a writer thread executing on one of the plurality of nodes other than the given node, wherein passing ownership of the reader-writer lock to the writer thread executing on the other node comprises;

passing ownership of the top-level lock to the other writer thread;

passing ownership of the global writer lock to the other writer thread; and

releasing ownership of the node-level writer lock for the given node.

6. The method of claim 2,

wherein the method further comprises determining, subsequent to said accessing, that the writer thread is to release ownership of the reader-writer lock;

and

wherein said determining that the writer thread is to release ownership of the reader-writer lock comprises;

determining that an upper bound on the number of consecutive writer threads that hold the reader-writer lock has been met.

7. The method of claim 6, further comprising:

acquiring, by a reader thread executing on a particular one of the plurality of nodes, the reader-writer lock, wherein said acquiring comprises;

acquiring the global reader lock; and

acquiring the top-level lock.

8. The method of claim 7, further comprising:

acquiring, prior to acquiring the global reader lock, a node-level reader lock for the particular node at the lowest level in the multiple-level lock hierarchy, wherein the node-level reader lock is one of a plurality of node-level reader locks at the lowest level in the multiple-level lock hierarchy, each of which is a reader lock for a respective one of the plurality of nodes in a non-uniform memory-access (NUMA) architecture.

9. The method of claim 8,

wherein the method further comprises:

determining that ownership of the reader-writer lock is to be passed to another reader thread that is executing on the particular node; and

passing ownership of the reader-writer lock to the other reader thread;

wherein said determining that ownership of the reader-writer lock is to be passed to the other reader thread comprises determining that an upper bound on the number of consecutive reader threads executing on a single node that hold the reader-writer lock has not yet been met; and

wherein passing ownership of the reader-writer lock to the other reader thread comprises;

passing ownership of the top-level lock to the other reader thread;

passing ownership of the global reader lock to the other reader thread; and

passing ownership of the node-level reader lock to the other reader thread.

10. The method of claim 7, further comprising:

incrementing a counter whose value represents the number of reader threads that hold the global reader lock;

releasing the global reader lock;

incrementing a counter whose value represents the number of reader threads that hold the reader-writer lock;

releasing the reader-writer lock; and

accessing, by the reader thread, the critical section.

11. The method of claim 10,

wherein the method further comprises determining that ownership of the reader-writer lock is to be passed to another reader thread;

and

wherein said determining that ownership of the reader-writer lock is to be passed to the other reader thread comprises;

determining that an upper bound on the number of consecutive reader threads that hold the reader-writer lock has not yet been met.

12. The method of claim 11,

wherein the method further comprises passing ownership of the reader-writer lock to the other reader thread;

and

wherein passing ownership of the reader-writer lock to the other reader thread comprises;

passing ownership of the top-level lock to the other reader thread; and

passing ownership of the global reader lock to the other reader thread.

13. The method of claim 11,

wherein the upper bound on the number of consecutive reader threads that hold the reader-writer lock and the upper bound on the number of consecutive writer threads that hold the reader-writer lock have different values.

14. The method of claim 11,

wherein one or more of the upper bound on the number of consecutive reader threads that hold the reader-writer lock or the upper bound on the number of consecutive writer threads that hold the reader-writer lock is configurable during runtime.

15. A system, comprising:

a plurality of nodes, 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 nodes;

wherein the system 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;

acquiring, by a writer thread executing on a given one of the plurality of nodes, a reader-writer lock having a multiple-level lock hierarchy, wherein said acquiring comprises;

acquiring a node-level writer lock for the given node at a lowest level in the multiple-level lock hierarchy, wherein the node-level writer lock is one of a plurality of node-level writer locks at the lowest level in the multiple-level lock hierarchy, each of which is a writer lock for a respective one of the plurality of nodes, and wherein at most one writer thread executing on the given node holds the node-level writer lock at a time;

acquiring a global writer lock at a different level in the multiple-level lock hierarchy, wherein the different level comprises the global writer lock and a global reader lock, and wherein at most one writer thread holds the global writer lock at a time; and

acquiring a top-level lock in the lock hierarchy, wherein at most one writer thread or one reader thread holds the top-level lock at a time.

16. The system of claim 15, wherein when executed on the one or more processor cores, the program instructions further cause the one or more processor cores to perform:

accessing, by the writer thread, a critical section of code protected by the reader-writer lock;

determining whether to release the reader-writer lock or pass ownership of the reader-writer lock to another concurrently executing thread, wherein said determining is dependent on an upper limit on the number of consecutive writer threads that hold the reader-writer lock;

releasing the reader-writer lock in response to determining that the upper limit on the number of consecutive writer threads that hold the reader-writer lock has been met, wherein said releasing comprises releasing the top-level lock, the global writer lock, and the node-level writer lock;

passing ownership of the reader-writer lock to another concurrently executing thread in response to determining that the upper limit on the number of consecutive writer threads that hold the reader-writer lock has not yet been met; and

acquiring, by a reader thread executing on one of the plurality of nodes in response to said releasing, the reader-writer lock.

17. The system of claim 16,

wherein said passing ownership of the reader-writer lock to another concurrently executing thread comprises:

determining whether or not an upper bound on the number of consecutive writer threads executing on a single node that hold the global writer lock has been met;

passing ownership of the reader-writer lock to another writer thread executing on the given node in response to determining that the upper bound on the number of consecutive writer threads executing on a single node that hold the global writer lock has not yet been met; and

passing ownership of the reader-writer lock to a writer thread executing on a node other than the given node in response to determining that the upper bound on the number of consecutive writer threads executing on a single node that hold the global writer lock has been met.

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:

acquiring, by a writer thread executing on a given node of a plurality of nodes sharing a memory, a reader-writer lock having a multiple-level lock hierarchy, wherein said acquiring comprises;

acquiring a node-level writer lock for the given node at a lowest level in the multiple-level lock hierarchy, wherein the node-level writer lock is one of a plurality of node-level writer locks at the lowest level in the multiple-level lock hierarchy, each of which is a writer lock for a respective one of the plurality of nodes, and wherein at most one writer thread executing on the given node holds the node-level writer lock at a time;

acquiring a global writer lock at a different level in the multiple-level lock hierarchy, wherein the different level comprises the global writer lock and a global reader lock, and wherein at most one writer thread of a plurality of concurrently executing threads holds the global writer lock at a time; and

acquiring a top-level lock in the lock hierarchy, wherein at most one writer thread of the concurrently executing threads or one reader thread of the concurrent executing threads holds the top-level lock at a time.

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

accessing, by the writer thread, a critical section of code protected by the reader-writer lock;

determining whether to release the reader-writer lock or pass ownership of the reader-writer lock to another one of the concurrently executing threads, wherein said determining is dependent on an upper limit on the number of consecutive writer threads that hold the reader-writer lock;

releasing the reader-writer lock in response to determining that the upper limit on the number of consecutive writer threads that hold the reader-writer lock has been met, wherein said releasing comprises releasing the top-level lock, the global writer lock, and the node-level writer lock;

passing ownership of the reader-writer lock to another one of the concurrently executing threads in response to determining that the upper limit on the number of consecutive writer threads that hold the reader-writer lock has not yet been met; and

acquiring, by a reader thread executing on one of the plurality of nodes in response to said releasing, the reader-writer lock.

20. The non-transitory, computer-readable storage medium of claim 19,

wherein said passing ownership of the reader-writer lock to another one of the concurrently executing threads comprises:

determining whether or not an upper bound on the number of consecutive writer threads executing on a single node that hold the global writer lock has been met;

passing ownership of the reader-writer lock to another writer thread executing on the given node in response to determining that the upper bound on the number of consecutive writer threads executing on a single node that hold the global writer lock has not yet been met; and

passing ownership of the reader-writer lock to a writer thread executing on a node other than the given node in response to determining that the upper bound on the number of consecutive writer threads executing on a single node that hold the global writer lock has been met.