A condition variable is a programming construct for communicating information about the state of shared data. A condition variable is itself shared data and therefore must be protected with a mutex.

Imagine a shared queue. The code for removing things from the queue will look something like this :

   Acquire(Mutex);
   while (QueueEmpty()) Wait();
   item = GetItem();
   Release(Mutex);
   return item;
Without a condition variable, the Wait() routine above would have to be something like
   Release(Mutex);
   sleep();
   Acquire(Mutex);
There are other options than sleep(); for example, on multiprocessor systems you can count to a million in a tight loop, this is called a spin lock or busy wait, and wastes a lot of CPU time, but can make very short waits possible. In any event, you have to somehow wait around and hope someone has put something in the queue. This is quite inefficient because you have to decide ahead of time how long you're going to wait. If you wait too long, you've wasted time. If you wait too short, you just have to wait again and have wasted CPU.

With a condition variable, the Wait() call becomes CondWait(Mutex, Condition), and, very importantly, somewhere else, some other thread must do this :

   Acquire(Mutex);
   AddToQueue();
   Notify(Condition)
   Release(Mutex)
CondWait thus releases the mutex, waits for a notification, and then gets the mutex back and continues. The benefit here is that the implementation of condition variables uses tricky OS-specific things to pass signals around so that the CondWait calls uses very little CPU and can wait exactly the right amount of time.

The downside is the the programmer has to take extra care to make sure that Notify's are done at the appropriate time, otherwise your CondWait may wait forever. There are two kinds of Notify: one that wakes up a single, randomly chosen, waiting thread, and another, broadcast, that wakes up all waiting threads. Broadcast is less efficient, but allows the programmer to be more lazy.

Condition variables are also used to create higher level threading control structues, such as read/write locks.

In POSIX threads, also called pthreads, CondWait, Signal and Broadcast are spelled pthread_cond_wait, pthread_cond_signal and pthread_cond_broadcast respectively.

See Programming with POSIX threads by David Butenhof for more detail.