scheduling after cond_broadcast

[Raghu Angadi]

Hi,

Situation:
Thread A removes from a queue and B and C add to the queue.

A does pthread_cond_broadcast(&not_full) when it removes from a
full-queue. (similarly a threads A and B do
pthread_cond_broadcast(&not_empty) when they add to an empty-queue).

At sometime both B and C are blocked on not_full.
Whats happening is, A and B getting scheduled and C is rarely getting
scheduled. One would expect both B and C to get scheduled. Because both
are woken up by the broadcast.

All the threads have equal priority and the policy is SCHED_RR.
Platform is an embedded os. I think pthread implementaion might be based
on linux.

Can somebody through some light on typical implementation policies for
scheduling the threads which are woken up by a broadcast. In my case it
looks like the thread which is calling wait last is aquiring the mutex.

Thanks,
Raghu.

Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

[Ian Collins]

Raghu Angadi wrote:
>
> Hi,
>
> Situation:
> Thread A removes from a queue and B and C add to the queue.
>
> A does pthread_cond_broadcast(&not_full) when it removes from a
> full-queue. (similarly a threads A and B do
> pthread_cond_broadcast(&not_empty) when they add to an empty-queue).
>
> At sometime both B and C are blocked on not_full.
> Whats happening is, A and B getting scheduled and C is rarely getting
> scheduled. One would expect both B and C to get scheduled. Because both
> are woken up by the broadcast.
>
> All the threads have equal priority and the policy is SCHED_RR.
> Platform is an embedded os. I think pthread implementaion might be based
> on linux.
>
> Can somebody through some light on typical implementation policies for
> scheduling the threads which are woken up by a broadcast. In my case it
> looks like the thread which is calling wait last is aquiring the mutex.
>

There are no rules in this case, if both threads have the same priority,
it is down to the implementation which one gets woken up first.

You might try some form of second level arbitration, where a thead
re-pends
before it updates the condition if it gets the woken up first too often.

--
Ian Collins

[Tom Payne]

Raghu Angadi <ang...@my-deja.com> wrote:
: Hi,

: Situation:
: Thread A removes from a queue and B and C add to the queue.

: A does pthread_cond_broadcast(&not_full) when it removes from a
: full-queue. (similarly a threads A and B do
: pthread_cond_broadcast(&not_empty) when they add to an empty-queue).

: At sometime both B and C are blocked on not_full.
: Whats happening is, A and B getting scheduled and C is rarely getting
: scheduled. One would expect both B and C to get scheduled. Because both
: are woken up by the broadcast.

: All the threads have equal priority and the policy is SCHED_RR.
: Platform is an embedded os. I think pthread implementaion might be based
: on linux.

: Can somebody through some light on typical implementation policies for
: scheduling the threads which are woken up by a broadcast. In my case it
: looks like the thread which is calling wait last is aquiring the mutex.

Normally the broadcast-resumed threads compete for the mutex. It
appears that, as a side-effect of some implementation decisions, C is
consistently winning that competition. If that's not desirable,
perhaps you can use signal rather than broadcast.

Tom Payne

[David Schwartz]

> A does pthread_cond_broadcast(&not_full) when it removes from a
> full-queue. (similarly a threads A and B do
> pthread_cond_broadcast(&not_empty) when they add to an empty-queue).
>
> At sometime both B and C are blocked on not_full.
> Whats happening is, A and B getting scheduled and C is rarely getting
> scheduled. One would expect both B and C to get scheduled. Because both
> are woken up by the broadcast.

Your code is in error. You are broadcasting only when you add to an
empty queue. You need to broadcast whether the queue is empty or not.
Consider the following sequence:

1) One thread (call it B) is waiting for a signal, the other is working.

2) Another thread (A) puts something on queue, sends a broadcast, waking
only the ONE waiting thread.

3) A second thread (C) begins waiting for a signal.

4) The queuing thread (A) puts something on else the queue, but the
queue is not empty, no broadcast.

5) The one thread that was waiting during the broadcast (B) pulls one
thing off the queue.

6) Uh oh, we have a thread waiting, but there's stuff on the queue!

So your code is not waking C, so it's not running.

David Schwartz
http://www.gpsclock.com/

[Patrick TJ McPhee]

In article <3797FDEC...@webmaster.com>,
David Schwartz <dav...@webmaster.com> wrote:

[somebody wrote]
% > A does pthread_cond_broadcast(&not_full) when it removes from a
% > full-queue. (similarly a threads A and B do
% > pthread_cond_broadcast(&not_empty) when they add to an empty-queue).

% Your code is in error. You are broadcasting only when you add to an
% empty queue. You need to broadcast whether the queue is empty or not.

Bollocks.

% 1) One thread (call it B) is waiting for a signal, the other is working.
%
% 2) Another thread (A) puts something on queue, sends a broadcast, waking
% only the ONE waiting thread.
%
% 3) A second thread (C) begins waiting for a signal.
%
% 4) The queuing thread (A) puts something on else the queue, but the
% queue is not empty, no broadcast.

So why is C waiting? What's it waiting for? Why isn't it emptying the
queue?

If this is happening, you're using the wait wrong:
B&C:
lock mutex
if something on queue
take it off
if queue was full
broadcast not-full
else
while queue is empty
wait on not-empty
unlock mutex

A:
lock mutex
if room on queue
put something on
if queue was empty
broadcast not-empty
else
while queue is full
wait on not-full
unlock mutex

Nobody can wait on not-empty unless the queue is empty. The queue can't
become empty in the middle because the mutex is locked.
--

Patrick TJ McPhee
East York Canada
pt...@interlog.com

[David Schwartz]

You are making assumptions about his code that he did not state. In any
event, he's also releasing the mutex before issuing the signal, which is
unsafe as well.

DS

[Dave Butenhof]

David Schwartz wrote:

> > A does pthread_cond_broadcast(&not_full) when it removes from a

> > full-queue. (similarly a threads A and B do

> > pthread_cond_broadcast(&not_empty) when they add to an empty-queue).
> >

> > At sometime both B and C are blocked on not_full.
> > Whats happening is, A and B getting scheduled and C is rarely getting
> > scheduled. One would expect both B and C to get scheduled. Because both
> > are woken up by the broadcast.
>

> Your code is in error. You are broadcasting only when you add to an

> empty queue. You need to broadcast whether the queue is empty or not.

> Consider the following sequence:

Not necessarily "in error", but it probably expects something unreasonable.
Remember that when multiple threads are awakened by a broadcast, their first
goal, before any goals set by the application, is to lock the associated
mutex. Only one thread can do this. The other thread(s) awakened by the
broadcast will block on the mutex waiting for it to be released. (If you
signal or broadcast while holding the mutex, this will usually happen to ALL
threads awakened, until the signaller or broadcaster releases the mutex. Note
that this is a problem with any "read-write" lock package implemented using a
mutex and condition variable(s)... even though you broadcast all the readers,
they cannot return concurrently from the lock operation.)

Mutexes aren't "fair". When threads B and C frequently contend for the same
mutex, there's nothing to prevent thread B from ALWAYS (or, more
realistically, "usually") winning the race. That is probably why you see
thread C "rarely getting scheduled". (By "scheduled", I assume you mean that
it rarely acquires the mutex and continues to application work.) Most likely,
it is getting scheduled, periodically, but it either finds the mutex locked,
and must blocked, or, when it acquires the mutex, it finds that the queue is
no longer not_full, and goes back to sleep on the condition variable.

You may signal (or broadcast) regardless of whether you hold the associated
mutex. It doesn't matter, for most programs. However, you may find that it's
more efficient on some implementations to signal after releasing the mutex,
because otherwise the awakened thread may run while you still hold the mutex,
and need to block on the mutex. On the other hand, some implementations
provide what I call "wait morphing", which automatically moves the blocked
thread from the condition variable to the mutex with little overhead, making
this issue pretty much irrelevant. You may find that the scheduling behavior
of realtime applications is "slightly more predictable" if you signal while
holding the mutex, because all threads wishing access to the shared data,
including the thread you awaken, are likely to end up queued (in priority
order) on the mutex, meaning that the mutex is "more likely to be" granted to
the highest priority contender when you unlock it.

By the way, regarding signal vs. broadcast, here's the actual rule:

Signal is an OPTIMIZATION of broadcast, for the case where you know that all
threads waiting on the condition variable are waiting for the same predicate,
and that only one thread is needed to "service" the predicate change that
caused you to signal.

Rephrased: You can ALWAYS use broadcast, correctly. You can only correctly use
signal in the restricted case where "any thread can continue" and "only one
thread needs to continue".

Any time you mix several predicates on the same condition variable, you must
ALWAYS broadcast. (This is sometimes done to allow implementing a "wait for
multiple conditions" function along the lines of Win32.)

/---------------------------[ 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 ]----------------/

[Patrick TJ McPhee]

In article <379BD4FF...@webmaster.com>,
David Schwartz <dav...@webmaster.com> wrote:
%
% You are making assumptions about his code that he did not state. In any
% event, he's also releasing the mutex before issuing the signal, which is
% unsafe as well.

Give me a break. I'm telling you that this statement:

% > % Your code is in error. You are broadcasting only when you add to an
% > % empty queue. You need to broadcast whether the queue is empty or not.

is wrong.

If you need to broadcast `whether the queue is empty or not', then you're
using the condition variable incorrectly. I demonstrated how to use the
condition variable correctly, so that you only need to broadcast when
the queue is empty. I made no assumptions about anything.

Now I'll tell you that it is safe to release the mutex before issuing the
signal.