The condition variable test
Szabolcs Ferenczi
enable hand compiling of higher level constructions such as
Conditional Critical Regions and Monitors. Two building block elements
are the mutex and the condition variable.
Many newcomers to concurrent programming tend to misuse the condition
variable. A typical mistake is that they use the condition variable in
a way they use the semaphores. That is a mistake which is easy to
detect by a simple test.
There is a simple test to check whether somebody uses the condition
variable in a correct way or not:
CV TEST: Replace the wait operation with a mutex unlock/lock pair.
If your program still works functionally correct when you short cut
the wait operation, then you use the condition variable as it is meant
to be used. Note that your program might become inefficient during
this test but its functionality must not change. For instance you can
use the following macro (in case of pthread library and C/C++):
#ifdef CV_TEST
#define pthread_cond_wait(c,m) \
do { \
pthread_mutex_unlock(m); \
pthread_mutex_lock(m); \
} while(0)
#endif
The program should function the same whether you compile it with or
without the CV_TEST defined. Any correct program should function the
same if the condition variable is removed from the program and the
wait is substituted with a unlock/lock operation pair. This is a
simple test.
Best Regards,
Szabolcs
Chris Thomasson
news:431d609e-58b8-4da5...@n14g2000pri.googlegroups.com...
> The thread libraries nowadays contain low level building blocks to
> enable hand compiling of higher level constructions such as
> Conditional Critical Regions and Monitors. Two building block elements
> are the mutex and the condition variable.
>
> Many newcomers to concurrent programming tend to misuse the condition
> variable. A typical mistake is that they use the condition variable in
> a way they use the semaphores.
Did you know that you can use a condvar to make semaphores? Did you know
that you can use condvars to signal about events that occur when mutations
to the state warrants them? Anyway...
> That is a mistake which is easy to detect by a simple test.
I do agree that correct programs should still work when CV_TEST is defined.
One major point...
[...]
Your test won't work as-is. See, correct programs are going to expect a
return value. The way you have it, well, there is not going to be one. You
should probably rewrite your test function to something like:
<simple sketch>
___________________________________________________________________
extern int pthread_cond_wait_test(pthread_mutex_t* const);
#if defined(CV_TEST)
# define pthread_cond_wait(mp_this, mp_pmtx) ( \
pthread_cond_wait_test((mp_pmtx)) \
)
#endif
int
pthread_cond_wait_test(
pthread_mutex_t* const _this
) {
if (! pthread_mutex_unlock(_this)) {
sched_yield();
if (! pthread_mutex_lock(_this)) {
return 0;
}
}
return EINVAL;
}
___________________________________________________________________
This is because correct programs are going to expect 'pthread_cond_wait()'
to either return zero, or 'EINVAL'.
Any thoughts?
Markus Elfring
> variable. A typical mistake is that they use the condition variable in
> a way they use the semaphores.
Would you like to point out any preferences for either synchronisation interface?
http://birrell.org/andrew/papers/ImplementingCVs.pdf
http://www.cs.utah.edu/classes/cs5460-regehr/lecs/lec12.pdf
http://lwn.net/Articles/166195/
Regards,
Markus
Szabolcs Ferenczi
I have made my point couple of times before on this discussion list
but why not summarize here again:
It is not about the synchronization interface rather it is about the
synchronization tools themselves. If we were talking just about the
interface we would assume that the tools are equivalent, however, they
are not. See also p.6 in your second reference link:
"Important: Condition variables != Semaphores
Don't be confused by the fact that both support wait() and
signal() operations --- the operations have different meanings
However, they can be used to implement each other (and both can
be implemented in terms of test&set, disabling interrupts. etc.)"
Similarly, it is also not about preferences because each tool has its
own scope of applicability.
The semaphore is a universal synchronization tool in concurrent
programming (see p.1 in your second reference) but the condition
variable is not one. You can use semaphores to implement almost any
higher level synchronization constructions such as Critical Regions,
Conditional Critical Regions, Monitors, Rendezvous, event signaling,
etc. For instance, your first reference link just uses semaphores to
implement condition variables and mutexes.
However, the condition variable is just an optimization tool for run
time efficiency. It has been invented for that purpose as well. It is
used for the run time optimization of the waiting loop on a condition
in Conditional Critical Regions and Monitors (again see your second
reference for the role of CV in Monitors). Check out that in these
higher level constructions the real condition is an expression on the
shared resource (e.g. a shared flag or a function on the shared state
space) and it is not the condition variable itself what the logic is
awaiting. Furthermore, the waiting for the condition always happens in
a busy loop which is optimized with help of a condition variable. That
is why CV TEST can legally shortcut the waiting operation of a
condition variable and the functionality must be the same.
So, for instance, the semaphore is a very simple and general tool to
implement event handling (termed `event completion' in your third
reference link). Let us consider a simple case where one thread is
informing another about an event and the other is awaiting that event.
With a semaphore, it is as simple as this:
sem_t event;
sem_init(&event, 0, 0);
...
observer:
...; sem_wait(&event); ...
signaler:
...; sem_post(&event); ...
Of course, we can solve the same problem with a shared flag but in
that case you additionally need two semaphores or a combination of a
mutex and a condition variable. Let us see the latter combination:
/*shared*/volatile char event = '0';
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t c = PTHREAD_COND_INITIALIZER;
...
observer:
...
pthread_mutex_lock(&m);
while (event != '1') pthread_cond_wait(&c, &m);
pthread_mutex_unlock(&m);
...
signaler:
...
pthread_mutex_lock(&m);
event = '1';
pthread_cond_signal(&c);
pthread_mutex_unlock(&m);
...
As you can see, the latter code sketch passes the CV TEST. This is
because the condition variable is not part of the logic. It is just a
performance optimization.
Also note that the latter code sketch mimics the functionality of the
binary semaphore and it looks a bit complicated for solving simple
event handling. Thus, in this situation using a semaphore results in a
simpler code.
Best Regards,
Szabolcs
Chris Thomasson
news:ZPqdnWdX2cD-RJ7V...@comcast.com...
/* you should also add a cancellation point because condvar waits are
cancellation points themselves. Put it after the lock because cancelled
condvar waits reacquire the mutex. */
pthread_testcancel();
Sergei Organov
[...]
> I have made my point couple of times before on this discussion list
> but why not summarize here again:
[...]
> However, the condition variable is just an optimization tool for run
> time efficiency. It has been invented for that purpose as well.
You keep saying this again and again, but fail to provide any evidence.
References to yourself don't count as evidence, sorry.
-- Sergei.
Szabolcs Ferenczi
Evidence is the argument supported by code examples. Of course needed
is your own understanding. I can tell it to you but you must be able
to understand it, sorry.
Here is the evidence just for you: "Listening not to me but to the
Logos it'is wise to agree that all things are one."
I hope I could help.
Best Regards,
Szabolcs
Chris Thomasson
On Apr 15, 11:31 am, Markus Elfring <Markus.Elfr...@web.de> wrote:
> > Many newcomers to concurrent programming tend to misuse the condition
> > variable. A typical mistake is that they use the condition variable in
> > a way they use the semaphores.
>
> Would you like to point out any preferences for either synchronisation
> interface?
> http://birrell.org/andrew/papers/ImplementingCVs.pdf
> http://www.cs.utah.edu/classes/cs5460-regehr/lecs/lec12.pdf
> http://lwn.net/Articles/166195/
[...]
> However, the condition variable is just an optimization tool for run
> time efficiency. It has been invented for that purpose as well.
You honestly think that condvars were invented to optmize waits? You don't
know what a condvar is. I tried to explain it to you several times, however,
you fail to understand. Condvars allow a thread to wait on complex
predicates.
[...]
> Of course, we can solve the same problem with a shared flag but in
> that case you additionally need two semaphores or a combination of a
> mutex and a condition variable. Let us see the latter combination:
> /*shared*/volatile char event = '0';
> pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
> pthread_cond_t c = PTHREAD_COND_INITIALIZER;
Why are you declaring the 'event' variable as volatile? This is not needed
at all.
[...]
> As you can see, the latter code sketch passes the CV TEST. This is
> because the condition variable is not part of the logic. It is just a
> performance optimization.
The condition variable is an essential part of the waitable event logic.
> Also note that the latter code sketch mimics the functionality of the
> binary semaphore and it looks a bit complicated for solving simple
> event handling.
What look's complicated? Complication is in the eye of the beholder.
Markus Elfring
> its own scope of applicability.
>
> The semaphore is a universal synchronization tool in concurrent
> programming (see p.1 in your second reference) but the condition
> variable is not one.
Well, there is the known difference that the function "sem_post" may be called
from inside signal handlers.
> Check out that in these higher level constructions the real condition
> is an expression on the shared resource (e.g. a shared flag
> or a function on the shared state space) and it is not the
> condition variable itself what the logic is awaiting.
Only higher level programming languages can make the waiting on predicate
updates an integral part of their systems.
> Also note that the latter code sketch mimics the functionality of
> the binary semaphore and it looks a bit complicated for solving
> simple event handling. Thus, in this situation using a semaphore
> results in a simpler code.
I have read lessons that prefer the other interface for simplicity and
correctness efforts. It might be interesting to get a more recent comparison
between these techniques published.
Regards,
Markus
Chris Thomasson
> "Szabolcs Ferenczi" <szabolcs...@gmail.com> wrote in message
> news:03cc1ef4-2a8e-4304...@h1g2000prh.googlegroups.com...
> On Apr 15, 11:31 am, Markus Elfring <Markus.Elfr...@web.de> wrote:
>> > Many newcomers to concurrent programming tend to misuse the condition
>> > variable. A typical mistake is that they use the condition variable in
>> > a way they use the semaphores.
>>
>> Would you like to point out any preferences for either synchronisation
>> interface?
>> http://birrell.org/andrew/papers/ImplementingCVs.pdf
>> http://www.cs.utah.edu/classes/cs5460-regehr/lecs/lec12.pdf
>> http://lwn.net/Articles/166195/
>
> [...]
>
>> However, the condition variable is just an optimization tool for run
>> time efficiency. It has been invented for that purpose as well.
>
> You honestly think that condvars were invented to optmize waits? You don't
> know what a condvar is. I tried to explain it to you several times,
> however, you fail to understand. Condvars allow a thread to wait on
> complex predicates.
Well, perhaps you equate the ability to wait on complex predicates with an
optimization over semaphores. I don't know.
Chris Thomasson
"Markus Elfring" <Markus....@web.de> wrote in message
news:66jb2kF...@mid.individual.net...
If you want to see a great condvar implementation with semaphores, go ahead
and check Alex Terekhov's algorithm in pthread_win32. IMVHO, it's a smart
piece of clean work. He tries fairly hard to reduce superfluous wakes and
handle timeouts/cancellations.
Chris Thomasson
news:03cc1ef4-2a8e-4304...@h1g2000prh.googlegroups.com...
> > > Many newcomers to concurrent programming tend to misuse the condition
> > > variable. A typical mistake is that they use the condition variable in
> > > a way they use the semaphores.
> >
> > Would you like to point out any preferences for either synchronisation
> > interface?
> > http://birrell.org/andrew/papers/ImplementingCVs.pdf
> > http://www.cs.utah.edu/classes/cs5460-regehr/lecs/lec12.pdf
> > http://lwn.net/Articles/166195/
> I have made my point couple of times before on this discussion list
> but why not summarize here again:
[...]
How would you efficiently use a semaphore to control access to a complex
predicate?
Sergei Organov
> On Apr 15, 8:38 pm, Sergei Organov <o...@javad.com> wrote:
>> Szabolcs Ferenczi <szabolcs.feren...@gmail.com> writes:
>>
>> [...]
>>
>> > I have made my point couple of times before on this discussion list
>> > but why not summarize here again:
>>
>> [...]
>>
>> > However, the condition variable is just an optimization tool for run
>> > time efficiency. It has been invented for that purpose as well.
>>
>> You keep saying this again and again, but fail to provide any evidence.
>> References to yourself don't count as evidence, sorry.
>
> Evidence is the argument supported by code examples. Of course needed
> is your own understanding.
Still can't give any references (but to yourself) supporting your
*personal* opinion ? ;) Don't you think that it could be you who lacks
understanding?
Please notice that your examples only prove that condvars are "just an
optimization" in your particular examples. On the other hand, to prove
you are wrong, it's enough to give at least one counter-example where
removing condvar will lead to program misbehavior.
Provided you know what real-time thread priorities are about, it should
be rather easy for you to come-up with such a counter-example yourself.
Hint: implement high-priority thread waiting for a condition that will
be signalled from a low-priority thread.
-- Sergei.
Marcin ‘Qrczak’ Kowalczyk
> The semaphore is a universal synchronization tool in concurrent
> programming (see p.1 in your second reference) but the condition
> variable is not one.
No, it's the other way around. It's much easier to implement a semaphore
using condition variables than to implement a condition variable using
semaphores (implementing condition variables with busy waiting doesn't
count in practice). This shows that condition variables are the basic
and general tool, and semaphores is just one of its utilities.
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
David Schwartz
wrote:
> However, the condition variable is just an optimization tool for run
> time efficiency. It has been invented for that purpose as well. It is
> used for the run time optimization of the waiting loop on a condition
> in Conditional Critical Regions and Monitors (again see your second
> reference for the role of CV in Monitors).
This is insanity. It is simply wrong.
The only argument you've ever made to support it is that you can
always replace a condition variable with a bunch of other functions
that serve the same purpose but perform worse. But it does not follow
from this that condition variables were created to optimize that
operation.
This argument is at least credible if the replacement code that
performs worse is at least moderately sensible. If people might
actually have written the code that performs worse but for the
purported optimization, then the argument is at least coherent.
People actually do travel on bicycles, and cars really are more
efficient than bicycles for long trips. So it's at least coherent to
argue that cars might have been designed to as an optimization over
bicycles for long trips.
But in this case, the claimed thing that is optimized is completely
irrational. No programmer would ever thing that was sensible code.
It's akin to arguing that cars were invented to optimize wandering
aimlessly on a bicycle until you happen to wind up where you want to
go. Since nobody would ever do that, except perhaps to prove it can be
done, it's nonsensical to argue that cars were invented to optimize
that.
DS
Szabolcs Ferenczi
> On Apr 15, 10:03 am, Szabolcs Ferenczi <szabolcs.feren...@gmail.com>
> wrote:
>
> > However, the condition variable is just an optimization tool for run
> > time efficiency. It has been invented for that purpose as well. It is
> > used for the run time optimization of the waiting loop on a condition
> > in Conditional Critical Regions and Monitors (again see your second
> > reference for the role of CV in Monitors).
>
> This is insanity. It is simply wrong.
>
> The only argument you've ever made to support it is that you can
> always replace a condition variable with a bunch of other functions
> that serve the same purpose but perform worse. But it does not follow
> from this that condition variables were created to optimize that
> operation.
It is not about performance but about correctness. You clearly
misunderstand the issue but at least you have enough hybris.
No, it is not an argument that during testing the condition variable
can be safely removed so that the wait is replaced with the unlock/
lock pair on the relevant mutex. Rather, it is a test for the correct
use of the condition variable. If the test fails, you use the
condition variable for event handling which is a programming error. So
simple is that.
> But it does not follow
> from this that condition variables were created to optimise that
> operation.
You are right, it does not follow from that. Just the other way
around: Since the condition variable has been introduced to optimise
the performance of the busy waiting loop in Conditional Critical
Regions and Monitors, it follows that it can be omitted and the
functionality must stay the same.
I suggest this simple test just because many examples appeared in this
discussion forum alone which prove that many people misuse the
condition variable.
Best Regards,
Szabolcs
P.S.: Please refrain yourself and try to avoid saying "insanity" and
"simply wrong" because it is a very low language.
Chris Thomasson
> On Apr 19, 12:41 am, David Schwartz <dav...@webmaster.com> wrote:
> > On Apr 15, 10:03 am, Szabolcs Ferenczi <szabolcs.feren...@gmail.com>
> > wrote:
> >
> > > However, the condition variable is just an optimization tool for run
> > > time efficiency. It has been invented for that purpose as well. It is
> > > used for the run time optimization of the waiting loop on a condition
> > > in Conditional Critical Regions and Monitors (again see your second
> > > reference for the role of CV in Monitors).
> >
> > This is insanity. It is simply wrong.
> >
> > The only argument you've ever made to support it is that you can
> > always replace a condition variable with a bunch of other functions
> > that serve the same purpose but perform worse. But it does not follow
> > from this that condition variables were created to optimize that
> > operation.
> It is not about performance but about correctness. You clearly
> misunderstand the issue but at least you have enough hybris.
> No, it is not an argument that during testing the condition variable
> can be safely removed so that the wait is replaced with the unlock/
> lock pair on the relevant mutex. Rather, it is a test for the correct
> use of the condition variable. If the test fails, you use the
> condition variable for event handling which is a programming error. So
> simple is that.
Condition variables _are_ designed to handle complex event handling such
that it allows for threads to wait on predicates which are not satisfied.
When a mutation renders a predicate into a "signaled" state, the waiting
threads are notified that an event has occurred. If that's not explicit
event handling, well, I don't quite know what is.
[...]
Markus Elfring
I doubt that it is really helpful. The implementation of the function
"pthread_cond_wait" must stay compliant to the POSIX standard. It might provide
additional error checking. Do you imagine any more return values that will
indicate the misuse of this API?
> If the test fails, you use the condition variable for event handling
> which is a programming error. So simple is that.
It seems that it is not so simple to achieve an agreement on the term "event
handling". Errors can be introduced with both synchronisation interfaces.
> I suggest this simple test just because many examples appeared
> in this discussion forum alone which prove that many people misuse
> the condition variable.
I guess that advanced tools for static source code analysis like the software
"IntelŽ Thread Checker" will provide a better service for correctness checking.
Would you like to suggest more powerful alternatives?
Regards,
Markus
Szabolcs Ferenczi
> > Rather, it is a test for the correct use of the condition variable.
>
> I doubt that it is really helpful. The implementation of the function
> "pthread_cond_wait" must stay compliant to the POSIX standard. It might provide
> additional error checking. Do you imagine any more return values that will
> indicate the misuse of this API?
It is not about error checking. However, you can include error
checking if you want. That is not the point. The main issue what you
should understand is that the wait operation of the condition variable
can return right after the moment you call it. Check the
specification. The CV_TEST just calls your attention to this fact.
> > If the test fails, you use the condition variable for event handling
> > which is a programming error. So simple is that.
>
> It seems that it is not so simple to achieve an agreement on the term "event
> handling". Errors can be introduced with both synchronisation interfaces.
The term is fixed in the concurrent programming area. Newcomers
without proper background might have problems with it, though.
The message here is again that you cannot use the condition variable
so that you signal an event from one thread and await the signal in
another thread. You can use a semaphore that way but not any condition
variable.
Do not forget, the condition variable is not designed for that.
> > I suggest this simple test just because many examples appeared
> > in this discussion forum alone which prove that many people misuse
> > the condition variable.
>
> I guess that advanced tools for static source code analysis like the software
> "Intel® Thread Checker" will provide a better service for correctness checking.
> Would you like to suggest more powerful alternatives?
You miss the point again. This test is rather for the understanding of
the right usage of the condition variable.
Best Regards,
Szabolcs
Markus Elfring
> of the condition variable can return right after the moment you call it.
Advanced synchronisation programmers are used to the wait loop for the handling
of spurious wakeups. Higher level software libraries can make this
implementation detail easier and safer for monitors.
> The message here is again that you cannot use the condition variable
> so that you signal an event from one thread and await the signal in
> another thread. You can use a semaphore that way but not any condition
> variable.
>
> Do not forget, the condition variable is not designed for that.
I would prefer further clarification from your view what can not be done by the
functions "pthread_cond_signal" or "pthread_cond_broadcast" in comparison to the
function "sem_post".
Regards,
Markus
Markus Elfring
> of the condition variable can return right after the moment you call it.
Advanced synchronisation programmers are used to the wait loop for the handling
of spurious wakeups. Higher level software libraries can make this
implementation detail easier and safer for monitors.
> The message here is again that you cannot use the condition variable
> so that you signal an event from one thread and await the signal in
> another thread. You can use a semaphore that way but not any condition
> variable.
>
> Do not forget, the condition variable is not designed for that.
I would prefer further clarification from your view what can not be done by the
Szabolcs Ferenczi
> > The main issue what you should understand is that the wait operation
> > of the condition variable can return right after the moment you call it.
>
> Advanced synchronisation programmers are used to the wait loop for the handling
> of spurious wakeups.
They simply have to use wait loop, they have no other choice, and not
only because the spurious wakeups. They have to use waiting loops
because what they are waiting for is the boolean expression to become
true and not any signal on the condition variable. So simple is that.
Besides, they must comply to the condition variable test too.
> Higher level software libraries can make this
> implementation detail easier and safer for monitors.
No question they can. However, they must themselves comply to the
test.
> > The message here is again that you cannot use the condition variable
> > so that you signal an event from one thread and await the signal in
> > another thread. You can use a semaphore that way but not any condition
> > variable.
>
> > Do not forget, the condition variable is not designed for that.
>
> I would prefer further clarification from your view what can not be done by the
> functions "pthread_cond_signal" or "pthread_cond_broadcast" in comparison to the
> function "sem_post".
I am afraid I have clarified clear enough. You must try to follow.
Anyway, you can find a clear example about what cannot be done here:
http://groups.google.com/group/comp.programming.threads/msg/fc06ff81b98a9823
It is just surprising how many of you support the wrong usage and
attack me who highlights the problem. It is also amazing that you are
not able to follow simple working examples.
Best Regards,
Szabolcs
Chris Thomasson
LOL!
> Anyway, you can find a clear example about what cannot be done here:
> http://groups.google.com/group/comp.programming.threads/msg/fc06ff81b98a9823
Szabolcs, you are a complete fool! I am sorry, but you know better. The link
points to bugged code. You think that semaphores are superior and more
flexible than condvars because you can point to a piece of code that LACKED
A PREDICATE? Learn about condvars before you post here again.
:^/
> It is just surprising how many of you support the wrong usage and
> attack me who highlights the problem. It is also amazing that you are
> not able to follow simple working examples.
:^D
Chris Thomasson
>> Rather, it is a test for the correct use of the condition variable.
>
> I doubt that it is really helpful. The implementation of the function
> "pthread_cond_wait" must stay compliant to the POSIX standard. It might
> provide additional error checking. Do you imagine any more return values
> that will indicate the misuse of this API?
I guess it's helpful in a sense. The only problem is that Szabolcs' initial
test code was:
#ifdef CV_TEST
#define pthread_cond_wait(c,m) \
do { \
pthread_mutex_unlock(m); \
pthread_mutex_lock(m); \
} while(0)
#endif
Not good at all. This was my suggestion:
___________________________________________________________________
extern int pthread_cond_wait_test(pthread_mutex_t* const);
#if defined(CV_TEST)
# define pthread_cond_wait(mp_this, mp_pmtx) ( \
pthread_cond_wait_test((mp_pmtx)) \
)
#endif
int
pthread_cond_wait_test(
pthread_mutex_t* const _this
) {
if (! pthread_mutex_unlock(_this)) {
sched_yield();
if (! pthread_mutex_lock(_this)) {
pthread_testcancel();
return 0;
}
}
return EINVAL;
}
___________________________________________________________________
At least this tries to give standard return value for pthread_cond_wait, and
makes sure to try and execute a cancellation point. However, I am not sure
how Szabolcs will react... He seems to have killfiled me! ;^/
Chris Thomasson
[...]
Okay. Please correct me if I am wrong Szabolcs... When you say condvars are
not designed to handle events, what you really mean is that its an error to
use them without an explicit predicate. Right? If so, well, your wording
confused me.
Markus Elfring
> only because the spurious wakeups. They have to use waiting loops
> because what they are waiting for is the boolean expression to become
> true and not any signal on the condition variable. So simple is that.
I agree that it is important to stress proper predicate handling in software
development.
http://groups.google.de/group/comp.programming.threads/msg/9704618a0d9ce43d
http://groups.google.de/groups?threadm=40ed1d8f.04111...@posting.google.com
> I am afraid I have clarified clear enough. You must try to follow.
I find your personal reasons for a semaphore preference not clear enough so far.
This API is one approach from the little bigger choice of synchronisation
primitives.
> It is just surprising how many of you support the wrong usage and
> attack me who highlights the problem.
Which wording do you interpret as an attack?
It seems that you contributed something to computer science.
http://www.kfki.hu/~ferenczi/
I think that it is usual to discuss different opinions here. Would you like to
achieve a consensus on the technical facts?
Regards,
Markus
David Schwartz
wrote:
> On Apr 19, 12:41 am, David Schwartz <dav...@webmaster.com> wrote:
> > > However, the condition variable is just an optimization tool for run
> > > time efficiency. It has been invented for that purpose as well. It is
> > > used for the run time optimization of the waiting loop on a condition
> > > in Conditional Critical Regions and Monitors (again see your second
> > > reference for the role of CV in Monitors).
> It is not about performance but about correctness. You clearly
> misunderstand the issue but at least you have enough hybris.
Okay, so it's "an optimization tool for run time efficiency" that's
not about performance. I'm with you so far.
> No, it is not an argument that during testing the condition variable
> can be safely removed so that the wait is replaced with the unlock/
> lock pair on the relevant mutex. Rather, it is a test for the correct
> use of the condition variable. If the test fails, you use the
> condition variable for event handling which is a programming error. So
> simple is that.
You say "X and Y". I say "not X". You say "Y".
> > But it does not follow
> > from this that condition variables were created to optimise that
> > operation.
> You are right, it does not follow from that. Just the other way
> around: Since the condition variable has been introduced to optimise
> the performance of the busy waiting loop in Conditional Critical
> Regions and Monitors, it follows that it can be omitted and the
> functionality must stay the same.
Except that it has not been "introduced to optimize the performance of
the busy waiting loop". Please read the post you are responding to
again. It clearly explains why this claim is wrong.
> I suggest this simple test just because many examples appeared in this
> discussion forum alone which prove that many people misuse the
> condition variable.
You say "X and Y". I say "not X". You say "Y".
> P.S.: Please refrain yourself and try to avoid saying "insanity" and
> "simply wrong" because it is a very low language.
Nevertheless, you have consistently demonstrated that you are wrong
about this, that you refuse to recognize that you are wrong on this,
and that you continue to state it as if it were a fact to people who
don't know any better. This leaves everyone else with no choice but to
warn people not to listen to you, lest they wind up with the same
crazy misunderstandings you have.
This part here:
> > > However, the condition variable is just an optimization tool for run
> > > time efficiency. It has been invented for that purpose as well. It is
> > > used for the run time optimization of the waiting loop on a condition
> > > in Conditional Critical Regions and Monitors (again see your second
> > > reference for the role of CV in Monitors).
Is insanity and is simply wrong. I'm not the only person to tell you
this.
DS
Chris Thomasson
>> Anyway, you can find a clear example about what cannot be done here:
>> http://groups.google.com/group/comp.programming.threads/msg/fc06ff81b98a9823
>
> Szabolcs, you are a complete fool!
I am sorry for calling you a fool. That was very foolish of me!
:^|
> I am sorry, but you know better. The link points to bugged code. You think
> that semaphores are superior and more flexible than condvars because you
> can point to a piece of code that LACKED A PREDICATE? Learn about condvars
> before you post here again.
>
> :^/
[...]
Szabolcs Ferenczi
> > I am afraid I have clarified clear enough. You must try to follow.
>
> I find your personal reasons for a semaphore preference not clear enough so far.
Where can you see any general preference for the semaphore in my
posts?
Perhaps it is not clear to you just because I do not have any general
preference for the semaphore in the sense most of you interpret it for
some strange reason. All along I claim that you should use semaphores
when it is appropriate and you should use mutex and condition variable
when that is appropriate.
What you cannot do, however, is to use the condition variable as if it
were a semaphore. It is not a semaphore and it is not designed to be a
substitute for it. (It is also highlighted in one of your own
references!)
Let me give you a metaphor: You can have cutting devices such as a
knife and an ax at hand. I would say you should use the knife when you
have to slice the bread but you should use the ax when you have to cut
the tree. You might want to do that the other way around but it is not
a good idea.
That is what I am saying with respect to the synchronisation means as
well: You can have different synchronisation means available. You
might be in love with the mutex and condition variable pair but there
are certain programming problems what you can more easily solve with
semaphores. One of them is signaling that an event has happened in one
of the threads. For others the mutex and condition variable pair may
be more appropriate.
I think I explained it in the following post at quite a low level,
step by step, giving solutions BOTH with semaphores and with mutex
condition variable pairs to compare:
http://groups.google.com/group/comp.programming.threads/msg/bc2c0a9dfe7b1655
Please let me know what can you not understand in the simple examples
I have already given to you there.
Also in the discussion thread, when someone dropped in with a problem,
I have pointed out the problem and I have shown solution to him BOTH
with mutex condition variable pairs ...
http://groups.google.com/group/comp.programming.threads/msg/41fa64966fe090ca
... and with semaphores:
http://groups.google.com/group/comp.programming.threads/msg/64cfa20ab92bcd12
So, please tell me where can you see any general preference for the
semaphore in my posts?
The semaphore is the first general purpose synchronization tool for
solving concurrency problems in the history of concurrent programming
and this fact is widely acknowledged and agreed.---Except for the
pseudo "experts" on comp.programming.threads who deny the obvious
facts just for the enjoyment of opposing.
> This API is one approach from the little bigger choice of synchronisation
> primitives.
Yes, your problem might be that every one of you tends to talk about
API and there you fall into an ontological fallacy. But that is
already a different story ...
Best Regards,
Szabolcs
Chris Thomasson
> On Apr 21, 10:10 am, Markus Elfring <Markus.Elfr...@web.de> wrote:
> > > I am afraid I have clarified clear enough. You must try to follow.
> >
> > I find your personal reasons for a semaphore preference not clear enough
> > so far.
> > Where can you see any general preference for the semaphore in my
> > posts?
> Perhaps it is not clear to you just because I do not have any general
> preference for the semaphore in the sense most of you interpret it for
> some strange reason. All along I claim that you should use semaphores
> when it is appropriate and you should use mutex and condition variable
> when that is appropriate.
> What you cannot do, however, is to use the condition variable as if it
> were a semaphore. It is not a semaphore and it is not designed to be a
> substitute for it. (It is also highlighted in one of your own
> references!)
You cannot use a condvar as a semaphore? Oh really?
______________________________________________________________
typedef struct semaphore_s semaphore;
struct semaphore_s {
int state;
pthread_mutex_t lock;
pthread_cond_t cond;
};
#define SEMAPHORE_STATICINIT_EX(mp_state) {
(mp_state), PTHREAD_MUTEX_INITIALIZER, \
PTHREAD_COND_INITIALIZER \
}
#define SEMAPHORE_STATICINIT() \
SEMAPHORE_STATICINIT_EX(0)
void
semaphore_post(
semaphore* const _this
) {
pthread_mutex_lock(&_this->lock);
++_this->state;
pthread_mutex_unlock(&_this->lock);
pthread_cond_signal(&_this->cond);
}
void
semaphore_sys_wait_cancel(
semaphore* const _this
) {
pthread_mutex_unlock(&_this->lock);
}
void
semaphore_wait(
semaphore* const _this
) {
pthread_mutex_lock(&_this->lock);
pthread_cleanup_push(semaphore_sys_wait_cancel, _this);
while (! _this->state) {
pthread_cond_wait(&_this->cond, &_this->lock);
}
--_this->state;
pthread_cleanup_pop(1);
}
______________________________________________________________
Humm, looks like a semaphore to me!
[...]
Sergei Organov
> well: You can have different synchronisation means available. You
> might be in love with the mutex and condition variable pair but there
> are certain programming problems what you can more easily solve with
> semaphores.
Fine so far...
> One of them is signaling that an event has happened in one of the
> threads. For others the mutex and condition variable pair may be more
> appropriate.
Except that it's condvar (+mutex +predicate) that is specifically
designed for the purpose of signalling that an event has happened in one
of the threads.
From this POV, semaphore is just a very special case of
condvar+mutex+predicate, where predicate is an integer that is only ever
decremented or incremented by 1, and those threads that try to decrement
it below 0 are forced to wait for the event of the predicate being
incremented by another thread. If you do have exactly this case, the
semaphore is perfect match indeed. However, the problem is that this
case is rather rare in practice. Even most frequently provided example
of counting semaphore usage, an implementation of a FIFO queue, is
better served by condvar, as in practice the queue itself holds a state
that (a) needs a mutex to protect it, and (b) is natural predicate by
itself, rendering yet another integer predicate hidden in the semaphore
pure overhead.
Another possible use of semaphore, mutual exclusion, is better served by
mutex that is specifically designed for this exact purpose, except maybe
in those cases (that are in turn mostly design flaws) where locking is
performed for long time spans.
Overall, when one has condvars and mutexes, the usefulness of semaphores
is rather limited. On the other hand, when either condvars or mutexes
are not available, semaphores could serve as poor-man replacement for
both.
-- Sergei.
Giancarlo Niccolai
> Szabolcs Ferenczi <szabolcs...@gmail.com> writes:
> Except that it's condvar (+mutex +predicate) that is specifically
> designed for the purpose of signalling that an event has happened in one
> of the threads.
>
To my best knowledge, mutex + condvar wait are designed to tell a thread
that the result of the evaluation of a blocking predicate MAY have
changed (with respect to a previous check), because of an action in
another thread on the predicate determinants.
In other words, "signaling" (usually, broadcasting) a condition variable
means that there is a chance that one or more of the threads checking
the blocking predicate bound with the CV will find out that it is now
possible to proceed.
Different predicates require different condvars, even when they insists
on the same determinants (and so, require the same mutex).
It is very important to understand this semantic to use CVs correctly
and effectively.
"Events", in MT terminology, are interlocked and waitable variables that
can be in "set" or "reset" state; a "set" state means that "something
has happened", and requires attention of a service thread. It is
possible to implment events through a boolean variable, a mutex, a
condvar and a predicate checking the boolean variable, but the "event"
itself is not the condvar being signaled, but the boolean value being
changed.
Bests,
GN.
Markus Elfring
> semaphore in my posts?
Not "general". - You made it clear that you prefer semaphores for event
handling. I am interested in concrete reasons which make them more appropriate
for this purpose than other synchronisation primitives.
> The semaphore is the first general purpose synchronization tool for
> solving concurrency problems in the history of concurrent programming
> and this fact is widely acknowledged and agreed.---Except for the
> pseudo "experts" on comp.programming.threads who deny the obvious
> facts just for the enjoyment of opposing.
There is no disagreement on this history. We have got different opinions about
specific applications of the available means.
Regards,
Markus
Szabolcs Ferenczi
> > So, please tell me where can you see any general preference for the
> > semaphore in my posts?
>
> Not "general". - You made it clear that you prefer semaphores for event
> handling. I am interested in concrete reasons which make them more appropriate
> for this purpose than other synchronisation primitives.
Here is the concrete reason and a concrete code illustration:
<quote>
So, for instance, the semaphore is a very simple and general tool to
implement event handling (termed `event completion' in your third
reference link). Let us consider a simple case where one thread is
informing another about an event and the other is awaiting that
event.
With a semaphore, it is as simple as this:
sem_t event;
sem_init(&event, 0, 0);
...
observer:
...; sem_wait(&event); ...
signaler:
...; sem_post(&event); ...
Of course, we can solve the same problem with a shared flag but in
that case you additionally need two semaphores or a combination of a
mutex and a condition variable. Let us see the latter combination:
/*shared*/volatile char event = '0';
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t c = PTHREAD_COND_INITIALIZER;
...
observer:
...
pthread_mutex_lock(&m);
while (event != '1') pthread_cond_wait(&c, &m);
pthread_mutex_unlock(&m);
...
signaler:
...
pthread_mutex_lock(&m);
event = '1';
pthread_cond_signal(&c);
pthread_mutex_unlock(&m);
...
</quote>
http://groups.google.com/group/comp.programming.threads/msg/bc2c0a9dfe7b1655
As I asked you already, ask what can you not follow from the already
given simple example above. Which is the simpler solution to the same
problem from the application programming point of view?
Best Regards,
Szabolcs
Szabolcs Ferenczi
> > The semaphore is the first general purpose synchronization tool for
> > solving concurrency problems in the history of concurrent programming
> > and this fact is widely acknowledged and agreed.---Except for the
> > pseudo "experts" on comp.programming.threads who deny the obvious
> > facts just for the enjoyment of opposing.
>
> There is no disagreement on this history.
Oh yes, there is, as I said in the last sentence:
http://groups.google.com/group/comp.programming.threads/msg/2e4e4ad48d1f8dd7
Best Regards,
Szabolcs
Szabolcs Ferenczi
> Szabolcs Ferenczi <szabolcs.feren...@gmail.com> writes:
...
> > threads. For others the mutex and condition variable pair may be more
> > appropriate.
>
> Except that it's condvar (+mutex +predicate) that is specifically
> designed for the purpose of signalling that an event has happened in one
> of the threads.
You cannot prove that, of course. Nor can you give any reference to
support what you said (it is your mania asking for references, isn't
it). You can try, however, because so far it is a big blunder.
Homework for you: Please find in the concurrent programming litarature
(1) when was the semaphore invented and for what purpose, (2) when the
condition variable has been introduced and for what purpose.
It looks like you are mistaken by the fact that the condvar signal can
indicate that simething MIGHT happen. It does not guarantee it to you.
If you wait on a condvar and if the wait is finished you cannot be
sure that the expected event has happened.
The same is however works for the semaphore.
Best Regards,
Szabolcs
Chris Thomasson
On Apr 21, 10:10 pm, Markus Elfring <Markus.Elfr...@web.de> wrote:
> > > So, please tell me where can you see any general preference for the
> > > semaphore in my posts?
> >
> > Not "general". - You made it clear that you prefer semaphores for event
> > handling. I am interested in concrete reasons which make them more
> > appropriate
> > for this purpose than other synchronisation primitives.
> Here is the concrete reason and a concrete code illustration:
[...]
How would you use semaphores for signaling on a more "complex" predicate?
Lets go for a highly contrived pseudo-code example:
struct condition {
int event1;
int event2;
int event3;
};
void thread_a() {
for (;;) {
/* this thread_a is only interested in the following predicate:
(condition::event1 >= 5 &&
condition::event2 <= 3 &&
condition::event3 == 9)
*/
}
}
void thread_b() {
for (;;) {
/* this thread_b is only interested in the following predicate:
(condition::event1 == 12 &&
condition::event2 >= 3 &&
condition::event3 < 9)
*/
}
}
void thread_c() {
for (;;) {
/* this thread_c is only interested in the following predicate:
(condition::event1 == 1 &&
condition::event2 == 2 &&
condition::event3 == 3)
*/
}
}
Please show me exactly how you would handle this using semaphores?
This is trivial to solve using a single condition variable and
broadcasting...
Szabolcs Ferenczi
wrote:
> Dnia 15-04-2008, wto o godzinie 10:03 -0700, Szabolcs Ferenczi pisze:
>
> > The semaphore is a universal synchronization tool in concurrent
> > programming (see p.1 in your second reference) but the condition
> > variable is not one.
>
> No, it's the other way around. It's much easier to implement a semaphore
> using condition variables than to implement a condition variable using
> semaphores (implementing condition variables with busy waiting doesn't
> count in practice).
There is a general consensus among professionals (not among the self
made "experts" of comp.programming.threads, however) that the
semaphore is a general synchronisaton tool in concurrent programming.
If you open any book on concurrent programming or on operating
systems, you can find the same claim.
> This shows that condition variables are the basic
> and general tool, and semaphores is just one of its utilities.
Well, what is shows is that you missed some classes in concurrent
programming.
Best Regards,
Szabolcs
Markus Elfring
> given simple example above. Which is the simpler solution to the same
> problem from the application programming point of view?
The first approach looks simpler in your design sketch in the context of the
metric "line count".
Regards,
Markus
Ian Collins
> On Apr 16, 9:01 pm, Marcin ‘Qrczak’ Kowalczyk <qrc...@knm.org.pl>
> wrote:
>> Dnia 15-04-2008, wto o godzinie 10:03 -0700, Szabolcs Ferenczi pisze:
>>
>>> The semaphore is a universal synchronization tool in concurrent
>>> programming (see p.1 in your second reference) but the condition
>>> variable is not one.
>> No, it's the other way around. It's much easier to implement a semaphore
>> using condition variables than to implement a condition variable using
>> semaphores (implementing condition variables with busy waiting doesn't
>> count in practice).
>
> There is a general consensus among professionals (not among the self
> made "experts" of comp.programming.threads, however) that the
> semaphore is a general synchronisaton tool in concurrent programming.
> If you open any book on concurrent programming or on operating
> systems, you can find the same claim.
>
--
Ian Collins.
Chris Thomasson
Also, what about another threads c through N:
void threads_c_N(int state) {
for (;;) {
if (state == 0) {
/* this threads_c_N is only interested in the following predicate:
(condition::event1 == 1 &&
condition::event2 == 2 &&
condition::event3 == 3)
*/
} else if (state == 1) {
/* this threads_c_N is only interested in the following predicate:
(condition::event1 == 4 &&
condition::event2 == 5 &&
condition::event3 == 6)
*/
} else {
/* this threads_c_N is only interested in the following predicate:
(condition::event1 == 7 &&
condition::event2 == 8 &&
condition::event3 == 9)
*/
}
}
}
???
Dave Butenhof
OK, I'm generally really trying hard to avoid feeding the troll, but
this statement is just ridiculous.
The post you quote here makes no claims at all about history. It does
say that mutexes and condition variables provide a lower level (more
primitive) mechanism on which semaphores can be built. The fact that the
semaphore was invented first is irrelevant to this compositional
argument. That you're trying to warp the statement into some sort of
slight against history is further evidence that you're looking for
nothing but a fight.
You speak blithely of "facts", presumably to establish that you and only
you are the gatekeeper of true knowledge. Priestly, perhaps. But "facts"
are seldom obvious. Opinions are. When a lot of people in a generally
knowledgeable forum "deny your facts" you might devote some serious
meditation to the concept that your "facts" might just be opinions after
all. Conversely, if you really believe nobody here is knowledgeable,
tell me again exactly why you're wasting your time? Those who are
knowledgeable quite understandably interpret your attitude as empty
defensive blustering, because you've actually said nothing.
If you want to argue history, recognize that there's no argument. If you
want to argue "philosophy of synchronization", stop trying to bring
history into it because it's irrelevant. But if you just want to argue,
pointlessly and without result, you're sure on the right track.
Szabolcs Ferenczi
> OK, I'm generally really trying hard to avoid feeding the troll, but
> this statement is just ridiculous.
You should try it even harder.
Well, you should really try to refrain and do your work instead. You
must still demonstrate how you can use a single condition variable
instead of the semaphore for event signalling. When I said that it is
an error to communicate an event via condition variable (it was an
obvious error everyone could see it except for some self made expert),
you jumped into the middle of the discussion in a very low language:
"That's silly". Then you got your homework that you failed to complete
so far:
http://groups.google.com/group/comp.programming.threads/msg/7a0e9c383420d3fc
Try to figure it out and report it back when you are ready. I am
really curious about your solution, if any.
Best Regards,
Szabolcs
Szabolcs Ferenczi
wrote:
> There is a simple test to check whether somebody uses the condition
> variable in a correct way or not:
>
> CV TEST: Replace the wait operation with a mutex unlock/lock pair.
I can see that many readers have problems in understanding the role of
the condition variable. I am trying to help step by step.
Let us consider an example, where we have a mutex `m' that protects
some shared resource `r' and we have a condition variable (for
optimising the performance, i.e. to park the calling process when the
condition is not fulfilled to carry out the critical operation).
Would you use the `if' statement to check whether a condition holds on
the shared state space to do the critical operation `do_r' just like
the following fragment illustrates?
1: mutex m;
2: condvar c;
...
3: m.lock();
4: if (!B) c.wait(m); // be aware that `if' is wrong here
5: do_r();
6: m.unlock();
I hope not.
And why not?
Just because the wait on the condition variable might end with a
signal to the condition variable but that signal does not necessarily
mean that the condition `B' is true. The signal might come from a
broadcast on the condition variable. Not to mention the spurious
wakeups which are allowed by the specification.
Line 4 would not pass the CV_TEST.
So, how would you fix it?
7: m.lock();
8: while (!B) c.wait(m);
9: do_r();
10: m.unlock();
Now can you tell me what the thread is waiting for at line 8?
Is it waiting for a signal on `c'? No, it is not. Any signal received,
it is just ignored if condition `B' does not hold.
Is it waiting on condition `B'? Yes, it is. No matter how many times
the call `c.wait(m)' returns the waiting continues until condition `B'
becomes true. So, condition `B' is awaited.
You cannot use the condition variable for anything else but to hand
optimise a waiting loop on the shared state space inside a critical
region. Why? Because it has been invented just for that goal.
That is the background. The logic of the program waits on the boolean
condition `B' and not on the condition variable `c' which is just an
auxiliary aid there. It is there to optimise the busy waiting loop
`while (!B);'
But there is another side of the condition variable usage:
Actually, something else must be present for this construction (line
8) to work: When the shared resource is changed, there must be a
signal sent to the condition variable to wake the sleeping thread up
and make it re-check the condition `B'. It is a safe practice to issue
a broadcast on `c' whenever `r' is changed.
This simple CV_TEST is there just to call your attention that it is a
definite mistake to use the condition variable for anything else than
for waiting loop optimisation, e.g. for event signalling. This test,
on the other hand, does not detect the bug when you miss to issue
signals when due to a change of resource `r' the condition `B' might
become true. In fact this CV_TEST would give correct functionality if
you have that kind of a bug in your code.
Best Regards,
Szabolcs
Dave Butenhof
You're absolutely determined not to learn anything, aren't you? That's
really sad. But, fine. Your life. Go live it.
Oh, and I am doing my work. Which is why I've avoided wasting time
writing more responses to you. And, in particular, why I refuse to do
your homework for you.
Dave Butenhof
> On Apr 15, 12:08 am, Szabolcs Ferenczi <szabolcs.feren...@gmail.com>
> wrote:
>
>> There is a simple test to check whether somebody uses the condition
>> variable in a correct way or not:
>>
>> CV TEST: Replace the wait operation with a mutex unlock/lock pair.
>
> I can see that many readers have problems in understanding the role of
> the condition variable. I am trying to help step by step.
You consistently denigrate a condition variable for being what it is not
intended to be and should not be. You write as if you have no idea at
all what a predicate means, or how to maintain them using a mutex and
communicate regarding the state with the help of a condition variable.
Since I don't believe you're actually that ignorant, judging from some
of your other comments, I really have no idea what you're trying to
accomplish... except that it clearly can have nothing to do with "helping".
This is why I call you a troll; because I see no other feasible
explanation of your behavior.
Fine; so here I am, feeding the troll. It's late and I'm tired.
Chris Thomasson
> On Apr 16, 9:01 pm, Marcin ‘Qrczak’ Kowalczyk <qrc...@knm.org.pl>
> wrote:
> > Dnia 15-04-2008, wto o godzinie 10:03 -0700, Szabolcs Ferenczi pisze:
> >
> > > The semaphore is a universal synchronization tool in concurrent
> > > programming (see p.1 in your second reference) but the condition
> > > variable is not one.
> >
> > No, it's the other way around. It's much easier to implement a semaphore
> > using condition variables than to implement a condition variable using
> > semaphores (implementing condition variables with busy waiting doesn't
> > count in practice).
> There is a general consensus among professionals (not among the self
> made "experts" of comp.programming.threads, however)
Your the expert Sir.
> that the
> semaphore is a general synchronisaton tool in concurrent programming.
> If you open any book on concurrent programming or on operating
> systems, you can find the same claim.
Yeah. The semaphore synchronization primitive is a general tool indeed. How
can it be effectively used in the following contrived scenario:
http://groups.google.com/group/comp.programming.threads/msg/843592562151ee34
http://groups.google.com/group/comp.programming.threads/msg/9d41d4375ac5f7b1
???
Semaphores have their place...
> > This shows that condition variables are the basic
> > and general tool, and semaphores is just one of its utilities.
> Well, what is shows is that you missed some classes in concurrent
> programming.
Na. You fail to understand that semaphores are generally not all that useful
in "certain" scenarios. Condition variables can be applied to a wide range
of diverse complex predicates. If you try to apply semaphore(so) to a
complex/compound predicate, in a sense, you will only be re-inventing
various types of condition variable logic... Why would you want to do that?
Humm...
Markus Elfring
> 2: condvar c;
> ...
> 3: m.lock();
> 4: if (!B) c.wait(m); // be aware that `if' is wrong here
I hope that more (free) static source code analysis tools become available that
can detect the missing while loop.
http://findbugs.sourceforge.net/bugDescriptions.html#WA_NOT_IN_LOOP
> You cannot use the condition variable for anything else but to hand
> optimise a waiting loop on the shared state space inside a critical
> region. Why? Because it has been invented just for that goal.
I would like to point out once more that the semantics of the functions
"sem_post" and "pthread_cond_signal" are different on the mutual exlusion
effects. There are different sizes of lock scopes involved. Are further
clarifications of usage patterns needed?
> In fact this CV_TEST would give correct functionality if
> you have that kind of a bug in your code.
I would trust a powerful thread checker more than your incomplete approach.
Regards,
Markus
Alexander Terekhov
Szabolcs Ferenczi wrote:
[... "if (!B) c.wait(m); // be aware that `if' is wrong here" ...]
> You cannot use the condition variable for anything else but to hand
> optimise a waiting loop on the shared state space inside a critical
> region. Why? Because it has been invented just for that goal.
Uhmm. Regarding the history of condition variable invention you seem to
be somewhat misinformed. See
http://pages.cs.wisc.edu/~cs736-1/cs736.html/Papers/hoare-monitors.pdf
<quote>
In many cases, there may be more than one reason for waiting, and these
need to be distinguished by both the waiting and the signalling
operation. We therefore
introduce a new type of "variable" known as a "condition"; and the
writer of a {nonitor should declare a variable of type condition for
each reason why a program might have to wait. Then the wait and signal
operations should be preceded by the name of the
relevant condition variable, separated from it by a dot:
condvariable.wait;
condvariable.signal;
Note that a condition "variable" is neither true nor false; indeed, it
does not have any stored value accessible to the program. In practice, a
condition variable will be represented by an (initially empty) queue of
processes which are currently waiting on the condition; but this queue
is invisible both to waiters and signallers. This design of the
condition variable has been deliberately kept as primitive and
rudimentary as possible, so that it may' be implemented efficiently and
used flexibly to achieve a wide variety of effects. There is a great
temptation to introduce a more complex synchronization primitive, which
may be easier to use for many purposes. We shall resist this temptation
for a while.
As the simplest example of a monitor, we will design a scheduling
algorithm for a single resource, which is dynamically acquired and
released by an unknown number of customer processes by calls on
procedures
procedure acquire;
procedure release;
A variable 1 [1 As in PASCAL [15], a variable declaration is of the
form:
(variable identifier) : (type);]
busy: Boolean
determines whether or not the resource is in use. If an attempt is made
to acquire the resource when it is busy, the attempting program must be
delayed by waiting on a variable
nonbusy : condition
which is signalled by the next subsequent release. The initial value of
busy is false. These design decisions lead to the following code for the
monitor:
single resource:monitor
begin busy: Boolean;
nonbusy : condition;
procedure acquire;
begin if busy then nonbusy.wait;
busy : = true
end;
procedure release;
begin busy := false;
nonbusy.signal
end;
busy : = false; comment initial value;
end single resource
</quote>
It was not until a few years after invention of the condition variable
that it was optimized by MESA folks to get rid of "if" and require
waiters to reevaluate the predicates after wait() on condition variable.
http://www.cs.berkeley.edu/~brewer/cs262/Mesa.pdf
<quote>
4. Condition variables
In this section we discuss the precise semantics of WAIT and other
details associated with condition variables. Hoare’s definition of
monitors [8] requires that a process waiting on a condition variable
must run immediately when another process signals that variable, and
that the signaling process in turn runs as soon as the waiter leaves the
monitor. This definition allows the waiter to assume the truth of some
predicate stronger than the monitor invariant (which the signaler must
of course establish), but it requires several additional process
switches whenever a process continues after a WAIT. It also requires
that the signaling mechanism be perfectly reliable.
Mesa takes a different view: When one process establishes a condition
for which some other process may be waiting, it notifies the
corresponding condition variable. A NOTIFY is regarded as a hint to a
waiting process; it causes execution of some process waiting on the
condition to resume at some convenient future time. When the waiting
process resumes, it will reacquire the monitor lock. There is no
guarantee that some other process will not enter the monitor before the
waiting process. Hence nothing more than the monitor invariant may be
assumed after a WAIT, and the waiter must reevaluate the situation each
time it resumes. The proper pattern of code for waiting is therefore:
WHILE NOT <OK to proceed> DO WAIT c ENDLOOP.
This arrangement results in an extra evaluation of the <OK to proceed>
predicate after a wait, compared to Hoare’s monitors, in which the code
is:
IF NOT <OK to proceed> THEN WAIT c.
In return, however, there are no extra process switches, and indeed no
constraints at all on when the waiting process must run after a NOTIFY.
In fact, it is perfectly all right to run the waiting process even if
there is no NOTIFY, although this is presumably pointless if a NOTIFY is
done whenever an interesting change is made to the protected data.
It is possible that such a laissez-faire attitude to scheduling monitor
accesses will lead to unfairness and even starvation. We do not think
this is a legitimate cause for concern, since in a properly designed
system there should typically be no processes waiting for a monitor
lock. As Hoare, Brinch Hansen, Keedy, and others have pointed out, the
low level scheduling mechanism provided by monitor locks should not be
used to implement high level scheduling decisions within a system (for
example, about which process should get a printer next). High level
scheduling should be done by taking account of the specific
characteristics of the resource being scheduled (for example, whether
the right kind of paper is in the printer). Such a scheduler will delay
its client processes on condition variables after recording information
about their requirements, make its decisions based on this information,
and notify the proper conditions. In such a design the data protected by
a monitor is never a bottleneck.
The verification rules for Mesa monitors are thus extremely simple: The
monitor invariant must be established just before a return from an entry
procedure or a WAIT, and it may be assumed at the start of an entry
procedure and just after a WAIT. Since awakened waiters do not run
immediately, the predicate established before a NOTIFY cannot be assumed
after the corresponding WAIT, but since the waiter tests explicitly for
<OK to proceed>, verification is actually made simpler and more
localized.
Another consequence of Mesa’s treatment of NOTIFY as a hint is that many
applications do not trouble to determine whether the exact condition
needed by a waiter has been established. Instead, they choose a very
cheap predicate which implies the exact condition (for example, some
change has occurred), and NOTIFY a covering condition variable. Any
waiting process is then responsible for determining whether the exact
condition holds; if not, it simply waits again. For example, a process
may need to wait until a particular object in a set changes state. A
single condition covers the entire set, and a process changing any of
the objects broadcasts to this condition (see Section 4.1). The
information about exactly which objects are currently of interest is
implicit in the states of the waiting processes, rather than having to
be represented explicitly in a shared data structure. This is an
attractive way to decouple the detailed design of two processes: it is
feasible because the cost of waking up a process is small.
</quote>
regards,
alexander.
Sergei Organov
> Sergei Organov wrote:
>> Szabolcs Ferenczi <szabolcs...@gmail.com> writes:
>
>> Except that it's condvar (+mutex +predicate) that is specifically
>> designed for the purpose of signalling that an event has happened in one
>> of the threads.
>>
>
> To my best knowledge, mutex + condvar wait are designed to tell a thread
> that the result of the evaluation of a blocking predicate MAY have
> changed (with respect to a previous check), because of an action in
> another thread on the predicate determinants.
Yes, sure. How it is not an "event"? "Event" in this case means
"something relevant to predicate associated with this condvar happened".
> In other words, "signaling" (usually, broadcasting) a condition variable
> means that there is a chance that one or more of the threads checking
> the blocking predicate bound with the CV will find out that it is now
> possible to proceed.
Yes, you basically signal an event of changing the predicate. It doesn't
mean that another thread will find the predicate in required state, so
checking of predicate is still required.
> Different predicates require different condvars, even when they insists
> on the same determinants (and so, require the same mutex).
Not necessarily. I fail to see what prevents from using the same
condvar for different predicates. IMHO it's more a question of
particular design and efficiency than of correctness.
> It is very important to understand this semantic to use CVs correctly
> and effectively.
Sure.
>
> "Events", in MT terminology, are interlocked and waitable variables that
> can be in "set" or "reset" state; a "set" state means that "something
> has happened", and requires attention of a service thread.
This specific primitive called "event" with its rather special semantics
is not what I meant. I've used the word "event" in its generic meaning.
You see, "event" you are referring to can't "happen". It's just a
primitive that can be "set" or "reset". Yes this primitive is indeed
designed to signal events, but no more or less so than condvars are.
-- Sergei.
Sergei Organov
> On Apr 21, 8:57 pm, Sergei Organov <o...@javad.com> wrote:
>> Szabolcs Ferenczi <szabolcs.feren...@gmail.com> writes:
> ...
>> > One of them is signaling that an event has happened in one of the
>> > threads. For others the mutex and condition variable pair may be more
>> > appropriate.
>>
>> Except that it's condvar (+mutex +predicate) that is specifically
>> designed for the purpose of signalling that an event has happened in one
>> of the threads.
>
> You cannot prove that, of course. Nor can you give any reference to
> support what you said (it is your mania asking for references, isn't
> it). You can try, however, because so far it is a big blunder.
Yes, I can try, but I won't care until I see at least one reference that
supports your vision. However, you can try to google for "condition
variable event signaling" yourself, -- you'll get *plenty* of
references.
> Homework for you: Please find in the concurrent programming litarature
> (1) when was the semaphore invented and for what purpose, (2) when the
> condition variable has been introduced and for what purpose.
Well, I thought we discuss current state of the art, making historic
arguments rather irrelevant. No matter when and what for condvars were
introduced, nowadays they are considered to be generic event signaling
mechanism. Welcome to the 21'st century.
[BTW, did you do your homework and came-up with an example program where
condition variable is not just an "optimization", or did you fail?]
> It looks like you are mistaken by the fact that the condvar signal can
> indicate that simething MIGHT happen. It does not guarantee it to you.
Sure I do understand that. Where did I say otherwise?
> If you wait on a condvar and if the wait is finished you cannot be
> sure that the expected event has happened.
Sure, but I fail to see how it violates what I said. Condvar is
*generic* event signaling mechanism. What constitutes *particular*
event is determined by the predicate associated with condvar. Therefore,
you need to check the predicate to determine if "event" you are waiting
for is indeed happened.
Overall, when used correctly, condvar is generic event signaling
mechanism. When used incorrectly it is nothing good, similar to any
other incorrectly used primitive out there. Telling us again and again
that incorrect use of condvar doesn't achieve event signaling leads you
nowhere.
-- Sergei.
Sergei Organov
[...]
> This simple CV_TEST is there just to call your attention that it is a
> definite mistake to use the condition variable for anything else than
> for waiting loop optimisation, e.g. for event signalling.
The irony is that it's used inside the loop exactly for waiting for
event, and in another thread exactly for event signaling. Therefore,
what you actually proved is that the only correct use of condvar is for
event waiting and signaling. I don't think anybody but you consider this
usage to be "loop optimization", sorry.
-- Sergei.
Szabolcs Ferenczi
...
> You consistently denigrate a condition variable for being what it is not
> intended to be and should not be.
To be exact, I make the role of the condition variable clear, whereas
you have no idea why and when this concept has been introduced. You
know something about Pthreads and you believe that there was nothing
before Pthreads. At the most you heard something about some monitor
but you do not exactly know what it is.
Well, the role of the condition variable is nothing else but to make a
busy waiting loop less resource consuming. It must be clear to anyone
who is capable of thinking on his own since I have deduced it here
step by step. Others can be educated in concurrent programming well
enough and they know it already.
It is explained by the many code fragments I have shown you already
but which you apparently cannot follow. They are a couple of lines,
though.
http://groups.google.com/group/comp.programming.threads/msg/f3a4fd9e3ec0eb1f
Oh yes, the hybris is hybris.
> You write as if you have no idea at
> all what a predicate means, or how to maintain them using a mutex and
> communicate regarding the state with the help of a condition variable.
Well, in this context a predicate belongs to the business logic of the
program whereas the condition variable is just a performance sugar on
it. The logic must work without the condition variable, as I have
demonstrated. If it does not work without the condition variable, you
have made a buggy program.
I tried to explain it to you step by step in the post you just reacted
to but which you apparently were not able to follow. That you could
not follow it is clear from your hysteria.
> Fine; so here I am, feeding the troll. It's late and I'm tired.
Please stop trolling.
If you do not understand something, do not hesitate to ask it. I am
willing to help. Especially when I see that someone really needs help.
Best Regards,
Szabolcs
Giancarlo Niccolai
>
> Please stop trolling.
>
> If you do not understand something, do not hesitate to ask it. I am
> willing to help. Especially when I see that someone really needs help.
>
ROTFL
You're great, really! Can I hire you for my birthday party?
GN.
Markus Elfring
> you have no idea why and when this concept has been introduced. You
> know something about Pthreads and you believe that there was nothing
> before Pthreads. At the most you heard something about some monitor
> but you do not exactly know what it is.
Is a little competition going on between synchronisation primitives here?
Regards,
Markus
Szabolcs Ferenczi
...
> I hope that more (free) static source code analysis tools become available that
> can detect the missing while loop.http://findbugs.sourceforge.net/bugDescriptions.html#WA_NOT_IN_LOOP
Let us hope so. Furthermore I hope that there will be decent
concurrent programming languages soon available where the compiler can
support you preventing many basic programming errors that are possible
now with the pure library approaches.
The CV_TEST is just a memento for you to prevent this kind of error in
the first place (i.e. to use it just like a semaphore). You must know
something about concurrent programming already before you submit your
program to any checker. This property of the condition variable simply
must be known by everyone using it.
> > You cannot use the condition variable for anything else but to hand
> > optimise a waiting loop on the shared state space inside a critical
> > region. Why? Because it has been invented just for that goal.
>
> I would like to point out once more that the semantics of the functions
> "sem_post" and "pthread_cond_signal" are different on the mutual exlusion
> effects.
So much quite different that with the semaphore you can implement
mutual exclusion effect whereas the condition variable is only a
performance optimisation means in order to be able to wait inside a
mutual exclusion area without wasting resources.
I can refer you to your own reference what you have copied here in:
http://groups.google.com/group/comp.programming.threads/msg/f8d3f15718868fa2
I have quoted it for you from your own reference:
<quote>
See also p.6 in your second reference link:
"Important: Condition variables != Semaphores
Don't be confused by the fact that both support wait() and
signal() operations --- the operations have different meanings
However, they can be used to implement each other (and both can
be implemented in terms of test&set, disabling interrupts. etc.)"
</quote>
http://www.cs.utah.edu/classes/cs5460-regehr/lecs/lec12.pdf
Question: Are you reading at all what I am answering to your
questions?
> There are different sizes of lock scopes involved. Are further
> clarifications of usage patterns needed?
Yes, please. What are the sizes of the scopes? What lock scopes? Are
you going to do locking with condition variables? Do not do that, you
will not pass the CV_TEST.
Best Regards,
Szabolcs
Dave Butenhof
It's true; clowns are almost universally loved, aren't they? I wonder if
he makes balloon animals?
Markus Elfring
> concurrent programming languages soon available where the compiler can
> support you preventing many basic programming errors that are possible
> now with the pure library approaches.
Does the programming language from the book "Foundations of Multithreaded,
Parallel, and Distributed Programming" by Gregory R. Andrews fit to your
expectations?
http://www.cs.arizona.edu/mpd/
> So much quite different that with the semaphore you can implement
> mutual exclusion effect whereas the condition variable is only a
> performance optimisation means in order to be able to wait inside a
> mutual exclusion area without wasting resources.
I do not see it as an "optimisation". The temporary release of the associated
lock for the waiting is a fundamental design aspect of the Pthread API.
> http://www.cs.utah.edu/classes/cs5460-regehr/lecs/lec12.pdf
>
> Question: Are you reading at all what I am answering to your questions?
Yes, of course.
It seems that we can cherry-pick from this reference what fits best for either
argumentation in our discussion.
> Yes, please. What are the sizes of the scopes? What lock scopes?
I try to clarify the different usage patterns from my view.
The POSIX thread interface provides lock and unlock functions for the mutex
implementation. Unlocking of critical sections is also performed by the function
"sem_post". This mutex is similar to a binary semaphore.
A semaphore manages a counter already while a mutex keeps only a flag. This API
does not provide the function "sem_signal" while there is a
"pthread_cond_signal()". The condition signal/notification has got the property
that the corresponding mutex remains locked while a "post" has got other effects.
> Are you going to do locking with condition variables?
> Do not do that, you will not pass the CV_TEST.
I have got the impression that your testing procedure will need a general
adjustment. An other wording might help more to achieve your goal.
There are more interesting use cases from the approach of mutual exclusion
algorithm discovery.
http://bardavid.com/mead/
Regards,
Markus
Luke Elliott
Maybe you have a standout candidate for the last question from
http://www.thinkingparallel.com/2007/04/11/ten-questions-with-david-butenhof-about-parallel-programming-and-posix-threads/
now?!
Szabolcs Ferenczi
> Parallel, and Distributed Programming" by Gregory R. Andrews fit to your
> expectations?http://www.cs.arizona.edu/mpd/
Our concern here is the misuse vs the correct use of the condition
variable. MPD has not anyhing to do with condition variables, has it?
See your own reference again:
"...MPD supports the same variety of concurrent programming mechanisms
as SR: co statements, semaphores, call/send/forward invocations, and
receive and input statements."
http://www.cs.arizona.edu/mpd/language.html
> > So much quite different that with the semaphore you can implement
> > mutual exclusion effect whereas the condition variable is only a
> > performance optimisation means in order to be able to wait inside a
> > mutual exclusion area without wasting resources.
>
> I do not see it as an "optimisation".
So you don't see it as an "optimisation". Good. Let us try it even
harder. I have written a simple single threaded algorithm for you. You
are invited to follow it. Please try to honestly answer my questions
and at the end we can see whether it is an optimisation or not:
Let us have critical operation 'S' on a shared state space. Operation
`S' is allowed to be preformed only if predicate `B' on the shared
state space yields true. Note that predicate `B' can be made true by
some other thread performing critical operation `Q' at some
unpredictable point of time {m.lock(); Q; m.unlock();}.
1. Do you think this logic would work?
m.lock();
while (!B) {m.unlock(); m.lock();}
S;
m.unlock();
A: yes
B: yes but it will be very inefficient
C: yes but I would never solve it like that
D: yes but I do not see cv as an "optimisation"
E: no
F: don't know
If your answer is 1.A or 1.B or 1.C or 1.D go to 2 else explain why
did you choose 1.E and go to 7.
2. Would the busy waiting loop mean any problem provided the thread
would be performed as the only one on a dedicated processing element,
i.e. the PE would not have anything else to do?
A: yes
B: no
C: no but it is not a realistic situation
D: no but still I do not see cv as an "optimisation"
E: don't know
If your answer is 2.B or 2.C or 2.D go to 3 else explain why did you
choose 2.A and go to 7.
3. What is the problem, if the PE has other concurrent activities to
do as well?
A: nothing
B: busy waiting loop consumes valuable processing power
C: busy waiting loop consumes valuable processing power but I do
not see cv as an "optimisation"
D: don't know
If your answer is 3.B or 3.C go to 4 else explain why did you choose
3.A and go to 7.
4. Does argument 3.B apply to the following modified code?
m.lock();
while (!B) c.wait(); // also {m.lock(); Q; c.signal(); m.unlock();}
S;
m.unlock();
A: yes
B: no
C: don't know
If your answer is 4.B go to 5 else explain why did you choose 4.A and
go to 7.
5. Does the business logic of code (1) and code (4) differ in anything
but (4) is more efficient?
A: yes
B: no
C: don't know
If your answer is 5.B go to 6 else explain why did you choose 5.A and
go to 7.
6. Congratulations! You have got the idea. Now you do see the cv as an
optimisation, don't you? Finished.
7. Otherwise we will see your specific problem explained at the
relevant question.
> The temporary release of the associated
> lock for the waiting is a fundamental design aspect of the Pthread API.
The temporary release is taken care of the test, of course, see:
#ifdef CV_TEST
m.unlock();
m.lock();
#else
c.wait(m);
#endif
Best Regards,
Szabolcs
Markus Elfring
It was a simple suggestion for a programming language that has got built-in
support for concurrent software development. Do you know any better or more
sophisticated tools?
> 1. Do you think this logic would work?
> m.lock();
> while (!B) {m.unlock(); m.lock();}
> S;
> m.unlock();
A: yes
> 2. Would the busy waiting loop mean any problem provided the thread
> would be performed as the only one on a dedicated processing element,
> i.e. the PE would not have anything else to do?
D: no
> 3. What is the problem, if the PE has other concurrent activities to
> do as well?
C: busy waiting loop consumes valuable processing power
> 4. Does argument 3.B apply to the following modified code?
> m.lock();
> while (!B) c.wait(); // also {m.lock(); Q; c.signal(); m.unlock();}
> S;
> m.unlock();
C: don't know because I can not see the implementation or characteristics of
"wait()" that you expect here.
http://en.wikipedia.org/wiki/Busy_waiting#Alternatives_to_busy_waiting
Regards,
Markus
Szabolcs Ferenczi
> > 4. Does argument 3.B apply to the following modified code?
> > m.lock();
> > while (!B) c.wait(); // also {m.lock(); Q; c.signal(); m.unlock();}
> > S;
> > m.unlock();
>
> C: don't know because I can not see the implementation or characteristics of
> "wait()" that you expect here.
> http://en.wikipedia.org/wiki/Busy_waiting#Alternatives_to_busy_waiting
Try to guess it.
Hint: Try to think on e.g. pthread_cond_wait if you have basic
problems with abstractions.
I could not imagine that anyone would blame himself with the answer
"don't know".
I expected that you have enough professional experience that you are
able to follow simple things like that. Would you like me to explain
the dot (".") in front of the "wait()" tag as well? How about
understanding the semicolon (";") in programming languages? Well, not
all programming languages use the semicolon either. Are you confident
with interpreting the semicolon?
Well, you cannot see the implementation or the characteristic of the
"wait()". Hmmm... I did not expect someone will be unable to follow a
simple piece of code like that and select "don't know" by which he
admits a kind of an incompetence.
Well, instead of a pointer to some junk Wikipedia page (even my son is
not allowed to refer to Wikipedia at the elementary school), you could
have used your intelligence and guess some semantics for the "wait()".
It is not so difficult, is it? Do you really mean you cannot
understand a simple thing like that? Now I start to realize why you
could simply not understand the original idea that I was trying to
explain by simple example.
You could almost complete it but just failed before the target. It is
your problem, every intelligent reader can realize it.
It is a general truth that there must be two parties in every
communication. No matter how hard one is trying to tell if the other
party is not willing to follow simple steps.
I am sure, though, that you and everyone else got the idea now. It is
simple cannot be that hard to understand something that is explained
at an elementary level like that.
Best Regards,
Szabolcs
Chris Thomasson
On Apr 24, 8:04 pm, Markus Elfring <Markus.Elfr...@web.de> wrote:
> > 4. Does argument 3.B apply to the following modified code?
> > m.lock();
> > while (!B) c.wait(); // also {m.lock(); Q; c.signal(); m.unlock();}
> > S;
> > m.unlock();
>
> C: don't know because I can not see the implementation or characteristics
> of
> "wait()" that you expect here.
> http://en.wikipedia.org/wiki/Busy_waiting#Alternatives_to_busy_waiting
> Try to guess it.
[...]
TRY to read this paper:
http://pages.cs.wisc.edu/~cs736-1/cs736.html/Papers/hoare-monitors.pdf
Your history is flawed, your assertion that condition variables cannot be
used for events is fundamentally flawed, your assertion that condition
variables are only an optimization is flawed. Your wrong on multiple fronts;
got it? Anyway, I challenged you to provide a simple solution to the
following contrived basic problem:
http://groups.google.com/group/comp.programming.threads/msg/843592562151ee34
http://groups.google.com/group/comp.programming.threads/msg/9d41d4375ac5f7b1
I know how to solve it with condition variables and semaphores; big deal. I
am only interested if you know how to do it. Humm... I have my doubts! You
insult others so easily. Please Sir, the next time you insult somebody
PLEASE be sure to stare into a clean mirror as you do it, at least then you
will be correct!
:^|
Szabolcs Ferenczi
> Szabolcs Ferenczi <szabolcs.feren...@gmail.com> writes:
>
> [...]
>
> > This simple CV_TEST is there just to call your attention that it is a
> > definite mistake to use the condition variable for anything else than
> > for waiting loop optimisation, e.g. for event signalling.
>
> The irony is that it's used inside the loop exactly for waiting for
> event,
Hmmm... The irony is that you wait for what you express in your code,
that is condition B and not any condition variable:
while (!B) /* wait more */;
The condition variable only implements a waiting that does not consume
computing resources:
while (!B) cv.wait();
Still you are waiting for condition `B' and not for the condition
variable `c' in your program logic.
> and in another thread exactly for event signaling.
"A NOTIFY is regarded as a hint to a waiting process;"
See Alexander Terekhov's copy-paste text:
http://groups.google.com/group/comp.programming.threads/msg/584954ee104e9722
Szabolcs Ferenczi
> Therefore,
> what you actually proved is that the only correct use of condvar is for
> event waiting and signaling.
Negative. You cannot signal an event with help of a condition
variable. The wait of the condition variable is technically incapable
of indicating it to you that you have given a signal to that variable.
Check the documentation of the wait operation of the condition
variable of your thread library.
If you try to communicate an event with the condition variable, you
will fail the CV_TEST. If you fail the CV_TEST, your program is buggy.
Chris Thomasson
On Apr 22, 1:00 pm, Sergei Organov <o...@javad.com> wrote:
> Szabolcs Ferenczi <szabolcs.feren...@gmail.com> writes:
>
> [...]
>
> > This simple CV_TEST is there just to call your attention that it is a
> > definite mistake to use the condition variable for anything else than
> > for waiting loop optimisation, e.g. for event signalling.
>
> The irony is that it's used inside the loop exactly for waiting for
> event,
> Hmmm... The irony is that you wait for what you express in your code,
> that is condition B and not any condition variable:
> while (!B) /* wait more */;
> The condition variable only implements a waiting that does not consume
> computing resources:
[...]
The condition variable MUST be used in conjunction with a MUTEX and a
PREDICATE. They all work together. The PREDICATE is the VARIABLE part of the
CONDITION. GOT IT!
ARGH!
Chris Thomasson
On Apr 22, 1:00 pm, Sergei Organov <o...@javad.com> wrote:
...
> > Therefore,
> > what you actually proved is that the only correct use of condvar is for
> > event waiting and signaling.
> Negative. You cannot signal an event with help of a condition
> variable. The wait of the condition variable is technically incapable
> of indicating it to you that you have given a signal to that variable.
> Check the documentation of the wait operation of the condition
> variable of your thread library.
> If you try to communicate an event with the condition variable, you
> will fail the CV_TEST. If you fail the CV_TEST, your program is buggy.
YOU COMMUNICATE AN EVENT WITH THE PREDICATE, MUTEX ___AND___ CONDVAR! They
all work together. I am so close to PLONKING YOU!
One problem with plonking you... I cannot help any newbie's that may read
your garbage and think its correct in any sense of the term.
;^/
Markus Elfring
I try to be very careful about assuming too much details so that
misinterpretations are avoidable.
> Hint: Try to think on e.g. pthread_cond_wait if you have basic
> problems with abstractions.
Thanks for this clarification.
Regards,
Markus
Szabolcs Ferenczi
> Szabolcs Ferenczi wrote:
...
> > You cannot use the condition variable for anything else but to hand
> > optimise a waiting loop on the shared state space inside a critical
> > region. Why? Because it has been invented just for that goal.
>
> Uhmm. Regarding the history of condition variable invention you seem to
> be somewhat misinformed. See
>
> http://pages.cs.wisc.edu/~cs736-1/cs736.html/Papers/hoare-monitors.pdf
Very good. At least you try to do the work for the others. Do you
think I am misinformed? Uhmm. Did you go back as far as Hoare's
monitor paper? Is that the first publication about the monitor
concept? Anyway, good work. Well done.
At least you start to realize that concurrent programming is not
started with Pthreads. There was life in concurrent programming before
Pthreads and Java.
But unfortunately it is so far inadequate as an effort to locate why
and when the condition variable was introduced.
You must go even further back. Check how the monitor was invented.
What was the motivation? Check what language elements has been
proposed before the monitor. What problems were attempted to be solved
by the monitor concept? What was the advantage and what was the
drawback of the previous language elements? (Hint: Look for
Conditional Critical Regions.)
Let us see what you can find out.
If you cannot manage with it, please let me know about it and I will
help you.
Best Regards,
Szabolcs
Chris Thomasson
> > On Apr 22, 10:58 am, Alexander Terekhov <terek...@web.de> wrote:
> > Szabolcs Ferenczi wrote:
> ...
> > > You cannot use the condition variable for anything else but to hand
> > > optimise a waiting loop on the shared state space inside a critical
> > > region. Why? Because it has been invented just for that goal.
> >
> > Uhmm. Regarding the history of condition variable invention you seem to
> > be somewhat misinformed. See
> >
> > http://pages.cs.wisc.edu/~cs736-1/cs736.html/Papers/hoare-monitors.pdf
> Very good. At least you try to do the work for the others. Do you
> think I am misinformed? Uhmm. Did you go back as far as Hoare's
> monitor paper? Is that the first publication about the monitor
> concept? Anyway, good work. Well done.
> At least you start to realize that concurrent programming is not
> started with Pthreads. There was life in concurrent programming before
> Pthreads and Java.
Who stated otherwise Sir?
> But unfortunately it is so far inadequate as an effort to locate why
> and when the condition variable was introduced.
> You must go even further back. Check how the monitor was invented.
> What was the motivation? Check what language elements has been
> proposed before the monitor. What problems were attempted to be solved
> by the monitor concept? What was the advantage and what was the
> drawback of the previous language elements? (Hint: Look for
> Conditional Critical Regions.)
> Let us see what you can find out.
> If you cannot manage with it, please let me know about it and I will
> help you.
Ummm... Alexander Terekhov is a very smart individual... I advise against
insulting his intelligence.
Alexander Terekhov
Based on your "hint" about conditional critical regions, it appears that
the source of your confusion regarding "busy waiting" is this:
http://brinch-hansen.net/papers/1972a.pdf
"All processes waiting for one condition or another on variable v enter
the same event queue. When another process (here called the producer)
changes v by a statement S2 inside a critical region, it is possible
that one or more of the conditions expected by processes in the event
queue will be satisfied. So, after completion of a critical region, all
processes in the event queue Qe are transferred to the main queue Qv to
enable them to reenter their critical regions and inspect the shared
variable v again.
It is possible that a consumer will be transferred in vain between Qv
and Qe several times before its condition B holds. But this can only
occur as frequently as producers change the shared variable. This
controlled amount of busy waiting is the price we pay for the conceptual
simplicity achieved by using arbitrary Boolean expressions as
synchronizing conditions."
But what you're missing is the fact that you can have exact same sort of
"busy waiting" using real POSIX condition variables too (e.g. when
associating multiple predicates with one condition variable).
regards,
alexander.
Szabolcs Ferenczi
Very good again. The young forum troller is right, you are good. Now,
at least, you could get very close to the solution.
The issue is that the Conditional Critical Region is Hoare's invention
(Towards a Theory of Parallel Programming, 1971). That was regarded to
be very inefficient and Brinch Hansen has introduced the queueing
variable in the article you have found. Later on he says:
"The major concern was that it did not seem possible to implement
conditional critical regions effciently. The root of the problem is
the unbounded reevaluation of Boolean expressions until they are true.
...
I suggested that programmers should be able to associate secure
queueing variables with shared data structures and control the
transfers of processes to and from them."
THE INVENTION OF CONCURRENT PROGRAMMING
http://brinch-hansen.net/papers/2002b.pdf
When they (Brinch Hansen and Hoare) introduced the monitor concept (in
1973-74), they additionally solved the locality and encapsulation of
the shared resources and the handling procedures. The long term
process scheduling tools, however, were already there (queueing
variables). Hoare has renamed the queueing variable a condition
variable.
There we are. You at least did the job. Good work.
> But what you're missing is the fact that you can have exact same sort of
> "busy waiting" using real POSIX condition variables too (e.g. when
> associating multiple predicates with one condition variable).
It is not the question here how many ways you can do "busy waiting".
The point is that what construction you mimic with the mutex and
condition variable pair is essentially a hand built Conditional
Critical Region. Especially it is true for the procedural libraries
just like the Pthreads.
The other side of he story is that from the same building blocks, i.e.
from the mutex and condition variable, you can hand build a Monitor
construction as well.
None of the hand build versions, however, substitute the Conditional
Critical Region or the Monitor at the language level. It looks like
that the next successful multi-threaded language must have them at
language level. Since today, it is already possible to implement the
Conditional Critical Region efficiently.
Best Regards,
Szabolcs
David Schwartz
wrote:
> Negative. You cannot signal an event with help of a condition
> variable. The wait of the condition variable is technically incapable
> of indicating it to you that you have given a signal to that variable.
> Check the documentation of the wait operation of the condition
> variable of your thread library.
> If you try to communicate an event with the condition variable, you
> will fail the CV_TEST. If you fail the CV_TEST, your program is buggy.
For some reason, this is one thing that you are simply incapable of
understanding. You are wrong and everybody else is right. It has been
patiently explained to you many times, and for some strange reason you
actively refuse to understand it. At this point, I don't know what
else can be done.
You say things that are manifestly false. For example, "You cannot
signal an event with help of a condition variable". This is precisely
what a condition variable does. Yes, you cannot signal an event
reliably with just a condition variable, but you can signal an event
with the help of a condition variable. (And this is precisely what
condition variables are intended for, signalling events.)
Further, condition variables don't optimize anything nor are they
intended to optimize anything. Yes, you can write code that does the
same thing as a condition variable just much, MUCH worse. But nobody
would ever need to optimize such code because nobody would ever write
such code in the first place, except perhaps an example of how bad
code can be written.
DS
Chris Thomasson
On Apr 25, 12:18 am, Alexander Terekhov <terek...@web.de> wrote:
> > Szabolcs Ferenczi wrote:
> >
> > > On Apr 22, 10:58 am, Alexander Terekhov <terek...@web.de> wrote:
> > > > Szabolcs Ferenczi wrote:
> > > ...
> > > > > You cannot use the condition variable for anything else but to
> > > > > hand
> > > > > optimise a waiting loop on the shared state space inside a
> > > > > critical
> > > > > region. Why? Because it has been invented just for that goal.
> >
> > > > Uhmm. Regarding the history of condition variable invention you seem
> > > > to
> > > > be somewhat misinformed. See
> >
> > > >http://pages.cs.wisc.edu/~cs736-1/cs736.html/Papers/hoare-monitors.pdf
> >
> > > Very good. At least you try to do the work for the others. Do you
> > > think I am misinformed? Uhmm. Did you go back as far as Hoare's
> > > monitor paper? Is that the first publication about the monitor
> > > concept? Anyway, good work. Well done.
> >
> > > Let us see what you can find out.
> >
> > > If you cannot manage with it, please let me know about it and I will
> > > help you.
> >
> > Based on your "hint" about conditional critical regions, it appears that
> > the source of your confusion regarding "busy waiting" is this:
> >
> > http://brinch-hansen.net/papers/1972a.pdf
> >
[...]
> > But what you're missing is the fact that you can have exact same sort of
> > "busy waiting" using real POSIX condition variables too (e.g. when
> > associating multiple predicates with one condition variable).
> It is not the question here how many ways you can do "busy waiting".
> The point is that what construction you mimic with the mutex and
> condition variable pair is essentially a hand built Conditional
> Critical Region. Especially it is true for the procedural libraries
> just like the Pthreads.
> The other side of he story is that from the same building blocks, i.e.
> from the mutex and condition variable, you can hand build a Monitor
> construction as well.
> None of the hand build versions, however, substitute the Conditional
> Critical Region or the Monitor at the language level. It looks like
> that the next successful multi-threaded language must have them at
> language level. Since today, it is already possible to implement the
> Conditional Critical Region efficiently.
I advise _you_, and _you_ alone, to never program with POSIX Threads. You
already tried to use semaphores:
http://groups.google.com/group/comp.lang.c++/browse_frm/thread/8f21ab45c5d72a03
Dmitriy V'jukov pointed out a race-condition:
http://groups.google.com/group/comp.lang.c++/msg/ededaff354ed5791
You ignorantly flamed him:
http://groups.google.com/group/comp.lang.c++/msg/6f0753ab14272322
And he was correct all along:
http://groups.google.com/group/comp.lang.c++/msg/c96012abdb2f4b7d
Sounds like exact same problem your having now... Your right and everybody
else is wrong... Your the expert.
:^|
Sergei Organov
> On Apr 22, 1:00 pm, Sergei Organov <o...@javad.com> wrote:
>> Szabolcs Ferenczi <szabolcs.feren...@gmail.com> writes:
>>
>> [...]
>>
>> > This simple CV_TEST is there just to call your attention that it is a
>> > definite mistake to use the condition variable for anything else than
>> > for waiting loop optimisation, e.g. for event signalling.
>>
>> The irony is that it's used inside the loop exactly for waiting for
>> event,
>
> Hmmm... The irony is that you wait for what you express in your code,
> that is condition B and not any condition variable:
>
> while (!B) /* wait more */;
>
> The condition variable only implements a waiting that does not consume
^^^^^^^ Waiting for *what*?
Almost everybody seem to call those *what* "an event". If you don't
agree with this widely adopted terminology, it's your own problem,
sorry.
> computing resources:
>
> while (!B) cv.wait();
>
> Still you are waiting for condition `B' and not for the condition
> variable `c' in your program logic.
The whole loop waits for condition 'B' to become true indeed; the
cv.wait() inside the loop waits for event. Therefore, 'cv' is used
exactly to wait for event. If you can't grok this perfect simplicity, I
give up.
-- Sergei.
Szabolcs Ferenczi
> Szabolcs Ferenczi <szabolcs.feren...@gmail.com> writes:
> > On Apr 22, 1:00 pm, Sergei Organov <o...@javad.com> wrote:
> >> Szabolcs Ferenczi <szabolcs.feren...@gmail.com> writes:
>
> >> [...]
>
> >> > This simple CV_TEST is there just to call your attention that it is a
> >> > definite mistake to use the condition variable for anything else than
> >> > for waiting loop optimisation, e.g. for event signalling.
>
> >> The irony is that it's used inside the loop exactly for waiting for
> >> event,
>
> > Hmmm... The irony is that you wait for what you express in your code,
> > that is condition B and not any condition variable:
>
> > while (!B) /* wait more */;
>
> > The condition variable only implements a waiting that does not consume
>
> ^^^^^^^ Waiting for *what*?
Waiting for *what*?---you ask. Obvious: Waiting for predicate `B' to
become true. That is the condition for the process to proceed, nothing
else.
> Almost everybody seem to call those *what* "an event". If you don't
> agree with this widely adopted terminology, it's your own problem,
> sorry.
Noone, who is reasonable enough, calls that an event. I am afraid you
can be really sorry not being able follow simple things like this.
The condition variable makes the waiting just optimal with respect to
using computing cycles. That was the reason the condition variable has
been introduced in the history of concurrent programming.
> > computing resources:
>
> > while (!B) cv.wait();
>
> > Still you are waiting for condition `B' and not for the condition
> > variable `c' in your program logic.
>
> The whole loop waits for condition 'B' to become true indeed; the
> cv.wait() inside the loop waits for event.
Would you be surprised to learn that cv.wait() can return legally so
that there is no `event' in the sense you are trying to understand it?
Because it is true that cv.wait() can legally return immediately
without having received any signal at all.
Hence caring about CV_TEST helps you to write correct programs,
whether you are sorry or not.
Best Regards,
Szabolcs
Markus Elfring
> can be really sorry not being able follow simple things like this.
Do you like the wording about a potential state change in shared variables more?
> The condition variable makes the waiting just optimal with respect to
> using computing cycles. That was the reason the condition variable has
> been introduced in the history of concurrent programming.
Are you interested in news on recent software development for generic semaphores
in the Linux kernel?
http://lwn.net/Articles/273731/
> Would you be surprised to learn that cv.wait() can return legally so
> that there is no `event' in the sense you are trying to understand it?
> Because it is true that cv.wait() can legally return immediately
> without having received any signal at all.
Which specification would handle spurious wakeups better in your terminology?
Regards,
Markus
David Schwartz
wrote:
> Would you be surprised to learn that cv.wait() can return legally so
> that there is no `event' in the sense you are trying to understand it?
> Because it is true that cv.wait() can legally return immediately
> without having received any signal at all.
This argument is complete nonsense. If I leave for lunch at noon, does
this prove I wasn't waiting for a phone call at eleven o'clock? Or can
you prove I wasn't waiting for a phone call because I left when the
fire alarm went off? We are "waiting for" anything that can cause us
to stop waiting, not just the thing that actually does cause us to
stop waiting or the long list of possible extraordinary things that
might.
By your logic, you can never wait for an event, since the computer
being turned off might cause you to stop waiting.
DS
Szabolcs Ferenczi
> ...
> For some reason, this is one thing that you are simply incapable of
>
> You say things that are manifestly false. ...
>
> Further, condition variables don't optimize anything nor are they
> intended to optimize anything.
Better to say you have no idea when and for what reason condition
variables have been introduced.
I can tell you that the condition variable was not invented in
Pthreads. Not even for the Monitors. Furthermore, there was a reason
why condition variables have been introduced and this reason was
exactly run time efficiency, optimising busy waiting loops.
That is why the condition variable does not and must not contribute
anything to the logic of the program. If it does contribute to the
logic, that is an error and hence caring about the CV_TEST can help
you.
However, if you do not know it from your education what is the role of
the condition variable in multi-threaded programs, I helped you with
setp-by-step demonstration. Anyone having just basic education in
programming can follow the simple step-by-step examples I have
provided in this discussion thread. You and some other trollers
cannot, of course.
If you are not educated enough to know about what was the reason we
have condition variables now, please do not think that everyone is at
your level and do not try to suppress ideas you are not able to
understand.
Best Regards,
Szabolcs
Sergei Organov
> On Apr 25, 4:57 pm, Sergei Organov <o...@javad.com> wrote:
>> Szabolcs Ferenczi <szabolcs.feren...@gmail.com> writes:
>> > On Apr 22, 1:00 pm, Sergei Organov <o...@javad.com> wrote:
>> >> Szabolcs Ferenczi <szabolcs.feren...@gmail.com> writes:
[...]
>>
>> > The condition variable only implements a waiting that does not consume
>>
>> ^^^^^^^ Waiting for *what*?
>> > computing resources:
>
> Waiting for *what*?---you ask. Obvious: Waiting for predicate `B' to
> become true.
Nope. The condition variable knows nothing about predicate 'B', so it
can't implement waiting for predicate 'B'.
Wasn't it you who said "The condition variable only implements a waiting
that does not consume computing resources"? You are lost then in your
own arguments already, sorry, and the rest of your response is direct
consequence of this loss.
> That is the condition for the process to proceed, nothing else.
>
>> Almost everybody seem to call those *what* "an event". If you don't
>> agree with this widely adopted terminology, it's your own problem,
>> sorry.
>
> Noone, who is reasonable enough, calls that an event.
Well, we already know you are the only reasonable enough person in the
world, -- you can already skip this.
On the other hand, there are plenty of persons who are not enough
reasonable and think otherwise, e.g., the first hit in Google search for
"condition variable event signaling" gives:
<http://www.cs.mtu.edu/~shene/NSF-3/e-Book/MONITOR/CV.html>
"For a similar reason, a thread in a monitor may have to block itself
because of its request may not complete immediately. This waiting for an
event (e.g., I/O completion) to occur is realized by condition
variables.
A condition variable indicates an event and has no value. More
precisely, one cannot store a value into nor retrieve a value from a
condition variable. If a thread must wait for an event to occur, that
thread waits on the corresponding condition variable. If another
thread causes an event to occur, that thread simply signals the
corresponding condition variable."
BTW, this reference apparently has nothing to do with pthreads,
references to which you actively hate.
Here is another "unreasonable" person writing in Wikipedia:
"To avoid entering a busy waiting state, processes must be able to
signal each other about events of interest. Monitors provide this
capability through condition variables."
here: <http://en.wikipedia.org/wiki/Monitor_(synchronization)>
Don't you think you should immediately try to edit and fix the above
Wikipedia article?
> I am afraid you can be really sorry not being able follow simple
> things like this.
Yeah, I got it -- you are the only reasonable person, period.
> The condition variable makes the waiting just optimal with respect to
> using computing cycles.
Waiting for what? Name it.
> That was the reason the condition variable has been introduced in the
> history of concurrent programming.
Irrelevant.
>>
>> > while (!B) cv.wait();
>>
>> > Still you are waiting for condition `B' and not for the condition
>> > variable `c' in your program logic.
>>
>> The whole loop waits for condition 'B' to become true indeed; the
>> cv.wait() inside the loop waits for event.
>
> Would you be surprised to learn that cv.wait() can return legally so
> that there is no `event' in the sense you are trying to understand it?
No, I won't be surprised. The cv.wait() waits for something anyway. Name
that *something*.
> Because it is true that cv.wait() can legally return immediately
> without having received any signal at all.
Really? What a surprise!
> Hence caring about CV_TEST helps you to write correct programs,
> whether you are sorry or not.
No, it doesn't help *me* as it has nothing non-obvious. If it helps you,
or somebody else, -- that's fine with me though.
-- Sergei.
Sergei Organov
> On Apr 25, 1:23 am, David Schwartz <dav...@webmaster.com> wrote:
>> ...
>> For some reason, this is one thing that you are simply incapable of
>> understanding. You are wrong and everybody else is right. ...
>>
>> You say things that are manifestly false. ...
>>
>> Further, condition variables don't optimize anything nor are they
>> intended to optimize anything.
>
> Better to say you have no idea when and for what reason condition
> variables have been introduced.
>
> I can tell you that the condition variable was not invented in
> Pthreads. Not even for the Monitors. Furthermore, there was a reason
> why condition variables have been introduced and this reason was
> exactly run time efficiency, optimising busy waiting loops.
To *avoid* busy waiting loops, not to optimise them, I'd say.
-- Sergei.
Szabolcs Ferenczi
> ...
> > The condition variable makes the waiting just optimal with respect to
> > using computing cycles.
>
> Waiting for what? Name it.
Condition `B'.
That is what is awaited, condition `B'. The condition variable is just
an auxiliary aid there to make the waiting less costly in terms of
computing cycles. Do not forget that it is exactly for this goal it
has been invented. Just check it in the professional literature.
I hope I could help, though.
Best Regards,
Szabolcs
Szabolcs Ferenczi
> ...
> On the other hand, there are plenty of persons who are not enough
> reasonable and think otherwise, e.g., the first hit in Google search for
> "condition variable event signaling" gives:
>
> <http://www.cs.mtu.edu/~shene/NSF-3/e-Book/MONITOR/CV.html>
It is a very good example that googling does not substitute basic
education. If you miss basic knowledge about the subject, you are
lost.
Instead of trying to learn from an unreliable source, you should try
to follow the arguments I have provided already.
Do not forget that you must judge with your own logos what I have said
about it.
Best Regards,
Szabolcs
Sergei Organov
> On Apr 25, 6:49 pm, Sergei Organov <o...@javad.com> wrote:
>> ...
>> > The condition variable makes the waiting just optimal with respect to
>> > using computing cycles.
>>
>> Waiting for what? Name it.
>
> Condition `B'.
Nope. CV doesn't know about 'B'.
-- Sergei.
Sergei Organov
> On Apr 25, 6:49 pm, Sergei Organov <o...@javad.com> wrote:
>> ...
>> On the other hand, there are plenty of persons who are not enough
>> reasonable and think otherwise, e.g., the first hit in Google search for
>> "condition variable event signaling" gives:
>>
>> <http://www.cs.mtu.edu/~shene/NSF-3/e-Book/MONITOR/CV.html>
>
> It is a very good example that googling does not substitute basic
> education.
Who said it does?
> If you miss basic knowledge about the subject, you are lost.
Emerged to self-criticism?
> Instead of trying to learn from an unreliable source, you should try
> to follow the arguments I have provided already.
The problem is that your arguments are senseless.
> Do not forget that you must judge with your own logos what I have said
> about it.
Yeah, I've already got that you are the only person everybody should
listen to. Second Advent? Hallelujah!
-- Sergei.
Alexander Terekhov
Szabolcs Ferenczi wrote:
[...]
> I can tell you that the condition variable was not invented in
> Pthreads. Not even for the Monitors. Furthermore, there was a reason
> why condition variables have been introduced and this reason was
> exactly run time efficiency, optimising busy waiting loops.
You're still being confused by Per Brinch Hansen's use of phrase "busy
waiting" regarding conditional critical regions.
C.A.R Hoare invented conditional critical regions. See "TOWARDS A THEORY
OF PARALLEL PROGRAMMING" (1971). His paper states:
"... the effect of a critical region is to re-establish the necessary
degree of serialism into the parallel execution, so that the only one of
the processes may enter its critical region at any time. ... Let B be a
Boolean expression which tests the permissibility of an operation
carried out by a critical region C. Then I suggest the notation:
with r when B do C
to specify that C is not to be carried out until B is true.
Some care must be exercised in the implementation of this new feature.
The first action (as before) is to seize the semaphore associated with
r. Then the condition B is tested. If it is false, the given process
will hang itself up on the queue of processes waiting for r, and must
then release the semaphore. If B is true, the critical region C is
executed normally; and on completion the queue of waiting processes (if
any) will be inspected, in the order of longest wait. ..."
That is clearly not "busy waiting" in the sense of your CV_TEST.
regards,
alexander.
Sergei Organov
> On Apr 25, 1:23 am, David Schwartz <dav...@webmaster.com> wrote:
>> ...
>> For some reason, this is one thing that you are simply incapable of
>> understanding. You are wrong and everybody else is right. ...
>>
>> You say things that are manifestly false. ...
>>
>> Further, condition variables don't optimize anything nor are they
>> intended to optimize anything.
>
> Better to say you have no idea when and for what reason condition
> variables have been introduced.
Bingo! You've won! Nobody but you have any idea at all!
> I can tell you that the condition variable was not invented in
> Pthreads. Not even for the Monitors. Furthermore, there was a reason
> why condition variables have been introduced
What a surprise! We all thought there were no reason at all.
> and this reason was exactly run time efficiency, optimising busy
> waiting loops.
Don't you know that Linux completes even forever loops in not more than
5 seconds?! That's real optimisation! Though optimising busy waiting
loops this way I'd put next on the scale of most wonderful optimizations
out there.
Do you realize that when you put CV into busy waiting loop, it's not
busy waiting loop anymore? When you call removing busy waiting loop an
optimization of the busy waiting, it once again confirms serious
problems with either your logic or terminology, to the level where other
people stop understanding you. Yeah, it's their problem, not yours, -- I
know.
> That is why the condition variable does not and must not contribute
> anything to the logic of the program. If it does contribute to the
> logic, that is an error and hence caring about the CV_TEST can help
> you.
Still didn't do your homework? Please show how you implement waiting for
a condition in high-real-time-priority thread when that condition is to
be set by a low-real-time-priority thread. You are not allowed to use CV
that is "just an optimization". Mutex is the only tool you left with.
Then run your code on single CPU to assure yourself that your program
just hangs in the high-priority thread that waits forever.
[ Yeah, here am I feeding the troll as well. Any drugs to help me get
out? ;) ]
-- Sergei.
Szabolcs Ferenczi
> Szabolcs Ferenczi <szabolcs.feren...@gmail.com> writes:
> > On Apr 25, 6:49 pm, Sergei Organov <o...@javad.com> wrote:
> >> ...
> >> > The condition variable makes the waiting just optimal with respect to
> >> > using computing cycles.
>
> >> Waiting for what? Name it.
>
> > Condition `B'.
>
> Nope. CV doesn't know about 'B'.
No, it does not. It is just a code. But you does not know about
concurrent programming either and you are starting to make fool of
yourself.
Please stop trolling. Go and learn instead.
Best Regards,
Szabolcs
David Jones
was dealing with more that 2 players. There are reasons you can see a
'spurious' wakeup other the whim of a capricious scheduler.
David L. Jones | Phone: (614) 271-6718
Ohio State University | Internet:
140 W. 19th St. | jon...@ecr6.ohio-state.edu
Columbus, OH 43210 | vm...@osu.edu
Disclaimer: I'm looking for marbles all day long.
Chris Thomasson
Oh the irony!!! Wow. :^D
Szabolcs Ferenczi
> Szabolcs Ferenczi wrote:
>
> [...]
>
> > I can tell you that the condition variable was not invented in
> > Pthreads. Not even for the Monitors. Furthermore, there was a reason
> > why condition variables have been introduced and this reason was
> > exactly run time efficiency, optimising busy waiting loops.
>
> You're still being confused by Per Brinch Hansen's use of phrase "busy
> waiting" regarding conditional critical regions.
Am I?
> C.A.R Hoare invented conditional critical regions. See "TOWARDS A THEORY
> OF PARALLEL PROGRAMMING" (1971). His paper states:
>
> "... the effect of a critical region is to re-establish the necessary
> degree of serialism into the parallel execution, so that the only one of
> the processes may enter its critical region at any time. ... Let B be a
> Boolean expression which tests the permissibility of an operation
> carried out by a critical region C. Then I suggest the notation:
>
> with r when B do C
>
> to specify that C is not to be carried out until B is true.
>
> Some care must be exercised in the implementation of this new feature.
> The first action (as before) is to seize the semaphore associated with
> r. Then the condition B is tested. If it is false, the given process
> will hang itself up on the queue of processes waiting for r, and must
> then release the semaphore. If B is true, the critical region C is
> executed normally; and on completion the queue of waiting processes (if
> any) will be inspected, in the order of longest wait. ..."
Well done. You are reading the right paper now.
> That is clearly not "busy waiting" in the sense of your CV_TEST.
No, it is not. What you are reading now is the concurrent language
concept of the Conditional Critical Region.
Hoare's Conditional Critical Region (CCR) is a very high level
language means for process synchronisation and communication. The
semantics of it includes mutual exclusion and long term
synchronisation but it itself is not defined in terms of low level
means like mutex and condition variable. But it can be implemented
with them. And then you do have the busy waiting loop. It is so clear
that I just wonder why it is so difficult for somebody to understand.
I have shown a possible mapping between the high level CCR and the low
level library elements in C++0x already on the other discussion
thread:
http://groups.google.com/group/comp.lang.c++/msg/041b2d8d13869371
So, if you have studied Hoare's paper, excellent, you know the concept
and the original syntax of the CCR already. Good.
> with r when B do C
Now we could express it in a C++-like pseudo syntax as follows:
resource class r {
public:
void foo()
{
when (B) {
C;
}
}
};
However, it is not compiling since the low level language C++ cannot
understand the high level CCR. Let us then apply by hand source-to-
source compilation into library calls. We need a mutex since low level
language C++ does not have any critical region.
class r {
mutex m;
public:
void foo()
{
m.lock();
while (!B) {m.unlock(); m.lock();}
C;
m.unlock();
}
};
Now you can see the busy loop which would be there in any
implementation even if it is not a source-to-source mapping. That is
what Brinch Hansen explained and I have already quoted to you.
Nevertheless, repetitio est mater studiorum, here you go again:
"The major concern was that it did not seem possible to implement
conditional critical regions effciently. The root of the problem is
the unbounded reevaluation of Boolean expressions until they are true.
...
I suggested that programmers should be able to associate secure
queueing variables with shared data structures and control the
transfers of processes to and from them."
THE INVENTION OF CONCURRENT PROGRAMMING
http://brinch-hansen.net/papers/2002b.pdf
Finally, if we follow Brinch Hansen, we can arrive at the optimised
version where we need yet another library element, a condition
variable:
class r {
mutex m;
condvar cv(m);
public:
void foo()
{
m.lock();
while (!B) cv.wait(); // we need to insert cv.signal() elsewhere
too
C;
m.unlock();
}
};
Brinch Hansen also explains that his queueing variable has been taken
over into the Monitors, it has been renamed to condition variable, and
finally it is taken over by Java and Pthreads library (from Mesa
monitors, of course).
And there we are, back again.
I hope you are getting the idea now.
Best Regards,
Szabolcs
Alexander Terekhov
Szabolcs Ferenczi wrote:
[... "busy waiting" ...]
> I have shown a possible mapping between the high level CCR and the low
> level library elements in C++0x already on the other discussion
> thread:
> http://groups.google.com/group/comp.lang.c++/msg/041b2d8d13869371
comp.lang.c+? Well, Sir Peter Olcott and his famous "NewString is
22-fold (2,200 %) faster than string" et al comedy threads come to my
mind. :-)
As for your CV_TEST, see
http://google.com/group/comp.lang.c++.moderated/msg/84afea748e450937
Hth.
regards,
alexander.
Szabolcs Ferenczi
> > I have shown a possible mapping between the high level CCR and the low
> > level library elements in C++0x already on the other discussion
> > thread:
> >http://groups.google.com/group/comp.lang.c++/msg/041b2d8d13869371
>
> comp.lang.c+? Well, Sir Peter Olcott and his famous "NewString is
> 22-fold (2,200 %) faster than string" et al comedy threads come to my
> mind. :-)
That is your problem.
> As for your CV_TEST, see
>
> http://google.com/group/comp.lang.c++.moderated/msg/84afea748e450937
So what?
The question is whether you can understand now the origin of the
condition variable or you still have some problem.
Best Regards,
Szabolcs
Markus Elfring
>> and this reason was exactly run time efficiency, optimising busy waiting loops.
>
> To *avoid* busy waiting loops, not to optimise them, I'd say.
I admit that the elimination of busy waiting can be seen as an optimisation
goal. It is a reasonable motivation for improvement.
There is also a view in the opposite direction possible. Busy loops are the
fastest way to react on state changes in the application of spin locks.
What are appropriate optimisations for square wheels? ;-)
http://blogs.chron.com/sciguy/archives/2007/01/and_now_for_som.html#c366688
Regards,
Markus
Alexander Terekhov
Szabolcs Ferenczi wrote:
[...]
> The question is whether you can understand now the origin of the
> condition variable or you still have some problem.
I have no problem understanding the origin of the condition variable: it
certainly didn't come from "busy waiting" in the sense of your CV_TEST
(see "TOWARDS A THEORY OF PARALLEL PROGRAMMING" (1971), "MONITORS: AN
OPERATING SYSTEM STRUCTURING CONCEPT" (1974), and "EXPERIENCE WITH
PROCESSES AND MONITORS in MESA" (1980)).
regards,
alexander.
Szabolcs Ferenczi
It is up to you what you think about it but then I am afraid you
failed to understand it. For you I have written here the "Origin of
condition variable for dummies in history and by examples" and you
were even unable to follow it.
I am afraid I overestimated you and now it is clear that the junior
forum troller was wrong talking about your abilities.
Nevertheless, it does not affect the facts that CV_TEST as a memento
can indicate whether you use the condition variable in a compliant way
or not.
You are invited, though, to come up with an example what although
fails the CV_TEST but still would be a valid use of the condition
variable.
I have a good feeling that you will fail to do this homework as failed
the big face pthreads hero here to do his homework.
Thanks for your efforts anyway.
Best Regards,
Szabolcs
Alexander Terekhov
Szabolcs Ferenczi wrote:
[...]
> You are invited, though, to come up with an example what although
> fails the CV_TEST but still would be a valid use of the condition
> variable.
You are invited to enumerate possible failures as seen by program's user
regarding invalid use of the condition variable.
Sergei Organov has already given you an example regarding your CV_TEST.
regards,
alexander.
Chris Thomasson
news:67gtsbF...@mid.individual.net...
>>> Furthermore, there was a reason why condition variables have been
>>> introduced
>>> and this reason was exactly run time efficiency, optimising busy waiting
>>> loops.
>>
>> To *avoid* busy waiting loops, not to optimise them, I'd say.
>
> I admit that the elimination of busy waiting can be seen as an
> optimisation goal. It is a reasonable motivation for improvement.
Sure. There is one point, the condition variable in the context of PThreads
must be used in conjunction with a mutex and predicate. IMHO, it can be
somewhat helpful to think of them as a whole unit. When you think of them as
an intergraded system, (e.g., pthread_cond_wait() has mutex parameter
hardcoded into interface), then you can quickly understand that it can be a
fairly flexible conditional event handling medium.
This is why I think Szabolcs Ferenczi' assertion that condition variables
cannot be used for events is flawed.
> There is also a view in the opposite direction possible. Busy loops are
> the fastest way to react on state changes in the application of spin
> locks.
>
> What are appropriate optimisations for square wheels? ;-)
> http://blogs.chron.com/sciguy/archives/2007/01/and_now_for_som.html#c366688
:^)
Szabolcs Ferenczi
> Szabolcs Ferenczi wrote:
>
> [...]
>
> > You are invited, though, to come up with an example what although
> > fails the CV_TEST but still would be a valid use of the condition
> > variable.
>
> You are invited to enumerate possible failures as seen by program's user
> regarding invalid use of the condition variable.
You are not clear enough but if you are asking for an example where
condition variable is misused, see:
http://groups.google.com/group/comp.programming.threads/msg/fc06ff81b98a9823
Now it is your turn to do your homework. But do not try to escape
again as a piker.
Best Regards,
Szabolcs
Chris Thomasson
On Apr 26, 8:15 pm, Alexander Terekhov <terek...@web.de> wrote:
> > Szabolcs Ferenczi wrote:
> >
> > [...]
> >
> > > You are invited, though, to come up with an example what although
> > > fails the CV_TEST but still would be a valid use of the condition
> > > variable.
> >
> > You are invited to enumerate possible failures as seen by program's user
> > regarding invalid use of the condition variable.
> You are not clear enough but if you are asking for an example where
> condition variable is misused, see:
> http://groups.google.com/group/comp.programming.threads/msg/fc06ff81b98a9823
_______________________________________________________________
void
dosignal (void)
{
pthread_mutex_lock (&cond_mutex);
pthread_cond_signal(&cond);
pthread_mutex_unlock (&cond_mutex);
/* sched_yield(); without this I get 0! with Linux and RT patches
*/
}
________________________________________________________________
The OP of the thread provided in the link above forgot to add a predicate.
From this you base your claim that condvars are no good for event handling.
If you don't provide a predicate, what event are you waiting on? In a sense,
the condvar, mutex and predicate work together as a team.