Concurrency Control Using Slotted Read-Write Locks

• US 20100332770A1
• Filed: 06/26/2009
• Published: 12/30/2010
• Est. Priority Date: 06/26/2009
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Shavit, Nir N., Dice, David
• Granted Patent: US 8,539,168 B2
• Time in Patent Office: Days
• US Class Current: 711/148
• 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 computer-readable storage medium storing program instructions executable by one or more processors to implement:

assigning a plurality of threads to respective slots of a data structure, 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 the data structure indicates whether any thread has a read lock for a shared memory area and whether any thread has a write lock for the shared memory area, 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 the thread'"'"'s assigned slot in the data structure for 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 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 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 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 computer-readable storage medium of claim 1, wherein each of the slots of the data structure are individually writable by a single store operation and multiple ones of the slots are simultaneously readable by a single load operation.

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

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

8. The 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 its respective slot for the read lock when it no longer requires read access to the shared memory area.

9. The 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 the thread'"'"'s assigned slot in the data structure for the write lock;

checking the data structure to determine whether any thread has 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 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 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 a plurality of threads to respective slots of a data structure, 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 the data structure indicates whether any thread has a read lock for a shared memory area and whether any thread has a write lock for the shared memory area, 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 the thread'"'"'s assigned slot in the data structure for 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.

13. The computer-implemented method of claim 13, 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.

12. The computer-implemented method of claim 13, 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.

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

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

16. The computer-implemented method of claim 13, 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 the thread'"'"'s assigned slot in the data structure for the write lock;

checking the data structure to determine whether any thread has 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 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 a plurality of threads to respective slots of a data structure, 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 the data structure indicates whether any thread has a read lock for a shared memory area and whether any thread has a write lock for the shared memory area, 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 the thread'"'"'s assigned slot in the data structure for 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 the thread'"'"'s assigned slot in the data structure for the write lock;

checking the data structure to determine whether any thread has 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 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.