Conditional wait overhead

Question

When using boost::conditional_variable, ACE_Conditional or directly pthread_cond_wait, is there any overhead for the waiting itself? These are more specific issues that trouble be:

1. After the waiting thread is unscheduled, will it be scheduled back before the wait expires and then unscheduled again or it will stay unscheduled until signaled?
2. Does wait acquires periodically the mutex? In this case, I guess it wastes each iteration some CPU time on system calls to lock and release the mutex. Is it the same as constantly acquiring and releasing a mutex?
3. Also, then, how much time passes between the signal and the return from wait?

Afaik, when using semaphores the acquire calls responsiveness is dependent on scheduler time slice size. How does it work in pthread_cond_wait? I assume this is platform dependent. I am more interested in Linux but if someone knows how it works on other platforms, it will help too.

And one more question: are there any additional system resources allocated for each conditional? I won't create 30000 mutexes in my code, but should I worry about 30000 conditionals that use the same one mutex?

Answer 1

You should only call pthread_cond_wait if the variable is already in the "wrong" state. Since it always waits, there is always the overhead associated with putting the current thread to sleep and switching.

When the thread is unscheduled, it is unscheduled. It should not use any resources, but of course an OS can in theory be implemented badly. It is allowed to re-acquire the mutex, and even to return, before the signal (which is why you must double-check the condition), but the OS will be implemented so this doesn't impact performance much, if it happens at all. It doesn't happen spontaneously, but rather in response to another, possibly-unrelated signal.

30000 mutexes shouldn't be a problem, but some OSes might have a problem with 30000 sleeping threads.

Answer 2

Here's what is written in the pthread_cond man page:

pthread_cond_wait atomically unlocks the mutex and waits for the condition variable cond to be signaled. The thread execution is suspended and does not consume any CPU time until the condition variable is signaled.

So from here I'd answer to the questions as following:

1. The waiting thread won't be scheduled back before the wait was signaled or canceled.
2. There are no periodic mutex acquisitions. The mutex is reacquired only once before wait returns.
3. The time that passes between the signal and the wait return is similar to that of thread scheduling due to mutex release.

Regarding the resources, on the same man page:

In the LinuxThreads implementation, no resources are associated with condition variables, thus pthread_cond_destroy actually does nothing except checking that the condition has no waiting threads.

Update: I dug into the sources of pthread_cond_* functions and the behavior is as follows:

1. All the pthread conditionals in Linux are implemented using futex.
2. When a thread calls wait it is suspended and unscheduled. The thread id is inserted at the tail of a list of waiting threads.
3. When a thread calls signal the thread at the head of the list is scheduled back. So, the waking is as efficient as the scheduler, no OS resources are consumed and the only memory overhead is the size of the waiting list (see futex_wake function).