System and method for implementing scalable adaptive reader-writer locks

Patent metadata

Field	Value
Publication number	US-9996402-B2
Application number	US-201414246975-A
Country	US
Kind code	B2
Filing date	Apr 7, 2014
Priority date	Apr 7, 2014
Publication date	Jun 12, 2018
Grant date	Jun 12, 2018

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.

First claim

What is claimed:

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 whet

Assignees

• Oracle Int Corp

Inventors

• Yadav Rahul

Classifications

• G06F9/528 Primary

  by using speculative mechanisms · CPC title

• G06F12/1466

  Key-lock mechanism · CPC title

• G06F12/0811

  with multilevel cache hierarchies · CPC title

• G06F12/0842

  for multiprocessing or multitasking · CPC title

• G06F9/526 Primary

  Mutual exclusion algorithms · CPC title