Fair scalable reader-writer mutual exclusion

• US 8,127,303 B2
• Filed: 05/18/2010
• Issued: 02/28/2012
• Est. Priority Date: 08/30/2005
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Kukanov, Alexey, Robison, Arch
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): Lee, Adam
• Application Number:
  US12/782,394
• Publication Number:
  US 20100293553A1
• Time in Patent Office: 651 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 in a processing system is accomplished by creating a first queue node for a first thread on the first thread'"'"'s stack, the queue node representing a request by the first thread to access the critical section; adding the first queue node to a queue pointed to by a single word reader writer mutex for the critical section, the queue representing a list of threads desiring access to the critical section, each queue node in the queue being on a stack of a thread of the plurality of processing threads; waiting until the first queue node has no preceding write requests as indicated by predecessor queue nodes on the queue; entering the critical section by the first thread; exiting the critical section by the first thread; and removing the first queue node from the queue.

Claims

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

creating a first queue node for a first thread of a plurality of processing threads executing on the processor, wherein the first queue node is created in a first region of the memory allocated for a stack of the first thread, the first queue node representing a request by the first thread to access the critical section;

adding the first queue node to a queue pointed to by a single word reader writer mutex for the critical section by setting pointers within the queue to point to the first queue node, the queue representing a list of threads desiring access to the critical section, each queue node in the queue being in a region of the memory allocated for a stack of a thread of the plurality of processing threads, the first queue node being added to a tail of the queue;

waiting until a condition is met, the condition being that the first queue node has no preceding write requests as indicated by predecessor queue nodes on the queue;

entering the critical section by the first thread when the condition is met;

releasing a spin lock by the first thread, the spin lock acquired by a second thread of the plurality of processing threads; and

exiting the critical section by the first thread.

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, wherein the first thread prevents 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 the reader writer mutex, the reader thread causes the predecessor thread to wait until the reader thread completes linking the queue node into 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. An article comprising:

a machine accessible non-transitory storage medium containing instructions, which when executed, result in implementing fair scalable reader writer mutual exclusion for access to a critical section of a memory coupled to a processor by a plurality of processing threads executing on the processor by

creating a first queue node for a first thread of the plurality of processing threads, wherein the first queue node is created in a first region of the memory allocated for a stack of the first thread, the first queue node representing a request by the first thread to access the critical section;

adding the first queue node to a queue pointed to by a single word reader writer mutex for the critical section by setting pointers within the queue to point to the first queue node, the queue representing a list of threads desiring access to the critical section, each queue node in the queue being in a region of the memory of the processing system allocated for a stack of a thread of the plurality of processing threads, the first queue node being added to a tail of the queue;

waiting until a condition is met, the condition being that the first queue node has no preceding write requests as indicated by predecessor queue nodes on the queue;

entering the critical section by the first thread when the condition is met;

releasing a spin lock by the first thread, the spin lock acquired by a second thread of the plurality of processing threads; and

exiting the critical section by the first thread.

9. The article of claim 8, wherein a thread that is a reader never blocks another thread that is a reader.

10. The article of claim 8, wherein the first thread prevents 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.

11. The article of claim 8, wherein after a reader thread partially links a queue node into the queue while its predecessor thread is trying to acquire a lock on the reader writer mutex, the reader thread causes the predecessor thread to wait until the reader thread completes linking the queue node into the queue.

12. The article of claim 8, 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.

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

14. The article of claim 13, 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.

15. A computer system comprising:

a processor to execute a plurality of processing threads, each thread having a respective stack; and

a memory coupled to the processor, the memory to store a single word reader writer mutex to point to a queue representing a list of threads desiring access to a critical section of the memory;

wherein the processor is further configured to;

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

add the first queue node to the queue by setting pointers within the queue to point to the first queue node, each queue node in the queue being in a region of the memory allocated for a stack of a thread of the plurality of processing threads, the first queue node being added to a tail of the queue;

wait until a condition is met, the condition being that the first queue node has no preceding write requests as indicated by predecessor queue nodes on the queue;

cause the first thread to enter the critical section when the condition is met;

cause the first thread to release a spin lock acquired by a second thread of the plurality of processing threads; and

cause the first thread to exit the critical section.

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

17. The system of claim 15, 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.

18. The system of claim 15, 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 reader writer mutex, the reader thread causes the predecessor thread to wait until the reader thread completes linking the queue node into the queue.

19. The system of claim 15, 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.

20. The system of claim 15, 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.

21. The system of claim 20, 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.