SCALABLE READER-WRITER LOCK

• US 20100241774A1
• Filed: 03/18/2009
• Published: 09/23/2010
• Est. Priority Date: 03/18/2009
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Lev, Yosef, Luchangco, Victor M., Olszewski, Marek K.
• Granted Patent: US 8,504,540 B2
• Time in Patent Office: Days
• US Class Current: 710/200
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A reader-writer lock is provided that scales to accommodate multiple readers without contention. The lock comprises a hierarchical C-SNZI (Conditioned Scalable Non-Zero Indicator) structure that scales with the number readers seeking simultaneous acquisition of the lock. All readers that have joined the C-SNZI structure share concurrent acquisition, and additional readers may continue to join until the structure is disabled. The lock may be disabled by a writer, at which time subsequent readers will wait (e.g., in a wait queue) until the lock is again available. The C-SNZI structure may be implemented in a lockword or in reader entries within a wait queue. If implemented in reader entries of a wait queue, the lockword may be omitted, and new readers arriving at the queue may be able join an existing reader entry even if the reader entry is not at the tail of the queue.

Claims

1. A method of facilitating acquisition of a reader-writer lock by multiple readers, the method comprising:

constructing a hierarchical C-SNZI (Conditioned Scalable Non-Zero Indicator) structure within the lock;

joining multiple readers to the C-SNZI structure, wherein the multiple readers share acquisition of the lock while joined to the C-SNZI structure; and

updating a surplus configured to remain greater than zero as long as at least one of the multiple readers is joined to the C-SNZI structure.

2. The method of claim 1, wherein the C-SNZI structure comprises:

a root node; and

a plurality of non-root nodes, wherein one or more non-root nodes expose;

an arrive operation invocable by a reader to join the C-SNZI structure; and

a depart operation invocable by a reader to leave the C-SNZI structure, wherein the depart operation is invoked by readers that previously invoked the arrive operation.

3. The method of claim 1, further comprising:

setting a first flag in the C-SNZI structure in response to a request by a writer; and

after setting of the first flag, prohibiting an additional reader from joining the C-SNZI structure.

4. The method of claim 3, further comprising:

setting a second flag when the writer acquires the lock.

5. The method of claim 1, wherein:

the reader-writer lock comprises a lockword and a queue; and

a root node of the C-SNZI structure is included in the lockword.

6. The method of claim 5, wherein:

the queue is protected by a mutual exclusion lock; and

a reader need not acquire the mutual exclusion lock in order to join the C-SNZI structure if the C-SNZI structure is not disabled.

7. The method of claim 5, further comprising:

when a final reader of the multiple readers leaves the C-SNZI structure, releasing the lockword if the queue is not empty.

8. The method of claim 5, wherein the C-SNZI structure comprises:

a plurality of non-root nodes; and

a root node, said root node comprising;

a first counter configured to indicate whether more readers have arrived at the C-SNZI structure than have departed;

a first flag configurable to indicate that a writer is waiting to acquire the lock; and

a second flag configurable to indicate that a writer has acquired the lock.

9. The method of claim 8, wherein said root node further comprises a third flag configurable to indicate that the queue is not empty.

10. The method of claim 8, wherein said root node further comprises a second counter configured to track a number of readers that have joined the C-SNZI structure without invoking an arrive operation on a node of the C-SNZI structure.

11. The method of claim 10, wherein:

one or more non-root nodes offer;

an arrive operation invocable by a reader to join the C-SNZI structure; and

a depart operation invocable by a reader to leave the C-SNZI structure, wherein the depart operation is invoked by readers that previously invoked the arrive operation; and

a given reader joins the C-SNZI structure by

invoking the arrive operation on a non-root node in the presence of contention;

or

incrementing the second counter in the absence of contention.

12. The method of claim 1, further comprising:

determining whether only a single reader is joined to the C-SNZI structure; and

if only a single reader is joined to the C-SNZI structure, upgrading the single reader to a writer.

13. The method of claim 1, wherein:

the reader-writer lock comprises a queue;

the C-SNZI structure is included in each reader entry in the queue; and

the multiple readers have joined a first reader entry.

14. The method of claim 13, wherein the C-SNZI structure comprises:

a plurality of non-root nodes, wherein one or more of the non-root nodes offer;

an arrive operation invocable by a reader to join the C-SNZI structure; and

a depart operation invocable by a reader to leave the C-SNZI structure, wherein the depart operation is invoked by readers that previously invoked the arrive operation; and

a root node, said root node comprising;

a first counter configured to indicate whether more readers have invoked the arrive operation at the one or more non-root nodes of the C-SNZI structure than have invoked the depart operation;

a first flag configurable to indicate that a writer is waiting to acquire the lock; and

a second flag configurable to indicate that a writer has acquired the lock.

15. The method of claim 13, wherein an additional reader may join the multiple readers that have joined the C-SNZI structure of the first reader entry only while the first reader entry is at the tail of the queue.

16. The method of claim 13, wherein an additional reader may join the multiple readers that have joined the C-SNZI structure of the first reader entry, unless:

the first reader entry is at the head of the queue; and

a writer entry is enqueued.

17. The method of claim 13, further comprising:

configuring a pointer to identify a reader entry in the queue that an additional reader may join.

18. A computer-readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of facilitating acquisition of a reader-writer lock by multiple readers, the method comprising:

constructing a hierarchical C-SNZI (Conditioned Scalable Non-Zero Indicator) structure within the lock;

joining multiple readers to the C-SNZI structure, wherein the multiple readers share acquisition of the lock while joined to the C-SNZI structure; and

updating a surplus configured to remain greater than zero as long as at least one of the multiple readers is joined to the C-SNZI structure.

19. A computing device, comprising:

a resource that is readable by read requesters and writable by write requesters; and

a lock configured to arbitrate access to the resource by the read requesters and the write requesters, the lock including a conditioned scalable non-zero indicator (C-SNZI) object comprising a root node and a set of non-root nodes, wherein one or more of the non-root nodes comprise;

arrive logic configured to join one or more read requesters to the C-SNZI object; and

depart logic configured to sever a joined read requester from the C-SNZI object;

wherein read requesters joined to the C-SNZI object share acquisition of the lock;

wherein multiple read requesters invoke said arrive logic of different non-root nodes to join the C-SNZI object without contention.

20. The computing device of claim 19, wherein said root node of the C-SNZI object comprises:

a first counter configured to indicate whether more read requesters have invoked the arrive operation at the one or more non-root nodes of the C-SNZI object than have invoked the depart operation;

a first flag configurable to indicate that a write requester is waiting to acquire the lock; and

a second flag configurable to indicate that a write requester has acquired the lock.