Whats the point of pthread_cond_broadcast() ?

[Mut...@dastardlyhq.com]

Even though I've been doing threads programming for years I've always
avoided this function call because I never understood the point of it
with condition variables. Ie: because all threads contend to lock the
associated mutex only one actually exits the wait call anyway, so whats
the point of using this instead of cond_signal?

[Nicolas George]

Mut...@dastardlyhq.com, dans le message <trqgmc$312l3$1...@dont-email.me>,
a écrit :

An example of use:

https://git.ffmpeg.org/gitweb/ffmpeg.git/blob/HEAD:/libavcodec/frame_thread_encoder.c

[Mut...@dastardlyhq.com]

On 06 Feb 2023 10:50:30 GMT

Far too complex to be helpful.

[Nicolas George]

Mut...@dastardlyhq.com, dans le message <trqn7r$3278q$1...@dont-email.me>,
a écrit :

> Far too complex to be helpful.

You do not need to read all of it to see why the function if used. But fine,
suit yourself.

[Mut...@dastardlyhq.com]

On 06 Feb 2023 12:28:44 GMT

I read it. Its no help. As far as I can see it could use signal instead of
broadcast.

[Rainer Weikusat]

I've yet to encounter a situation where this is useful myself. SUS
names, single-producer/ multiple consumers, writer releases a rw lock,
and two-phase commit as examples. OTOH, it's unclear (to me at least)
why one shouldn't use signal to wake up one thread which could resignal
in case there's more work to do than it plans to handle.

[Kaz Kylheku]

You should always reach for pthread_cond_broadcast in initial designs
and implementaitons, because it will more easily assure correctness.

In a correct program, every pthread_cond_signal can be replaced with
pthread_cond_broadcast without sacrificing correctness. The reverse
isn't true.

pthread_cond_signal is an optimization for the case when you are
absolutely sure that the program will still behave correctly if only
at most one thread is woken.

(I seem to recall that no function guarantees that no more than one
thread will wake up; programs must be prepared for spurious wakeups.)

There are situations in which making some Boolean condition true means
that any number of threads are unblocked, not only one. For instance
a ready-wait: one or more threads are blocked waiting for some API
to become ready for service.

A situation where you need at most one thread to wake up is when
implementing a counting semaphore.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazi...@mstdn.ca

[Kaz Kylheku]

Suppose you have a "bool api_ready = false" flag, with a condition and
mutex. Threads must wait for the API to become ready before using it:


void api_wait()
{
pthread_mutex_lock(&api_mutex);
while (!api_ready)
pthread_cond_wait(&api_cond, &api_mutex);
pthread_mutex_ulock(&api_mutex);
}

void api_ready()
{
pthread_mutex_lock(&api_mutex);
api_ready = true;
pthread_mutex_ulock(&api_mutex);
// pthread_cond_signal, or pthread_cond_broadcast?
}

How would you complete api_ready?

If you chose signal, how would you code around the fact that
only one thread was woken up to use the API?

Do you put a just-in-case pthread_cond_signal into every single API
call?

[Mut...@dastardlyhq.com]

On Mon, 6 Feb 2023 22:30:39 -0000 (UTC)
Kaz Kylheku <864-11...@kylheku.com> wrote:
>On 2023-02-06, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>> Even though I've been doing threads programming for years I've always
>> avoided this function call because I never understood the point of it
>> with condition variables. Ie: because all threads contend to lock the
>> associated mutex only one actually exits the wait call anyway, so whats
>> the point of using this instead of cond_signal?
>
>You should always reach for pthread_cond_broadcast in initial designs
>and implementaitons, because it will more easily assure correctness.
>
>In a correct program, every pthread_cond_signal can be replaced with
>pthread_cond_broadcast without sacrificing correctness. The reverse
>isn't true.
>
>pthread_cond_signal is an optimization for the case when you are
>absolutely sure that the program will still behave correctly if only
>at most one thread is woken.

But why? Regardless of which call you use only 1 waiting thread exits the
pthread_cond_wait() call so what difference does it make? The ONLY difference
I have found is that signal wakes up threads in a particular order (seems to
be creation order on MacOS) so you know which thread will exit wait() whereas
broadcast wakes them all up and a random thread exits wait(). However I can't
see how that is any kind of advantage if the threads are all executing the
same code anyway.

[Nicolas George]

Mut...@dastardlyhq.com, dans le message <trt544$3guf1$1...@dont-email.me>,
a écrit :

> But why? Regardless of which call you use only 1 waiting thread exits the
> pthread_cond_wait() call so what difference does it make?

I consider Kaz's answer to be nonsense. Signal is absolutely not just an
optimization over broadcast: they have clear semantics and are to be used in
different circumstances. The FFmpeg code I quoted gives a very good example
of these different circumstances.

[Mut...@dastardlyhq.com]

On 07 Feb 2023 09:34:57 GMT

How about explaining it then because I can't see it.

[Gary R. Schmidt]

What I was told, a couple of decades ago, was that _signal meant that
(usually/mostly/maybe/probably) only one thread waiting on that signal
would wake up, whereas _broadcast meant that *all* threads waiting on
that signal would wake. (I think it may have been by David Butenhof, I
kind of trust him. (And it may have been DEC Alpha-specific.))

So, frex, if you have multiple consumers waiting on data that is being
fed into a single queue, starting them all up when something is
available can drain the queue faster, as data may be added while they
are waiting on the queue mutex. Sort of. Worked for me. :-)

Cheers,
Gary B-)

[Rainer Weikusat]

Kaz Kylheku <864-11...@kylheku.com> writes:
> On 2023-02-06, Rainer Weikusat <rwei...@talktalk.net> wrote:
>> Mut...@dastardlyhq.com writes:
>>> Even though I've been doing threads programming for years I've always
>>> avoided this function call because I never understood the point of it
>>> with condition variables. Ie: because all threads contend to lock the
>>> associated mutex only one actually exits the wait call anyway, so whats
>>> the point of using this instead of cond_signal?
>>
>> I've yet to encounter a situation where this is useful myself. SUS
>> names, single-producer/ multiple consumers, writer releases a rw lock,
>> and two-phase commit as examples. OTOH, it's unclear (to me at least)
>> why one shouldn't use signal to wake up one thread which could resignal
>> in case there's more work to do than it plans to handle.
>
> Suppose you have a "bool api_ready = false" flag, with a condition and
> mutex. Threads must wait for the API to become ready before using it:
>

static unsigned waiting;

>
> void api_wait()
> {

unsigned more;

> pthread_mutex_lock(&api_mutex);

if (!api_ready) {
++waiting;
do pthread_cond_wait(&api_cond, &api_mutex); while (!api_ready);
more = --waiting;
> pthread_mutex_ulock(&api_mutex);
if (more) pthread_cond_signal(&api_cond);

}
> }
>
> void api_ready()
> {
> pthread_mutex_lock(&api_mutex);
> api_ready = true;
> pthread_mutex_ulock(&api_mutex);

pthread_cond_signal(&api_cond);

>
> How would you complete api_ready?
>
> If you chose signal, how would you code around the fact that
> only one thread was woken up to use the API?

It's not particularly difficult to code this without thundering nerds.

[Mut...@dastardlyhq.com]

On Wed, 8 Feb 2023 00:54:51 +1100
"Gary R. Schmidt" <grsc...@acm.org> wrote:
>On 06/02/2023 20:19, Mut...@dastardlyhq.com wrote:
>> Even though I've been doing threads programming for years I've always
>> avoided this function call because I never understood the point of it
>> with condition variables. Ie: because all threads contend to lock the
>> associated mutex only one actually exits the wait call anyway, so whats
>> the point of using this instead of cond_signal?
>>
>What I was told, a couple of decades ago, was that _signal meant that
>(usually/mostly/maybe/probably) only one thread waiting on that signal
>would wake up, whereas _broadcast meant that *all* threads waiting on
>that signal would wake. (I think it may have been by David Butenhof, I
>kind of trust him. (And it may have been DEC Alpha-specific.))

Yes, that is the official position and in the OS kernel all the threads
may well get woken up. However from the application program POV there's no
difference because only 1 thread exits pthread_cond_wait() per signal or
broadcast sent.

>So, frex, if you have multiple consumers waiting on data that is being
>fed into a single queue, starting them all up when something is
>available can drain the queue faster, as data may be added while they
>are waiting on the queue mutex. Sort of. Worked for me. :-)

I don't follow. For 1 condition signal/broadcast 1 thread exits a wait call.
If multiple threads exited the wait then that would be a useful paradigm
but AFAIK pthreads doesn't supply that functionality.

[Scott Lurndal]

If you use broadcast, all threads waiting on the condition variable
will be made runnable. Then they will all immediately contend for
the mutex that was temporarily dropped while waiting on the event,
particularly if there are enough cores to run them all in parallel
and the scheduling constraints (e.g. thread priorities) allow the
newly runnable threads to be assigned to a physical thread/core.

This is known as a thundering herd.

[Mut...@dastardlyhq.com]

Its also invisible to the application program so I still don't see what the
difference and/or advantage of using broadcast vs signal is to the application.

[Rainer Weikusat]

Mut...@dastardlyhq.com writes:
> On Tue, 07 Feb 2023 16:33:34 GMT
> sc...@slp53.sl.home (Scott Lurndal) wrote:
>>Mut...@dastardlyhq.com writes:

[...]

>>>I don't follow. For 1 condition signal/broadcast 1 thread exits a wait call.
>>>If multiple threads exited the wait then that would be a useful paradigm
>>>but AFAIK pthreads doesn't supply that functionality.
>>
>>If you use broadcast, all threads waiting on the condition variable
>>will be made runnable. Then they will all immediately contend for
>>the mutex that was temporarily dropped while waiting on the event,
>>particularly if there are enough cores to run them all in parallel
>>and the scheduling constraints (e.g. thread priorities) allow the
>>newly runnable threads to be assigned to a physical thread/core.
>>
>>This is known as a thundering herd.
>
> Its also invisible to the application program so I still don't see
> what the difference and/or advantage of using broadcast vs signal is
> to the application.

I think that was supposed to describe a disadvantage. :-)

My guess why this interface exists would be that it's historical baggage
instinctively carried over from the UNIX kernel by people who were
accustomed to it. In order to wait for an event, a process executing
kernel code would go to sleep on a so-called sleep channel identified by
a pointer. This would typically be the address of a kernel variable
associated with the event the process wanted to wait for. This sleep
channel identifier was hashed to map it to a sleep queue and the process
would then put onto this sleep queue. At some later time, some other
code also executing in the kernel would do a wake up call using a sleep
channel identifer. This would cause all processes on the corresponding
sleep queue to be woken up. This had to be done because there was no way
to determine what event a process using a certain sleep channel
identifier was actually interested in (and possibly, because of hash
collisions in case the actual sleep channel identifier a process had
used wasn't stored anywhere).

With pthread_cond_broadcast, a condition variable can act as sleep
channel: It's possible to write a program such that it uses a single
condition variable for everything some thread might need to wait for. If
this was done, broadcast wakeup would be needed for the same reason it
was needed for UNIX sleep channels.

[Rainer Weikusat]

Rainer Weikusat <rwei...@talktalk.net> writes:
> Mut...@dastardlyhq.com writes:

[...]

>> I still don't see
>> what the difference and/or advantage of using broadcast vs signal is
>> to the application.

[...]

> My guess why this interface exists would be that it's historical baggage
> instinctively carried over from the UNIX kernel by people who were
> accustomed to it. In order to wait for an event, a process executing
> kernel code would go to sleep on a so-called sleep channel identified by
> a pointer.

[...]

> With pthread_cond_broadcast, a condition variable can act as sleep
> channel

[...]

Slight correction: It can act as sleep queue for any number of sleep
channels, ie, the original UNIX sleep/ wakeup mechanism can be
implemented with the help of a condition variable or an array of condition
variables sleep channel IDs are hashed onto.

[Kaz Kylheku]

On 2023-02-07, Nicolas George <nicolas$geo...@salle-s.org> wrote:
> Mut...@dastardlyhq.com, dans le message <trt544$3guf1$1...@dont-email.me>,
> a écrit :
>> But why? Regardless of which call you use only 1 waiting thread exits the
>> pthread_cond_wait() call so what difference does it make?
>
> I consider Kaz's answer to be nonsense. Signal is absolutely not just an
> optimization over broadcast: they have clear semantics and are to be used in

I explained very clearly that it's not that kind of optimization where
we improve something, but the semantics stays the same (as in "compiler
optimization").

It definitely has different semantics; it gives you an optimization when
it is unnecessary and wasteful (or even pathologic) for more than one
thread to wake up.

[Kaz Kylheku]

On 2023-02-07, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
> Yes, that is the official position and in the OS kernel all the threads
> may well get woken up. However from the application program POV there's no
> difference because only 1 thread exits pthread_cond_wait() per signal or
> broadcast sent.

That is simply false. It's true that only one waiting thread at a time
can exit from the function. But that's because of the mutex.

If you broadcast the condition, all threads waiting on the condition
will wake up and contend for the mutex.

Threads contenting for the mutex proceed when the mutex is available.

Threads sleeping on the condition variable do not proceed regardless
of what is happening with the mutex.

> If multiple threads exited the wait then that would be a useful paradigm
> but AFAIK pthreads doesn't supply that functionality.

Yes it does! If you need the paradigm of multiple threads being
woken up together without having to pass serially through a mutex,
POSIX provides barriers: pthread_barrier_wait.

It is indeed useful for parallel processing.

[Kaz Kylheku]

On 2023-02-07, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:

> Its also invisible to the application program so I still don't see
> what the difference and/or advantage of using broadcast vs signal is
> to the application.

It is completely visible to the application. Compare:

"Ten threads have been woken up and are contending for the mutex in
order the all return from their respective pthread_cond_wait calls."

"One threads has been woken up and is contending for the mutex in
order to return from pthread_cond_wait."

Do you understand the api_ready example? Here it is again:

bool api_ready = false;
pthread_mutex_t api_ready_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t api_ready_cond = PTHREAD_COND_INITIALIZER;

// internal function: indicates API is ready
static void api_becomes_ready(void)
{
pthread_mutex_lock(&api_mutex);
api_ready = true;
pthread_mutex_unlock(&api_mutex);
pthread_cond_broadcast(&api_cond); // wake up everyone
}

void api_ready_wait(void)

{
pthread_mutex_lock(&api_mutex);
while (!api_ready)
pthread_cond_wait(&api_cond, &api_mutex);

// Yes, only one thread can be here at a time

pthread_mutex_unlock(&api_mutex);

// Multiple threads can be returning here.
}

The api_becomes_ready function is called exactly once by the API
itself to indicate that it is ready.

Muliple threads from different subsystems may have called api_ready_wait
in order to wait for this indication.

If pthread_cond_signal is used, then quite likely, only one of those
threads will wake up; the others will stay stuck forever.

You can code this up and try it.

I think the subtlety you're missing is what I commented on in the code:
although exit from pthread_cond_wait is serialized due to the mutex,
exit from the surrounding function api_ready_wait isn't; mutiple threads
can be exiting from that function. The serialization through the mutex
is just a local speedbump.

[Rainer Weikusat]

Kaz Kylheku <864-11...@kylheku.com> writes:
> On 2023-02-07, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>> Its also invisible to the application program so I still don't see
>> what the difference and/or advantage of using broadcast vs signal is
>> to the application.
>
> It is completely visible to the application. Compare:
>
> "Ten threads have been woken up and are contending for the mutex in
> order the all return from their respective pthread_cond_wait calls."
>
> "One threads has been woken up and is contending for the mutex in
> order to return from pthread_cond_wait."

The thread is not contending for the mutex. Assuming the wakeup call was
done with the mutex unlocked, it'll just acquire it without contention
and without again having to enter the kernel and can just continue
running.

For the other case (assuming 1:1 threading) n, n > 1 threads sleeping in the
kernel are woken up, exit the kernel and contend for the mutex which
will cause n - 1 threads to immediately enter the kernel again and again go to
sleep there. That's not an issue on uniprocessors because only one of
these n threads can actually be running at any given time, hence, n - 1
end up on the runqueue and exit the kernel without contention on the
mutex one-by-one.

> Do you understand the api_ready example? Here it is again:

[...]

> If pthread_cond_signal is used, then quite likely, only one of those
> threads will wake up; the others will stay stuck forever.
>
> You can code this up and try it.

As demonstrated in another posting: This can be handled by maintaing a
counter of waiting threads and having the running thread wake up the
next one if there's still a thread waiting.

[Scott Lurndal]

Rainer Weikusat <rwei...@talktalk.net> writes:
>Kaz Kylheku <864-11...@kylheku.com> writes:
>> On 2023-02-07, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>>> Its also invisible to the application program so I still don't see
>>> what the difference and/or advantage of using broadcast vs signal is
>>> to the application.
>>
>> It is completely visible to the application. Compare:
>>
>> "Ten threads have been woken up and are contending for the mutex in
>> order the all return from their respective pthread_cond_wait calls."
>>
>> "One threads has been woken up and is contending for the mutex in
>> order to return from pthread_cond_wait."
>
>The thread is not contending for the mutex. Assuming the wakeup call was
>done with the mutex unlocked, it'll just acquire it without contention
>and without again having to enter the kernel and can just continue
>running.

The thread (and all other threads released by 'broadcast') will be
contending for the mutex. And it can't "acquire it without contention"
because they may be other threads, not currently waiting on the condition
variable, one of which may be holding the mutex.

[Rainer Weikusat]

sc...@slp53.sl.home (Scott Lurndal) writes:
> Rainer Weikusat <rwei...@talktalk.net> writes:
>>Kaz Kylheku <864-11...@kylheku.com> writes:
>>> On 2023-02-07, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>>>> Its also invisible to the application program so I still don't see
>>>> what the difference and/or advantage of using broadcast vs signal is
>>>> to the application.
>>>
>>> It is completely visible to the application. Compare:
>>>
>>> "Ten threads have been woken up and are contending for the mutex in
>>> order the all return from their respective pthread_cond_wait calls."
>>>
>>> "One threads has been woken up and is contending for the mutex in
>>> order to return from pthread_cond_wait."
>>
>>The thread is not contending for the mutex. Assuming the wakeup call was
>>done with the mutex unlocked, it'll just acquire it without contention
>>and without again having to enter the kernel and can just continue
>>running.
>
> The thread (and all other threads released by 'broadcast') will be
> contending for the mutex.

The paragraph I'm referring to obviously talks about pthread_cond_signal
("one thread has been woken up").

> And it can't "acquire it without contention"
> because they may be other threads, not currently waiting on the condition
> variable, one of which may be holding the mutex.

That's an act of God outside of the scope of this discussion.

[Nicolas George]

Mut...@dastardlyhq.com, dans le message <trt6bs$3h5nq$1...@dont-email.me>,
a écrit :

> How about explaining it then because I can't see it.

Consider a message queue with possibly multiple consumers.

If you add a message to the queue, you should call signal, because only one
consumer will be able to get your message.

If you mark the end of the queue, you should call broadcast, because all
consumers need to know the work is done.

[Mut...@dastardlyhq.com]

On Tue, 7 Feb 2023 19:04:59 -0000 (UTC)
Kaz Kylheku <864-11...@kylheku.com> wrote:
>On 2023-02-07, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>> Yes, that is the official position and in the OS kernel all the threads
>> may well get woken up. However from the application program POV there's no
>> difference because only 1 thread exits pthread_cond_wait() per signal or
>> broadcast sent.
>
>That is simply false. It's true that only one waiting thread at a time
>can exit from the function. But that's because of the mutex.

Err yes, and you can't use condition variables without a mutex so I'm not
sure what your point is.

>If you broadcast the condition, all threads waiting on the condition
>will wake up and contend for the mutex.

I know. And? How does that change the functionality from the POV of the
application code?

>Threads contenting for the mutex proceed when the mutex is available.
>
>Threads sleeping on the condition variable do not proceed regardless
>of what is happening with the mutex.

That makes no sense. Either a thread is waiting in pthread_cond_wait() or it
isn't. If it isn't then its irrelevant to this discussion.

>> If multiple threads exited the wait then that would be a useful paradigm
>> but AFAIK pthreads doesn't supply that functionality.
>
>Yes it does! If you need the paradigm of multiple threads being
>woken up together without having to pass serially through a mutex,
>POSIX provides barriers: pthread_barrier_wait.

Ok, didn't know about that. However it appears to be optional not mandatory
and MacOS doesn't support it so not much use for truly portable code.

[Mut...@dastardlyhq.com]

I don't have time to write boilerplate to get this up and running but I
can't see how using broadcast instead of signal makes any difference
in how the code operates.

[Rainer Weikusat]

Mut...@dastardlyhq.com writes:
> On Tue, 7 Feb 2023 19:33:41 -0000 (UTC)
> Kaz Kylheku <864-11...@kylheku.com> wrote:
>>On 2023-02-07, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>>> Its also invisible to the application program so I still don't see
>>> what the difference and/or advantage of using broadcast vs signal is
>>> to the application.
>>
>>It is completely visible to the application. Compare:
>>
>>"Ten threads have been woken up and are contending for the mutex in
>>order the all return from their respective pthread_cond_wait calls."
>>
>>"One threads has been woken up and is contending for the mutex in
>>order to return from pthread_cond_wait."
>>
>>Do you understand the api_ready example? Here it is again:
>>
>> bool api_ready = false;
>> pthread_mutex_t api_ready_mutex = PTHREAD_MUTEX_INITIALIZER;
>> pthread_cond_t api_ready_cond = PTHREAD_COND_INITIALIZER;
>>
>> // internal function: indicates API is ready
>> static void api_becomes_ready(void)
>> {
>> pthread_mutex_lock(&api_mutex);
>> api_ready = true;
>> pthread_mutex_unlock(&api_mutex);
>> pthread_cond_broadcast(&api_cond); // wake up everyone
>> }

[...]

>>The api_becomes_ready function is called exactly once by the API
>>itself to indicate that it is ready.
>>
>>Muliple threads from different subsystems may have called api_ready_wait
>>in order to wait for this indication.
>>
>>If pthread_cond_signal is used, then quite likely, only one of those
>>threads will wake up; the others will stay stuck forever.
>
> I don't have time to write boilerplate to get this up and running but I
> can't see how using broadcast instead of signal makes any difference
> in how the code operates.

As written, the code is correct with _broadcast and wouldn't be with
signal. Any number of threads can be waiting for the api to become
ready. Hence, whatever threads are actually waiting by that time must be
woken up as they'll otherwise sleep forever.

[Mut...@dastardlyhq.com]

On Wed, 08 Feb 2023 14:56:47 +0000

Rainer Weikusat <rwei...@talktalk.net> wrote:
>Mut...@dastardlyhq.com writes:

>> I don't have time to write boilerplate to get this up and running but I
>> can't see how using broadcast instead of signal makes any difference
>> in how the code operates.
>
>As written, the code is correct with _broadcast and wouldn't be with
>signal. Any number of threads can be waiting for the api to become
>ready. Hence, whatever threads are actually waiting by that time must be
>woken up as they'll otherwise sleep forever.

Yes, they all get woken up then they all go back to sleep again except 1
without doing anything. Sorry, still not seeing it.

[Scott Lurndal]

But the will be sleeping on the mutex, not the condition variable
at that point. A far different sleep entirely.

[Mut...@dastardlyhq.com]

If they're all sleeping on a mutex you don't need condition variables to
start with. Whether you use signal or broadcast ONLY ONE thread exits the
wait. The behaviour from an application program POV is identical.

[Scott Lurndal]

No, when you use broadcast, _all_ threads exit the wait for the event
and start waiting for the mutex. Subsequently, as each thread gets
the mutex, does something in the critical region, then releases
the mutex, the remaining threads will contend for mutex, perform
the critical region and release the mutex. They won't be still waiting
on the condition variable until each thread calls pthread_cond_wait* again.

The difference between signal and broadcast is _what_ the remaining
threads end up waiting for. In the former, the remaining threads
continue to wait on the condition variable; in the latter the
remaining threads contend for the mutex protecting the resource/critical
section.

[Rainer Weikusat]

Without broadcast, only one thread sleeping on the queue of the
condition variable would ever be woken up. All others would remain
sleeping there forever. If they're instead sleeping the queue of the
mutex, they'd eventually all be woken up due to mutex unlock operations.

[Mut...@dastardlyhq.com]

On Wed, 08 Feb 2023 16:36:56 GMT

Ok, someone finally explained it in a comprehensible way. Thanks.

Nowhere have I read that inside pthread_cond_wait() there are 2 possible thread
states which you have to be aware of. What a bloody awful API design.

[Rainer Weikusat]

Mut...@dastardlyhq.com writes:
> On Wed, 08 Feb 2023 16:02:02 GMT
> sc...@slp53.sl.home (Scott Lurndal) wrote:
>>Mut...@dastardlyhq.com writes:
>>>On Wed, 08 Feb 2023 14:56:47 +0000
>>>Rainer Weikusat <rwei...@talktalk.net> wrote:
>>>>Mut...@dastardlyhq.com writes:
>>>>> I don't have time to write boilerplate to get this up and running but I
>>>>> can't see how using broadcast instead of signal makes any difference
>>>>> in how the code operates.
>>>>
>>>>As written, the code is correct with _broadcast and wouldn't be with
>>>>signal. Any number of threads can be waiting for the api to become
>>>>ready. Hence, whatever threads are actually waiting by that time must be
>>>>woken up as they'll otherwise sleep forever.
>>>
>>>Yes, they all get woken up then they all go back to sleep again except 1
>>>without doing anything. Sorry, still not seeing it.
>>
>>But the will be sleeping on the mutex, not the condition variable
>>at that point. A far different sleep entirely.
>
> If they're all sleeping on a mutex you don't need condition variables to
> start with.

A locked mutex has an owner and implementations may throw an error if a
thread other than the one which owns the mutex tries to unlock it (NPTL
does). Condition variables can be signalled by any thread.

> Whether you use signal or broadcast ONLY ONE thread exits the
> wait. The behaviour from an application program POV is identical.

... until this one thread unlocks the mutex. If broadcast had been used
on the condition variable, another thread originally sleeping on that
will now start to run. Otherwise, the outcome is an unlocked mutex and a set
of threads still sleeping on something else.

[Scott Lurndal]

This seems pretty clear to me:

https://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_cond_wait.html

[Mut...@dastardlyhq.com]

On Wed, 08 Feb 2023 17:09:26 GMT

"Once all waiting threads have been unblocked (as by the
pthread_cond_broadcast() operation), the next wait operation on that condition
variable shall form a new dynamic binding with the mutex specified by that wait
operation. Even though the dynamic binding between condition variable and mutex
may be removed or replaced between the time a thread is unblocked from a wait on
the condition variable blah blah blah ....."

I'm not sure what your definition of "clear" is but its obviously very different
to mine.

[Rainer Weikusat]

Mut...@dastardlyhq.com writes:

[...]

> "Once all waiting threads have been unblocked (as by the
> pthread_cond_broadcast() operation), the next wait operation on that condition
> variable shall form a new dynamic binding with the mutex specified by that wait
> operation. Even though the dynamic binding between condition variable and mutex
> may be removed or replaced between the time a thread is unblocked from a wait on
> the condition variable blah blah blah ....."
>
> I'm not sure what your definition of "clear" is but its obviously very different
> to mine.

This seems clear to me: Assuming a condition variable c is initially
idle, ie, there are not threads waiting on in, the mutex m used in the
first call to pthread_cond_wait on c must be recorded somewhere to
enable woken-up threads to acquire the correct mutex. A new mutex mm can be
associated with c once all threads sleeping on c+m have been woken up. But
this shall not affect threads which haven't yet returned to the caller
which slept on c while it was still associated with m.

[Nicolas George]

Scott Lurndal, dans le message <aHQEL.430433$gGD7....@fx11.iad>, a
écrit :

> This seems pretty clear to me:

Not only is it clear, but it is also entirely natural. Once you have threads
of the kind of POSIX threads and mutexes, if you think what API you need to
implement the kind of things conditions are for, and then you compare with
what conditions actually do, your solution is usually more or less the same,
but the condition API is sleeker.

[Scott Lurndal]

Indeed. It is rather similar to the hardware-based mutual exclusion
and event (condition) mechanism we invented for a Burroughs mainframe
around 1982. The LOK instruction was implemented in hardware, OS (MCP)
scheduling was performed in a microkernel that handled all interrupts
and scheduled the highest priority ready task (and very little else other
than timers). The MCP ran at a slightly less privileged level when
processing "system calls" on behalf of a user task (known as Branch Communicate,
i.e. the BCT instruction). The main difference with POSIX is the atomic
releasing of the mutex during the condition wait function.

===== Lock/Unlock (LOK)/OP=60 =====

==== Format ====

^ OP ^ AF ^ BF ^ A Syllable ^

''OP = 60''

**AF** Unused and reserved; can be specified as an indirect field length. A literal flag causes an invalid instruction fault (IEX = 21).\\
**BF** Instruction variant; can be indirect.

^ Variant ^ Function ^
| 10 | Event cause no interrupt |
| 09 | Event cause and reset |
| 08 | Event reset and wait |
| 07 | Test happened status |
| 06 | Event reset |
| 05 | Event wait |
| 04 | Event cause |
| 02 | Conditional lock |
| 01 | Unconditional lock |
| 00 | Unlock |

All other BF values cause an invalid instruction fault (IEX = 26).

**A** is the address of the lock/event structure. Address can be indexed, indirect, or extended. The final address controller must be UN, or an invalid instruction fault (IEX = 03) occurs. The final address must be Mod-2, but the hardware does not check it.\\
If BF has a value of 00-02, A represents a lock structure.\\
If BF has a value of 04-10, A represents an event structure.

The lock structure format is as follows:

^ Information ^ Digits ^
| Lock status field | 00-01 |
| Lock owner field | 02-05 |
| Lock waiter link field | 06-09 |
| Lock number field | 10-13 |
| Lock number link field | 14-17 |
| Reserved | 18-19 |

^ Note: The lowest memory address is 00.^

The event structure format is as follows:

^ Information ^ Digits ^
| Event status field | 00-01 |
| Event owner field | 02-05 |
| Event waiter link field | 06-09 |
| Event designator field | 10-13 |
| Event count | 14-19 |

^ Note: The lowest memory address is 00. ^

If any of the lock/event structure values contain undigits, an invalid
instruction (IEX=07) occurs.

^ Note: This instruction only executes with the privileged enable set otherwise an invalid instruction fault (IEX=02) is reported. ^

==== Function ====

LOK examines the lock/event structure (A) and, depending on its value
and the instruction variant (BF), modifies the lock/event structure
(A) and associated lock fields in the [[processor_state:reinstate_list|reinstate list]] entry for the
current task, and other tasks owning or contending for the lock or
event.

The lock waiter link field and the event waiter link field provide the
MCP kernel with the task number, which execution is linked to, for a
specific change of the current lock or event structure.

The lock number field and the lock number link field implement a
canonical lock algorithm to prevent deadlock situations. All locks are
assigned a level number; a task that owns a lock at level
n can only get a lock at level n+1 or greater. A
lock at a level lower than n can be acquired only by a task that
has released all locks at or above that level in reverse order from which
it had acquired them.

The processor must determine if a lock is owned or available. If the
owner field of the lock structure is zero, the lock is available. If the
owner field is not zero, the lock is owned.

The processor must determine if an event has happened. If the event owner
field is zero, the event has happened. If the event state field is not
equal to zero, the event has not happened.

The event designator field ensures that the current structure is an event
structure. A nonzero value in this field causes a fault.

^ Note: The equivalent field in a lock structure (lock number) is always a nonzero value. ^

The event count field identifies a particular occurrence of a particular
event since the same structure can be used for multiple purposes over a
period of time.

The machine-dependent lock status field of the lock/even structure (A)
can also represent the status of the structure, with one value
representing owned, and another representing available. The lock status
field of the lock structure is not used to determine if the lock is
available.

==== Variants ====

The variants are described as follows:

=== BF=00 Unlock ===

This variant releases a Lock and, if any task is waiting for this lock, causes
an interrupt to the MCP kernel.

Obtain exclusive rights to the lock structure specified by the A address.

The value of the lock owner field must equal the current task
number; otherwise, relinquish exclusive access rights
to the lock structure, cause an invalid instruction fault (IEX=06)
and terminate the instruction with no futher action.

Compare the lock number field of the lock structure (A)
with the MCP canonical lock number field located in the
[[processor_state:reinstate_list|reinstate list entry]] for the current task. If they are not
equal, relinquish exclusive access rights to the lock
structure; cause an invalid instruction fault (IEX=06) and
terminate the instruction with no further action.

Otherwise, store zeros into the lock owner field of the
lock structure (A) to indicate that this lock is available.
It also stores the contents of the lock number link field of
the lock structure (A) into the MCP canonical lock number
field that is located in the reinstate list entry for the
current task.

Examine the lock waiter link field of the lock structure. If it is equal to
zero, set the [[processor_state:comparison_flags|Comparison flags]] to **EQUAL**, relinquish exclusive access rights to
the lock structure and terminate the instruction with no further action.

If the lock waiter link field is not equal to zero, perform the following
operations:
- Set the comparison flags to HIGH.
- Assemble and save, within the processor, the released contended lock value for future update of the instruction interrupt cause descriptor in the [[processor_state:kernel_data_area|kernel data area]].
- Assemble and save, within the processor, the pointer to the reinstate list entry of the task specified by the task number in the lock waiter link field of the lock structure (A). The pointer is to be used for update to the instruction interrupt cause extension descriptor (C7AAAAAA).
- Assemble and save, within the processor, the next instruction address. The next instruction address will be used to update the interrupt frame in the reinstate list entry for the current task.
- Relinquish exclusive access rights to the lock structure.
- Perform an interrupt procedure that reports an instruction interrupt in the interrupt descriptor in the [[processor_state:kernel_data_area|kernel data area]].

=== BF=01 Unconditional Lock ===

This variant competes for the lock specified by the Lock Structure (A) and, if
the lock is owned, causes an interrupt to the MCP kernel.

Obtain exclusive rights to the lock structure specified by the A address.

Compare the lock number field of the lock structure (A) with the MCP canonical lock number field located in the reinstate list entry for the current task. If the lock number field is less than or equal to the MCP canonical lock number field, relinquish exclusive access rights to the lock structure, raise an invalid instruction fault (IEX=06) and terminate the instruction.

If the lock is available, perform the following operations:
- Store the active task number in the lock owner field.
- Copy the contents of the MCP canonical lock number field, that is located in the active reinstate list entry, into the lock number link field of the lock structure.
- Copy the contents of the lock number field of the lock structure into the MCP canonical lock number field that is located in the active reinstate list entry.
- Set the comparison flags to **EQUAL**.
- Relinquish exclusive access rights to the lock structure and terminate the instruction.

If the lock is owned, perfrom the following operations:
- Copy the lock owner field of the lock structure (A) into the task number owning field located in the reinstate list entry for the current task.
- Copy the lock waiter link field of the lock structure (A) to the next task in list field located in the reinstate list entry for the current task.
- Store the current task number into the lock waiter link field of the lock structure (A).
- Store the waiting lock value into the state indicator field located in the reinstate list entry for the current task.
- Set the comparison flags to LOW.
- Assemble and save, within the processor, the failed lock value for update of the instruction interrupt cause descriptor in the kernel data area.
- Assemble and save, within the processor the pointer to the reinstate list entry of the task specified by the task number in the lock owner field of the lock structure (A). The pointer is to be used for update to the instruction interrupt cause extension descriptor (C7AAAAAA).
- Assemble and save, within the processor, the next instruction address to point to the instruction following the current instruction for future update of the interrupt frame in the reinstate list entry for the current task.
- Relinquish exclusive access rights to the lock structure.
- Perform an interrupt procedure that reports an instruction interrupt in the interrupt descriptor in the kernel data area.

Ignore the trace enable toggle, even if trace is enabled. Do not perform a trace hardware call following this variant.

=== BF=02 Conditional Lock ===

This variant attempts to obtain the lock specified by the lock structure at the location specified by the A-address.

Obtain exclusive rights to the lock structure specified by the A address.

Compare the lock number field of the lock structure (A) with the MCP canonical lock number field located in the reinstate list entry for the current task.

If the lock number field is less than or equal to the MCP canonical lock number field, relinquish the exclusive access rights to the lock structure, cuase an instruction fault (IEX=06), and terminate the instruction.

If the lock is available, perform the lock available case of the unconditional lock variant, BF=01.

If the lock is owned, perform the following operations:
* If the lock owner field is equal to the task number, set the comparison flags to LOW, relinquish exclusive access rights to the lock structure, and terminate the instruction.
* If the lock owner field does not equal the current task number, set the comparison flags to HIGH, relinquish exclusive access rights to the lock structure, and terminate the instruction.

=== BF=04 Event Cause ===

This variant causes an event and signals all tasks awaiting the event that the event is available.

Obtain exclusive rights to the lock structure specified by the A address.

If the event designator field is not equal to zero,
relinquish exclusive rights to the event structure, cause an
invalid instruction fault (IEX=06), and terminate the instruction.

If the event is in the happened state, increment the event
count field by one, or if the field is already at the maximum
counter value, reset the counter to zero. Then set the
comparison flags to EQUAL, relinquish the exclusive access rights
to the event structure, and terminate the instruction.

If the event is in the not happened state, increment the event
count field of the event structure (A) by one, or if the field is
already at the maximum counter value, reset the counter to zero.
Then set the event owner field to the happened state (zero).

Examine the event waiter link field of the event structure (A). If it is
equal to zero, set the comparision flags to EQUAL, relinquish exclusive
access rights to the event structure and terminate the instruction with no
further action.

If the event waiter link field is not equal to zero, perform the following
operations:
- Set the comparison flags to HIGH.
- Store zeros in the event waiter link field of the event structure.
- Assemble and save the released event value within the processor for future update of the instruction interrupt cause descriptor in the kernel data area.
- Assemble and save, within the processor, the pointer to the reinstate list entry of the task specified by the task number in the lock owner field of the lock structure (A). The pointer is to be used for update to the instruction interrupt cause extension descriptor (C7AAAAAA).
- Assemble and save, within the processor, the next instruction address to point to the instruction following the current instruction for future update of the interrupt frame in the reinstate list entry for the current task.
- Relinquish exclusive access rights to the event structure.
- Perform an interrupt procedure that reports an instruction interrupt in the interrupt descriptor in the kernel data are

=== BF=05 Event Wait ===

This variant causes the current task to wait until the specified event, if it is in the not happened state, is caused.

Obtain exclusive rights to the lock structure specified by the A address.

If the event designator field is not equal to zero, relinquish exclusive rights to the event structure, cause an invalid instruction fault (IEX=06), and terminate the instruction.

If the event is in the happened state, set the comparison flags to EQUAL, relinquish exclusive rights to the event structure, and terminate the instruction.

If the event is in the not happened state, perform the following operations:
- Copy the event owner field of the event structure (A) into the task number owning field located in the reinstate list entry for the current task.
- Copy the event waiter link field of the event structure (A) into the next task in list field located in the reinstate list entry for the current task.
- Store the current task number into the event waiter link field of the event structure (A).
- Store the waiting event value into the state indicator field located in the reinstate list entry for the current task.
- Set the comparison flags to LOW.
- Assemble and save, within the processor, the failed event value for future update of the instruction interrupt cause descriptor in the kernel data area.
- Assemble and save a 6-digit zero field for future update of the instruction interrupt cause extension descriptor (format 7000000).
- Assemble and save, within the processor, the next instruction address. The next instruction address will be used to update the interrupt frame in the reinstate list entry for the current task.
- Relinquish exclusive access rights to the event structure.
- Perform an interrupt procedure that reports an instruction interrupt in the interrupt descriptor in the kernel area.

Ignore the trace enable toggle, even if trace is enabled. Do not perform a trace hardware call following this variant.

=== BF=06 Event Reset ===

This variant resets the happened state of the event to the not happened state.

Obtain exclusive rights to the lock structure specified by the A address.

If the event designator field is not equal to zero,
relinquishe exclusive rights to the event structure, cause an
invalid instruction fault (IEX=06), and terminate the instruction.

If the event is in the not happened state, set the comparison
flags to HIGH, relinquish exclusive rights to the event
structure, and terminate the instruction.

If the event is in the happened state, store the current task
number into the event owner field of the event structure (A) and
store zeroes into the event waiter link field of the event
structure (A).

Set the comparison flags to EQUAL, relinquish exclusive
rights to the event structure, and terminate the instruction with no further
action..

=== BF=07 Event Test Happened Status ===

This variant tests whether or not an event happened.

Obtain exclusive rights to the lock structure specified by the A address.

If the event designator field is not equal to zero,
relinquish exclusive rights to the event structure, cause an
invalid instruction fault (IEX=06), and terminate the instruction.

If the event is in the not happened state, set the comparison
flags to HIGH, relinquish exclusive rights to the event
structure, and terminate the instruction.

If the event is in the happened state, set the comparison
flags to HIGH, relinquish exclusive rights to the event
structure, and terminate the instruction.

=== BF=08 Event Reset and Wait ===

This variant resets an event structure to the not happened state
and forces the current task to wait until the event has been
caused.

Obtain exclusive rights to the lock structure specified by the A address.

If the event designator field is not equal to zero, LOK
relinquishes exclusive rights to the event structure, causes an
invalid instruction fault (IEX=06), and terminates the instruction.

If the event designator field is equal to zero, LOK does the
following:
- Store the current task number into the event owner field of the event structure (A) and into the task owning field in the reinstated list entry for the current task.
- Copy the event waiter link field of the event structure (A) into the next task in list field located in the reinstate list entry for the current task.
- Store the waiting event value into the state indicator field located in the reinstate list entry for the current task.
- Set the comparison flags to LOW.
- Assemble and save, within the processor, the failed event value for future update of the instruction interrupt cause descriptor in the kernel data area.
- Assemble and save a 6-digit zero field for future update of the instruction interrupt cause extension descriptor (format C7000000).
- Assemble and save, within the processor, the next instruction address to point to the instruction following the current instruction for future update of the interrupt frame in the reinstate list entry for the current task.
- Relinquish the exclusive access rights to the event structure.
- Perform an interrupt procedure that reports an instruction interrupt in the interrupt descriptor in the kernel area.

Ignore the trace enable toggle, even if trace is enabled. Do not perform a trace hardware call following this variant.

=== BF=09 Event Cause and Reset ===

This variant causes an event that allows any task, waiting for the
event, to continue processing and then leaves the event structure
in the not happened state.

Obtain exclusive rights to the lock structure specified by the A address.

If the event designator field is not equal to zero,
relinquish exclusive rights to the event structure, cause an
invalid instruction fault (IEX=06), and terminate the instruction.

If the event designator field is equal to zero, increment the
event count field of the event structure (A) by one, or if the
field is already at the maximum counter value, reset the counter
to zero. Then store the current task number into the event
owner field of the event structure (A).

Examine the event waiter link field of the event structure (A).

If it is equal to zero, set the comparison flags to EQUAL,
relinquish exclusive rights to the event structure, and
terminate the instruction.

If it is not equal to zero, perform the following operations:
- Set the comparison flags to HIGH.
- Store zeros in the event waiter link field of the event structure.
- Assemble and save the released event value within the processor for future update of the instruction interrupt cause descriptor in the kernel data area.
- Assemble and save a 6-digit zero field for future update of the instruction interrupt cause extension descriptor (format C7000000).
- Assemble and save, within the processor, the next instruction address to point to the instruction following the current instruction for future update of the interrupt frame in the reinstate list entry for the current task.
- Relinquish exclusive access rights to the event structure.
- Perform an interrupt procedure that reports an instruction interrupt in the interrupt descriptor in the kernel data area.

=== BF=10 Event Cause No Interrupt ===

This variant causes an event and reports to the current task the
head of the list of the tasks that are waiting for this event.

Obtain exclusive rights to the lock structure specified by the A address.

If the event designator field is not equal to zero,
relinquish exclusive rights to the event structure, set the
comparison flags to LOW, and terminate the instruction.

If the event is in the happened state, increment the event
count field by one, or if the field is already at the maximum
counter value, reset the counter to zero. Then set the
comparison flags to EQUAL, relinquish the exclusive access rights
to the event structure, and terminate the instruction.

If the event is in the not happened state, increment the event
count field of the event structure, A, by one, or if the field is
already at the maximum counter value, reset the counter to zero.
Set the event owner field to the happened state (zero).

Examine the event waiter link field of the event structure (A).

If it is equal to zero, set the comparison flags to EQUAL, relinquish exclusive access rights to the event structure, and terminate the instruction.

If it is not equal to zero, perform the following operations:
- Use the event waiter link field of the event structure as an index into the reinstate list to locate a new specific reinstate list entry. The address of the specified reinstate list entry is stored in memory in the IX1 field, relative to base 0, for the current task (format C7AAAAAA).
- Set the event waiter link field of the event structure (A) to zero.
- Set the comparison flags to HIGH, relinquish exclusive access rights to the event structure and terminate the instruction with no further action.

==== Comparison Flags ====

The [[processor_state:comparison_flags|Comparison Flags]] are set according to
the variant.

[Mut...@dastardlyhq.com]

No.

Clear would be:

"Once the thread is woken up on the condition variable it then waits on
the mutex AND DOES NOT EXIT pthread_cond_wait() until it aquires it."

That is clarity, not the technogibberish above.

[Mut...@dastardlyhq.com]

On Wed, 08 Feb 2023 21:11:18 GMT
sc...@slp53.sl.home (Scott Lurndal) wrote:
>Nicolas George <nicolas$geo...@salle-s.org> writes:
>>Scott Lurndal, dans le message <aHQEL.430433$gGD7....@fx11.iad>, a
>> écrit :
>>> This seems pretty clear to me:
>>
>>Not only is it clear, but it is also entirely natural. Once you have threads
>>of the kind of POSIX threads and mutexes, if you think what API you need to
>>implement the kind of things conditions are for, and then you compare with
>>what conditions actually do, your solution is usually more or less the same,
>>but the condition API is sleeker.
>
>Indeed. It is rather similar to the hardware-based mutual exclusion
>and event (condition) mechanism we invented for a Burroughs mainframe
>around 1982. The LOK instruction was implemented in hardware, OS (MCP)

Did the Tron scriptwriters nick the MCP acronym from you or you from them? :)

[Scott Lurndal]

The paragraph you call technogibberish has nothing to do with
what happens with the mutex, it's more of an internal implementation
detail and a warning to the implementer and the user of the effects of using a single
condition variable with different mutexes.

This paragraph:

Upon successful return, the mutex shall have been locked and
shall be owned by the calling thread.

Is clear and states exactly what you said "clear would be" above.

Perhaps

... the mutex shall have been acquired as if by
pthread_mutex_lock and shall be owned...

would be slightly more clear, but the current statement is clear to
those skilled in the art, which is generally the point of a standard.

[Scott Lurndal]

We were using MCP long before the movie. We (the MCP department) took
a morning off to go to see Tron at a nearby (walking distance) theater
when it came out (the theater was also rented for periodic all-hands
meetings). This was in Pasadena California.

I doubt the scriptwriters had even heard of Burroughs MCP; likely
a parallel development.

[Mut...@dastardlyhq.com]

That also describe the behaviour with signal.

>Is clear and states exactly what you said "clear would be" above.

Its as clear as mud. If people like you write man pages it explains a lot.

[Rainer Weikusat]

As Scott Lurndal already mentioned, this a caveat regarding the
implementation of condition variables: The mutex currently associated
with one must be recorded somewhere. The obvious idea would be whatever
data structure is associated with the condition variable. But that's not
sufficent: If a pthread_cond_broadcast call wakes up all threads waiting
on a condition variable, some of them might not get an actual chance to
run before a subsequent pthread_cond_wait call causes a different mutex
to be associated with it. Hence, the mutex at time of the wakeup must be
recorded somewhere where it remains available to the woken-up threads
regardles of the current state of the condition variable.

[Rainer Weikusat]

Mut...@dastardlyhq.com writes:
> sc...@slp53.sl.home (Scott Lurndal) wrote:
>>Mut...@dastardlyhq.com writes:

[...]

>>>Clear would be:
>>>
>>>"Once the thread is woken up on the condition variable it then waits on
>>>the mutex AND DOES NOT EXIT pthread_cond_wait() until it aquires it."
>>>
>>>That is clarity, not the technogibberish above.
>>
>>The paragraph you call technogibberish has nothing to do with
>>what happens with the mutex, it's more of an internal implementation
>>detail and a warning to the implementer and the user of the effects of using a
>>single
>>condition variable with different mutexes.
>>
>>This paragraph:
>>
>> Upon successful return, the mutex shall have been locked and
>> shall be owned by the calling thread.
>
> That also describe the behaviour with signal.

Obviously, as the behaviour is identical in this regard.

[Mut...@dastardlyhq.com]

Exactly. So in trying to prove the man page was fine showed that even he
hadn't read it properly.

[Nicolas George]

Mut...@dastardlyhq.com, dans le message <ts55k0$10vn2$1...@dont-email.me>,
a écrit :

>>Obviously, as the behaviour is identical in this regard.

^^^^^^^^^^^^^^

> Exactly. So in trying to prove the man page was fine showed that even he
> hadn't read it properly.

You are the one who is not reading properly in this whole thread.

[Mut...@dastardlyhq.com]

On 10 Feb 2023 10:29:37 GMT

I can read fine thank you, however you're not following it properly.
I said the man page was cryptic and he uses an example from its text showing
it describes how broadcast differs from signal when it didn't say any such
thing.

[Nicolas George]

Mut...@dastardlyhq.com, dans le message <ts58nd$11apa$1...@dont-email.me>,
a écrit :

> it describes how broadcast differs from signal when it didn't say any such
> thing.

It says such a thing, but you are obviously deep into Dunning-Kruger
territory when it comes to threads.

[Rainer Weikusat]

Ehh ... no ... the implementation note is unrelated to this issue and
the difference between signal and broadcast is that the latter wakes up
all threads sleeping on the condition variable. As they must all acquire
the mutex before returning to the caller, it follows that they'll now
all be sleeping on the queue of that until each got its turn to hold
it.

[Mut...@dastardlyhq.com]

On 10 Feb 2023 12:06:14 GMT

Whatever. I'm certainly tired of this thread.

[Kaz Kylheku]

On 2023-02-07, Scott Lurndal <sc...@slp53.sl.home> wrote:
> Rainer Weikusat <rwei...@talktalk.net> writes:
>>Kaz Kylheku <864-11...@kylheku.com> writes:
>>> On 2023-02-07, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>>>> Its also invisible to the application program so I still don't see
>>>> what the difference and/or advantage of using broadcast vs signal is
>>>> to the application.
>>>
>>> It is completely visible to the application. Compare:
>>>
>>> "Ten threads have been woken up and are contending for the mutex in
>>> order the all return from their respective pthread_cond_wait calls."
>>>
>>> "One threads has been woken up and is contending for the mutex in
>>> order to return from pthread_cond_wait."
>>
>>The thread is not contending for the mutex. Assuming the wakeup call was
>>done with the mutex unlocked, it'll just acquire it without contention
>>and without again having to enter the kernel and can just continue
>>running.
>
> The thread (and all other threads released by 'broadcast') will be
> contending for the mutex. And it can't "acquire it without contention"
> because they may be other threads, not currently waiting on the condition
> variable, one of which may be holding the mutex.

Well, it can; if the time spent in the mutex after the pthread_cond_wait
is very short, it could be that it's entirely uncontended.

On a single processor it could happen in an obvious way: only one thread
at a time runs. Several threads are made runnable by the broadcast.
One is at th ehead of the run queue. It acquires the mutex, returns from
pthread_cond_wait, does something in the mutex and then calls
pthread_mutex_unlock. Its time quantum is nowhere near up yet; the other
threads are still in the run queue. As they are dispatched by the
scheduler one by one, it's entirely possible they each find the mutex
similarly uncontended.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazi...@mstdn.ca

[Kaz Kylheku]

On 2023-02-08, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
> On Wed, 08 Feb 2023 14:56:47 +0000

> Rainer Weikusat <rwei...@talktalk.net> wrote:
>>Mut...@dastardlyhq.com writes:

>>> I don't have time to write boilerplate to get this up and running but I
>>> can't see how using broadcast instead of signal makes any difference
>>> in how the code operates.
>>
>>As written, the code is correct with _broadcast and wouldn't be with
>>signal. Any number of threads can be waiting for the api to become
>>ready. Hence, whatever threads are actually waiting by that time must be
>>woken up as they'll otherwise sleep forever.
>
> Yes, they all get woken up then they all go back to sleep again except 1
> without doing anything. Sorry, still not seeing it.

No, threads woken up by pthread_cond_broadcast do not go back to sleep;
they all return from the pthread_cond_wait function. That function call has
a loop around it; so they will go back to sleep only if the loop
iterates again. The loop is guarded by the while (!api_ready) condition
which was set true before the pthread_cond_broadcast call, So all the
threads returning from the condition wait will see the true value and
bail out of the loop, returning from api_ready_wait.

The loop is is in the critical region protected by the mutex, so that
only one thread at a time can be checking while (!api_ready).
That's a separate consideration. "All threads return from
pthread_cond_wait" doesn't mean they do that concurrently; since a
thread returning from that function owns the mutex, all threads
returning from a condition wait against the same mutex are serialized.
Being serialized is not the same thing as being indefinitely blocked.

[Kaz Kylheku]

On 2023-02-08, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:

> If they're all sleeping on a mutex you don't need condition variables to
> start with.

1. condition varaibles exist because you can't do everything with mutexes.

2. the idea they are sleeping on the mutex is a simplification; it's
possible that the threads woken by the broadcast can each get the mutex
without waiting for it. This will happen on a single processor, if the
critical region is short:

E.g. here it is very short, just a few instructions:

while (!api_ready)
pthread_cond_wait(...)

pthread_mutex_unlock(...)

the returning thread acquires the mutex, examines api_ready,
finds it to be true, and immediately gives up the mutex.

You have to use multiple processors to get contention. On a single
processor, pthread_cond_broadcast will transfer all the waiting threads
to the run queue. The scheduler will then serialize their execution,
because only one thread can have the CPU at a time. So the first thread
gets the CPU, which may give it a time quantum of up to several
milliseconds or whatever. During that time quantum, it gets the mutex,
checks the flag and releases it. None of the other woken up threads
have yet executed, yet the first one is already done with the mutex;
it's returned out of api_ready_wait and has moved on to other work.
When the second thread is dispatched, it may well find the mutex
unlocked, and ditto with the third and subsequent.

> Whether you use signal or broadcast ONLY ONE thread exits the
> wait. The behaviour from an application program POV is identical.

If people are escaping from a burning a building, don't you think there
is a difference between "one person at a time jumps out of the window
onto the life net so they are all saved" versus "only one person manages
to jump out of the window to safety?"

[Kaz Kylheku]

On 2023-02-08, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:

> Nowhere have I read that inside pthread_cond_wait() there are 2
> possible thread states which you have to be aware of.

No, there aren't. Condition variablews are specifically stateless (or
appear that way to the application), which make them easy to use. You
don't have to think whether a condition variable is in some signalled
versus non-signalled state.

> What a bloody awful API design.

What is your proposal to fix it, or make an alternative?

Condition variables are directly derived from an invention called
"monitors and condition variables", by C. A. R. Hoare.
(Monitors and condition variables have some different properties
from POSIX-like mutexes and condition variables; there are certain
guarantees so that while loops are not required around condition waits.)

Anyway the API design comes more or less from the theory, which dictates
what it looks like.

Microsoft eventually added condition variables to Windows, and look,
the API is the same, under different names.

https://learn.microsoft.com/en-us/windows/win32/sync/condition-variables

If you think conditions are mutexes are complicated to use, you can use
something else. Conditions are very good for implementing other
kinds of primitives and being sure you got it right.

E.g. it's pretty trivial to make a correct counting semaphore with
a mutex and condition. The reverse isn't true; implementing conditions
with semaphores is a tricky exercise.

[Mut...@dastardlyhq.com]

On Sat, 11 Feb 2023 06:30:46 -0000 (UTC)
Kaz Kylheku <864-11...@kylheku.com> wrote:
>On 2023-02-08, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>> On Wed, 08 Feb 2023 14:56:47 +0000
>> Rainer Weikusat <rwei...@talktalk.net> wrote:
>>>Mut...@dastardlyhq.com writes:
>>>> I don't have time to write boilerplate to get this up and running but I
>>>> can't see how using broadcast instead of signal makes any difference
>>>> in how the code operates.
>>>
>>>As written, the code is correct with _broadcast and wouldn't be with
>>>signal. Any number of threads can be waiting for the api to become
>>>ready. Hence, whatever threads are actually waiting by that time must be
>>>woken up as they'll otherwise sleep forever.
>>
>> Yes, they all get woken up then they all go back to sleep again except 1
>> without doing anything. Sorry, still not seeing it.
>
>No, threads woken up by pthread_cond_broadcast do not go back to sleep;
>they all return from the pthread_cond_wait function. That function call has

No they don't all return, only 1 does.

Its interesting that hardly anyone really understands the difference between
the signal and broadcast and to me that is indicative of a very poorly designed
API.

[Mut...@dastardlyhq.com]

On Sat, 11 Feb 2023 07:13:26 -0000 (UTC)
Kaz Kylheku <864-11...@kylheku.com> wrote:
>On 2023-02-08, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>> Nowhere have I read that inside pthread_cond_wait() there are 2
>> possible thread states which you have to be aware of.
>
>No, there aren't. Condition variablews are specifically stateless (or
>appear that way to the application), which make them easy to use. You

I meant the *function* has 2 states:
1) Waiting on the condition variable
2) Waiting on the mutex

It would seem that for signal only 1 thread goes from 1 -> 2 whereas with
broadcast ALL threads go from 1 -> 2 but only ONE thread exits the wait()
function in either case.

>don't have to think whether a condition variable is in some signalled
>versus non-signalled state.
>
>> What a bloody awful API design.
>
>What is your proposal to fix it, or make an alternative?

Apperently there is an alternative in pthreads someone mentioned called
barriers but its not mandatory and MacOS doesn't support them. However
they don't seem to have this 2 state locking nonsense.

>Condition variables are directly derived from an invention called
>"monitors and condition variables", by C. A. R. Hoare.
>(Monitors and condition variables have some different properties
>from POSIX-like mutexes and condition variables; there are certain
>guarantees so that while loops are not required around condition waits.)
>
>Anyway the API design comes more or less from the theory, which dictates
>what it looks like.

Thats the trouble with theories - they don't always translate into real world
use very well.

>E.g. it's pretty trivial to make a correct counting semaphore with
>a mutex and condition. The reverse isn't true; implementing conditions
>with semaphores is a tricky exercise.

SysV semaphores do a good job but the API is a mess.

[Gary R. Schmidt]

On 11/02/2023 20:49, Mut...@dastardlyhq.com wrote:
> On Sat, 11 Feb 2023 06:30:46 -0000 (UTC)
> Kaz Kylheku <864-11...@kylheku.com> wrote:
>> On 2023-02-08, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>>> On Wed, 08 Feb 2023 14:56:47 +0000
>>> Rainer Weikusat <rwei...@talktalk.net> wrote:
>>>> Mut...@dastardlyhq.com writes:
>>>>> I don't have time to write boilerplate to get this up and running but I
>>>>> can't see how using broadcast instead of signal makes any difference
>>>>> in how the code operates.
>>>>
>>>> As written, the code is correct with _broadcast and wouldn't be with
>>>> signal. Any number of threads can be waiting for the api to become
>>>> ready. Hence, whatever threads are actually waiting by that time must be
>>>> woken up as they'll otherwise sleep forever.
>>>
>>> Yes, they all get woken up then they all go back to sleep again except 1
>>> without doing anything. Sorry, still not seeing it.
>>
>> No, threads woken up by pthread_cond_broadcast do not go back to sleep;
>> they all return from the pthread_cond_wait function. That function call has
>
> No they don't all return, only 1 does.
>

That does not tally with my experience.

What Operating System, programming language, and pthreads library are
you using? (You may have mentioned these things ages ago, I don't recall.)

> Its interesting that hardly anyone really understands the difference between
> the signal and broadcast and to me that is indicative of a very poorly designed
> API.
>

Well, those of us who have been using pthreads for a few decades seem to
have no trouble.

Cheers,
Gary B-)

[Mut...@dastardlyhq.com]

On Sat, 11 Feb 2023 22:28:48 +1100
"Gary R. Schmidt" <grsc...@acm.org> wrote:
>On 11/02/2023 20:49, Mut...@dastardlyhq.com wrote:
>> On Sat, 11 Feb 2023 06:30:46 -0000 (UTC)
>> Kaz Kylheku <864-11...@kylheku.com> wrote:
>>> On 2023-02-08, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>>>> On Wed, 08 Feb 2023 14:56:47 +0000
>>>> Rainer Weikusat <rwei...@talktalk.net> wrote:
>>>>> Mut...@dastardlyhq.com writes:
>>>>>> I don't have time to write boilerplate to get this up and running but I
>>>>>> can't see how using broadcast instead of signal makes any difference
>>>>>> in how the code operates.
>>>>>
>>>>> As written, the code is correct with _broadcast and wouldn't be with
>>>>> signal. Any number of threads can be waiting for the api to become
>>>>> ready. Hence, whatever threads are actually waiting by that time must be
>>>>> woken up as they'll otherwise sleep forever.
>>>>
>>>> Yes, they all get woken up then they all go back to sleep again except 1
>>>> without doing anything. Sorry, still not seeing it.
>>>
>>> No, threads woken up by pthread_cond_broadcast do not go back to sleep;
>>> they all return from the pthread_cond_wait function. That function call has
>>
>> No they don't all return, only 1 does.
>>
>That does not tally with my experience.

I don't believe you. If all threads exited the wait at the same time that
would mean they'd all acquired a lock on the same mutex at the same time.

>What Operating System, programming language, and pthreads library are
>you using? (You may have mentioned these things ages ago, I don't recall.)

MacOS.

>Well, those of us who have been using pthreads for a few decades seem to
>have no trouble.

I'd revisit the pthread_cond_wait man page if I were you.

[Scott Lurndal]

Gary wrote that they exited the wait. By that, he was referring to
the internal implementation of pthread_cond_wait, he did not intend
to imply that the they returned from the pthread_cond_wait call;
clearly only one of the threads racing on the mutex will acquire
it, thus only one thread can return from pthread_cond_wait and
the remainder will wait for that thread to release the mutex
either explicitly or implicitly (e.g. calling pthread_cond_wait).

[Scott Lurndal]

Kaz Kylheku <864-11...@kylheku.com> writes:
>On 2023-02-08, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>> Nowhere have I read that inside pthread_cond_wait() there are 2
>> possible thread states which you have to be aware of.
>
>No, there aren't. Condition variablews are specifically stateless (or
>appear that way to the application), which make them easy to use. You
>don't have to think whether a condition variable is in some signalled
>versus non-signalled state.
>
>> What a bloody awful API design.
>
>What is your proposal to fix it, or make an alternative?
>
>Condition variables are directly derived from an invention called
>"monitors and condition variables", by C. A. R. Hoare.
>(Monitors and condition variables have some different properties
>from POSIX-like mutexes and condition variables; there are certain
>guarantees so that while loops are not required around condition waits.)

There was an early unix implementation of mutexes and condition
variables in Ultrix in the mid-80's when it added support for
multithreaded applications. Members of that team participated
heavily in the posix 1003.4 development that resulted in pthreads.

VMS on the other hand, used a more heavy-weight, but rather flexible
waiting mechanism called event flags, which Cutler brought over
when designing NT. The event flags interface allowed one to wait
on a set of events, rather than the single event that pthread condition
variables support.

Earlier mainframes had custom wait-for-event interfaces, such as
Burroughs complex wait (a more generalized version of the unix
poll(2) or select(2) system calls which allowed the application
to wait for a wide variety of events atomically, such as
I/O complete for a card reader, a timer, a message from another
application, input from a datacomm terminal, host-to-host
communications or a network packet.

Along with Hoare, was CSP (Cooperating Sequential Processes)
by Dykstra wherein he coined the term 'loosely connected processes',
or what we'd call today multithreaded processes and introduced
the concept of the semaphore as a synchronization primitive.

Then there were the distributed synchronization algorithms
espoused by Leslie Lamport (particularly with respect to
obtaining a consistent and rational view of time).

https://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html

[Mut...@dastardlyhq.com]

On Sat, 11 Feb 2023 17:01:34 GMT
sc...@slp53.sl.home (Scott Lurndal) wrote:

>Kaz Kylheku <864-11...@kylheku.com> writes:
>>Condition variables are directly derived from an invention called
>>"monitors and condition variables", by C. A. R. Hoare.
>>(Monitors and condition variables have some different properties
>>from POSIX-like mutexes and condition variables; there are certain
>>guarantees so that while loops are not required around condition waits.)
>
>There was an early unix implementation of mutexes and condition
>variables in Ultrix in the mid-80's when it added support for
>multithreaded applications. Members of that team participated
>heavily in the posix 1003.4 development that resulted in pthreads.
>
>VMS on the other hand, used a more heavy-weight, but rather flexible
>waiting mechanism called event flags, which Cutler brought over
>when designing NT. The event flags interface allowed one to wait

Shame he didn't port VMS's reliability too.

[Kaz Kylheku]

On 2023-02-11, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
> On Sat, 11 Feb 2023 06:30:46 -0000 (UTC)
> Kaz Kylheku <864-11...@kylheku.com> wrote:
>>No, threads woken up by pthread_cond_broadcast do not go back to sleep;
>>they all return from the pthread_cond_wait function. That function call has
>
> No they don't all return, only 1 does.

They all return, just not at the same time. Obviously, if the first
thread which returns does something unusual, like never unlocking the
mutex, then the others are stuck. That's almost certainly going to only
happen due to a bug.

I have the impression you are just trying to rearrange the verbal
expressions of concepts instead of thinking in terms of the actual
concurrency.

[Kaz Kylheku]

On 2023-02-11, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:

> On Sat, 11 Feb 2023 07:13:26 -0000 (UTC)
> Kaz Kylheku <864-11...@kylheku.com> wrote:
>>On 2023-02-08, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>>> Nowhere have I read that inside pthread_cond_wait() there are 2
>>> possible thread states which you have to be aware of.
>>
>>No, there aren't. Condition variablews are specifically stateless (or
>>appear that way to the application), which make them easy to use. You
>
> I meant the *function* has 2 states:
> 1) Waiting on the condition variable
> 2) Waiting on the mutex

Such states are not externally observable. There is literally no
standard API by which you can tell, and application logic isn't
required to handle any such states.

> It would seem that for signal only 1 thread goes from 1 -> 2 whereas with
> broadcast ALL threads go from 1 -> 2 but only ONE thread exits the wait()
> function in either case.

That is not the proper understanding. Whether (2) waiting on the mutex
happens is a matter of chance: it depends on factors like how many
processors are there, and how long is the mutex being held.

All those threads will go through the mutex, taking turns owning it; but
that doesn't imply they were ever waiting on it. Mutex locks can be
acquired without waiting.

>>don't have to think whether a condition variable is in some signalled
>>versus non-signalled state.
>>
>>> What a bloody awful API design.
>>
>>What is your proposal to fix it, or make an alternative?
>
> Apperently there is an alternative in pthreads someone mentioned called

That was me.

> barriers but its not mandatory and MacOS doesn't support them.

That's pretty lame; I wrote the first glibc/linux version of
pthread_barrier_wait in 2001, now 22 years ago. Kids born then
are graduating with degrees.

Be that as it may, you can quite easily make barriers if you have
mutexes/conditions. A program depending on pthread_barrier_wait can
easily supply its own implementation to be ported to a system where that
is missing.

Barriers are not an alternative to conditions.

> However they don't seem to have this 2 state locking nonsense.

Barriers are also not useful in many situations in which conditions
are. They have their own limitations. You have to declare how many
threads are using a barrier. When that many threads wait on it, the
barrier triggers, letting them all go. One of the threads is selected
(perhaps randomly) as the "serial thread": it receives a different
return value informing it.

This is useful for parallel processing scenarios, where you have all the
threads doing some portion of the same overall task, like some sort
of parallelized number crunching.

>>E.g. it's pretty trivial to make a correct counting semaphore with
>>a mutex and condition. The reverse isn't true; implementing conditions
>>with semaphores is a tricky exercise.
>
> SysV semaphores do a good job but the API is a mess.

Good job of what? Implementing condition variables?

[Mut...@dastardlyhq.com]

On Sun, 12 Feb 2023 05:35:48 -0000 (UTC)

Kaz Kylheku <864-11...@kylheku.com> wrote:
>On 2023-02-11, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>> On Sat, 11 Feb 2023 06:30:46 -0000 (UTC)
>> Kaz Kylheku <864-11...@kylheku.com> wrote:
>>>No, threads woken up by pthread_cond_broadcast do not go back to sleep;
>>>they all return from the pthread_cond_wait function. That function call has
>>
>> No they don't all return, only 1 does.
>
>They all return, just not at the same time. Obviously, if the first
>thread which returns does something unusual, like never unlocking the
>mutex, then the others are stuck. That's almost certainly going to only
>happen due to a bug.

Why is it a bug? It may be a long time before the first exiting the wait
unlocks the mutex depending on what the program does. The fact remains that
only one thread exits the wait at a time regardless of whether you send a
signal or broadcast. The disctinction in the behaviour is confusing and IMO
its a poorly designed API. For a start if all you want to do is control
threads stopping and starting without potentially having a deadlock with the
controlling thread there's no need to use mutexes in the first place.

[Mut...@dastardlyhq.com]

On Sun, 12 Feb 2023 06:27:07 -0000 (UTC)

Kaz Kylheku <864-11...@kylheku.com> wrote:
>On 2023-02-11, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>> On Sat, 11 Feb 2023 07:13:26 -0000 (UTC)
>> Kaz Kylheku <864-11...@kylheku.com> wrote:
>>>On 2023-02-08, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>>>> Nowhere have I read that inside pthread_cond_wait() there are 2
>>>> possible thread states which you have to be aware of.
>>>
>>>No, there aren't. Condition variablews are specifically stateless (or
>>>appear that way to the application), which make them easy to use. You
>>
>> I meant the *function* has 2 states:
>> 1) Waiting on the condition variable
>> 2) Waiting on the mutex
>
>Such states are not externally observable. There is literally no
>standard API by which you can tell, and application logic isn't
>required to handle any such states.

No, but the application logic has to be different depending on whether you're
using signal or broadcast.

>> It would seem that for signal only 1 thread goes from 1 -> 2 whereas with
>> broadcast ALL threads go from 1 -> 2 but only ONE thread exits the wait()
>> function in either case.
>
>That is not the proper understanding. Whether (2) waiting on the mutex
>happens is a matter of chance: it depends on factors like how many
>processors are there, and how long is the mutex being held.

If the API behaves differently depending on the hardware core count then
frankly its a POS and shouldn't be used.

>> barriers but its not mandatory and MacOS doesn't support them.
>
>That's pretty lame; I wrote the first glibc/linux version of
>pthread_barrier_wait in 2001, now 22 years ago. Kids born then
>are graduating with degrees.

Yeah well, Apple. They tend to suffer from NIH syndrome quite badly. I guess
I'm lucky they support pthreads at all.

>Be that as it may, you can quite easily make barriers if you have
>mutexes/conditions. A program depending on pthread_barrier_wait can
>easily supply its own implementation to be ported to a system where that
>is missing.

Lifes too short.

>> SysV semaphores do a good job but the API is a mess.
>
>Good job of what? Implementing condition variables?

Gatekeeping critical code sections in seperate processes (not sure about
threads, are they thread safe?).

[Rainer Weikusat]

Mut...@dastardlyhq.com writes:
> Kaz Kylheku <864-11...@kylheku.com> wrote:
>>On 2023-02-11, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>>> On Sat, 11 Feb 2023 07:13:26 -0000 (UTC)
>>> Kaz Kylheku <864-11...@kylheku.com> wrote:
>>>>On 2023-02-08, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>>>>> Nowhere have I read that inside pthread_cond_wait() there are 2
>>>>> possible thread states which you have to be aware of.
>>>>
>>>>No, there aren't. Condition variablews are specifically stateless (or
>>>>appear that way to the application), which make them easy to use. You
>>>
>>> I meant the *function* has 2 states:
>>> 1) Waiting on the condition variable
>>> 2) Waiting on the mutex
>>
>>Such states are not externally observable. There is literally no
>>standard API by which you can tell, and application logic isn't
>>required to handle any such states.
>
> No, but the application logic has to be different depending on whether you're
> using signal or broadcast.

One would assume that different applications use either broadcast or
signal, depending on what the intended use of the condition variable
is.

>>> It would seem that for signal only 1 thread goes from 1 -> 2 whereas with
>>> broadcast ALL threads go from 1 -> 2 but only ONE thread exits the wait()
>>> function in either case.
>>
>>That is not the proper understanding. Whether (2) waiting on the mutex
>>happens is a matter of chance: it depends on factors like how many
>>processors are there, and how long is the mutex being held.
>
> If the API behaves differently depending on the hardware core count then
> frankly its a POS and shouldn't be used.

The API doesn't behave differently. The behaviour of the implementation
depends partially on the hardware. It also depends on the available
system facilities. Eg, on Linux, there's a FUTEX_CMP_REQUEUE operation
which can be used to implement pthread_cond_broadcast more efficiently
than a naive implementation: Assuming more than one thread is sleeping
on the condition variable, a single syscall can be used to wake up n
threads (usually 1) and move the remaining ones to the queue of the
mutex would the wake up, exit kernel, test lock, enter kernel, sleep
dance.

[Rainer Weikusat]

But that's not what a condition variable is supposed to be good for. The
idea behind that is that there's some shared state, eg, head and tail/
chain pointers for queue different threads need to work with. Hence, a
mutex is needed to serialize access to this state. The simple example is
a set of consumer threads consuming work items produced by a set of
producer threads. A producer thread does the following:

1. Lock the mutex.
2. Put a work item on the queue.
3. Unlock the mutex.
4. Broacast on the condition variable to wake up sleeping consumer
threads.

Consumer thread:

1. Lock the mutex.
2. Work to do? If so, goto 5
3. Sleep on condvar.
4. Goto 2.
5. Take work item off the queue.
6. Unlock the mutex.

[Kaz Kylheku]

On 2023-02-12, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
> On Sun, 12 Feb 2023 05:35:48 -0000 (UTC)
> Kaz Kylheku <864-11...@kylheku.com> wrote:
>>On 2023-02-11, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>>> On Sat, 11 Feb 2023 06:30:46 -0000 (UTC)
>>> Kaz Kylheku <864-11...@kylheku.com> wrote:
>>>>No, threads woken up by pthread_cond_broadcast do not go back to sleep;
>>>>they all return from the pthread_cond_wait function. That function call has
>>>
>>> No they don't all return, only 1 does.
>>
>>They all return, just not at the same time. Obviously, if the first
>>thread which returns does something unusual, like never unlocking the
>>mutex, then the others are stuck. That's almost certainly going to only
>>happen due to a bug.
>
> Why is it a bug? It may be a long time before the first exiting the wait
> unlocks the mutex depending on what the program does.

It may or may not.

The point is that all the threads that were waiting on the condition are
no longer waiting on it; they are waiting to return from the funtion,
which is subject to being serialized.

Like people who got their burgers from the fast food restaurant, which
are just passing through the exit door. They are not waiting for
burgers, just their turn to exit.

Now imagine there was some situation like "restaurant on fire". That
condition has to be broadcast: everyone leave! The customers stop
waiting for burgers and head for the door. They still can't pass through
it at the same time; one person emerges at a time.

> The fact remains that
> only one thread exits the wait at a time regardless of whether you send a
> signal or broadcast.

The fact remains that only one person leaves the burger joint, whether
or not you sound a fire alarm telling them all to leave, or whether
a single burger order was just filled, and the other customers are still
waiting for theirs.

> The disctinction in the behaviour is confusing and IMO
> its a poorly designed API.

Not to anyone who understands burger joints, doors and fire alarms.

> For a start if all you want to do is control
> threads stopping and starting without potentially having a deadlock with the
> controlling thread there's no need to use mutexes in the first place.

Controlling the starting and stopping of another thread is fraught with
race conditions. Pretty much only two kinds of applications do this:
debuggers, and stop-the-world garbage collectors.

You cannot use that for everyday synchronization.

[Kaz Kylheku]

On 2023-02-12, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:

> On Sun, 12 Feb 2023 06:27:07 -0000 (UTC)
> Kaz Kylheku <864-11...@kylheku.com> wrote:
>>On 2023-02-11, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>>> On Sat, 11 Feb 2023 07:13:26 -0000 (UTC)
>>> Kaz Kylheku <864-11...@kylheku.com> wrote:
>>>>On 2023-02-08, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>>>>> Nowhere have I read that inside pthread_cond_wait() there are 2
>>>>> possible thread states which you have to be aware of.
>>>>
>>>>No, there aren't. Condition variablews are specifically stateless (or
>>>>appear that way to the application), which make them easy to use. You
>>>
>>> I meant the *function* has 2 states:
>>> 1) Waiting on the condition variable
>>> 2) Waiting on the mutex
>>
>>Such states are not externally observable. There is literally no
>>standard API by which you can tell, and application logic isn't
>>required to handle any such states.
>
> No, but the application logic has to be different depending on whether you're
> using signal or broadcast.

Umm, not really. Mostly, you just have to avoid using signal when the
logic calls for brodcast, and use broadcast.

If you need broadcast, but insist on using signal, then your application
logic has to be different --- because the code as-is will not work with
signal. You have to somehow emulate the behavior of broadcast.

Rainer W. pointed this out in a reasponse to the api_ready example:
there is a way to code it without broadcast with additional logic,
involving signal being called multiple times.

We can work this back into the burger joint example. Signal is used
to indicate that a customer's order is ready. If the place is on fire,
that situation is broadcast, so everyone leaves.

Suppose you don't broadcast the "fire" signal, but still want to get
everyone to leave? You can do it like this: signal one person to leave
the building. When they exit, /they/ turn around and signal again,
causing the next person inside to exit. This repeats until the last
person leaves. When the last person signals into the building, there is
nobody left there so the signal is ignored. (If the building maitains a
count how of many people are in it, this wasteful last signal can be
avoided.)

This is simply a simulation of broadcast, which distributes the
responsibility among the threads.

>>> It would seem that for signal only 1 thread goes from 1 -> 2 whereas with
>>> broadcast ALL threads go from 1 -> 2 but only ONE thread exits the wait()
>>> function in either case.
>>
>>That is not the proper understanding. Whether (2) waiting on the mutex
>>happens is a matter of chance: it depends on factors like how many
>>processors are there, and how long is the mutex being held.
>
> If the API behaves differently depending on the hardware core count then
> frankly its a POS and shouldn't be used.

Anything with threads behaves differently based on OS platform and
its scheduling, number of cores, system load, tuning parameters, CPU
model, ...

If the application has any dependency on the execution order of pieces
of logic on different threads, then it has to ensure that somehow;
otherwise it's just depending on that by fluke.

It's possible for mutexes and ocnditions to provide stronger guarantees
about certain behaviors. For instance we can have Hoare semantics,
whereby the signaler atomically transfers a waiting thread into the
mutex, and is then guaranteed to immediately get the mutex back when
that thread is done (no matter who else wants the mutex in the
meanwhile). Hoare's semantics make it easier to prove the correctness of
some programs --- but are awful for implementing the stuff on a modern
multiprocessor, in terms of performance.

There is a tradeoff between enforcing orders---who gets the mutex in
what order, and what not---and performance. Enforcing orders introduces
overhead. Potentially huge overhead. Because you run into situations
like, for instance, a thread currently running on a processor being
primed and ready to seize a mutex, do something quick and release it,
but being prevented from doing that because some other thread is
supposed to get that mutex first. Wasteful context switching occurs.
The threads involved execute hundreds, or thousands of unnecessary
instructions.

[Mut...@dastardlyhq.com]

Nonsense. What do you think spinlocks are for?

[Kaz Kylheku]

Mainly, I think that spinlocks are not an example of one thread
controlling (stopping, starting) the execution of another, so they
are unrelated to my remarks.

Spinlocks are a kind of mutex. They are acquired and released, and
understood to be held by a thread (or other context).

Deadlocks are possible with spinlocks, just as with mutexes.
For instance, two threads both try to acquire a pair of spinlocks,
but in opposite order.

[Scott Lurndal]

Kaz Kylheku <864-11...@kylheku.com> writes:
>On 2023-02-14, Mut...@dastardlyhq.com <Mut...@dastardlyhq.com> wrote:
>> On Tue, 14 Feb 2023 02:46:45 -0000 (UTC)
>> Kaz Kylheku <864-11...@kylheku.com> wrote:
>>>> For a start if all you want to do is control
>>>> threads stopping and starting without potentially having a deadlock with the
>>>> controlling thread there's no need to use mutexes in the first place.
>>>
>>>Controlling the starting and stopping of another thread is fraught with
>>>race conditions. Pretty much only two kinds of applications do this:
>>>debuggers, and stop-the-world garbage collectors.
>>>
>>>You cannot use that for everyday synchronization.
>>
>> Nonsense. What do you think spinlocks are for?
>
>Mainly, I think that spinlocks are not an example of one thread
>controlling (stopping, starting) the execution of another, so they
>are unrelated to my remarks.
>
>Spinlocks are a kind of mutex. They are acquired and released, and
>understood to be held by a thread (or other context).
>
>Deadlocks are possible with spinlocks, just as with mutexes.
>For instance, two threads both try to acquire a pair of spinlocks,
>but in opposite order.

Although to be fair, you can use a spinlock as a sort of condition
variable in cases where:
1) there will only be one waiter and you want signal semantics
2) there may be multiple waiters and you want broadcast semantics
3) you don't care that a core will be spinning while waiting.

More suitable for coordinating between supervisory software
on an SMP processor (i.e. a bare metal hypervisor).

/**
* Initialize the condition variable to a unsignalled state.
*/
inline void
c_condition::init(void)
{
condition = 0;
timedout = 0;
}

/**
* Wait for condition state to be signalled. The waiter is awakened by
* the c_condition::signal() function setting the c_condition::condition
* value to 1.
*/
inline void
c_condition::wait(void)
{
__asm__ __volatile__ (
"\n1:\t"
"testl $0xffffffff, %0\n\t"
"jnz 2f\n\t"
"xorq %%rcx, %%rcx\n\t"
"xorq %%rdx, %%rdx\n\t"
"leaq %0, %%rax\n\t"
"monitor\n\t"
"testl $0xffffffff, %0\n\t"
"jnz 2f\n\t"
"xorq %%rax, %%rax\n\t"
"mwait\n\t"
"jmp 1b\n\t"
"2:\n\t"
"movl $0, %0\n\t"
:
: "m"(condition)
: "memory", "ax", "cx", "dx");
}

/**
* Signal condition. Implemented by setting the condition value to 1.
*/
inline void
c_condition::signal(void)
{
__asm__ __volatile__ ("movl $1, %0": "=m" (condition): : "memory");
}

/**
* Condition variable with timeout semantics. Wait for the condition
* to be signalled, or a specified timeout to elapse. Returns 'true'
* if the timeout fired.
*
* @param ns The number of nanoseconds to wait.
* @returns true if the wait was satisfied, false if the timer fired.
*/
bool
c_condition::timed_wait(uint64 ns)
{
timedout = 0;
c_timer *to = new c_timer(c_timer::ONESHOT,
c_core::get_current()->get_current_time() + ns, this);

wait();

delete to;
return (timedout == 0);
}

/**
* Callback function for condition variable timer expiration.
*
* @param arg Callback argument, unused.
*/
void
c_condition::timer_callback(void *arg)
{
timedout = 1;
signal();
}

/**
* Wait for condition state to be signalled. The waiter is awakened by
* the c_condition::signal() function setting the c_condition::condition
* value to 1 and intermitantly it wakes up and processes any pending defered
* tasks.
*/
void
c_condition::wait_run_defer(void)
{
c_core *cp = c_core::get_current();

while (condition == 0) {
cp->delay(MICROSECONDS(1));
// Handle deferred work
cp->get_dispatcher()->intercept();
}
condition = 0;
}

/**
* Condition variable with timeout semantics. Wait for the condition
* to be signalled, or a specified timeout to elapse. This function
* intermittently wakes up and processes any pending deferred tasks.
*
* @param ns The number of nanoseconds to wait.
* @returns true if the wait was satisfied, false if the timer fired.
*/
bool
c_condition::timed_wait_run_defer(uint64 ns)
{
timedout = 0;
c_timer *to = new c_timer(c_timer::ONESHOT,
c_core::get_current()->get_current_time() + ns, this);

wait_run_defer();

delete to;
return (timedout == 0);
}

/* vim: sw=4 sts=4 sta ts=8:
*/

[Mut...@dastardlyhq.com]

On Thu, 16 Feb 2023 03:03:31 GMT

sc...@slp53.sl.home (Scott Lurndal) wrote:
>Kaz Kylheku <864-11...@kylheku.com> writes:

Nice code but I suspect not very portable :)