System and method for implementing scalable adaptive reader-writer locks

• US 9,996,402 B2
• Filed: 04/07/2014
• Issued: 06/12/2018
• Est. Priority Date: 04/07/2014
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Yadav, Rahul
• Primary Examiner(s): Padmanabhan, Mano
• Assistant Examiner(s): Baughman, William E.
• Application Number:
  US14/246,975
• Publication Number:
  US 20150286586A1
• Time in Patent Office: 1,527 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 12/1466 Key-lock mechanism
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G06F 9/528 by using speculative mechanisms

Abstract

NUMA-aware reader-writer locks may leverage lock cohorting techniques and may support reader re-entrancy. They may implement a delayed sleep mechanism by which a thread that fails to acquire a lock spins briefly, hoping the lock will be released soon, before blocking on the lock (sleeping). The maximum spin time may be based on the time needed to put a thread to sleep and wake it up. If a lock holder is not executing on a processor, an acquiring thread may go to sleep without first spinning. Threads put in a sleep state may be placed on a turnstile sleep queue associated with the lock. When a writer thread that holds the lock exits a critical section protected by the lock, it may wake all sleeping reader threads and one sleeping writer thread. Reader threads may increment and decrement node-local reader counters upon arrival and departure, respectively.

Claims

1. A method, comprising:

performing by a computer;

beginning execution of a multithreaded application that comprises one or more requests to acquire a reader-writer lock, wherein the reader-writer lock controls write access to a critical section of code by concurrently executing threads of the application and further controls access to the critical section of code in read-only mode, wherein the reader-writer lock allows at most one writer thread to hold the reader-writer lock for writing at a time, and wherein the reader-writer lock allows multiple reader threads to hold the reader-writer lock in read-only mode at the same time;

a given thread of the application requesting acquisition of the reader-writer lock;

determining that another thread has acquired the reader-writer lock;

determining one of a plurality of available actions to be taken in response to said requesting;

taking the determined action; and

the other thread releasing the reader-writer lock, wherein said releasing comprises waking one or more reader threads wishing to acquire the reader-writer lock that are in a sleep state and a single writer thread of a plurality of writer threads wishing to acquire the reader-writer lock that are in a sleep state.

2. The method of claim 1,

wherein determining the one of the plurality of available actions to be taken comprises determining whether the other thread that has acquired the reader-writer lock is currently executing the critical section of code on a processor core;

wherein said determining one of the plurality of available actions comprises selecting from among the plurality actions comprising the given thread beginning a spin-type operation, putting the given thread in a sleep state, wherein in the sleep state the given thread does not consume processor resources, and the given thread acquiring the reader-writer lock without first performing a spin-type operation and without first being put in sleep state;

wherein the given thread is a reader thread;

wherein the other thread is a reader thread;

wherein the determined action comprises the given thread acquiring the reader-writer lock in read-only mode without first performing the spin-type operation and without first being put in sleep state, wherein said acquiring comprises incrementing a read indicator portion of the reader-writer lock; and

wherein the method further comprises the given thread entering the critical section of code.

3. The method of claim 2,

wherein each of the concurrently executing threads of the application executes on one of a plurality of processor cores that share a memory and that are located on a single node, and wherein the single node is one of a plurality of nodes comprising processor cores on which threads of the multithreaded application are executing;

wherein the read indicator portion of the reader-writer lock comprises a plurality of node-local reader counters; and

wherein said incrementing the reader counter portion of the reader-writer lock comprises incrementing a reader counter that is local to a node comprising a processor core on which the given thread is executing.

4. The method of claim 2, further comprising:

the given thread exiting the critical section of code, wherein said exiting comprises;

decrementing the read indicator portion of the reader-writer lock;

determining whether any other reader threads hold the reader-writer lock; and

in response to determining that no other reader threads hold the reader-writer lock, releasing the reader-writer lock.

5. The method of claim 2, further comprising:

the given thread exiting the critical section of code; and

subsequent to said exiting, and without first releasing the reader-writer lock;

the given thread requesting acquisition of the reader-writer lock in read-only mode; and

determining that the thread already holds the lock.

6. The method of claim 1,

wherein each of the concurrently executing threads of the application executes on a processor core located on a respective one of a plurality of nodes,

wherein each node comprises a plurality of processor cores on which threads of the multithreaded application are executing;

wherein a read indicator portion of the reader-writer lock comprises a plurality of node-local reader counters;

wherein said determining that the other thread has acquired the reader-writer lock comprises determining that an aggregate value representing a sum of the values of the plurality of node-local reader counters is non-zero.

7. The method of claim 1,

wherein the other thread is not currently executing the critical section of code on a processor core;

wherein the determined action comprises putting the given thread in a sleep state; and

wherein the other thread releasing the reader-writer lock further comprises;

waking the given thread.

8. The method of claim 7, wherein said putting the given thread in a sleep state comprises placing the given thread on a turnstile sleep queue associated with the reader-writer lock.

9. The method of claim 7, further comprising, subsequent to said waking:

the given thread acquiring the reader-writer lock; and

the given thread entering the critical section of code.

10. The method of claim 7,

wherein the other thread is a writer thread;

wherein the method further comprises;

the one or more reader threads acquiring the reader-writer lock in read-only mode such that the one or more reader threads hold the reader-writer lock in read-only mode at the same time.

11. The method of claim 10,

wherein the method further comprises, subsequent to waking the one of the one or more writer threads, the one of the one or more writer threads attempting to acquire the reader-writer lock.

12. The method of claim 1,

wherein the given thread is a reader thread;

wherein the other thread is a writer thread;

wherein the other thread is currently executing the critical section of code on a processor core; and

wherein the determined action comprises the given thread beginning a spin-type operation in which the given thread spins on a portion of the reader-writer lock indicating that a thread has acquired the reader-writer lock for writing or has indicated an intent to acquire the reader-writer lock for writing.

13. The method of claim 12, further comprising:

the given thread spinning on the portion of the reader-writer lock until the portion of the reader-writer lock indicates that no thread has acquired the reader-writer lock for writing or has indicated an intent to acquire the reader-writer lock for writing, or until an amount of time equal to a pre-determined reader patience threshold value has passed; and

in response to the amount of time equal to the pre-determined reader patience threshold value passing without the portion of the reader-writer lock indicating that no thread has acquired the reader-writer lock for writing or has indicated an intent to acquire the reader-writer lock for writing, putting the given thread in a sleep state.

14. The method of claim 13, wherein the pre-determined reader patience threshold value is dependent on one or more of:

an amount of time to put a thread in a sleep state, or an amount of time to wake a thread that was previously put in a sleep state.

15. The method of claim 1,

wherein the given thread is a writer thread;

wherein the other thread is currently executing the critical section of code on a processor core; and

wherein the determined action comprises the given thread beginning a spin-type operation in which the given thread spins on a portion of the reader-writer lock indicating whether any reader threads currently hold the reader-writer lock in read-only mode.

16. The method of claim 15, further comprising:

the given thread spinning on the portion of the reader-writer lock until the portion of the reader-writer lock indicates that no reader threads hold the reader-writer lock in read-only mode, or until an amount of time equal to a pre-determined writer patience threshold value has passed;

subsequent to the given thread spinning for an amount of time equal to the pre-determined writer patience threshold value, the given thread determining that one or more threads still hold the reader-writer lock in read-only mode; and

in response to determining that one or more threads still hold the reader-writer lock in read-only mode, putting the given thread in a sleep state.

17. The method of claim 16, wherein the pre-determined writer patience threshold value is dependent on one or more of:

an amount of time to put a thread in a sleep state, or an amount of time to wake a thread that was previously put in a sleep state.

18. 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;

beginning execution of a multithreaded application that comprises one or more requests to acquire a reader-writer lock, wherein the reader-writer lock controls write access to a critical section of code by concurrently executing threads of the application and further controls access to the critical section of code in read-only mode, wherein the reader-writer lock allows at most one writer thread to hold the reader-writer lock for writing at a time, and wherein the reader-writer lock allows multiple reader threads to hold the reader-writer lock in read-only mode at the same time;

a given thread of the application requesting acquisition of the reader-writer lock;

determining that another thread has acquired the reader-writer lock;

determining one of a plurality of available actions to be taken in response to said requesting;

taking the determined action; and

the other thread releasing the reader-writer lock, wherein said releasing comprises waking one or more reader threads wishing to acquire the reader-writer lock that are in a sleep state and a single writer thread of a plurality of writer threads wishing to acquire the reader-writer lock that are in a sleep state.

19. The system of claim 18,

wherein each of the concurrently executing threads of the application executes on one of the plurality of processor cores on a respective node;

wherein a read indicator portion of the reader-writer lock comprises a plurality of node-local reader counters; and

wherein said determining that the other thread has acquired the reader-writer lock comprises determining that an aggregate value representing a sum of the values of the plurality of node-local reader counters is non-zero.

20. 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 reader-writer lock, wherein the reader-writer lock controls write access to a critical section of code by concurrently executing threads of the application and further controls access to the critical section of code in read-only mode, wherein the reader-writer lock allows at most one writer thread to hold the reader-writer lock for writing at a time, and wherein the reader-writer lock allows multiple reader threads to hold the reader-writer lock in read-only mode at the same time;

a given thread of the application requesting acquisition of the reader-writer lock;

determining that another thread has acquired the reader-writer lock;

determining one of a plurality of available actions to be taken in response to said requesting;

taking the determined action; and

the other thread releasing the reader-writer lock, wherein said releasing comprises waking one or more reader threads wishing to acquire the reader-writer lock that are in a sleep state and a single writer thread of a plurality of writer threads wishing to acquire the reader-writer lock that are in a sleep state.