Fair scalable reader-writer mutual exclusion

• US 20070067774A1
• Filed: 08/30/2005
• Published: 03/22/2007
• Est. Priority Date: 08/30/2005
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Robison, Arch, Kukanov, Alexey
• Granted Patent: US 7,730,491 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• 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 method of implementing fair scalable reader writer mutual

exclusion for access to a critical section by a plurality of processing

threads in a processing system comprising:

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.

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 second thread.

4. The method of claim 1, further comprising deleting the first queue node from the first thread'"'"'s stack.

5. The method of claim 1, wherein a thread releases a spin lock acquired by another thread.

6. 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.

7. 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.

8. 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.

9. The method of claim 8, 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.

10. An article comprising:

a machine accessible medium containing instructions, which when executed, result in implementing fair scalable reader writer mutual exclusion for access to a critical section by a plurality of processing threads in a processing system 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.

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 instructions for 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.

13. The article of claim 10, further comprising instructions for deleting the first queue node from the first thread'"'"'s stack.

14. The article of claim 10, wherein a thread releases a spin lock acquired by another thread.

15. The article of claim 10, 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.

16. 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.

17. 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.

18. The article of claim 17, 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.

19. A system for controlling access to a critical section of memory in a multithreaded processing system comprising:

a plurality of processing threads, 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 on the first thread'"'"'s stack, the queue node representing a request by the first thread to access the critical section;

adds the first queue node to the queue;

waits until the first queue node has no preceding write requests as indicated by predecessor queue nodes on the queue;

enters the critical section;

exits the critical section; and

removes the first queue node from the queue.

20. The system of claim 19, wherein a thread that is a reader never blocks another thread that is a reader.

21. The system of claim 19, wherein the system 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.

22. The system of claim 19, wherein the first thread deletes the first queue node from the first thread'"'"'s stack.

23. The system of claim 19, wherein a thread releases a spin lock acquired by another thread.

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

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

26. The system of claim 19, wherein each queue node comprises one of a plurality of node states, and notification of node states between threads is accomplished by atomic operations.

27. The system of claim 26, 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.