[ECOS] Condition Variables recap

[ECOS] Condition Variables recap

[Trenton D. Adams]

Ok, below I describe condition variables as far as I know them.  I'm not
actually using them yet, I'm just preparing to use them.  Please tell me
if I'm wrong somewhere.  If I'm not wrong, a simple "Sounds good" will
be sufficient! :)

Main Program
I initialize the condition variable and corresponding mutex before
starting my threads.

Producer Thread
I lock the mutex in my producer thread before starting or resuming the
consumer threads.
When data is ready, I call cyg_cond_broadcast ().

Consumer Thread
Each consumer thread starts in a loop and checks the condition variable
by calling cyg_cond_wait ().
They will either be suspended, or one will succeed.
After the producer thread calls cyg_cond_broadcast (), ONE consumer
thread will lock the mutex, and begin reading data.
Now this thread should call cyg_mutex_unlock () which will cause another
ONE thread to lock it.


Now I have a question.  What happens to the cyg_cond_wait () call in the
OTHER consumer threads when cyg_cond_broadcast () is called?  Do they
simply get suspended, after that other ONE consumer thread locks the
mutex, and until the mutex is available to ONE of them again?

Trenton D. Adams
Embedded Developer
Windows Developer
Extreme Engineering Ltd.
Calgary Alberta.

Re: [ECOS] Condition Variables recap

[Jonathan Larmour]

"Trenton D. Adams" wrote:
> 
> Consumer Thread
> Each consumer thread starts in a loop and checks the condition variable
> by calling cyg_cond_wait ().
> They will either be suspended, or one will succeed.
> After the producer thread calls cyg_cond_broadcast (), ONE consumer
> thread will lock the mutex, and begin reading data.
> Now this thread should call cyg_mutex_unlock () which will cause another
> ONE thread to lock it.
> 
> Now I have a question.  What happens to the cyg_cond_wait () call in the
> OTHER consumer threads when cyg_cond_broadcast () is called?  Do they
> simply get suspended, after that other ONE consumer thread locks the
> mutex, and until the mutex is available to ONE of them again?

Yes. They will all have been woken up by the broadcast, and then each go
through locking and unlocking the mutex. By that point the condition may no
longer be true of course, i.e. there may be no more waiting data. I would
imagine cyg_cond_signal() would be more appropriate (although there's still
a chance more than one thread is woken up).

Jifl
-- 
Red Hat, Rustat House, Clifton Road, Cambridge, UK. Tel: +44 (1223) 271062
Maybe this world is another planet's Hell -Aldous Huxley || Opinions==mine
Come to the Red Hat TechWorld open source conference in Brussels!
Keynotes, techie talks and exhibitions    http://www.redhat-techworld.com/

RE: [ECOS] Condition Variables recap

[Trenton D. Adams]

  > 
  > "Trenton D. Adams" wrote:
  > >
  > > Consumer Thread
  > > Each consumer thread starts in a loop and checks the condition
  > variable
  > > by calling cyg_cond_wait ().
  > > They will either be suspended, or one will succeed.
  > > After the producer thread calls cyg_cond_broadcast (), ONE
consumer
  > > thread will lock the mutex, and begin reading data.
  > > Now this thread should call cyg_mutex_unlock () which will cause
  > another
  > > ONE thread to lock it.
  > >
  > > Now I have a question.  What happens to the cyg_cond_wait () call
in
  > the
  > > OTHER consumer threads when cyg_cond_broadcast () is called?  Do
they
  > > simply get suspended, after that other ONE consumer thread locks
the
  > > mutex, and until the mutex is available to ONE of them again?
  > 
  > Yes. They will all have been woken up by the broadcast, and then
each go
  > through locking and unlocking the mutex. By that point the condition
may
  > no
  > longer be true of course, i.e. there may be no more waiting data. I
  > would
  > imagine cyg_cond_signal() would be more appropriate (although
there's
  > still
  > a chance more than one thread is woken up).
  > 

Why would cyg_cond_signal () be more appropriate?  After all, I want my
producer thread to continue on right away doing what it was doing.  If I
used cyg_cond_signal () wouldn't I have to call it multiple times?  Or
would I just have each of the consumer threads call it again when
they're finished?

Is there any way that two of the threads could accidentally lock a mutex
at the exact same time and not even know it?  I would think that it
doesn't really matter as long as the resource required is meant to be
read-only to the consumer threads right?

Re: [ECOS] Condition Variables recap

[Jonathan Larmour]

"Trenton D. Adams" wrote:
> 
>   >
>   > "Trenton D. Adams" wrote:
>   > >
>   > > Consumer Thread
>   > > Each consumer thread starts in a loop and checks the condition
>   > variable
>   > > by calling cyg_cond_wait ().
>   > > They will either be suspended, or one will succeed.
>   > > After the producer thread calls cyg_cond_broadcast (), ONE
> consumer
>   > > thread will lock the mutex, and begin reading data.
>   > > Now this thread should call cyg_mutex_unlock () which will cause
>   > another
>   > > ONE thread to lock it.
>   > >
>   > > Now I have a question.  What happens to the cyg_cond_wait () call
> in
>   > the
>   > > OTHER consumer threads when cyg_cond_broadcast () is called?  Do
> they
>   > > simply get suspended, after that other ONE consumer thread locks
> the
>   > > mutex, and until the mutex is available to ONE of them again?
>   >
>   > Yes. They will all have been woken up by the broadcast, and then
> each go
>   > through locking and unlocking the mutex. By that point the condition
> may
>   > no
>   > longer be true of course, i.e. there may be no more waiting data. I
>   > would
>   > imagine cyg_cond_signal() would be more appropriate (although
> there's
>   > still
>   > a chance more than one thread is woken up).
>   >
> 
> Why would cyg_cond_signal () be more appropriate?

Shouldn't only one thread need to process the arrived data? With
_broadcast(), all of them will wake up. But still, I don't know your
application, so it's up to you. If it works for you, whatever :).
 
> Is there any way that two of the threads could accidentally lock a mutex
> at the exact same time and not even know it?

No. Unless you misuse the API (e.g. by calling cyg_mutex_trylock() and
don't check the return code).

Jifl
-- 
Red Hat, Rustat House, Clifton Road, Cambridge, UK. Tel: +44 (1223) 271062
Maybe this world is another planet's Hell -Aldous Huxley || Opinions==mine
Come to the Red Hat TechWorld open source conference in Brussels!
Keynotes, techie talks and exhibitions    http://www.redhat-techworld.com/

RE: [ECOS] Condition Variables recap

[Gary Thomas]

On 24-Jul-2001 Trenton D. Adams wrote:
>   > 
>   > "Trenton D. Adams" wrote:
>   > >
>   > > Consumer Thread
>   > > Each consumer thread starts in a loop and checks the condition
>   > variable
>   > > by calling cyg_cond_wait ().
>   > > They will either be suspended, or one will succeed.
>   > > After the producer thread calls cyg_cond_broadcast (), ONE
> consumer
>   > > thread will lock the mutex, and begin reading data.
>   > > Now this thread should call cyg_mutex_unlock () which will cause
>   > another
>   > > ONE thread to lock it.
>   > >
>   > > Now I have a question.  What happens to the cyg_cond_wait () call
> in
>   > the
>   > > OTHER consumer threads when cyg_cond_broadcast () is called?  Do
> they
>   > > simply get suspended, after that other ONE consumer thread locks
> the
>   > > mutex, and until the mutex is available to ONE of them again?
>   > 
>   > Yes. They will all have been woken up by the broadcast, and then
> each go
>   > through locking and unlocking the mutex. By that point the condition
> may
>   > no
>   > longer be true of course, i.e. there may be no more waiting data. I
>   > would
>   > imagine cyg_cond_signal() would be more appropriate (although
> there's
>   > still
>   > a chance more than one thread is woken up).
>   > 
> 
> Why would cyg_cond_signal () be more appropriate?  After all, I want my
> producer thread to continue on right away doing what it was doing.  If I
> used cyg_cond_signal () wouldn't I have to call it multiple times?  Or
> would I just have each of the consumer threads call it again when
> they're finished?
> 

The difference between cyg_cond_signal() and cyg_cond_broadcast() is that
with the former at most one thread waiting on the condition variable will
be awakened.  With cyg_cond_broadcast(), all threads waiting on the variable
will wake up.  

In most cases, it is far more efficient to wake up a single thread than it is
for a number to be awakened, only to fight over which one gets to actually
perform the service being signalled.

> Is there any way that two of the threads could accidentally lock a mutex
> at the exact same time and not even know it?  I would think that it
> doesn't really matter as long as the resource required is meant to be
> read-only to the consumer threads right?

No - if this were possible, then it would not be a mutex!  (mutex = device
for _mutual exclusion_)

RE: [ECOS] Condition Variables recap

[Trenton D. Adams]

Jonathan Larmour wrote:
  > 
  > Shouldn't only one thread need to process the arrived data? With
  > _broadcast(), all of them will wake up. But still, I don't know your
  > application, so it's up to you. If it works for you, whatever :).
  > 

Actually, I'm looking at my design document, and I only have one thread
accessing the data!  Sorry for the confusion!!!  I asked the question
before I started writing that part of the design document.

  > > Is there any way that two of the threads could accidentally lock a
  > mutex
  > > at the exact same time and not even know it?
  > 
  > No. Unless you misuse the API (e.g. by calling cyg_mutex_trylock()
and
  > don't check the return code).
  > 

cyg_mutex_trylock () is not documented in my documentation.  I assume
I'm not required to call that before the actual locking?



Gary Thomas wrote:
  >  > Is there any way that two of the threads could accidentally lock
a 
  >  > mutex at the exact same time and not even know it?  I would think
that 
  >  > it doesn't really matter as long as the resource required is
meant to 
  >  > be read-only to the consumer threads right?
  > No - if this were possible, then it would not be a mutex!  (mutex =
device for _mutual exclusion_)

Yes, I figured that much, I just wanted to be sure! ;)


Thanks for the info Jonathan and Gary, I think I'm almost ready for some
serious coding!  Assuming I can get that stupid PCMCIA controller to
quit screwing with my head! :)

Re: [ECOS] Condition Variables recap

[Jonathan Larmour]

"Trenton D. Adams" wrote:
> 
> cyg_mutex_trylock () is not documented in my documentation.  I assume
> I'm not required to call that before the actual locking?

Curiously that is true. I'll make a note to fix that.

Gary Thomas wrote:
> The difference between cyg_cond_signal() and cyg_cond_broadcast() is
> that with the former at most one thread waiting on the condition
> variable will be awakened. 

You mean "at least", not "at most". cyg_cond_signal() may wake up more than
one thread (which is the norm for CV implementations, not just eCos).
That's why you should always loop and retest the condition when doing a
cyg_cond_wait().

Jifl
-- 
Red Hat, Rustat House, Clifton Road, Cambridge, UK. Tel: +44 (1223) 271062
Maybe this world is another planet's Hell -Aldous Huxley || Opinions==mine
Come to the Red Hat TechWorld open source conference in Brussels!
Keynotes, techie talks and exhibitions    http://www.redhat-techworld.com/

RE: [ECOS] Condition Variables recap

[Trenton D. Adams]

  > Gary Thomas wrote:
  > > The difference between cyg_cond_signal() and cyg_cond_broadcast()
is
  > > that with the former at most one thread waiting on the condition
  > > variable will be awakened.
  > 
  > You mean "at least", not "at most". cyg_cond_signal() may wake up
more
  > than
  > one thread (which is the norm for CV implementations, not just
eCos).
  > That's why you should always loop and retest the condition when
doing a
  > cyg_cond_wait().
  > 

Ok, I'm not sure I understand at the moment.  Maybe I'm having a bad
day, or maybe I'm just a moron.  Either way, this is what I don't
understand.

Here's some quotes from another message sent by Srinivasan Sriram titled
"CONDITION VARIABLES & MUTEXES" about a month ago.

  > > WHY DO WE REQUIRE THE WHILE LOOP? ANY WAY THE
  > > CYG_COND_WAIT CANNOT PROCEED BEFORE IT OBTAINS THE
  > > MUTEX AND BROADCAST FROM THE PRODUCER AND OTHER
  > > THREADS?
  > 
  > Two threads waiting on the condition may be woken up. They won't run
at
  > the
  > same time since only one can have the mutex locked, but when the
second
  > one
  > runs, the condition will not be true any more.
  > 

Does this mean that during cyg_cond_wait () an internal variable is set
to FALSE?  If so, then the next thread to continue inside it's
cyg_cond_wait () will simply return because the condition variable is no
longer valid?  Also, this would only happen if two or more threads
happened to be woken up at the same time right?

  > > ALSO COULD ANYONE EXPLAIN - WHAT IS THE VARIABLE IN
  > > THE WHILE LOOP. WHAT DOES IT TEST?
  > 
  > The condition you are waiting for...
  >

The condition_not_true statement must contain a variable that I make for
testing whether the loop should continue or not, and I would set this
variable to true after one of the consumer threads finished using the
resource!  Correct?  Man that had to be the longest sentence I've ever
written! :~o

  > As Robin says, you should read some general books about concurrency
  > theory.
  > There's probably stuff on the web, or I can recommend Concurrent
Systems
  > by
  > J. Bacon published by Addison Wesley.

So, if I'm not correct above, then I'll assume I don't know what the
hell I'm talking about, and I'll do as Robin says and go and read more
on the subject!  (second longest sentence I've ever written) ;)

Re: [ECOS] Condition Variables recap

[Jonathan Larmour]

"Trenton D. Adams" wrote:
> 
>   > > WHY DO WE REQUIRE THE WHILE LOOP? ANY WAY THE
>   > > CYG_COND_WAIT CANNOT PROCEED BEFORE IT OBTAINS THE
>   > > MUTEX AND BROADCAST FROM THE PRODUCER AND OTHER
>   > > THREADS?
>   >
>   > Two threads waiting on the condition may be woken up. They won't run
> at
>   > the
>   > same time since only one can have the mutex locked, but when the
> second
>   > one
>   > runs, the condition will not be true any more.
>   >
> 
> Does this mean that during cyg_cond_wait () an internal variable is set
> to FALSE?

No, the state of the condition variable doesn't necessarily reflect the
_actual_ state of the condition, that's why you have to retest.

>  If so, then the next thread to continue inside it's
> cyg_cond_wait () will simply return because the condition variable is no
> longer valid?

It will lock the mutex though - as all cyg_cond_wait()'s must do on return,
so it won't block immediately.

>   > > ALSO COULD ANYONE EXPLAIN - WHAT IS THE VARIABLE IN
>   > > THE WHILE LOOP. WHAT DOES IT TEST?
>   >
>   > The condition you are waiting for...
>   >
> 
> The condition_not_true statement must contain a variable that I make for
> testing whether the loop should continue or not, and I would set this
> variable to true after one of the consumer threads finished using the
> resource!  Correct?

Generally the condition is more like  "is there data available to read" and
so on.

Jifl
-- 
Red Hat, Rustat House, Clifton Road, Cambridge, UK. Tel: +44 (1223) 271062
Maybe this world is another planet's Hell -Aldous Huxley || Opinions==mine
Come to the Red Hat TechWorld open source conference in Brussels!
Keynotes, techie talks and exhibitions    http://www.redhat-techworld.com/

RE: [ECOS] Condition Variables recap

[Trenton D. Adams]

Actually, I'm looking at the code for Cyg_Condition_Variable in
mutex.cxx and according to it, it only dequeues ONE thread for
wakeup/signal, and not more than that.  So I _BELIEVE_ that Gary was
correct in what he said before.  Is this right?

    if( !queue.empty() )
    {
        // The queue is non-empty, so grab the next
        // thread from it and wake it up.

        Cyg_Thread *thread = queue.dequeue();	// _I_ SAY ONE THREAD
ONLY

        CYG_ASSERTCLASS( thread, "Bad thread pointer");
        
        thread->set_wake_reason( Cyg_Thread::DONE );
        
        thread->wake();

        CYG_INSTRUMENT_CONDVAR(WAKE, this, thread);
        
    }


-----Original Message-----
From: ecos-discuss-owner@sources.redhat.com
[ mailto:ecos-discuss-owner@sources.redhat.com ] On Behalf Of Jonathan
Larmour
Sent: Tuesday, July 24, 2001 2:17 PM
To: Trenton D. Adams
Cc: 'eCos mailing list'
Subject: Re: [ECOS] Condition Variables recap


"Trenton D. Adams" wrote:
> 
> cyg_mutex_trylock () is not documented in my documentation.  I assume
> I'm not required to call that before the actual locking?

Curiously that is true. I'll make a note to fix that.

Gary Thomas wrote:
> The difference between cyg_cond_signal() and cyg_cond_broadcast() is
> that with the former at most one thread waiting on the condition
> variable will be awakened. 

You mean "at least", not "at most". cyg_cond_signal() may wake up more
than
one thread (which is the norm for CV implementations, not just eCos).
That's why you should always loop and retest the condition when doing a
cyg_cond_wait().

Jifl
-- 
Red Hat, Rustat House, Clifton Road, Cambridge, UK. Tel: +44 (1223)
271062
Maybe this world is another planet's Hell -Aldous Huxley ||
Opinions==mine
Come to the Red Hat TechWorld open source conference in Brussels!
Keynotes, techie talks and exhibitions
http://www.redhat-techworld.com/

Re: [ECOS] Condition Variables recap

[Nick Garnett]

"Trenton D. Adams" <tadams@theone.dnsalias.com> writes:

> Actually, I'm looking at the code for Cyg_Condition_Variable in
> mutex.cxx and according to it, it only dequeues ONE thread for
> wakeup/signal, and not more than that.  So I _BELIEVE_ that Gary was
> correct in what he said before.  Is this right?
> 

Be careful not to confuse the current implementation with the defined
behaviour. The current implementation will indeed only wake one
thread. But there are implementations, particularly in multiprocessor
systems, which may sometimes cause more than one thread to wake up.

Also, since the thread must re-aquire the mutex before continuing, it
may find that some other thread has invalidated the predicate before
it gets to run.

In general, whenever a condition wait returns, it must reevaluate the
predicate and decide whether to continue, wait again, or declare a
timeout (in the case of cyg_cond_timed_wait()). Returning from the
condition variable wait does not guarantee that the predicate is
either true or false. The usual way to make sure this works is to put
the call to cyg_cond_wait() into a loop that tests the predicate.

This is standard behaviour for any condition variable mechanism. The
POSIX standard requires condition variables to behave like this, and
we are following that as closely as possible.

Hope this makes things clearer.

-- 
Nick Garnett, eCos Kernel Architect
Red Hat, Cambridge, UK