Conditional variables without spinlocks

• US 7,770,172 B2
• Filed: 09/01/2004
• Issued: 08/03/2010
• Est. Priority Date: 09/01/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Clift, Neill Michael
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): ARCOS, CAROLINE H
• Application Number:
  US10/932,475
• Publication Number:
  US 20060048149A1
• Time in Patent Office: 2,162 Days
• Field of Search: 718/101, 718/102, 718/104, 718/107, 718/100, 709/225, 709/226
• US Class Current: 718/104
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

The use of spinlocks is avoided in the combination of mutex and condition variables by using any suitable atomic compare and swap functionality to add a thread to a list of waiting threads that waits for a data event to occur. Various embodiments of the present invention also provide an organization scheme of data, which describes an access bit, an awaken count, and a pointer to the list of waiting threads. This organization scheme of data helps to optimize the list of waiting threads so as to better awaken a waiting thread or all waiting threads at once.

Claims

1. A computer system comprising:

a processor;

a memory electronically coupled to the processor;

a shared resource on the computer system protected by a mutex to regulate access to the shared resource (the mutex of the shared resource);

multiple threads of execution that are each capable of concurrently and asynchronously accessing the shared resource to read or write data, wherein each of the multiple threads of execution are queued in a linked list of waiting threads to access the shared resource;

a lock-free condition variable that causes each of the multiple threads of execution to wait until an event associated with the lock-free condition variable has occurred, the causing of each thread to wait occurring without locking the lock-free condition variable;

an access bit that controls access to waiting threads;

an awaken count that is a tally of a number of waiting threads; and

a pointer to the linked list of waiting threads, wherein the pointer points to a head of the linked list of waiting threads, wherein the pointer is swapped within a wait function to point to a newly inserted thread in the linked list of waiting threads, and wherein the mutex of the shared resource is released such that the shared resource is freed for access by another thread within the wait function by freeing the mutex of the shared resource before any other thread is allowed to access the shared resource, the pointer being swapped and the mutex of the shared resource being released and freed in a single indivisible set of operations of the wait function.

2. The computer system of claim 1, wherein the shared resource includes a software resource or hardware resource.

3. The computer system of claim 1, wherein the multiple threads of execution are threads of one process.

4. The computer system of claim 1, wherein the multiple threads of execution are threads of multiple processes.

5. A computer-readable storage medium having a data structure and instructions stored thereon for use by a computing system, when executed by a computer, cause the computer to manage a linked list of waiting threads, the data structure comprising:

a pointer that points to a head of the linked list of waiting threads, wherein a waiting thread is a thread in a wait state;

an awaken count that is indicative of a count of waiting threads; and

an access bit that is indicative of whether the linked list of waiting threads is being accessed by a currently processing thread to awaken another thread in response to an occurrence of a data event connected with a lock-free condition variable;

wherein the instructions direct the computing system to perform operations comprising;

acquiring and locking, by the currently processing thread, a mutex associated with a shared resource;

checking a state of the shared resource;

swapping a waiting thread, in the linked list in a single indivisible operation without the use of any lock associated with the data structure, to point the waiting thread to a newly inserted thread in the linked list of waiting threads; and

releasing the shared resource by unlocking the mutex associated with the shared resource.

6. The computer-readable storage medium of claim 5, wherein the awaken count has a maximum value, wherein when the awaken count is greater than the maximum value of all waiting threads in the linked list of waiting threads, all waiting threads are awakened.

7. The computer-readable storage medium of claim 5, wherein a thread at the head of the linked list of waiting threads points to an oldest waiting thread in the linked list of waiting thread so as to awaken the oldest thread, and wherein the shared resource is released before any other thread is allowed to access the lock-free condition variable associated with the shared resource.

8. The computer-readable storage medium of claim 5, wherein the access bit is not set to insert a thread into a linked list of waiting threads when the thread is the only member of the linked list of waiting threads.

9. The computer-readable storage medium of claim 5, wherein the acts further comprise, after releasing the shared resource, sleeping the newly inserted thread.

10. The computer-readable storage medium of claim 5, wherein the acts are performed within an uninterruptible wait function.

11. A method implemented in a computer, the method comprising:

pointing at a particular thread at a head of a linked list of waiting threads, wherein a waiting thread is a thread in a wait state;

invoking, a signal function to awaken the particular thread; and

invoking, a wait function to cause the particular thread to wait until an event has occurred that is connected with a lock-free condition variable, the wait function, in a single indivisible operation, performing acts comprising;

acquiring and locking a mutex associated with a shared resource and associated with the lock-free condition variable, the mutex providing mutual exclusion to the shared resource;

checking a state of the shared resource;

unlocking the mutex associated with the shared resource; and

causing the particular thread to wait for access to the shared resource associated with the lock-free condition variable without locking the condition variable, wherein the shared resource is concurrently and asynchronously accessible by more than one thread to read or write data.

12. The method of claim 11 wherein arguments to the wait function comprise a lock-free condition variable and a mutex.

13. The method of claim 11, further setting an access bit to indicate that the linked list of waiting threads is being accessed to awaken a thread or to optimize the linked list of waiting threads.

14. The method of claim 11, further incrementing an awaken count to indicate that one or more waiting threads are to be awakened, all waiting threads in the linked list of waiting threads being awakened when the awaken count reaches a maximum allowed value.

15. The method of claim 11, wherein the particular thread at the head of the linked list of waiting threads is an oldest waiting thread of the linked list of waiting threads.

16. A computer-readable storage medium having executable instructions stored thereon that, when executed by a computer, cause the computer to perform operations comprising:

pointing at a head of a linked list of waiting threads, wherein a waiting thread is a thread in a wait state;

invoking a signal function to awaken the waiting thread; and

invoking a wait function by a thread to cause the thread to wait until an event has occurred that is connected with a lock-free condition variable, the wait function, in a single indivisible operation, performing acts comprising;

acquiring and locking a mutex associated with a shared resource and associated with the lock-free condition variable, the mutex providing mutual exclusion to the shared resource;

checking a state of the shared resource;

unlocking the mutex associated with the lock-free condition variable; and

causing the thread to wait for access to the shared resource associated with the lock-free condition variable without locking the condition variable, wherein the shared resource is concurrently and asynchronously accessible by more than one thread to read or write data.

17. The computer-readable storage medium of claim 16, wherein arguments to the wait function comprise the lock-free condition variable and the mutex and wherein the thread is inserted at the head of a linked list of waiting threads through the use of an atomic compare and swap operation which obviates the need for any looping to obtain a lock on the lock-free condition variable.

18. The computer-readable storage medium of claim 16, further comprising setting an access bit to indicate that the linked list of waiting threads is being accessed to awaken a thread or to optimize the linked list of waiting threads.

19. The computer-readable storage medium of claim 16, further comprising incrementing an awaken count to indicate that one or more threads are to be awakened, all threads in the linked list of waiting threads being awakened when the awaken count reaches a maximum allowed value.

20. The computer-readable storage medium of claim 16, wherein the head of the linked list of the linked list of waiting threads is an oldest waiting thread of the linked list of waiting threads.