Program concurrency control using condition variables

• US 8,578,380 B1
• Filed: 08/27/2004
• Issued: 11/05/2013
• Est. Priority Date: 12/17/2003
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Adams, Keith M., Agesen, Ole
• Primary Examiner(s): ZHE, MENG YAO
• Application Number:
  US10/929,045
• Time in Patent Office: 3,357 Days
• Field of Search: 178/100, 718/100
• US Class Current: 718/100
• CPC Class Codes: G06F 2209/521 Atomic
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A condition variable for controlling access to a critical section of computer code by a plurality of concurrently running execution threads comprises a data structure with a head list linking threads in an arrival order and a tail list linking threads in a reverse arrival order. Together, the head and tail lists together indicate which threads are currently blocked on the condition variable. A wait counter indicates how many threads are currently linked in the data structure and a signal counter indicates how many times the condition variable has been signaled for waiting threads that are currently linked in the data structure. The head and tail pointers, as well as the wait and signal counters, may be implemented as fields of a single, atomically updatable data word.

Claims

1. In a computer system that has at least one processor with at least one atomic instruction for atomically changing the contents of a data word, and a plurality of threads of execution running concurrently on the processor(s), a condition variable comprising:

computer-executable code for synchronizing the threads;

a head list and a tail list together indicating which threads, if any, are currently blocked on the condition variable,

wherein the head list links threads in arrival order and the tail list links threads in reverse arrival order, the head list and the tail list together indicating an arrival order for any currently blocked threads; and

a data structure comprising;

a head pointer to a first blocked thread in the head list, if any;

a tail pointer to the last blocked thread in the tail list, if any;

a wait counter indicating how many threads are currently linked in the data structure; and

a signal counter indicating how many times the condition variable has been signaled for waiting threads that are currently linked in the data structure,

wherein the head pointer, the tail pointer, the wait counter and the signal counter all comprise portions of a single data word that can be atomically updated using a single atomic instruction, the data word comprising a unit of data bits addressable by read-modify-write primitives, the data bits being partitioned into four groups of data bits, a first group constituting the head pointer, a second group constituting the tail pointer, a third group constituting the wait counter and the fourth group constituting the signal counter,

wherein when a wait function is invoked for a first thread, the first thread is linked into the data structure and the wait counter is incremented, both in a single atomic operation using a single atomic instruction, and

wherein when a second thread is to be dequeued, the second thread is removed from the data structure, the wait counter is decremented and the signal counter is decremented, all three in a single atomic operation using a single atomic instruction.

2. A condition variable as in claim 1, in which the data structure is lock-free.

3. A condition variable as in claim 1, in which the head and tail lists are each singly linked.

4. The condition variable of claim 1, where a semaphore is associated with each thread, the condition variable further comprising computer-executable code:

for incrementing the wait counter each time a new thread is added to the data structure;

for incrementing the signal counter when the condition variable is not saturated and is signaled and for decrementing the signal counter when a listed thread leaves the data structure; and

for indicating to the semaphore of the first linked thread in the head list that the first linked thread has become releasable and may proceed to run only when the number of threads having signaled the condition variable changes from zero to one.

5. The condition variable of claim 4, further comprising computer-executable code:

for linking the threads in the tail list in arrival order to the head list when there is only one thread in the head list and that one thread is to be removed from the head list;

for removing a current thread from the data structure and decrementing both the wait and signal counters; and

for performing a cascading wake-up of other releasable threads in the data structure.

6. In a computer system that has at least one processor with at least one atomic instruction for atomically changing the contents of a data word, and a plurality of threads of execution running concurrently on the processor(s), a semaphore being associated with each thread, a condition variable comprising:

computer-executable code for synchronizing the threads;

a head list and a tail list each being singly linked and together indicating which threads, if any, are currently blocked on the condition variable,

wherein, the head list links threads in an arrival order and the tail list links threads in a reverse arrival order, the head list and the tail list together indicating an arrival order for any currently blocked threads; and

a lock-free data structure comprising;

a head pointer to a first blocked thread in the head list, if any;

a tail pointer to the last blocked thread in the tail list, if any;

a wait counter indicating how many threads are currently linked in the data structure; and

a signal counter indicating how many times the condition variable has been signaled for waiting threads that are currently linked in the data structure,

wherein the head pointer, the tail pointer, the wait counter and the signal counter all comprise portions of a single data word that can be atomically updated using a single atomic instruction, the data word comprising a unit of data bits addressable by read-modify-write primitives, the data bits being partitioned into four groups of data bits, a first group constituting the head pointer, a second group constituting the tail pointer, a third group constituting the wait counter and the fourth group constituting the signal counter,

wherein when a wait function is invoked for a first thread, the first thread is linked into the data structure and the wait counter is incremented, both in a single atomic operation using a single atomic instruction, and

wherein when a second thread is to be dequeued, the second thread is removed from the data structure, the wait counter is decremented and the signal counter is decremented, all three in a single atomic operation using a single atomic instruction, the computer-executable code including code for;

incrementing the wait counter each time a new thread is added to the data structure;

incrementing the signal counter when the condition variable is not saturated and is signaled and decrementing the signal counter when a listed thread leaves the data structure;

indicating to the semaphore of the first linked thread in the head list that the first linked thread has become releasable and may proceed to run only when the number of threads having signaled the condition variable changes from zero to one;

linking the threads in the tail list in arrival order to the head list when there is only one thread in the head list and that one thread is to be removed from the head list;

removing a current thread from the data structure and decrementing both the wait and signal counters; and

performing a cascading wake-up of other releasable threads in the data structure.