On Wed, 18 Nov 2009 22:48:06 +0100
Jean-Yves Migeon <jeanyves.migeon%free.fr@localhost> wrote:
raymond.meyer%rambler.ru@localhost wrote:
> The problem here is when all 256 threads wake up at the same time,
> they will all try to lock the same mutex, creating a lot of
> contention. Because the data is partitioned into 256 parallel
> regions, each thread works on a different data set, hence no need
> for mutual exclusion.
From what I understand, it is the traditional worker thread model
from Butenhof, which is based on what you say, except that the
processed data is shared between threads (not your case).
You could split up the thing in 1/2, 1/3, 1/4... with multiple
conditional variables, so that you reduce by an order of magnitude
the contention on the different mutexes, without relying to the "one
condvar per thread" model (actually, that is two, one to signal that
there is data to process, and one to signal that the processing just
finished).
IMHO, the "one condvar model to wake them all" is too much of a
bottleneck, as when one of the region is filled, the associated
thread is waiting for the 255 other regions to be filled (right when
you will issue the broadcast).
> When
> a thread wakes up, it immediately calls pthread_mutex_unlock, which
> seems to be redundant, but necessary to allow other threads to
> continue.
No, it is necessary as the mutex protects a shared state, like a work
queue. If the mutex_cond_wait returned with the mutex unlocked, there
could be two threads working on the same queue at a time, generously
poping/pushing items in it without locking, which is bad.
> The alternative is to have each thread sleep on its own private
> condition variable and mutex. This would require calling
> 'pthread_cond_signal' for each thread, that is 256 time in total.
>
> So is there a way to design a function similar to
> pthread_cond_broadcast, that doesn't cause each thread to lock the
> same mutex when it wakes up?
You mean a function to wake up different sleeping threads without
relying to mutex protection? Seems hard, especially when you have to
handle spurious wakeups.
No, not really. What I mean is this:
Currently Posix 'pthread_cond_wait' is defined as:
int pthread_cond_wait(
pthread_cond_t *cond, pthread_mutex_t *mutex);
I think it would be better to redesign this function as:
int pthread_cond_wait(
pthread_cond_t *cond, pthread_mutex_t *mutex, int lock_mutex);
When you call this function and pass 'lock_mutex' set to 1, then it
behaves just like a currently implemented Posix function, i.e. when the
thread wakes up, the mutex will be automatically locked.
However when you pass 'lock_mutex' set to 0, then when the thread wakes
up, the mutex will be UNLOCKED. The rationale for this is to avoid the
'thundering herd' problem and to wake up as many threads in parallel as
possible. If you have 256 threads sleeping, and your algorithms and
data structures are designed in such a way that threads don't modify
shared data when woken up, then it would be much better to broadcast
condition and have 256 threads wake up WITHOUT blocking on the same
mutex in user space. The kernel would still probably have to lock the
mutex when moving threads from sleep queue to run queue etc, but at
least this would avoid unnecessary context switching in user space.