Fine-grained condvar/eventcount
Dmitriy V'jukov
consumer, but it doesn't have means to distinguish consumers, so it
has to signal all consumers.
For example consider following producer-consumer queue algorithm.
T pop()
{
int idx = atomic_inc(tail_idx);
while (empty(data[idx]))
ec.wait();
return data[idx];
}
void push(T v)
{
int idx = atomic_inc(head_idx);
data[idx] = v;
ec.signal_all();
}
Signaling all consumer will result in spurious wake-ups, i.e.
consumers will wake-up, recheck their items, and wait again. Only one
consumer will find data in his item.
Provided following condvar implementation:
http://groups.google.com/group/comp.programming.threads/msg/16d84e282387516d
we can improve it this way.
Crude algorithm sketch:
void wait_ctx(void* ctx)
{
waitset.push(this_thread, ctx);
}
void signal_ctx(void* ctx)
{
foreach((thread, thread_ctx) in waitset)
{
if (predicate(thread_ctx, ctx))
{
signal(thread->event);
}
}
}
Now we can rewrite queue example this way:
T pop()
{
int idx = atomic_inc(tail_idx);
while (empty(data[idx]))
ec.wait_ctx(&data[idx]);
return data[idx];
}
void push(T v)
{
int idx = atomic_inc(head_idx);
data[idx] = v;
ec.signal_ctx(&data[idx]);
}
Effectively this is equal to situation when we have separate condvar/
eventcount associated with every item in queue, but w/o associated
overheads.
Predicate for condvar/eventcount for queue must be:
bool predicate(void* thread_ctx, void* ctx)
{
return thread_ctx == ctx;
}
But in general case predicate can be arbitrary complicated. And it can
return 'true' for several or all waiters.
What do you think?
Dmitriy V'jukov
--
Relacy Race Detector: Make your synchronization correct!
http://groups.google.ru/group/relacy/web
Szabolcs Ferenczi
> In some situations producer need to signal only one particular
> consumer, but it doesn't have means to distinguish consumers, so it
> has to signal all consumers.
Consider to use dedicated buffer for the particular consumers. You
must design your algorithm.
> Signaling all consumer will result in spurious wake-ups, ...
That is normal wakeup. Spurious wakeup is something different. Check
the documentation of the condition variable.
Best Regards,
Szabolcs
David Schwartz
wrote:
> That is normal wakeup. Spurious wakeup is something different. Check
> the documentation of the condition variable.
He wasn't talking about POSIX condition variables, so the POSIX-
specific definition of "spurious wakeup" doesn't apply. Yes, "spurious
wakeup" has a very special meaning when specifically talking about
return from pthread_cond_* functions. But since he never mentioned
those functions, he meant the generic meaning -- a wakeup (thread
resumes after calling a blocking function) that is spurious (outwardly
similar or corresponding to something without having its genuine
qualities, false).
It's unfortunate and confusing that the two meanings are easily
confused. But it is not reasonable to call either use incorrect.
The POSIX-specific meaning is that a thread returns from a blocking
function despite no *application* thread calling any wakeup function
on the particular object it blocked on. This is a very narrow
specialized meaning. (And it still isn't totally clear. For example,
if an implementation has 'pthread_cond_signal' call
'pthread_cond_broadcast', are all but one wakeups spurious? Which one
isn't?)
DS
Giancarlo Niccolai
David, your post is extremely interesting, but it seems you fumbled on a
couple of key sentences (i.e. "... confusing the two meanings are easily
confused"), or at least, a mean non native English speaker as I am is
not able to determine unequivocally their meaning. May you please,
rephrase them?
(Didn't mean to sound ironic, I always found your posts extremely clear
and right to the point; that's why something is ringing out of place
this time).
TIA,
Giancarlo.
Szabolcs Ferenczi
> On Sep 23, 11:04 am, Szabolcs Ferenczi <szabolcs.feren...@gmail.com>
> wrote:
>
> > That is normal wakeup. Spurious wakeup is something different. Check
> > the documentation of the condition variable.
>
> He wasn't talking about POSIX condition variables, so the POSIX-
> specific definition of "spurious wakeup" doesn't apply.
Neither the concept of the condition variable nor the spurious wakeup
is POSIX-specific.
The term spurious wakeup is practically reserved for the wakeup that
has no corresponding signal. It is an implementation issue of the
condition variables, not only the POSIX ones, though.
The wakeup he is talking about comes from the MESA degradation
efforts, however, they meant it for an improvement. The MESA guys
wanted to make the monitor construction more efficient with it. Here
you are. After all, these kind of wakeups are not that spurious
especially if you think about why do you have condition variables at
all. Do not forget that the condition variable is just an optimisation
means. I have explained it to you a couple of times already as well as
I have demonstrated it.
> ... (And it still isn't totally clear. For example,
> if an implementation has 'pthread_cond_signal' call
> 'pthread_cond_broadcast', are all but one wakeups spurious? Which one
> isn't?)
You are really not clear.
However, if you issue a broadcast, none of the corresponding wakeups
will be spurious, since your clear intention was to give all of the
awaiting threads a chance to re-evaluate their waiting conditions
alias predicates. That is what happened. Thus, all of them woke up as
you just wanted. Consequently, none of the wakeups was spurious.
Best Regards,
Szabolcs
David Schwartz
wrote:
> > He wasn't talking about POSIX condition variables, so the POSIX-
> > specific definition of "spurious wakeup" doesn't apply.
> Neither the concept of the condition variable nor the spurious wakeup
> is POSIX-specific.
> The term spurious wakeup is practically reserved for the wakeup that
> has no corresponding signal. It is an implementation issue of the
> condition variables, not only the POSIX ones, though.
Except that's impossible. What are you saying? A cosmic ray strikes
the computer and causes the wakeup? Space aliens do it?
The POSIX-specific definition of "spurious wakeup" is one where no
thread called pthread_cond_signal or pthread_cond_broadcast on the
particular condition variable the thread waited on. You need all those
details to make the definition.
For example, if an implementation of POSIX made any call to
pthread_cond_signal or pthread_cond_broadcast wake all threads
blocking on any condition variables, would those be spurious wakeups?
> > ... (And it still isn't totally clear. For example,
> > if an implementation has 'pthread_cond_signal' call
> > 'pthread_cond_broadcast', are all but one wakeups spurious? Which one
> > isn't?)
> You are really not clear.
> However, if you issue a broadcast, none of the corresponding wakeups
> will be spurious, since your clear intention was to give all of the
> awaiting threads a chance to re-evaluate their waiting conditions
> alias predicates. That is what happened. Thus, all of them woke up as
> you just wanted. Consequently, none of the wakeups was spurious.
You failed to address my example and instead replaced it with your
own. My example was one where a thread called 'pthread_cond_signal'
and the implementation made it a broadcast.
DS
David Schwartz
niccolai.cc> wrote:
> David, your post is extremely interesting, but it seems you fumbled on a
> couple of key sentences (i.e. "... confusing the two meanings are easily
> confused"), or at least, a mean non native English speaker as I am is
> not able to determine unequivocally their meaning. May you please,
> rephrase them?
>
> (Didn't mean to sound ironic, I always found your posts extremely clear
> and right to the point; that's why something is ringing out of place
> this time).
I'll make my point again, very simply.
There is a whole spectrum of wakeups. Some are obviously desired and
some are obviously spurious. Some fall in a continuum. In the POSIX
world, for condition variables, there's a fairly precise definition of
"spurious wakeup" that draws the line in a particular place. For other
synchronization primatives, it's not always clear where to draw the
line.
Dmitriy meant the generic definition and Szabolcs assumed he meant the
generic. He did not, since he never mentioned POSIX condition
variables.
For example:
1) An implementation treats all condition variables as a singleton.
Any call to pthread_cond_signal or pthread_cond_broadcast wakes every
thread blocked on any condition variable. Are these spurious?
2) An implementation maps pthread_cond_signal to
pthread_cond_broadcast. Are all the wakeups but one spurious? Which
one isn't?
Even the POSIX definition for condition variables is not precise.
Which wakeups are spurious and which aren't depends upon your point of
view.
The generic definition is simple -- a "spurious wakeup" is any wakeup
that is spurious. The POSIX definition for condition variables is more
precise, including some wakeups that are not in fact spurious and
excluding some that are in fact spurious.
To put it another way, in POSIX condition variable parlance, "spurious
wakeup" refers to a particular type of wakeup that may or may not
actually be spurious. In normal parlance, it refers to wakeups that
are in fact spurious.
Dmitriy clearly mean the generic definition, and Szabolcs corrected
him assuming he was using the POSIX definition incorrectly. He was
not.
DS
Chris M. Thomasson
> news:8b194e6e-7b09-4e85...@v16g2000prc.googlegroups.com...vwrote:
>
> > > He wasn't talking about POSIX condition variables, so the POSIX-
> > > specific definition of "spurious wakeup" doesn't apply.
>
> > Neither the concept of the condition variable nor the spurious wakeup
> > is POSIX-specific.
>
> > The term spurious wakeup is practically reserved for the wakeup that
> > has no corresponding signal. It is an implementation issue of the
> > condition variables, not only the POSIX ones, though.
>
> Except that's impossible. What are you saying? A cosmic ray strikes
> the computer and causes the wakeup? Space aliens do it?
>
> The POSIX-specific definition of "spurious wakeup" is one where no
> thread called pthread_cond_signal or pthread_cond_broadcast on the
> particular condition variable the thread waited on. You need all those
> details to make the definition.
>
> For example, if an implementation of POSIX made any call to
> pthread_cond_signal or pthread_cond_broadcast wake all threads
> blocking on any condition variables, would those be spurious wakeups?
My only question would be how would you define a wakeup that did not satisfy
a predicate?
David Schwartz
> My only question would be how would you define a wakeup that did not satisfy
> a predicate?
It depends. Are we talking POSIX condition variables or ordinary
practice?
In ordinary practice, I would say that if the thread wakes up to find
the predicate not satisfied, the wakeup is spurious unless the same
signaling primitive is used for more than one predicate.
In POSIX parlance, it would only be so if there were more wakeups that
request by calls to pthread_cond_signal and pthread_cond_broadcast.
Note that if a thread calls pthread_cond_signal and two threads
unblock, one of those wakeups is spurious but there is no way to tell
which.
Any wakeups beyond the minimum POSIX requires are considered spurious
in the POSIX condition variable world. This is not so in other worlds,
where all wakeups that are spurious are spurious wakeups.
DS
Dmitriy V'jukov
> My only question would be how would you define a wakeup that did not satisfy
> a predicate?
Application-level false wakeup?
Dmitriy V'jukov
Szabolcs Ferenczi
> Signaling all consumer will result in spurious wake-ups, i.e.
> consumers will wake-up, recheck their items, and wait again. Only one
> consumer will find data in his item.
Recently there was a related issue on this discussion list for which I
have proposed a solution already:
"Optimize pthread_cond_wait loop?"
http://groups.google.com/group/comp.programming.threads/msg/8106f4afc3a61853
Here is the crude algorithm sketch for your problem:
CONSUMER1:
...
cr.lock();
while (P1) {c1.wait(cr);}
do_critical_op_depending_on_P1();
cr.unlock();
...
CONSUMER2:
...
cr.lock();
while (P2) {c2.wait(cr);}
do_critical_op_depending_on_P2();
cr.unlock();
...
PRODUCER:
...
cr.lock();
... // P1 or P2 might become true here
if (P1) c1.signal()
if (P2) c2.signal()
cr.unlock();
Best Regards,
Szabolcs
David Schwartz
wrote:
> Here is the crude algorithm sketch for your problem:
>
> CONSUMER1:
> ...
> cr.lock();
> while (P1) {c1.wait(cr);}
> do_critical_op_depending_on_P1();
> cr.unlock();
> ...
>
> CONSUMER2:
> ...
> cr.lock();
> while (P2) {c2.wait(cr);}
> do_critical_op_depending_on_P2();
> cr.unlock();
> ...
>
> PRODUCER:
> ...
> cr.lock();
> ... // P1 or P2 might become true here
> if (P1) c1.signal()
> if (P2) c2.signal()
> cr.unlock();
This only covers the (bizarre, IMO) case where each consumer knows
what it's going to wait for when it decides to wait. However, IMO,
this case is bizarre to begin with. Why would you care which thread
you unblock? Just have whichever thread unblocks do the 'most
important' work item. The 'right thread' to do the most important job
is the one that's running right now and not doing anything else.
DS
Szabolcs Ferenczi
> This only covers the (bizarre, IMO) case where each consumer knows
> what it's going to wait for when it decides to wait.
It may look bizarre for you only if you do not know what you are
doing. Usually one knows what it is going to wait for when it decides
to wait.
> However, IMO,
> this case is bizarre to begin with.
For you it must be.
> Why would you care which thread
> you unblock?
It is not about particular threads, it is about particular condition
variables. Does that surprise you?
However, just see the first post to the topic. It is a problem there.
I am just helping.
> Just have whichever thread unblocks do the 'most
> important' work item. The 'right thread' to do the most important job
> is the one that's running right now and not doing anything else.
You are again unclear. Think about it and try to express yourself. You
may try to come with some example.
Best Regards,
Szabolcs
David Schwartz
wrote:
> > This only covers the (bizarre, IMO) case where each consumer knows
> > what it's going to wait for when it decides to wait.
> It may look bizarre for you only if you do not know what you are
> doing. Usually one knows what it is going to wait for when it decides
> to wait.
I know what I'm doing, I just don't know what you are doing.
If you decide to wait for X and later Y happens, why make some other
thread do Y? X hasn't happened, and some other thread can wait for X
just fine. If Y needs to get done, and this thread is the one the
scheduler can most easily wake, why not do it?
I suppose there might be some bizarre situation where you have to
force a sub-optimal thread to do a task. But people keep creating
these solutions in search of problems, and I have to keep stepping
back and saying -- if you think you need this solution, there may be
something wrong with your problem.
> > However, IMO,
> > this case is bizarre to begin with.
> For you it must be.
Definitely.
> > Why would you care which thread
> > you unblock?
> It is not about particular threads, it is about particular condition
> variables. Does that surprise you?
An event occurs. Some thread has to do something about it. Some thread
has been woken. What's the problem?
> However, just see the first post to the topic. It is a problem there.
> I am just helping.
I understand that you are helping, and there's nothing wrong with your
answer. I'm just pointing out that the question you are answering is a
question that strongly suggests something wrong in the solution the
person asking it has in mind.
> > Just have whichever thread unblocks do the 'most
> > important' work item. The 'right thread' to do the most important job
> > is the one that's running right now and not doing anything else.
> You are again unclear. Think about it and try to express yourself. You
> may try to come with some example.
There is a job to be done. You have threads waiting. You wake a
thread, any thread. The thread does the job. Simple.
Complexity may be justified, but if not, complexity is a bad thing.
DS
Greg Herlihy
> On Sep 23, 2:34 pm, Szabolcs Ferenczi <szabolcs.feren...@gmail.com>
> wrote:
> > > He wasn't talking about POSIX condition variables, so the POSIX-
> > > specific definition of "spurious wakeup" doesn't apply.
> > Neither the concept of the condition variable nor the spurious wakeup
> > is POSIX-specific.
> > The term spurious wakeup is practically reserved for the wakeup that
> > has no corresponding signal. It is an implementation issue of the
> > condition variables, not only the POSIX ones, though.
>
> Except that's impossible. What are you saying? A cosmic ray strikes
> the computer and causes the wakeup? Space aliens do it?
No, the wait routine itself wakes up the thread - and does so even
without having received any signal from the application to do so. So,
no cosmic rays or aliens are needed to have software follow its own
instructions.
Now one might ask: why would a wait routine wake up a thread on its
own, that is, without being told to do so by the application? The
answer is essentially: because it pretty much has to. That is, in
order to ensure that the thread does wake up whenever it is supposed
to wake up, it is necessary to make it possible (although extremely
unlikely) for the thread to wake up at other times as well. And this
group of wake-ups that occur at these are "other times" comprise the
set of spurious wake-ups.
So, Szabolcs is 100% correct. To the executing program, a spurious
wake-up has no apparent cause. The application never does anything
that that causes a spurious wakeup to occur - just as there is nothing
that the application can do to prevent them.
> The POSIX-specific definition of "spurious wakeup" is one where no
> thread called pthread_cond_signal or pthread_cond_broadcast on the
> particular condition variable the thread waited on. You need all those
> details to make the definition.
Exactly. A spurious wake up may occur even when the application has
done nothing at all. In other words, there is no cause-and-effect link
between the occurrence of a spurious wake up - and the application's
operations.
> In other words, the application
> For example, if an implementation of POSIX made any call to
> pthread_cond_signal or pthread_cond_broadcast wake all threads
> blocking on any condition variables, would those be spurious wakeups?
No, none of the wake-ups would be spurious. Granted those wake-ups may
be unwelcome, or inconvenient, or unintentional, or unexpected - but
there is no question that the call to pthread_cond_signal() is the
reason why threads woke up. And any wake-up that can be attributed to
a particular function call is not - by definition - spurious.
> > > ... (And it still isn't totally clear. For example,
> > > if an implementation has 'pthread_cond_signal' call
> > > 'pthread_cond_broadcast', are all but one wakeups spurious? Which one
> > > isn't?)
> > You are really not clear.
> > However, if you issue a broadcast, none of the corresponding wakeups
> > will be spurious, since your clear intention was to give all of the
> > awaiting threads a chance to re-evaluate their waiting conditions
> > alias predicates. That is what happened. Thus, all of them woke up as
> > you just wanted. Consequently, none of the wakeups was spurious.
Correct. If an application does something (call it "X") that causes a
thread to wake up then that wake up is not spurious. After all, the
application could have avoided waking up the thread simply by not
performing "X". An application has no comparable way to prevent
spurious wake-ups from occurring - because spurious wake-ups occur
without any regard to anything that program might be doing.
> You failed to address my example and instead replaced it with your
> own. My example was one where a thread called 'pthread_cond_signal'
> and the implementation made it a broadcast.
If the thread woke up because pthread_cond_signal() was called - (and
the thread would still be asleep if pthread_cond_signal() had not been
called), then the wake-up is not spurious. Because in this case we can
readily conclude that the call to pthread_cond_signal() woke up the
thread. The thread did not wake up spuriously - that is, for no
apparent reason.
Greg
David Schwartz
> > > The term spurious wakeup is practically reserved for the wakeup that
> > > has no corresponding signal. It is an implementation issue of the
> > > condition variables, not only the POSIX ones, though.
> > Except that's impossible. What are you saying? A cosmic ray strikes
> > the computer and causes the wakeup? Space aliens do it?
> No, the wait routine itself wakes up the thread - and does so even
> without having received any signal from the application to do so.
Except that it might have received a signal from the application. For
example, if an implementation allowed any call to pthread_cond_signal
or pthread_cond_broadcast to unblock every thread blocked on every
c.v., that would still be a spurious wakeup, despte it having received
a signal from the application.
> So,
> no cosmic rays or aliens are needed to have software follow its own
> instructions.
So what makes it spurious?
> Now one might ask: why would a wait routine wake up a thread on its
> own, that is, without being told to do so by the application? The
> answer is essentially: because it pretty much has to. That is, in
> order to ensure that the thread does wake up whenever it is supposed
> to wake up, it is necessary to make it possible (although extremely
> unlikely) for the thread to wake up at other times as well. And this
> group of wake-ups that occur at these are "other times" comprise the
> set of spurious wake-ups.
And these "other times" might be in response to a instruction from the
application, provided that application signal didn't *require* the
particular wakeup that it generated.
In other words, in the special case of the POSIX world, a "spurious
wakeup" is any wakeup not *required* by POSIX.
> So, Szabolcs is 100% correct. To the executing program, a spurious
> wake-up has no apparent cause. The application never does anything
> that that causes a spurious wakeup to occur - just as there is nothing
> that the application can do to prevent them.
But that's not true. The application might do something that causes
the spurious wakeup. It just didn't do something that *required* the
wakeup.
> > The POSIX-specific definition of "spurious wakeup" is one where no
> > thread called pthread_cond_signal or pthread_cond_broadcast on the
> > particular condition variable the thread waited on. You need all those
> > details to make the definition.
> Exactly. A spurious wake up may occur even when the application has
> done nothing at all. In other words, there is no cause-and-effect link
> between the occurrence of a spurious wake up - and the application's
> operations.
It can occur even though the application does nothing at all, but it
doesn't just include wakeups where the application does nothing at
all. It includes wakeups that the application caused.
> > In other words, the application
> > For example, if an implementation of POSIX made any call to
> > pthread_cond_signal or pthread_cond_broadcast wake all threads
> > blocking on any condition variables, would those be spurious wakeups?
> No, none of the wake-ups would be spurious. Granted those wake-ups may
> be unwelcome, or inconvenient, or unintentional, or unexpected - but
> there is no question that the call to pthread_cond_signal() is the
> reason why threads woke up. And any wake-up that can be attributed to
> a particular function call is not - by definition - spurious.
Then there are no spurious wakeups. Every spurious wakeup will have
*some* cause. It's not cosmic rays or aliens. If the cause can be
*any* call to *any* function, then there are none.
> > > You are really not clear.
> > > However, if you issue a broadcast, none of the corresponding wakeups
> > > will be spurious, since your clear intention was to give all of the
> > > awaiting threads a chance to re-evaluate their waiting conditions
> > > alias predicates. That is what happened. Thus, all of them woke up as
> > > you just wanted. Consequently, none of the wakeups was spurious.
> Correct. If an application does something (call it "X") that causes a
> thread to wake up then that wake up is not spurious. After all, the
> application could have avoided waking up the thread simply by not
> performing "X". An application has no comparable way to prevent
> spurious wake-ups from occurring - because spurious wake-ups occur
> without any regard to anything that program might be doing.
Then there are no spurious wakeups. Heck, an application at least has
to call pthread_cond_wait or there can be no wakeups.
> > You failed to address my example and instead replaced it with your
> > own. My example was one where a thread called 'pthread_cond_signal'
> > and the implementation made it a broadcast.
> If the thread woke up because pthread_cond_signal() was called - (and
> the thread would still be asleep if pthread_cond_signal() had not been
> called), then the wake-up is not spurious. Because in this case we can
> readily conclude that the call to pthread_cond_signal() woke up the
> thread. The thread did not wake up spuriously - that is, for no
> apparent reason.
Then there are no spurious wakeups at all. But this is not the correct
definition. In POSIX world, a spurious wakeup is any wakeup the
implementation makes that POSIX allows but does not require.
DS