Conditions/Mutex and speedH
Heinz Häberle
1.0.3 and glibc 2.0
compiled with c++ -lpthread event.c
I wrote this code (only as a test) and found that it first only hav
between 50 und 1600 loops and second
top says about 0.4%cpu per thread. This seems to be not a very good
performance.
If I change the scheduling to realtime it dosn't change very much.
What's the problem?
Kaz Kylheku
wrote:
>This is a multi-part message in MIME format.
>--------------398B8F43800DF622E3C72BA4
>Content-Type: text/plain; charset=us-ascii
>Content-Transfer-Encoding: 7bit
>
>I have Linux on a AMDK6 350 with RedHat 5.2 running. Compiled with egcs
>1.0.3 and glibc 2.0
>compiled with c++ -lpthread event.c
>I wrote this code (only as a test) and found that it first only hav
>between 50 und 1600 loops and second
>top says about 0.4%cpu per thread. This seems to be not a very good
>performance.
[ snip ]
>void *perftask1(void * data)
>{
> while(!ready)
> {
> WaitEventSem(perfev2);
> SignalEventSem(perfev3);
> perfeventcount++;
> }
>}
>
>void *perftask2(void*data)
>{
> while(!ready)
> {
> SignalEventSem(perfev2);
> WaitEventSem(perfev3);
> }
>}
Your ``benchmark'' doesn't use condition variables in a realistic way.
A condition variable ought to be associated with some logical predicate in
your program.
Waiting on the condition variable is executed only if the predicate is false,
and the signalling is only done when the predicate is about to become true.
Note that pthread_cond_wait *always* waits; the short-circuiting that bypasses
the potentially expensive wait is supposed to be performed by an explicit test
in your code, for example:
pthread_mutex_lock(&queue_lock);
while (is_empty(queue))
pthread_cond_wait(&queue_not_empty, &queue_lock);
/* queue is not empty now */
/* take item, process it */
pthread_mutex_unlock(&queue_lock);
>main()
>{
> pthread_t t1,t2;
> perfev2 = CreateEventSem("");
> perfev3 = CreateEventSem("");
An even or semaphore is more than just a condition variable and a monitor.
Such an object typically has a state associated with it, keeping track whether
the object is in a signalled state. A wait operation only delays the process if
the semaphore object is not signalled.
What you have imlpemented is not a semaphore, but an unreliable suspend/resume
mechanism that can't possibly be used to do any meaningful synchronization,
simply because the object doesn't remember that it's signalled and the
wait operation *always* waits.
root
> while (is_empty(queue))
> pthread_cond_wait(&queue_not_empty, &queue_lock);
> /* queue is not empty now */
> /* take item, process it */
> pthread_mutex_unlock(&queue_lock);
>
what's the difference her? Because it's no connection between the queue_not_empty
condition and the queue.
> An even or semaphore is more than just a condition variable and a monitor.
> Such an object typically has a state associated with it, keeping track whether
> the object is in a signalled state. A wait operation only delays the process if
> the semaphore object is not signalled.
>
> What you have imlpemented is not a semaphore, but an unreliable suspend/resume
> mechanism that can't possibly be used to do any meaningful synchronization,
> simply because the object doesn't remember that it's signalled and the
> wait operation *always* waits.
What I really locking for is a EventSemaphore with the chance for a timeout (as it
is in the WindowsNT-API and RTOS-API's.
Kaz Kylheku
<heinz.h...@gmx.net> wrote:
>> pthread_mutex_lock(&queue_lock);
>> while (is_empty(queue))
>> pthread_cond_wait(&queue_not_empty, &queue_lock);
>> /* queue is not empty now */
>> /* take item, process it */
>> pthread_mutex_unlock(&queue_lock);
>>
>
>what's the difference her? Because it's no connection between the queue_not_empty
>condition and the queue.
There is no explicit connection between the queue_lock and the queue either,
yet the lock protects the queue.
The connections are implicit in the way the objects are used.
The wait on queue_not_empty is done only if is_empty() returns false. If there
are items in the queue, the code just falls through to processing them
without waiting.
There is no chance of missing a wakeup, because pthread_cond_wait
atomically gives up the mutex and waits.
The signalling code logic can be like this:
pthread_mutex_lock(&queue_lock);
was_empty = is_empty(queue);
/* add item(s) to queue */
pthread_mutex_unlock(&queue_lock);
if (was_empty)
pthread_cond_signal(&queue_not_empty);
In this manner, the signalling is only done if the queue was taken from
an empty to a non-empty state. And the waiting is only done on an
empty queue. So in many cases, expensive operations are avoided.
>What I really locking for is a EventSemaphore with the chance for a timeout (as it
>is in the WindowsNT-API and RTOS-API's.
A semaphore can be implemented with a mutex that protects a counter, and a
condition variable that is used to wait when the semaphore is not
available. The logic is not unlike that of the queue.
struct sem_t {
int count;
pthread_mutex_t mutex;
pthread_cond_t cond;
};
void sem_down(struct sem_t *sem)
{
pthread_mutex_lock(&sem->mutex);
while (sem->count <= 0)
pthread_cond_wait(&sem->cond, &sem->mutex);
sem->count--;
pthread_mutex_unlock(&sem->mutex);
}
void sem_up(struct sem_t *sem)
{
pthread_mutex_lock(&sem->mutex);
if (sem->count++ == 0)
pthread_cond_signal(&sem->cond);
pthread_mutex_unlock(&sem->mutex);
}
Patrick TJ McPhee
Heinz Häberle <heinz.h...@gmx.net> wrote:
% I wrote this code (only as a test) and found that it first only hav
% between 50 und 1600 loops and second
% top says about 0.4%cpu per thread. This seems to be not a very good
% performance.
Your application is deadlocking. pthread_cond_signal doesn't store up
old signals. If you need that, you should add it to your event structure.
I made a few small changes, and I went from 0 updates to about 200,000:
% typedef struct __tEvent
% {
% pthread_cond_t cond;
% pthread_mutex_t mutex;
int outstanding_signals;
% } _tEvent;
% typedef _tEvent *tEvent;
%
% tEvent CreateEventSem(char *name)
% {
% tEvent te;
% te = (tEvent)malloc(sizeof(_tEvent));
te-> outstanding_signals = 0;
% pthread_cond_init(&(te->cond), NULL);
% if (pthread_mutex_init(&(te->mutex), NULL))
% return NULL;
/* why do you test just that one return code? */
% return te;
% }
% void WaitEventSem(tEvent te)
% {
% pthread_mutex_lock(&te->mutex);
while (!te->outstanding_signals)
% pthread_cond_wait(&te->cond, &te->mutex);
te->outstanding_signals --;
% pthread_mutex_unlock(&te->mutex);
% }
% void SignalEventSem(tEvent te)
% {
pthread_mutex_lock(&te->mutex);
te->outstanding_signals ++;
pthread_cond_signal(&(te->cond));
pthread_mutex_unlock(&te->mutex);
% }
% sleep(1);
/* don't rely on sleep to work as a synchronisation method.
* use pthread_join() instead, or roll your own signalling
* mechanism */
--
Patrick TJ McPhee
East York Canada
pt...@interlog.com
David Schwartz
>
> pthread_mutex_lock(&queue_lock);
>
> was_empty = is_empty(queue);
>
> /* add item(s) to queue */
>
> pthread_mutex_unlock(&queue_lock);
>
> if (was_empty)
> pthread_cond_signal(&queue_not_empty);
pthread_cond_signal only wakes one thread, and any number of threads
might be asleep waiting for objects to be placed on the queue.
If another thread immediately places an object on the queue, before the
thread woken by pthread_cond_signal can remove the object, it will _not_
call pthread_cond_signal, thus a thread will be sleeping waiting for an
object to be placed on the queue even though there is an object on the
queue.
Why do people keep getting this wrong?
Call pthread_cond_signal before you release the mutex, dammit.
DS
David Jones
Signalling before you release the mutex doesn't solve the problem since
there is no guarantee that the thread unblocked by the signal will be
the next thread to get the mutex.
One possible solution would be to have the thread that removes that
you woke issue another signal if the queue is still non-empty after
it removes the item(s) it is going to process.
David L. Jones | Phone: (614) 292-6929
Ohio State University | Internet:
140 W. 19th St. Rm. 231a | jon...@er6s1.eng.ohio-state.edu
Columbus, OH 43210 | vm...@osu.edu
Disclaimer: Dogs can't tell it's not bacon.
Kaz Kylheku
>> The signalling code logic can be like this:
>>
>> pthread_mutex_lock(&queue_lock);
>>
>> was_empty = is_empty(queue);
>>
>> /* add item(s) to queue */
>>
>> pthread_mutex_unlock(&queue_lock);
>>
>> if (was_empty)
>> pthread_cond_signal(&queue_not_empty);
>
> pthread_cond_signal only wakes one thread, and any number of threads
>might be asleep waiting for objects to be placed on the queue.
Yes, I screwed this up, mostly due to posting incomplete information. The
condition variable here represents a predicate that any number of threads may
be interested in it, without necessarily making it false. That is to say, the
predicate may be true before a consumer enters its critical region, and it may
remain true afterward. That predicate is ``the queue is not empty''.
One obvious solution is to broadcast a condition. The general principle is that
any condition representing a predicate that multiple threads are interested in
it without the intent of making it false should be broadcast.
Another solution is to change the logic of the woken threads so that they do
make the predicate false. In this case this is accomplished by changing the
consumer logic so that it consumes all of the items in such a way that it
cannot block anywhere else. I think this is what I had in mind when
I wrote the example, but I didn't make it clear.
A third solution is to call pthread_cond_signal as many times as the number of
items that were added, regardless of the state of the queue. This is probably
the most common way it is done in queuing, but isn't a general solution
that is applicable with other kinds of predicates.
> If another thread immediately places an object on the queue, before the
>thread woken by pthread_cond_signal can remove the object, it will _not_
>call pthread_cond_signal, thus a thread will be sleeping waiting for an
>object to be placed on the queue even though there is an object on the
>queue.
>
> Why do people keep getting this wrong?
>
> Call pthread_cond_signal before you release the mutex, dammit.
That is irrelevant and won't solve the problem. Calling pthread_cond_signal or
pthread_cond_broadcast when a mutex is held is a bad idea because these
operations are potentially expensive system calls (in the case that threads
have to be woken). If you can avoid it, you don't want to be making system
calls while in a critical region protected by a mutex. By moving the signalling
outside of the region, it has been shortened to just the few instructions
needed to compute ``was_empty'' and perform the queuing operations.
David Schwartz
> That is not possible. Look closer at the use of the boolean ``was_empty''. It
> is a local value computed while the mutex is held, and represents the state of
> the queue as recorded by the producer before the insertion. If the queue was
> empty before the insertion, the producer will signal regardless of what happens
> to the queue after the mutex is released. The scenario you describe cannot
> happen.
This does not prevent the race condition. Neither does having each pass
only place one item on the queue. Any number of threads can do the
lock/check_empty/place_time/unlock loop in sequence and only one of them
will decide to wake a thread, since only one of them put an object onto
an empty list.
> (I should have made it more clear that ``was_empty'' is not a shared object,
> but a local value.)
Does not matter.
> > Why do people keep getting this wrong?
> >
> > Call pthread_cond_signal before you release the mutex, dammit.
>
> This is poor advice. The pthread_cond_signal operation may result in a system
> call. You rarely want to be doing that in a critical region protected by a
> mutex.
Actually, if you pthread_cond_signal while holding the mutex, no system
call should result. Any thread waiting for the signal is waiting for the
mutex as well (which you _still_hold_), so no thread has changed from
waiting to runnable or vice-versa.
DS
Kaz Kylheku
>
>> That is not possible. Look closer at the use of the boolean ``was_empty''. It
>> is a local value computed while the mutex is held, and represents the state of
>> the queue as recorded by the producer before the insertion. If the queue was
>> empty before the insertion, the producer will signal regardless of what happens
>> to the queue after the mutex is released. The scenario you describe cannot
>> happen.
>
> This does not prevent the race condition. Neither does having each pass
Right. I misunderstood what you were objecting to, that's why I cancelled that
article and posted a more relevant response. I posted a stupid example that was
riddled with nasty assumptions about how the queue is used. (I can't remember
what I assumption I was thinking but it was either that there is only one
consumer, or that each consumer completely drains the queue.)
>only place one item on the queue.
... and neither does signalling while the mutex is held. Suppose the producer
adds three items to the (empty) queue, and signal before unlocking the mutex.
And suppose the consumer consumes only one without waking anyone up. There are
now two items in the queue. Other threads are waiting, but haven't been
notified.
Or suppose that the producer adds only one item and signals within the monitor,
but a thread that was not waiting on any condition variable happens to grab the
mutex before the one that was signalled. Same problem. POSIX only guarantees
wakeup ordering on conditions. It doesn't require that only one of the
signalled threads can acquire the mutex after a signaller gives it up. When a
mutex is given up, it is fair game for everyone, including some thread that
comes along without having waited on a condition first.
It's even possible that the same producer re-acquires the mutex and adds
another item, before any signalled thread gets a time-slice. This is that
case for which you are so fond of recommending sched_yield(). :) :)
There was a very recent discussion about signalling in the monitor versus
outside that you seem to have missed. (But then you are still catching up with
early July postings.) The conclusion is that signalling within the mutex
doesn't buy you anything. You may get slightly more predictable scheduling
by reducing the opportunity for spurious wakeup.
>> (I should have made it more clear that ``was_empty'' is not a shared object,
>> but a local value.)
>
> Does not matter.
>
>> > Why do people keep getting this wrong?
>> >
>> > Call pthread_cond_signal before you release the mutex, dammit.
>>
>> This is poor advice. The pthread_cond_signal operation may result in a system
>> call. You rarely want to be doing that in a critical region protected by a
>> mutex.
>
> Actually, if you pthread_cond_signal while holding the mutex, no system
>call should result. Any thread waiting for the signal is waiting for the
>mutex as well (which you _still_hold_), so no thread has changed from
>waiting to runnable or vice-versa.
A thread either waits on the condition or on the mutex, but not both at the
same time. At least in the abstract semantics. If you signal while holding the
mutex, you can actually cause another thread to wake up. If that thread gets a
timeslice before you get a chance to unlock the mutex, it will block on the
mutex. So you will be introducing needless context switches. This will almost
certainly be the case whenever the woken thread has a higher priority than the
signalling thread. The pthread_cond_signal will cause the higher priority
thread to become runnable, so the signaller is preempted in favor of that
thread. The higher priority thread will almost immediately block on the mutex,
so the lower priority thread has to be run again to unlock the mutex. As soon
as it does, the higher priority thread kicks in again.
David Schwartz
> ... and neither does signalling while the mutex is held. Suppose the producer
> adds three items to the (empty) queue, and signal before unlocking the mutex.
> And suppose the consumer consumes only one without waking anyone up. There are
> now two items in the queue. Other threads are waiting, but haven't been
> notified.
Right, you need to wake as many threads as you placed objects on the
queue, if you placed objects on an empty queue. So long as a thread can
only be waiting on the condition variable if the queue is empty, this
_should_ be sufficient.
In practice, you either run the risk of leaving threads sleeping or
guarantee you will wake too many threads. There is no perfect solution.
> Or suppose that the producer adds only one item and signals within the monitor,
> but a thread that was not waiting on any condition variable happens to grab the
> mutex before the one that was signalled. Same problem. POSIX only guarantees
> wakeup ordering on conditions. It doesn't require that only one of the
> signalled threads can acquire the mutex after a signaller gives it up. When a
> mutex is given up, it is fair game for everyone, including some thread that
> comes along without having waited on a condition first.
I don't think this is a problem.
> It's even possible that the same producer re-acquires the mutex and adds
> another item, before any signalled thread gets a time-slice. This is that
> case for which you are so fond of recommending sched_yield(). :) :)
Actually, you probably wouldn't wait to yield in this case. Better
queue two objects and then let a consumer thread run and consume both of
them -- it's fewer context switches. :)
> There was a very recent discussion about signalling in the monitor versus
> outside that you seem to have missed. (But then you are still catching up with
> early July postings.) The conclusion is that signalling within the mutex
> doesn't buy you anything. You may get slightly more predictable scheduling
> by reducing the opportunity for spurious wakeup.
I have found that failing to do so causes deadlocks. That is, if you
release the mutex before you signal, you run the risk of having threads
sleeping on the condition variable while the queue is non-empty. You can
design to tolerate this, but in the simple designs generally shown as
exemplative, it is fatal.
> > Actually, if you pthread_cond_signal while holding the mutex, no system
> >call should result. Any thread waiting for the signal is waiting for the
> >mutex as well (which you _still_hold_), so no thread has changed from
> >waiting to runnable or vice-versa.
>
> A thread either waits on the condition or on the mutex, but not both at the
> same time.
Correct, but as soon as the condition variable is signalled, if the
mutex is locked, you are waiting on the mutex.
> At least in the abstract semantics. If you signal while holding the
> mutex, you can actually cause another thread to wake up. If that thread gets a
> timeslice before you get a chance to unlock the mutex, it will block on the
> mutex.
That's just a bad implementation. There is no reason for it to wakeup a
thread just to have it block on the mutex it already knew the thread
wanted.
> So you will be introducing needless context switches.
No, a suboptimal implementation will do so.
> This will almost
> certainly be the case whenever the woken thread has a higher priority than the
> signalling thread. The pthread_cond_signal will cause the higher priority
> thread to become runnable, so the signaller is preempted in favor of that
> thread. The higher priority thread will almost immediately block on the mutex,
> so the lower priority thread has to be run again to unlock the mutex. As soon
> as it does, the higher priority thread kicks in again.
This is the reason why such a suboptimal implementation is so bad. :)
DS
David Schwartz
I usually use a weird combination of heuristics that, in my experience,
seems to both minimize extra sleeping and spurious wakeups:
1) I only call pthread_cond_signal if the number of objects on the
queue before I placed any is less than the number of consumer threads.
2) I call pthread_cond_signal as many times as I placed objects on the
queue, bounded by the number of consumer threads.
3) I _always_ signal while I still hold the mutex.
DS
Kaz Kylheku
>>
>> A thread either waits on the condition or on the mutex, but not both at the
>> same time.
>
> Correct, but as soon as the condition variable is signalled, if the
>mutex is locked, you are waiting on the mutex.
``As soon'' means after being woken up and possibly burning up many cycles
as it returns to wait on the mutex.
>> At least in the abstract semantics. If you signal while holding the
>> mutex, you can actually cause another thread to wake up. If that thread gets a
>> timeslice before you get a chance to unlock the mutex, it will block on the
>> mutex.
>
> That's just a bad implementation. There is no reason for it to wakeup a
>thread just to have it block on the mutex it already knew the thread
>wanted.
It's a realistic implementation. Mutexes are often implemented as user-space
objects. An atomic operation is used to determine whether the mutex is acquired
and some system call is used to resolve the contention if the acquisition
fails. If a thread unblocks on a condition variable wait, it has to return to
user space and try to acquire the mutex in the usual way.
>> So you will be introducing needless context switches.
>
> No, a suboptimal implementation will do so.
Can you cite some actual examples of better implementations?
Kaz Kylheku
>> outside that you seem to have missed. (But then you are still catching up with
>> early July postings.) The conclusion is that signalling within the mutex
>> doesn't buy you anything. You may get slightly more predictable scheduling
>> by reducing the opportunity for spurious wakeup.
>
> I have found that failing to do so causes deadlocks. That is, if you
>release the mutex before you signal, you run the risk of having threads
>sleeping on the condition variable while the queue is non-empty. You can
How would that happen? Why would any of the threads sleep on the condition
variable if they find items in the queue? The only way they can suspend
is if they find the queue empty while they hold the lock. Then what
can keep them suspended is lack of proper signalling.
>design to tolerate this, but in the simple designs generally shown as
>exemplative, it is fatal.
The deadlock must be inherent in the logic, and unrelated to whether you signal
inside or outside of the mutex. Because as we know, this makes no difference
whatsoever. Reveal the code that exhibits deadlock, and someone will readily
show that it's caused by something other than the relative placement of
pthread_cond_signal or broadcast to pthread_mutex_unlock.
In any correctly written program you can move the signalling or broadcasting
outside of the mutex without destroying the logic. Signalling and broadcasting
only wake up threads. That is to say, the bring some threads to a state where
they are eligible for execution. The threads may not actually run until later,
possibly long after the signalling thread has given up the mutex. In other
words, the actual scheduling event which causes control to be given to these
threads may occurs outside of the mutex whether you like it or not. You have no
control over when the threads actually run, and moving the signalling function
calls around won't make any difference. You might perturb the execution order,
that's about all.
David Schwartz
> >release the mutex before you signal, you run the risk of having threads
> >sleeping on the condition variable while the queue is non-empty. You can
>
> How would that happen? Why would any of the threads sleep on the condition
> variable if they find items in the queue? The only way they can suspend
> is if they find the queue empty while they hold the lock. Then what
> can keep them suspended is lack of proper signalling.
The queue was empty when they went to sleep on the cv. Then, before
they could wake, ten other threads each put an object on the queue. Only
one of them could have put an object on an empty queue, thus only one
signal will be sent.
> >design to tolerate this, but in the simple designs generally shown as
> >exemplative, it is fatal.
>
> The deadlock must be inherent in the logic, and unrelated to whether you signal
> inside or outside of the mutex. Because as we know, this makes no difference
> whatsoever.
Yes, it does. The race condition occurs when other threads put objects
on the queue before you signal -- since they are not putting objects on
an empty queue, they will not wake other threads that might be waiting.
If you still hold the mutex, this is impossible.
> In any correctly written program you can move the signalling or broadcasting
> outside of the mutex without destroying the logic. Signalling and broadcasting
> only wake up threads. That is to say, the bring some threads to a state where
> they are eligible for execution. The threads may not actually run until later,
> possibly long after the signalling thread has given up the mutex. In other
> words, the actual scheduling event which causes control to be given to these
> threads may occurs outside of the mutex whether you like it or not. You have no
> control over when the threads actually run, and moving the signalling function
> calls around won't make any difference. You might perturb the execution order,
> that's about all.
Hmm, let me think about that.
DS
David Schwartz
> Hmm, let me think about that.
>
I thought about it. You're right. I'm convinced. Release the mutex
before you signal/broadcast.
DS
David Schwartz
>
> DS
Until now. Kaz convinced me to release the mutex before
signalling/broadcasting.
DS
Kaz Kylheku
>> > I have found that failing to do so causes deadlocks. That is, if you
>> >release the mutex before you signal, you run the risk of having threads
>> >sleeping on the condition variable while the queue is non-empty. You can
>>
>> How would that happen? Why would any of the threads sleep on the condition
>> variable if they find items in the queue? The only way they can suspend
>> is if they find the queue empty while they hold the lock. Then what
>> can keep them suspended is lack of proper signalling.
>
> The queue was empty when they went to sleep on the cv. Then, before
>they could wake, ten other threads each put an object on the queue. Only
>one of them could have put an object on an empty queue, thus only one
>signal will be sent.
Right. But what you are describing is an error in the logic which has nothing
to do with the placement of the pthread_cond_signal outside of the mutex.
Moving the signalling inside the mutex doesn't solve the problem.
>> >design to tolerate this, but in the simple designs generally shown as
>> >exemplative, it is fatal.
>>
>> The deadlock must be inherent in the logic, and unrelated to whether you signal
>> inside or outside of the mutex. Because as we know, this makes no difference
>> whatsoever.
>
> Yes, it does. The race condition occurs when other threads put objects
>on the queue before you signal -- since they are not putting objects on
>an empty queue, they will not wake other threads that might be waiting.
>If you still hold the mutex, this is impossible.
But you don't hold the mutex for long. It's released soon after the
pthread_cond_signal. Immediately after the pthread_mutex_unlock, a thread
other than the signalled thread can sneak in and put an object onto the queue
before the signalled thread gets a chance to execute.
pthread_cond_signal is an asynchronous operation. If a thread is waiting on the
condition, it is made runnable. But there is no guarantee that it will get the
mutex. Or even that it will get a chance to execute before the
pthread_mutex_unlock happens. If it doesn't actually execute until after the
unlock, it might as well not have been signalled within the mutex.
>> In any correctly written program you can move the signalling or broadcasting
>> outside of the mutex without destroying the logic. Signalling and broadcasting
>> only wake up threads. That is to say, the bring some threads to a state where
>> they are eligible for execution. The threads may not actually run until later,
>> possibly long after the signalling thread has given up the mutex. In other
>> words, the actual scheduling event which causes control to be given to these
>> threads may occurs outside of the mutex whether you like it or not. You have no
>> control over when the threads actually run, and moving the signalling function
>> calls around won't make any difference. You might perturb the execution order,
>> that's about all.
>
> Hmm, let me think about that.
Also, while you are thinking, don't forget to include multiprocessor
considerations.
Suppose that the pthread_cond_signal is taking place on processor 0.
Just as you do pthread_mutex_unlock (after signalling), a running thread
on processor 1 grabs the mutex. The thread that was signalled hasn't
even been scheduled for execution yet! Processor 1 adds an item to the
queue without signalling because was_empty is false. Oops!
You could give pthread_cond_signal synchronous semantics, as in ``make sure
that the signalled thread gets the mutex before everyone else''. But the
mutex/condition semantics of POSIX do not have this. The synchronous
signalling semantics are known as ``Hoare semantics''. These were first
described by C. A. R. Hoare, and are illustrated that way in some textbooks on
operating systems. Often, they aree introduced in terms of an extension
to a Pascall-like language which lets you declare a module to be a monitor.
So locking and unlocking are not explicit.
Under Hoare semantics, there are no spurious wakeups, and a signalled thread
always gets into the monitor right after the signaller. In fact, the signal
operation gives up the monitor in favor of the signalled thread, causing the
recipient to be scheduled. So signalling is always necessarily done in the
monitor (and in the textbook programming language that supports monitors, this
is implicit because when you are inside a monitor function, the monitor is
locked). Another thing: the while loop to retest the predicate is not needed!
You simply do if not predicate then wait cond; Once you wake up,
it is guaranteed that the predicate is true, so there is no need to retest.
Hoare monitors are impractical to implement on multiprocessors and in other
situations in which the mutex and condition abstractions cannot be tightly
integrated with the underlying operating system. Also, Hoare monitors create a
potential for starvation, unfair precedence is given to the condition waiter to
get the mutex. You can end up in a sitatuion in which an ``clique'' of
threads pass ownership to each other by the synchronous signal operation, and
outsiders trying to get the mutex are locked out!
Kaz Kylheku
>>
>> Hmm, let me think about that.
>>
>
>before you signal/broadcast.
It's good to read David Butenhof's posts on this matter. He's the big
heavyweight around here, having implemented threads for Digital UNIX.
Dave Butenhof
OK, I admit I put on a couple of pounds over vacation, and I feel awful about it.
But, really, Kaz, "big heavyweight"? Cruel, cruel. Besides, it's not my fault: who
told my sister-in-law to leave all those chocolate chip cookies lying around,
anyway? ;-)
Seriously, the main advantage of signalling "inside" the mutex is that it may allow
you to push the thread scheduler into a "more predictable" behavior pattern,
especially when you're using realtime scheduling on an SMP system. That's because
the signalled thread will queue on the mutex along with any other threads that try
to lock the mutex "around the same time". Unlocking the mutex will then choose the
highest priority waiter to unblock. Even so, there's no real guarantee that the
unblocked waiter will acquire the mutex next; there could be yet another thread
already running that tries to lock the mutex during or immediately after the
unlock.
While the optimization that I call "wait morphing", which directly moves the waiter
from condition variable to mutex, seems "obvious" (which is the technical reason I
didn't try to patent it ages and ages ago), I doubt that it's anywhere near as
universal as several posts seem to expect. You probably will get (slightly) better
performance by signalling "outside" the mutex on many platforms. On the other hand,
if those extra context switches represent a big part of your application profile,
you're probably doing something else "suboptimally", if not wrong. (There are real
examples though; I developed wait morphing to fix problems with Ada rendezvous on
DEC OSF/1, back in the very early days.)
/---------------------------[ Dave Butenhof ]--------------------------\
| Compaq Computer Corporation David.B...@compaq.com |
| 110 Spit Brook Rd ZKO2-3/Q18 http://members.aol.com/drbutenhof |
| Nashua NH 03062-2698 http://www.awl.com/cseng/titles/0-201-63392-2/ |
\-----------------[ Better Living Through Concurrency ]----------------/
Kaz Kylheku
>OK, I admit I put on a couple of pounds over vacation, and I feel awful about
>it. But, really, Kaz, "big heavyweight"? Cruel, cruel. Besides, it's not my
>fault: who told my sister-in-law to leave all those chocolate chip cookies
>lying around, anyway? ;-)
:)
>Seriously, the main advantage of signalling "inside" the mutex is that it may
>allow you to push the thread scheduler into a "more predictable" behavior
>pattern,
Yep. *More* predictable, but not completely predictable. It's a *soft*
difference. Kind of like a nice chewy cookie. :)
David Schwartz
> Yep. *More* predictable, but not completely predictable. It's a *soft*
> difference. Kind of like a nice chewy cookie. :)
I'm increasingly becoming of the opinion that either you need
predictability or you don't. If you do, you need to put in code to
guarantee it. If you don't, you shouldn't waste your time on it.
DS
Dave Butenhof
Yes, there are degrees. However, if you "need predictability", really,
total predictability, then none of this discussion (or much of any others
in this group) are relevant. When you get to that point, you're writing for
an embedded realtime system where you know ALL relevant rules, completely,
because you either made the rules or the vendor wrote them down in careful
and thorough detail.
And even then, the package contents are measured by weight, not volume, and
some settling may have occurred during shipping. "Predictable" means you
can reliably plan for the worse case, not that you'll always get the best
case.