Conditional variables without spinlocks
First Claim
Patent Images
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4)
-
-
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. - View Dependent Claims (6, 7, 8, 9, 10)
-
-
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. - View Dependent Claims (12, 13, 14, 15)
-
-
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. - View Dependent Claims (17, 18, 19, 20)
-
Specification