READER/WRITER LOCK WITH REDUCED CACHE CONTENTION

• US 20100275209A1
• Filed: 04/28/2009
• Published: 10/28/2010
• Est. Priority Date: 04/28/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Detlefs, David L.
• Granted Patent: US 8,145,817 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A scalable locking system is described herein that allows processors to access shared data with reduced cache contention to increase parallelism and scalability. The system provides a reader/writer lock implementation that uses randomization and spends extra space to spread possible contention over multiple cache lines. The system avoids updates to a single shared location in acquiring/releasing a read lock by spreading the lock count over multiple sub-counts in multiple cache lines, and hashing thread identifiers to those cache lines. Carefully crafted invariants allow the use of partially lock-free code in the common path of acquisition and release of a read lock. A careful protocol allows the system to reuse space allocated for a read lock for subsequent locking to avoid frequent reallocating of read lock data structures. The system also provides fairness for write-locking threads and uses object pooling techniques to make reduce costs associated with the lock data structures.

Claims

1. A computer-implemented method for acquiring a read lock in a multiple processor system, the method comprising:

receiving a request to acquire a read lock;

inspecting a queue of waiting reader and writer nodes to identify a current queue tail, wherein a node at the head of the queue represents one or more threads that currently hold the lock and wherein new requests to acquire the lock are added at the current queue tail;

upon determining that the current queue tail is a reader node, incrementing a reader count by performing the following;

determining a distribution index associated with a current thread;

incrementing an indexed reader count based on the determined distribution index; and

waiting for the reader node to become the head of the queue, and in response to the reader node becoming the head of the queue responding to the request indicating the lock is acquired,

wherein the preceding steps are performed by at least one processor.

2. The method of claim 1 wherein determining a distribution index comprises performing a hash function on a thread identifier of a current thread and determining a modulus of a hash result based on a number of lock counts.

3. The method of claim 1 wherein determining a distribution index distributes received read lock requests to multiple lock counts reduce cache contention versus a single lock count.

4. The method of claim 1 further comprising, before incrementing the indexed reader count, determining whether the queue contains a writer node subsequent to the current reader node, and in response to determining that the queue contains a subsequent writer node, retrying the read lock request to ensure that readers do not starve writer requests.

5. The method of claim 1 wherein the indexed reader count is in a cache line isolated from other reader counts to reduce cache contention produced by the act of updating the reader count.

6. The method of claim 1 wherein the indexed reader count is offset from other reader counts by an amount of padding equal to or greater than a cache line width of a processor of the multiple processor system.

7. The method of claim 1 wherein waiting for the reader node to become the head of the queue comprises spinning for a threshold period and if the reader node does not become the head of the queue during the threshold period blocking waiting for a prior lock holder to release the lock.

8. A computer system for providing a reader/writer lock having favorable cache contention characteristics, the system comprising:

a processor and memory configured to execute software instructions;

an interface component configured to provide an interface to application code and receive requests to acquire and release locks in both a read mode and a write mode;

a queue component configured to maintain a list of reader and writer nodes that represent requests to acquire a lock and any current holder of the lock;

a reader state component configured to maintain an indexed list of reader lock counts for one or more reader nodes in the list maintained by the queue component, wherein the indexed list is structured so that lock counts are distributed with enough space between each count so that accessing a lock count at one index location is associated with a different cache line than accessing a lock count at any other index location;

a blocking component configured to allow threads to block waiting for the lock efficiently and wake threads in response to a particular thread releasing the lock; and

a node allocation component configured to allocate new reader and writer nodes for inclusion on the list maintained by the queue component.

9. The system of claim 8 wherein the interface component is further configured to provide a programmatic interface to applications through Microsoft .NET that includes a class with one or more functions that an application can invoke to acquire and release read and write locks.

10. The system of claim 8 wherein the queue component is further configured to store a node associated with the current holder of the lock at the head of the list and wherein each subsequent node in the list represents a next in line request to receive the lock after the current holder of the lock releases the lock.

11. The system of claim 8 wherein the queue component is further configured to provide lock fairness by enforcing acquisition of the lock based on an order of received requests to ensure that one type of request will not prevent another type of request from acquiring the lock.

12. The system of claim 8 wherein the reader state component prevents cache contention in response to a thread running on one processor modifying a lock count because of acquiring or releasing a read lock.

13. The system of claim 8 wherein the reader state component distributes the lock counts according to a scheme based on a number of processors associated with the system.

14. The system of claim 8 wherein the reader state component distributes the lock counts according to a scheme based on a number of threads using the lock.

15. The system of claim 8 wherein the blocking component is further configured to spin for a threshold number of loops before putting a thread to sleep to be awoken when the lock is available and wherein in response to the lock being released by a current lock holder, the blocking component wakes a thread of the next node in the list maintained by the queue component indicating that the thread has the lock.

16. The system of claim 8 wherein the node allocation component is further configured to use object pooling to provide efficient creation and destruction of nodes.

17. A computer-readable storage medium comprising instructions for controlling a computer system to release a read/write lock, wherein the instructions, when executed, cause a processor to perform actions comprising:

receiving a request to release a previously acquired read lock;

determining a distribution index associated with a current thread;

decrementing an indexed reader count based on the determined distribution index, wherein the indexed reader count is in a cache line isolated from other reader counts to reduce cache contention produced by updating the indexed reader count;

determining whether there is a writer node subsequent to a current reader node associated with the previously acquired read lock;

determining that a total of all indexed reader counts associated with the current reader node is zero; and

in response to determining that there is a writer node subsequent and that the total of all indexed reader counts is zero, releasing the next waiting node in the queue subsequent to the current reader node.

18. The medium of claim 17 wherein determining a distribution index comprises identifying a distribution index determined when the read lock was previously acquired to increment the lock count.

19. The medium of claim 17 wherein releasing the next waiting node comprises modifying a variable that spinning waiting nodes will notice on the next spin loop iteration.

20. The medium of claim 17 wherein releasing the next waiting node comprises calling an operating system provided function to wake threads that went to sleep blocking for the lock to be available.