Fair scalable reader-writer mutual exclusion

• US 8,707,324 B2
• Filed: 02/27/2012
• Issued: 04/22/2014
• Est. Priority Date: 08/30/2005
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Kukanov, Alexey, Robison, Arch D.
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): Lee, Adam
• Application Number:
  US13/405,772
• Publication Number:
  US 20120198471A1
• Time in Patent Office: 785 Days
• Field of Search: None
• US Class Current: 718/108
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Implementing fair scalable reader writer mutual exclusion for access to a critical section by a plurality of processing threads is accomplished by creating a first queue node for a first thread, the first queue node representing a request by the first thread to access the critical section; setting at least one pointer within a queue to point to the first queue node, the queue representing at least one thread desiring access to the critical section; waiting until a condition is met, the condition comprising the first queue node having no preceding write requests as indicated by at least one predecessor queue node on the queue; permitting the first thread to enter the critical section in response to the condition being met; and causing the first thread to release a spin lock, the spin lock acquired by a second thread of the plurality of processing threads.

Claims

1. A computer-implemented method of implementing fair scalable reader writer mutual exclusion for access to a critical section comprising:

creating a first queue node for a first thread of a plurality of processing threads executing on a processor, the first queue node representing a request by the first thread to access the critical section;

setting at least one pointer within a queue to point to the first queue node, the queue representing at least one thread desiring access to the critical section, the first queue node being added to a tail of the queue;

waiting until a condition is met, the condition comprising the first queue node having no preceding write requests as indicated by at least one predecessor queue node on the queue;

permitting the first thread to enter the critical section in response to the condition being met;

causing the first thread to release a spin lock, the spin lock acquired by a second thread of the plurality of processing threads, wherein each queue node in the queue is one of a reader queue node or a writer queue node; and

if the first thread is a reader thread, examining the tail of the queue by the reader thread in response to the reader thread wanting to acquire a lock on a reader writer mutex for the critical section;

if the tail of the queue points to a writer queue node;

setting a spin lock for the first queue node to true; and

changing a qNext pointer of a predecessor queue node in the queue to point to the first queue node.

2. The method of claim 1, wherein a thread that is a reader never blocks another thread that is a reader.

3. The method of claim 1, further comprising preventing an attempt to reference a second queue node by the first thread when the second queue node is already deleted by a third thread of the plurality of processing threads.

4. The method of claim 1, wherein after a reader thread partially links a queue node into the queue while its predecessor thread is trying to acquire a lock on a reader writer mutex for the critical section, the reader thread causes the predecessor thread to wait until the reader thread completes linking the queue node in to the queue.

5. The method of claim 1, wherein each queue node comprises one of a plurality of wait states, and one of the wait states comprises a Busy state, indicating that a queue node cannot be deleted yet.

6. The method of claim 1, wherein each queue node comprises one of a plurality of node states, and notification of node states between threads is accomplished by atomic operations.

7. The method of claim 6, wherein one of the node states comprises an UnblockNext state, the UnblockNext state allowing a successor thread to signal that the successor thread has only partially linked the successor thread'"'"'s queue node.

8. The method of claim 1, wherein setting at least one pointer within the queue to point to the first queue node comprises using CompareandSwap to change the tail of the queue from a null pointer to point to the first queue node.

9. The method of claim 1, further comprising:

if the tail of the queue points to a reader queue node;

waiting by the reader thread for a spin lock for the reader queue node to be released; and

when the spin lock for the reader queue node is released, causing the reader thread to enter the critical section.

10. An article comprising:

a machine accessible non-transitory storage medium containing instructions, which when executed, result implementing fair scalable reader writer mutual exclusion for access to a critical section by;

creating a first queue node for a first thread of a plurality of processing threads executing on a processor, the first queue node representing a request by the first thread to access the critical section;

setting at least one pointer within a queue to point to the first queue node, the queue representing at least one thread desiring access to the critical section, the first queue node being added to a tail of the queue;

waiting until a condition is met, the condition comprising the first queue node having no preceding write requests as indicated by at least one predecessor queue node on the queue;

permitting the first thread to enter the critical section in response to the condition being met;

causing the first thread to release a spin lock, the spin lock acquired by a second thread of the plurality of processing threads, wherein each queue node in the queue is one of a reader queue node or a writer queue node; and

if the first thread is a reader thread, examining the tail of the queue by the reader thread in response to the reader thread wanting to acquire a lock on a reader writer mutex for the critical section;

if the tail of the queue points to a writer queue node;

setting a spin lock for the first queue node to true; and

changing a qNext pointer of a predecessor queue node in the queue to point to the first queue node.

11. The article of claim 10, wherein a thread that is a reader never blocks another thread that is a reader.

12. The article of claim 10, further comprising preventing an attempt to reference a second queue node by the first thread when the second queue node is already deleted by a third thread of the plurality of processing threads.

13. The article of claim 10, wherein after a reader thread partially links a queue no de into the queue while its predecessor thread is trying to acquire a lock on a reader writer mutex for the critical section, the reader thread causes the predecessor thread to wait until the reader thread completes linking the queue node into the queue.

14. The article of claim 10, wherein each queue node comprises one of a plurality of wait states, and one of the wait states comprises a Busy state, indicating that a queue node cannot be deleted yet.

15. The article of claim 10, wherein each queue node comprises one of a plurality of node states, and notification of node states between threads is accomplished by atomic operations.

16. The article of claim 15, wherein one of the node states comprises an UnblockNext state, the UnblockNext state all owing a successor thread to signal that the successor thread has only partially linked the successor thread'"'"'s queue node.

17. The article of claim 10, wherein setting at least one pointer within the queue to point to the first queue node comprises using CompareandSwap to change the tail of the queue from a null pointer to point to the first queue node.

18. The article of claim 10, wherein the instructions, which when executed, result in implementing fair scalable reader writer mutual exclusion for access to a critical section further by:

if the tail of the queue points to a reader queue node;

waiting by the reader thread for a spin lock for the reader queue node to be released; and

when the spin lock for the reader queue node is released, causing the reader thread to enter the critical section.

19. A computer system comprising:

a processor to execute a plurality of processing threads; and

a memory coupled to the processor, the memory to store a single word reader writer mutex to point to a queue representing at least one thread desiring access to a critical section;

wherein the processor is further configured to;

create a first queue node in a first region of the memory, the first queue node representing a request by the first thread to access the critical section;

set at least one pointer within the queue to point to the first queue node, the first queue node being added to a tail of the queue;

wait until a condition is met, the condition comprising the first queue node having no preceding write requests as indicated by at least one predecessor queue node on the queue;

permit the first thread to enter the critical section in response to the condition being met; and

cause the first thread to release a spin lock acquired by a second thread of the plurality of processing threads, wherein each queue node in the queue is one of a reader queue node or a writer queue node; and

if the first thread is a reader thread, examine the tail of the queue by the reader thread in response to the reader thread wanting to acquire a lock on a reader writer mutex for the critical section;

if the tail of the queue points to a writer queue node;

set a spin lock for the first queue node to true; and

change a qNext pointer of a predecessor queue node in the queue to point to the first queue node.

20. The system of claim 19, wherein the processor is further configured such that a thread that is a reader never blocks another thread that is a reader.

21. The system of claim 19, wherein the processor is further configured to prevent an attempt to reference a second queue node by the first thread when the second queue node is already deleted by a third thread of the plurality of processing threads.

22. The system of claim 19, wherein the processor is further configured such that after a reader thread partially links a queue node into the queue while its predecessor thread is trying to acquire a lock on the single word reader writer mutex, the reader thread causes the predecessor thread to wait until the reader thread completes linking the queue node into the queue.

23. The system of claim 19, wherein the processor is further configured such that each queue node comprises one of a plurality of wait states, and one of the wait states comprises a Busy state, indicating that a queue node cannot be deleted yet.

24. The system of claim 19, wherein the processor is further configured such that each queue node comprises one of a plurality of node states, and notification of node states between threads is accomplished by atomic operations.

25. The system of claim 24, wherein the processor is further configured such that one of the node states comprises an UnblockNext state, the UnblockNext state allowing a successor thread to signal that the successor thread has only partially linked the successor thread'"'"'s queue node.

26. The system of claim 19, wherein setting at least one pointer within the queue to point to the first queue node comprises using CompareandSwap to change the tail of the queue from a null pointer to point to the first queue node.

27. The system of claim 19, wherein the processor is further configured to:

if the tail of the queue points to a reader queue node;

wait by the reader thread for a spin lock for the reader queue node to be released; and

when the spin lock for the reader queue node is released, cause the reader thread to enter the critical section.