READER/WRITER LOCK WITH REDUCED CACHE CONTENTION
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
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. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16)
-
-
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. - View Dependent Claims (18, 19, 20)
-
Specification