Concurrency control using slotted read-write locks

• US 8,539,168 B2
• Filed: 06/26/2009
• Issued: 09/17/2013
• Est. Priority Date: 06/26/2009
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Dice, David, Shavit, Nir N.
• Primary Examiner(s): Shah, Sanjiv
• Assistant Examiner(s): DILLON, SAMUEL A
• Application Number:
  US12/492,613
• Publication Number:
  US 20100332770A1
• Time in Patent Office: 1,544 Days
• Field of Search: 711/150, 711/152, 711/163, 707/704
• US Class Current: 711/152
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A system and method for concurrency control may use slotted read-write locks. A slotted read-write lock is a lock data structure associated with a shared memory area, wherein the slotted read-write lock indicates whether any thread has a read-lock and/or a write-lock for the shared memory area. Multiple threads may concurrently have the read-lock but only one thread can have the write-lock at any given time. The slotted read-write lock comprises multiple slots, each associated with a single thread. To acquire the slotted read-write lock for reading, a thread assigned to a slot performs a store operation to the slot and then attempts to determine that no other thread holds the slotted read-write lock for writing. To acquire the slotted read-write lock for writing, a thread assigned to a slot sets its write-bit and then attempts to determine that the write-lock is not held.

Claims

1. A non-transitory computer-readable storage medium storing program instructions executable by one or more processors to implement:

assigning each one of a plurality of threads to a respective one of a plurality of slots of a data structure, wherein the data structure comprises a pre-determined number of slots, each of which is individually addressable by the plurality of threads using a respective slot index, wherein each one of the plurality of threads is assigned to a different slot in the data structure such that at most only a single thread is assigned to any given one of the slots, wherein each of the respective slots in the data structure indicates whether the thread assigned to the slot has a read lock for a shared memory area, wherein the data structure further indicates whether any thread has a write lock for the shared memory area, and wherein multiple threads can concurrently have the read lock but only one thread can have the write lock at any given time; and

one of the plurality of threads attempting to acquire the read lock for the shared memory area, wherein said attempting to acquire the read lock comprises;

performing a store operation to set a field associated with the read lock in the thread'"'"'s assigned slot in the data structure to a value indicating acquisition of the read lock; and

performing a load operation from the data structure to determine whether any thread has the write lock for the shared memory area, wherein the thread acquires the read lock for the shared memory area if no other thread has the write lock for the shared memory area.

2. The non-transitory computer-readable storage medium of claim 1, wherein the program instructions are further executable by the one or more processors to implement:

one of the plurality of threads attempting to acquire the write lock for the shared memory area, wherein said attempting to acquire the write lock comprises performing an atomic operation on a write lock field of the data structure, wherein the thread acquires the write lock for the shared memory area if no other thread has the write lock for the shared memory area when the atomic operation is performed; and

the thread that acquired the write lock waiting until the data structure indicates that no other thread has the read lock for the shared memory area before the thread writes to the shared memory area.

3. The non-transitory computer-readable storage medium of claim 1, wherein the program instructions are further executable by the one or more processors to implement:

a thread not assigned to any of the slots of the data structure attempting to acquire the read lock for the shared memory area, wherein said attempting to acquire the read lock for the thread not assigned to any of the slots comprises the thread not assigned to any of the slots performing an atomic operation to increment a reader count field of the data structure, wherein the reader count field indicates whether one or more threads not assigned to one of the slots has the read lock.

4. The non-transitory computer-readable storage medium of claim 1, wherein the data structure fits within a single cache line of a processor executing one or more of the plurality of threads.

5. The non-transitory computer-readable storage medium of claim 1, wherein each one of the plurality of slots of the data structure is individually writable by a thread using a single store operation, and wherein multiple ones of the plurality of slots are simultaneously readable by a thread using a single load operation.

6. The non-transitory computer-readable storage medium of claim 1, wherein, for one or more of the plurality of threads, said assigning each of the one or more of the plurality of threads to a respective one of a plurality of slots of a data structure is performed when the thread is created.

7. The non-transitory computer-readable storage medium of claim 1, wherein, for one or more of the plurality of threads, said assigning each of the one or more of the plurality of threads to a respective one of a plurality of slots of a data structure is performed dynamically during execution of the thread such that said assigning comprises the thread requesting a slot assignment in the data structure.

8. The non-transitory computer-readable storage medium of claim 1, wherein the program instructions are further executable by the one or more processors to implement:

each thread assigned to a respective one of the slots and having the read lock clearing the value of the field associated with the read lock in its respective slot when it no longer requires read access to the shared memory area.

9. The non-transitory computer-readable storage medium of claim 1, wherein the program instructions are further executable by the one or more processors to implement:

one of the plurality of threads attempting to acquire the write lock for the shared memory area, wherein said attempting to acquire the write lock comprises;

performing a store operation to set a field associated with the write lock in the thread'"'"'s assigned slot in the data structure to a value indicating acquisition of the write lock;

checking the data structure to determine whether any thread has the write lock for the shared memory area or is attempting to acquire the write lock for the shared memory area, wherein the thread acquires the write lock for the shared memory area if no other thread has the write lock for the shared memory area or is attempting to acquire the write lock for the shared memory area;

the thread that acquired the write lock waiting until the data structure indicating that no other thread has the read lock for the shared memory area before the thread writes to the shared memory area.

10. The non-transitory computer-readable storage medium of claim 1, wherein a processor executing the one of the plurality of threads attempting to acquire the read lock supports out-of-order execution, wherein said attempting to acquire the read lock further comprises performing a memory barrier between said performing a store operation and said performing a load operation to ensure that the store operation and the load operation are performed by the processor in program order, wherein the load operation is performed subsequent to the store operation.

11. A computer-implemented method comprising:

assigning each one of a plurality of threads to a respective one of a plurality of slots of a data structure, wherein the data structure comprises a pre-determined number of slots, each of which is individually addressable by the plurality of threads using a respective slot index, wherein each one of the plurality of threads is assigned a different slot in the data structure such that at most only a single thread is assigned to any given one of the slots, wherein each of the respective slots in the data structure indicates whether the thread assigned to the slot has a read lock for a shared memory area, wherein the data structure further indicates whether any thread has a write lock for the shared memory area, and wherein multiple threads can concurrently have the read lock but only one thread can have the write lock at any given time; and

one of the plurality of threads attempting to acquire the read lock for the shared memory area, wherein said attempting to acquire the read lock comprises;

performing a store operation to set a field associated with the read lock in the thread'"'"'s assigned slot in the data structure to a value indicating acquisition of the read lock; and

performing a load operation from the data structure to determine whether any thread has the write lock for the shared memory area, wherein the thread acquires the read lock for the shared memory area if no other thread has the write lock for the shared memory area.

12. The computer-implemented method of claim 11, further comprising:

one of the plurality of threads attempting to acquire the write lock for the shared memory area, wherein said attempting to acquire the write lock comprises performing an atomic operation on a write lock field of the data structure, wherein the thread acquires the write lock for the shared memory area if no other thread has the write lock for the shared memory area when the atomic operation is performed; and

the thread that acquired the write lock waiting until the data structure indicates that no other thread has the read lock for the shared memory area before the thread writes to the shared memory area.

13. The computer-implemented method of claim 11, further comprising:

a thread not assigned to any of the slots of the data structure attempting to acquire the read lock for the shared memory area, wherein said attempting to acquire the read lock for the thread not assigned to any of the slots comprises the thread not assigned to any of the slots performing an atomic operation to increment a reader count field of the data structure, wherein the reader count field indicates whether one or more threads not assigned to one of the slots has the read lock.

14. The computer-implemented method of claim 11, wherein, for one or more of the plurality of threads, said assigning each of the one or more of the plurality of threads to a respective one of a plurality of slots of a data structure is performed when the thread is created.

15. The computer-implemented method of claim 11, wherein, for one or more of the plurality of threads, said assigning each of the one or more of the plurality of threads to a respective one of a plurality of slots of a data structure is performed dynamically during execution of the thread such that said assigning comprises the thread requesting a slot assignment in the data structure.

16. The computer-implemented method of claim 11, further comprising:

one of the plurality of threads attempting to acquire the write lock for the shared memory area, wherein said attempting to acquire the write lock comprises;

performing a store operation to set a field associated with the write lock in the thread'"'"'s assigned slot in the data structure to a value indicating acquisition of the write lock;

checking the data structure to determine whether any thread has the write lock for the shared memory area or is attempting to acquire the write lock for the shared memory area, wherein the thread acquires the write lock for the shared memory area if no other thread has the write lock for the shared memory area or is attempting to acquire the write lock for the shared memory area; and

the thread that acquired the write lock waiting until the data structure indicating that no other thread has the read lock for the shared memory area before the thread writes to the shared memory area.

17. A system, comprising:

one or more processors;

a memory coupled to the one or more processors and storing program instructions executable by the one or more processors to implement;

assigning each one of a plurality of threads to a respective one of a plurality of slots of a data structure, wherein the data structure comprises a pre-determined number of slots, each of which is individually addressable by the plurality of threads using a respective slot index, wherein each one of the plurality of threads is assigned a different slot in the data structure such that at most only a single thread is assigned to any given one of the slots, wherein each of the respective slots in the data structure indicates whether the thread assigned to the slot has a read lock for a shared memory area, wherein the data structure further indicates whether any thread has a write lock for the shared memory area, and wherein multiple threads can concurrently have the read lock but only one thread can have the write lock at any given time; and

one of the plurality of threads attempting to acquire the read lock for the shared memory area, wherein said attempting to acquire the read lock comprises;

performing a store operation to set a field associated with the read lock in the thread'"'"'s assigned slot in the data structure to a value indicating acquisition of the read lock; and

performing a load operation from the data structure to determine whether any thread has the write lock for the shared memory area, wherein the thread acquires the read lock for the shared memory area if no other thread has the write lock for the shared memory area.

18. The system of claim 17, wherein the program instructions are further executable by the one or more processors to implement:

one of the plurality of threads attempting to acquire the write lock for the shared memory area, wherein said attempting to acquire the write lock comprises performing an atomic operation on a write lock field of the data structure, wherein the thread acquires the write lock for the shared memory area if no other thread has the write lock for the shared memory area when the atomic operation is performed; and

the thread that acquired the write lock waiting until the data structure indicates that no other thread has the read lock for the shared memory area before the thread writes to the shared memory area.

19. The system of claim 17, wherein the program instructions are further executable by the one or more processors to implement:

a thread not assigned to any of the slots of the data structure attempting to acquire the read lock for the shared memory area, wherein said attempting to acquire the read lock for the thread not assigned to any of the slots comprises the thread not assigned to any of the slots performing an atomic operation to increment a reader count field of the data structure, wherein the reader count field indicates whether one or more threads not assigned to one of the slots has the read lock.

20. The system of claim 17, wherein the program instructions are further executable by the one or more processors to implement:

one of the plurality of threads attempting to acquire the write lock for the shared memory area, wherein said attempting to acquire the write lock comprises;

performing a store operation to set a field associated with the write lock in the thread'"'"'s assigned slot in the data structure to a value indicating acquisition of the write lock;

checking the data structure to determine whether any thread has the write lock for the shared memory area or is attempting to acquire the write lock for the shared memory area, wherein the thread acquires the write lock for the shared memory area if no other thread has the write lock for the shared memory area or is attempting to acquire the write lock for the shared memory area; and

the thread that acquired the write lock waiting until the data structure indicating that no other thread has the read lock for the shared memory area before the thread writes to the shared memory area.