Fair scalable reader-writer mutual exclusion

• US 7,730,491 B2
• Filed: 08/30/2005
• Issued: 06/01/2010
• Est. Priority Date: 08/30/2005
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Robison, Arch, Kukanov, Alexey
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): Lee; Adam
• Application Number:
  US11/215,863
• Publication Number:
  US 20070067774A1
• Time in Patent Office: 1,736 Days
• Field of Search: 718104-108, 712/229
• 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;

exiting the critical section by the first thread;

removing the first queue node from the queue; and

preventing an attempt to reference a second queue node by the first thread when the second queue node is already deleted by a second 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 a thread releases a spin lock acquired by another thread.

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;

exiting the critical section by the first thread;

removing the first queue node from the queue; and

preventing an attempt to reference a second queue node by the first thread when the second queue node is already deleted by a second 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 a thread releases a spin lock acquired by another thread.

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 for controlling access to a critical section of memory coupled to a processor in a multithreaded processing system comprising:

a plurality of processing threads executing on the processor, each thread having a stack; and

a single word reader writer mutex pointing to a queue representing a list of threads desiring access to the critical section;

wherein a first thread of the plurality of threads creates 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;

adds 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;

waits 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;

enters the critical section when the condition is met;

exits the critical section;

removes the first queue node from the queue; and

prevents an attempt to reference a second queue node by the first thread when the second queue node is already deleted by a second thread.

16. The system of claim 15, wherein a thread that is a reader never blocks another thread that is a reader.

17. The system of claim 15, wherein a thread releases a spin lock acquired by another thread.

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

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

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