Run this under Windows and Linux

[Bonita Montero]

MSVC's C++20 semaphore class spins to acquire the semaphore;
g++'s / libstdc++'s doesn't spin. I wote a little test program
to rest how long it takes to flip to another thread and back
with a binary_semaphore (always a counting_semaphore<1>).
Here it is:

#if defined(_WIN32)
#include <Windows.h>
#elif defined(__unix__)
#include <sys/resource.h>
#endif
#include <iostream>
#include <thread>
#include <semaphore>
#include <atomic>
#include <utility>
#include <vector>

using namespace std;

int main()
{
binary_semaphore
semA( 1 ),
semB( 0 );
auto getTimes = []() -> pair<int64_t, int64_t>
{
#if defined(_WIN32)
FILETIME ftDummy, ftKernel, ftUser;
GetThreadTimes( GetCurrentThread(), &ftDummy, &ftDummy, &ftKernel,
&ftUser );
auto compose = []( FILETIME &ft ) { return
((uint64_t)ft.dwHighDateTime << 32 | ft.dwLowDateTime) * 100; };
return { compose( ftKernel ), compose( ftUser ) };
#elif defined(__unix__)
rusage ru;
getrusage( RUSAGE_THREAD, &ru );
auto compose = []( timeval &tv ) -> int64_t { return
(uint64_t)tv.tv_sec * 1'000'000'000u + (uint32_t)tv.tv_usec * 1'000u; };
return { compose( ru.ru_stime ), compose( ru.ru_utime ) };
#endif
};
atomic_int64_t
aFlips( 0 ),
aKernel( 0 ),
aUser( 0 );
atomic_bool stop( false );
auto thr = [&]( binary_semaphore &semMe, binary_semaphore &semYou )
{
auto tBegin = getTimes();
uint64_t f = 0;
for( ; !stop.load( memory_order_relaxed ); ++f )
semMe.acquire(),
semYou.release();
auto tEnd = getTimes();
aFlips += f;
aKernel += tEnd.first - tBegin.first;
aUser += tEnd.second + tBegin.second;
};
vector<jthread> threads;
threads.emplace_back( thr, ref( semA ), ref( semB ) );
threads.emplace_back( thr, ref( semB ), ref( semA ) );
this_thread::sleep_for( 1s );
stop = true;
threads.resize( 0 );
double
kernel = (double)aKernel,
user = (double)aUser,
total = kernel + user,
flips = (double)aFlips;
cout << user / total * 100.0 << "%" << endl;
cout << total / flips << "ns" << endl;
}

Results unter Windows 11 on a AMD Ryzen 7950X (Zen4):
100%
89.3523ns
So 100% of the CPU time is spent in user space and a flip back
and forth takes 90ns.
Results unter Ubuntu 20.04 on a AMD Threadripper 3990X (Zen2):
6.56209%
476.213ns
So under Linux most of the time is spent in kernel space and I think
about 0.5us, thats about 2000 clock cycles with full boost, isn't bad
for an explicit kernel call.
I think this userland spinning isn't really necessary because you
normally a usual mutex and a condition_variable fits for everything
you need. An explicit semaphore is rather needed if you build your
own synchronization primitves on top of the semaphore. And if you do
that you usually have your own spinning with that and you don't need
further spinning if you want go into kernel mode. But this additional
spinning actually doesn't really hurt since the kernel call itself
costs a lot more.

[Bonita Montero]

MSVC's C++20 semaphore class spins to acquire the semaphore;
g++'s / libstdc++'s doesn't spin. I wote a little test program
to rest how long it takes to flip to another thread and back
with a binary_semaphore (always a counting_semaphore<1>).
Here it is:

#if defined(_WIN32)
#include <Windows.h>
#elif defined(__unix__)
#include <sys/resource.h>
#endif
#include <iostream>
#include <thread>
#include <semaphore>
#include <atomic>
#include <utility>
#include <vector>

using namespace std;

int main()
{
binary_semaphore

semA( true ),
semB( false );

[Chris M. Thomasson]

On 10/30/2023 12:12 AM, Bonita Montero wrote:
> MSVC's C++20 semaphore class spins to acquire the semaphore;
> g++'s / libstdc++'s doesn't spin. I wote a little test program
> to rest how long it takes to flip to another thread and back
> with a binary_semaphore (always a counting_semaphore<1>).
> Here it is:

[...]

Test out the benaphore:

https://www.haiku-os.org/legacy-docs/benewsletter/Issue1-26.html#Engineering1-26

[Bonita Montero]

I think this guy never heard of how a usual mutex works and re-invented
the wheel and called it a benaphore.

[Branimir Maksimovic]

formatt elf64

FUTEX_WAIT equ 0
FUTEX_WAKE equ 1
FUTEX_PRIVATE_FLAG equ 128

public futex_acquire
public futex_release

futex_acquire:
push rbx
push r15
; push r10
mov r15,rdi
.L0:
mov ebx,1
xor eax,eax
lock cmpxchg [r15],ebx
test eax,eax
jz .L1
mov eax, 202
mov rdi, r15
mov rsi, FUTEX_WAIT or FUTEX_PRIVATE_FLAG
mov edx, 1
xor r10,r10
syscall
jmp .L0
.L1:; pop r10
pop r15
pop rbx
ret

futex_release:
lock and dword[rdi],0
mov eax,202
; mov rdi, sema
mov rsi, FUTEX_WAKE or FUTEX_PRIVATE_FLAG
mov edx,1
syscall
ret

---------
x86 mutex on linux

--

7-77-777, Evil Sinner!
https://www.linkedin.com/in/branimir-maksimovic-6762bbaa/

[Chris M. Thomasson]

Why do you say that?

[Bonita Montero]

I guess he wouldn't have given the benaphore its name because its
the simplest form of a mutex and you can find for sure a lot of
similar implementations of that on the net.

[Bonita Montero]

Am 31.10.2023 um 21:59 schrieb Chris M. Thomasson:

> Why do you say that?

The article you mentioned is also discussed here:
https://stackoverflow.com/questions/1635416/are-benaphores-worth-implementing-on-modern-oss
The first replier says the same I said: its a normal mutex.

[Bonita Montero]

Am 01.11.2023 um 13:00 schrieb Bonita Montero:

> I guess he wouldn't have given the benaphore its name because its
> the simplest form of a mutex and you can find for sure a lot of
> similar implementations of that on the net.

I found that the name benaphore was given 1996. Maybe this was the
first time this idea was published. But this idea is that obvious
that I had it myself that I think there were several people which
also had this idea before 1996. A hint on how soon this has been
invented may be the introduction of the LOCK XADD instruction which
makes this kind of mutex implementable more efficient than with
LOCK CMPXCHG because this operation never fails.

[Bonita Montero]

Am 01.11.2023 um 19:24 schrieb Bonita Montero:

> I found that the name benaphore was given 1996. Maybe this was the
> first time this idea was published. But this idea is that obvious
> that I had it myself that I think there were several people which
> also had this idea before 1996. A hint on how soon this has been
> invented may be the introduction of the LOCK XADD instruction which
> makes this kind of mutex implementable more efficient than with
> LOCK CMPXCHG because this operation never fails.

I found that LOCK XADD was introduced 1990 with the i486.
I think the designers of this instruction had this specific
kind of mutex in mind.

[Scott Lurndal]

Bonita Montero <Bonita....@gmail.com> writes:
>Am 01.11.2023 um 19:24 schrieb Bonita Montero:
>
>> I found that the name benaphore was given 1996. Maybe this was the
>> first time this idea was published. But this idea is that obvious
>> that I had it myself that I think there were several people which
>> also had this idea before 1996. A hint on how soon this has been
>> invented may be the introduction of the LOCK XADD instruction which
>> makes this kind of mutex implementable more efficient than with
>> LOCK CMPXCHG because this operation never fails.
>
>I found that LOCK XADD was introduced 1990 with the i486.

Multiprocessor computer systems existed long before the i486;
nothing the 486 did was new.

Burroughs mainframes had mutexes and condition variables in the
1970s (during which time Dijkstra was a Burroughs fellow).

A great deal of research on synchronization was done in the
60s and 1970s, including work by Lamport, Hoare, Dijkstra
and others.

I always found Hoare's Co-operating Sequential Processes interesting,
here's his book (not pirated):

http://www.usingcsp.com/

The book is based on his 197x paper we studied in school.

[Bonita Montero]

Am 01.11.2023 um 20:04 schrieb Scott Lurndal:

> Bonita Montero <Bonita....@gmail.com> writes:

>> I found that LOCK XADD was introduced 1990 with the i486.

> Multiprocessor computer systems existed long before the i486;
> nothing the 486 did was new.

I treaded the indroduction of LOCK XADD just as a hint that sth.
like this benaphore was thoguht before 1996.

[Chris M. Thomasson]

The benaphore is a semaphore not a mutex! Fwiw, you can use any
semaphore as a binary semaphore for use as a mutex. Got it?

[Chris M. Thomasson]

Huh? The benaphore is a semaphore! So, both of you are totally wrong
here. Think about it...

[Chris M. Thomasson]

Its a semaphore, not a mutex. Any semaphore can be used for a mutex, hint:

Binary Semaphore

[Chris M. Thomasson]

If you can avoid using a CAS, aka CMPXCHG over on intel, then do it!
Although, wrt intel, there is a way to use CMPXCHG without looping.
Think, strong CAS vs weak CAS...

[Kaz Kylheku]

On 2023-11-01, Bonita Montero <Bonita....@gmail.com> wrote:
> Am 01.11.2023 um 13:00 schrieb Bonita Montero:
>
>> I guess he wouldn't have given the benaphore its name because its
>> the simplest form of a mutex and you can find for sure a lot of
>> similar implementations of that on the net.
>
> I found that the name benaphore was given 1996. Maybe this was the
> first time this idea was published.

But back then, Ben Affleck had a hotly publicized affair with a hot
water bottle (thermophore), so that's where that's from.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazi...@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

[Chris M. Thomasson]

On 11/1/2023 1:50 PM, Kaz Kylheku wrote:
> On 2023-11-01, Bonita Montero <Bonita....@gmail.com> wrote:
>> Am 01.11.2023 um 13:00 schrieb Bonita Montero:
>>
>>> I guess he wouldn't have given the benaphore its name because its
>>> the simplest form of a mutex and you can find for sure a lot of
>>> similar implementations of that on the net.
>>
>> I found that the name benaphore was given 1996. Maybe this was the
>> first time this idea was published.
>
> But back then, Ben Affleck had a hotly publicized affair with a hot
> water bottle (thermophore), so that's where that's from.
>

LOL! :^D

[Chris M. Thomasson]

On 11/1/2023 1:50 PM, Kaz Kylheku wrote:

> On 2023-11-01, Bonita Montero <Bonita....@gmail.com> wrote:
>> Am 01.11.2023 um 13:00 schrieb Bonita Montero:
>>
>>> I guess he wouldn't have given the benaphore its name because its
>>> the simplest form of a mutex and you can find for sure a lot of
>>> similar implementations of that on the net.
>>
>> I found that the name benaphore was given 1996. Maybe this was the
>> first time this idea was published.
>
> But back then, Ben Affleck had a hotly publicized affair with a hot
> water bottle (thermophore), so that's where that's from.
>

Be sure to check out:

https://vorbrodt.blog/2019/02/05/fast-semaphore

;^)

[Bonita Montero]

You can say that each binary semaphore is a mutex. And a semaphore
is usually not a compound of userland and kernel facilities, but a
pure kernel resource.

[Bonita Montero]

Am 01.11.2023 um 20:58 schrieb Chris M. Thomasson:

> The benaphore is a semaphore not a mutex! Fwiw, you can use any
> semaphore as a binary semaphore for use as a mutex. Got it?

A binary semaphore is also a mutex.

[Scott Lurndal]

No. Each is distinct.

It is correct, however, to say that both provide the same functionality.

[David Brown]

Both provide /similar/ functionality, but not necessarily the same.
Different OS's differ in the details, but it is common for mutexes to
have priority boosting if a high priority thread is waiting for a mutex
currently held by a low priority thread. Such boosting is normally not
part of the functionality of a binary semaphore. This makes them very
distinctly different on such OS's - a mutex is a lock, a semaphore
(binary or otherwise) is a signalling mechanism.

(I don't know if Windows makes such a distinction - it's not an OS you
use when thread or process priority is important. It is certainly
common, though not universal, for RTOS's. And while I don't know the
details, I'd be surprised if Linux and other *nix's didn't have such a
distinction.)

[Kaz Kylheku]

A semaphore can be used as a mutex, but it isn't one.

Firstly, it doesn't have to be binary to be used as a mutex.

A semaphore restricted to binary values can still serve as a mutex for
the reason that a mutex is never unlocked multiple times in a correct
program. So if we correctly use a semaphore as a mutex, its count should
never go over 1, and for that reason, we can get away with using
semaphore that only counts from 0 to 1.

A semaphore isn't a mutex because it doesn't incorporate the concept of
lock ownership.

The idea that a semaphore represents a locked state, which has an
associated owner, arise purely by the situational convention of how it
is applied.

A semaphore couldn't provide error checking, such as when a mutex
non-owner tries to unlock, or recursive deadlock detection.

[Bonita Montero]

Am 02.11.2023 um 15:58 schrieb Scott Lurndal:

> No. Each is distinct.

You can initialize a binary semaphore with true and use it
as a mutex. And a mutex can be realized without a short path
but just with a binary semaphore in the mentioned way.

[Bonita Montero]

Am 02.11.2023 um 16:34 schrieb David Brown:

> Both provide /similar/ functionality, but not necessarily the same.
> Different OS's differ in the details, but it is common for mutexes to
> have priority boosting if a high priority thread is waiting for a mutex
> currently held by a low priority thread. Such boosting is normally not

> part of the functionality of a binary semaphore.  Thismakes them very

> distinctly different on such OS's - a mutex is a lock, a semaphore
> (binary or otherwise) is a signalling mechanism.

Does Linux actually boost thread priorities with mutexes ?

[Bonita Montero]

Am 02.11.2023 um 16:37 schrieb Kaz Kylheku:

> Firstly, it doesn't have to be binary to be used as a mutex.

No, but when being used as a mutex its actual maximum value is one.

> A semaphore isn't a mutex because it doesn't incorporate the concept
> of lock ownership.

Thats not dependent on actual implementation but how you consider
the value of the binary semaphore. If it is false it is owned.

[Kaz Kylheku]

On 2023-11-02, Bonita Montero <Bonita....@gmail.com> wrote:

If it is false, it can be understood as representing a locked state.

Locked isn't necessarily owned.

The semaphore does not record the ID of an owner.

In a correct program, a binary semaphore can represent a lock, yet there
can be legitimate situations where a thread which didn't place the lock
releases it.

[Kaz Kylheku]

On 2023-11-02, Bonita Montero <Bonita....@gmail.com> wrote:

You can use a label, if and goto as a while loop.

That doesn't mean if and goto /are/ while.

Speaking of which, I have often mused that sempahores are like the go to
statement of synchronization---which is ironic, given their inventor.

[Bonita Montero]

Am 02.11.2023 um 17:00 schrieb Kaz Kylheku:

> Locked isn't necessarily owned.
> The semaphore does not record the ID of an owner.

A non-recursive mutes also doesn't do this. The surrounding
code itself is designed in a way that it behaves like an owner.

[Chris M. Thomasson]

On 11/2/2023 8:34 AM, David Brown wrote:
> On 02/11/2023 15:58, Scott Lurndal wrote:
>> Bonita Montero <Bonita....@gmail.com> writes:
>>> Am 01.11.2023 um 20:58 schrieb Chris M. Thomasson:
>>>
>>>> The benaphore is a semaphore not a mutex! Fwiw, you can use any
>>>> semaphore as a binary semaphore for use as a mutex. Got it?
>>>
>>> A binary semaphore is also a mutex.
>>
>> No.  Each is distinct.
>>
>> It is correct, however, to say that both provide the same functionality.
>>
>
> Both provide /similar/ functionality, but not necessarily the same.
> Different OS's differ in the details, but it is common for mutexes to
> have priority boosting if a high priority thread is waiting for a mutex
> currently held by a low priority thread.  Such boosting is normally not
> part of the functionality of a binary semaphore.  This makes them very
> distinctly different on such OS's - a mutex is a lock, a semaphore
> (binary or otherwise) is a signalling mechanism.

Right. Basically, any thread/process can increment and/or decrement a
semaphore. This is different than pure mutex logic. Even if the mutex
uses a semaphore under the covers...

[Chris M. Thomasson]

On 11/2/2023 9:00 AM, Kaz Kylheku wrote:
> On 2023-11-02, Bonita Montero <Bonita....@gmail.com> wrote:
>> Am 02.11.2023 um 16:37 schrieb Kaz Kylheku:
>>
>>> Firstly, it doesn't have to be binary to be used as a mutex.
>>
>> No, but when being used as a mutex its actual maximum value is one.
>>
>>> A semaphore isn't a mutex because it doesn't incorporate the concept
>>> of lock ownership.
>>
>> Thats not dependent on actual implementation but how you consider
>> the value of the binary semaphore. If it is false it is owned.
>
> If it is false, it can be understood as representing a locked state.
>
> Locked isn't necessarily owned.
>
> The semaphore does not record the ID of an owner.
>
> In a correct program, a binary semaphore can represent a lock, yet there
> can be legitimate situations where a thread which didn't place the lock
> releases it.
>

True. This makes me think of robust mutexes... ;^)

[David Brown]

On 02/11/2023 21:12, Chris M. Thomasson wrote:
> On 11/2/2023 8:34 AM, David Brown wrote:
>> On 02/11/2023 15:58, Scott Lurndal wrote:
>>> Bonita Montero <Bonita....@gmail.com> writes:
>>>> Am 01.11.2023 um 20:58 schrieb Chris M. Thomasson:
>>>>
>>>>> The benaphore is a semaphore not a mutex! Fwiw, you can use any
>>>>> semaphore as a binary semaphore for use as a mutex. Got it?
>>>>
>>>> A binary semaphore is also a mutex.
>>>
>>> No.  Each is distinct.
>>>
>>> It is correct, however, to say that both provide the same functionality.
>>>
>>
>> Both provide /similar/ functionality, but not necessarily the same.
>> Different OS's differ in the details, but it is common for mutexes to
>> have priority boosting if a high priority thread is waiting for a
>> mutex currently held by a low priority thread.  Such boosting is
>> normally not part of the functionality of a binary semaphore.  This
>> makes them very distinctly different on such OS's - a mutex is a lock,
>> a semaphore (binary or otherwise) is a signalling mechanism.
>
> Right. Basically, any thread/process can increment and/or decrement a
> semaphore. This is different than pure mutex logic. Even if the mutex
> uses a semaphore under the covers...
>

That's a very different issue - though of course it is an equally
important distinction between mutexes and binary semaphores. (And no, a
mutex cannot be implemented using semaphores if the mutex has protection
against priority inversion, and the semaphore does not.)

[David Brown]

Mutexes - recursive or non-recursive - /do/ record their owner when the
lock is taken. Only the owner can unlock the mutex again. This is
completely different from semaphores, where by design any thread can
raise or lower the semaphore.

[Bonita Montero]

Am 03.11.2023 um 10:15 schrieb David Brown:
> On 02/11/2023 17:26, Bonita Montero wrote:
>> Am 02.11.2023 um 17:00 schrieb Kaz Kylheku:
>>
>>> Locked isn't necessarily owned.
>>> The semaphore does not record the ID of an owner.
>>
>> A non-recursive mutes also doesn't do this. The surrounding
>> code itself is designed in a way that it behaves like an owner.
>
> Mutexes - recursive or non-recursive - /do/ record their owner when the

> lock is taken. ...

Absolutely not. You can take ownership of a mutex in one thread and
release it in another thread. The mentioned benaphore, which is the
basic skeleton for all mutexes, is a good example for that.

[Bonita Montero]

Am 01.11.2023 um 21:02 schrieb Chris M. Thomasson:

> If you can avoid using a CAS, aka CMPXCHG over on intel, then do it!
> Although, wrt intel, there is a way to use CMPXCHG without looping.

I don't believe that, give me some code-example _here_. The expected
value of a compare exchange might always have been asynchronously
changed, so you need looping every time.

> Think, strong CAS vs weak CAS...

Strong CAS vs. weak CAS only makes a difference of architectures with
LL/SC. With these architectures a CAS may fail although the actual
data corresponds with the expected value because the cacheline might
have been evicted in the meantime. compare_exchange_strong checks for
this case and loops internally, whereas compare_exchange_weak gives a
false result after one try.

[David Brown]

You can call that a mutex if you like, but you'd be wrong. You could
call it a banana, and you would do no worse.


Wikipedia may not be have any particular authority on its definitions,
but it explains the difference between mutexes and semaphores quite well:

<https://en.wikipedia.org/wiki/Lock_(computer_science)#Mutexes_vs._semaphores>


Critical to the point of a mutex is that only the thread that locks it
can unlock it.


You can look at the notes for C++ semaphores here, which make the
distinction clear:

<https://en.cppreference.com/w/cpp/thread/counting_semaphore>

Documentation for C++ mutexes is here :

<https://en.cppreference.com/w/cpp/thread/mutex>
<https://en.cppreference.com/w/cpp/thread/mutex/unlock>

Or you can read the C++ standards if you prefer. (I find the
cppreference pages much easier to follow.)

Or you can look up the documentation for Windows mutexes on MS's webpages.

[Michael S]

On Wed, 1 Nov 2023 19:24:06 +0100
Bonita Montero <Bonita....@gmail.com> wrote:

> Am 01.11.2023 um 13:00 schrieb Bonita Montero:
>
> > I guess he wouldn't have given the benaphore its name because its
> > the simplest form of a mutex and you can find for sure a lot of
> > similar implementations of that on the net.
>
> I found that the name benaphore was given 1996. Maybe this was the
> first time this idea was published. But this idea is that obvious
> that I had it myself that I think there were several people which
> also had this idea before 1996. A hint on how soon this has been
> invented may be the introduction of the LOCK XADD instruction which
> makes this kind of mutex implementable more efficient than with
> LOCK CMPXCHG because this operation never fails.
>

Semophores can be efficiently implemented on "old" x86 by means of
'LOCK ADD mem, reg'. It is possible due to arithmetic flags generated
by ADD instructiion. As far as semaphores goes 'LOCK XADD' adds little
or nothing to efficiency over 'LOCK ADD'. XADD is just easier to use as
an intrinsic from C or similar languages.

[Michael S]

On Thu, 2 Nov 2023 16:02:04 -0000 (UTC)
Kaz Kylheku <864-11...@kylheku.com> wrote:

> On 2023-11-02, Bonita Montero <Bonita....@gmail.com> wrote:
> > Am 02.11.2023 um 15:58 schrieb Scott Lurndal:
> >
> >> No. Each is distinct.
> >
> > You can initialize a binary semaphore with true and use it
> > as a mutex. And a mutex can be realized without a short path
> > but just with a binary semaphore in the mentioned way.
>
> You can use a label, if and goto as a while loop.
>
> That doesn't mean if and goto /are/ while.
>
> Speaking of which, I have often mused that sempahores are like the go
> to statement of synchronization---which is ironic, given their
> inventor.
>

IMHO, the word 'mutex' has no exact meaning agreed by all or even
majority of Computer Science community.

[Bonita Montero]

Am 03.11.2023 um 14:41 schrieb David Brown:
> On 03/11/2023 11:55, Bonita Montero wrote:
>> Am 03.11.2023 um 10:15 schrieb David Brown:
>>> On 02/11/2023 17:26, Bonita Montero wrote:
>>>> Am 02.11.2023 um 17:00 schrieb Kaz Kylheku:
>>>>
>>>>> Locked isn't necessarily owned.
>>>>> The semaphore does not record the ID of an owner.
>>>>
>>>> A non-recursive mutes also doesn't do this. The surrounding
>>>> code itself is designed in a way that it behaves like an owner.
>>>
>>> Mutexes - recursive or non-recursive - /do/ record their owner when
>>> the lock is taken. ...
>>
>> Absolutely not. You can take ownership of a mutex in one thread and
>> release it in another thread. The mentioned benaphore, which is the
>> basic skeleton for all mutexes, is a good example for that.
>>
>
> You can call that a mutex if you like, but you'd be wrong.  You could
> call it a banana, and you would do no worse.
> Wikipedia may not be have any particular authority on its definitions,
> but it explains the difference between mutexes and semaphores quite well:
> <https://en.wikipedia.org/wiki/Lock_(computer_science)#Mutexes_vs._semaphores>
> Critical to the point of a mutex is that only the thread that locks it
> can unlock it.
> You can look at the notes for C++ semaphores here, which make the
> distinction clear:

At this point in the thread I was discussion whether a mutex has the
notion of an ownership and it mutexes vs. semaphores.

[Bonita Montero]

Am 03.11.2023 um 15:04 schrieb Michael S:

> Semophores can be efficiently implemented on "old" x86 by means of

> 'LOCK ADD mem, reg'. ...

Semaphores need much more code and this code is usually in the kernel
since with a semaphore a thread may go to sleep or be awakened.

[Kaz Kylheku]

On 2023-11-03, Bonita Montero <Bonita....@gmail.com> wrote:
> Am 03.11.2023 um 10:15 schrieb David Brown:
>> On 02/11/2023 17:26, Bonita Montero wrote:
>>> Am 02.11.2023 um 17:00 schrieb Kaz Kylheku:
>>>
>>>> Locked isn't necessarily owned.
>>>> The semaphore does not record the ID of an owner.
>>>
>>> A non-recursive mutes also doesn't do this. The surrounding
>>> code itself is designed in a way that it behaves like an owner.
>>
>> Mutexes - recursive or non-recursive - /do/ record their owner when the
>> lock is taken. ...
>
> Absolutely not. You can take ownership of a mutex in one thread and
> release it in another thread.

Not POSIX mutexes: pthread_mutex_unlock by a non-owner is either
undefined behavior, or a condition diagnosed by an error return value,
depending on the mutex attributes:

See the table here:

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

E.g. for a norma mutex type which is not attributed as robust,
it is undefined behavior.

Support for unlocking by a non-owner is possible in a mutex, but that's
a non-mutex-like behavioral extension.

A mutex that is owned by a process, rather than a thread, can be locked
by one thread and unlocked by another. Classic POSIX file locks (F_SETLK
code of fcntl, etc) are like this, IIRC. That's still mutex-like, just
the scope is process, rather than thread.

[David Brown]

And using the definitions held by most people involved (including the
C++ standard library, the Windows API, and AFAIK POSIX), mutexes have
ownership and semaphores do not. A semaphore is not a lock, it is a
signalling mechanism - and any thread can signal it up or down. A mutex
is a locking mechanism to ensure mutually exclusive access to some
resource, and only the owner can release the lock (baring exceptional
circumstances, such as a process being killed by the OS). A sort-of
mutex where any thread could release the lock would be as useful as a
chocolate teapot - as would a semaphore which could only be lowered by
the thread that raised it.

[Bonita Montero]

Am 03.11.2023 um 16:35 schrieb David Brown:

> And using the definitions held by most people involved (including the
> C++ standard library, the Windows API, and AFAIK POSIX), mutexes have

> ownership and semaphores do not. ...

Mutexes only have ownership if they're recursive. Otherwise you
can easily unlock a mutex which was locked in another thread.

> A semaphore is not a lock, ...

It can be used as a lock although it is not recommended because
a semaphore is usually a pure kernel facility.

[Scott Lurndal]

Bonita Montero <Bonita....@gmail.com> writes:
>Am 03.11.2023 um 10:15 schrieb David Brown:
>> On 02/11/2023 17:26, Bonita Montero wrote:
>>> Am 02.11.2023 um 17:00 schrieb Kaz Kylheku:
>>>
>>>> Locked isn't necessarily owned.
>>>> The semaphore does not record the ID of an owner.
>>>
>>> A non-recursive mutes also doesn't do this. The surrounding
>>> code itself is designed in a way that it behaves like an owner.
>>
>> Mutexes - recursive or non-recursive - /do/ record their owner when the
>> lock is taken. ...
>
>Absolutely not. You can take ownership of a mutex in one thread and
>release it in another thread.

That has to be the worst idea you've proposed so far.

[David Brown]

On 03/11/2023 16:49, Bonita Montero wrote:
> Am 03.11.2023 um 16:35 schrieb David Brown:
>
>> And using the definitions held by most people involved (including the
>> C++ standard library, the Windows API, and AFAIK POSIX), mutexes have
>> ownership and semaphores do not. ...
>
> Mutexes only have ownership if they're recursive. Otherwise you
> can easily unlock a mutex which was locked in another thread.
>

Please read <https://en.cppreference.com/w/cpp/thread/mutex/unlock>.
Note the sentence "The mutex must be locked by the current thread of
execution, otherwise, the behavior is undefined."

Please read the C++ standards, section [thread.mutex.requirements.mutex]
and note that for "unlock()", there is the sentence "Preconditions: The
calling thread owns the mutex."

Please learn what "undefined behaviour" means, and what "preconditions"
mean.

Then come back and apologise.

>> A semaphore is not a lock, ...
>
> It can be used as a lock although it is not recommended because
> a semaphore is usually a pure kernel facility.
>

Using a semaphore as a lock is not recommended because a semaphore does
not make a good lock. A main reason for that is that it has no concept
of ownership. /All/ locking and inter-thread signalling mechanisms rely
on kernel facilities, because they need to be able to sleep, and to wake
sleeping threads.

[David Brown]

Mutexes are locks, but not all locks are mutexes. File locks are not
mutexes - they are for controlling access to files, and it might
(rarely) make sense to unlock them from a different thread than the
locking thread.

[Bonita Montero]

Am 03.11.2023 um 18:02 schrieb David Brown:

> Please read <https://en.cppreference.com/w/cpp/thread/mutex/unlock>.
> Note the sentence "The mutex must be locked by the current thread of
> execution, otherwise, the behavior is undefined."

Maybe, but I'm talking about how mutexes usually work internally.

> Using a semaphore as a lock is not recommended because a semaphore does
> not make a good lock.  A main reason for that is that it has no concept

> of ownership. ...

Mutexes also usually have no notion of ownership.

[Bonita Montero]

I won't say that this is recommendable but just that it is possible
from the way how a mutex usually works. I just wanted to say with
that that mutexes usually have no ownership. You can see that with
the benapohre.

[Kaz Kylheku]

On 2023-11-03, Bonita Montero <Bonita....@gmail.com> wrote:

> Am 03.11.2023 um 16:35 schrieb David Brown:
>
>> And using the definitions held by most people involved (including the
>> C++ standard library, the Windows API, and AFAIK POSIX), mutexes have
>> ownership and semaphores do not. ...
>
> Mutexes only have ownership if they're recursive. Otherwise you
> can easily unlock a mutex which was locked in another thread.

That depends entirely on which kind of mutex on what platform.

- POSIX mutexes make that either an error, or undefined behavior,
depending on the mutex attributes.

- MSDN says this about critical sections: "If a thread calls
LeaveCriticalSection when it does not have ownership of the specified
critical section object, an error occurs that may cause another thread
using EnterCriticalSection to wait indefinitely."

- MSDN, again, about Win32 mutex objects: "The ReleaseMutex function
fails if the calling thread does not own the mutex object."

- ISO C (since C11) mtx_unlock: undefined behavior if mutex is not
locked by the calling thread.

- C++ std::mutex::unlock: ditto.

At this point, I'm already well into stuff I don't give a shit about,
to look for more. I don't care if ScrotelyOS developed in Ruritania
between 1973 and 1981 had "mutexes" that had up to three owners.

[Kaz Kylheku]

On 2023-11-03, Bonita Montero <Bonita....@gmail.com> wrote:

> Am 03.11.2023 um 18:02 schrieb David Brown:
>
>> Please read <https://en.cppreference.com/w/cpp/thread/mutex/unlock>.
>> Note the sentence "The mutex must be locked by the current thread of
>> execution, otherwise, the behavior is undefined."
>
> Maybe, but I'm talking about how mutexes usually work internally.

"Never mind that a[i++] = i is undefined; I'm talking about how it
works internally, damn it!!!"

[Bonita Montero]

Am 03.11.2023 um 18:28 schrieb Kaz Kylheku:

> That depends entirely on which kind of mutex on what platform.
>
> - POSIX mutexes make that either an error, or undefined behavior,
> depending on the mutex attributes.
>
> - MSDN says this about critical sections: "If a thread calls
> LeaveCriticalSection when it does not have ownership of the specified
> critical section object, an error occurs that may cause another thread
> using EnterCriticalSection to wait indefinitely."
>
> - MSDN, again, about Win32 mutex objects: "The ReleaseMutex function
> fails if the calling thread does not own the mutex object."
>
> - ISO C (since C11) mtx_unlock: undefined behavior if mutex is not
> locked by the calling thread.
>
> - C++ std::mutex::unlock: ditto.
>
> At this point, I'm already well into stuff I don't give a shit about,
> to look for more. I don't care if ScrotelyOS developed in Ruritania
> between 1973 and 1981 had "mutexes" that had up to three owners.

The discussed benaphore allows this.

[Kaz Kylheku]

On 2023-11-03, Bonita Montero <Bonita....@gmail.com> wrote:

That's a kind of semaphore, and its name reflects that.

Benoit Schillings introduced this word as an optimization that is
for certain inefficient semaphore implementations:

https://www.haiku-os.org/legacy-docs/benewsletter/Issue1-26.html#Engineering1-26

He recommends this:

void acquire_benaphore()
{
long previous_value;
previous_value = atomic_add (&benaphore_atom, 1);

if (previous_value > 0)
acquire_sem(benaphore_sem);
}

Firstly, this is not a mutex but a semaphore. Secondly, it only makes
sense if acquire_sem is somehow expensive (like a trap to the kernel).

The reason is that acquire_sem already looks like acquire_benaphore:

void acquire_sem(semaphore *s)
{
long prev = atomic_add(&s->counter);

if (prev > 0) {
// suspend caller somehow
}

// ...

[Bonita Montero]

Am 03.11.2023 um 19:03 schrieb Kaz Kylheku:
> On 2023-11-03, Bonita Montero <Bonita....@gmail.com> wrote:

>> Am 03.11.2023 um 18:28 schrieb Kaz Kylheku:

>> The discussed benaphore allows this.

> That's a kind of semaphore, and its name reflects that.

It's a mutex, look at the code.
And look at the discussion on stack overflow about that:
https://stackoverflow.com/questions/1635416/are-benaphores-worth-implementing-on-modern-oss

[Bonita Montero]

Am 03.11.2023 um 19:07 schrieb Bonita Montero:

> It's a mutex, look at the code.
> And look at the discussion on stack overflow about that:
> https://stackoverflow.com/questions/1635416/are-benaphores-worth-implementing-on-modern-oss

And this article also refers to it as a mutex:
https://preshing.com/20120226/roll-your-own-lightweight-mutex/

[Scott Lurndal]

David Brown <david...@hesbynett.no> writes:
>On 03/11/2023 16:49, Bonita Montero wrote:
>> Am 03.11.2023 um 16:35 schrieb David Brown:
>>
>>> And using the definitions held by most people involved (including the
>>> C++ standard library, the Windows API, and AFAIK POSIX), mutexes have
>>> ownership and semaphores do not. ...
>>
>> Mutexes only have ownership if they're recursive. Otherwise you
>> can easily unlock a mutex which was locked in another thread.
>>
>
>Please read <https://en.cppreference.com/w/cpp/thread/mutex/unlock>.
>Note the sentence "The mutex must be locked by the current thread of
>execution, otherwise, the behavior is undefined."
>
>Please read the C++ standards, section [thread.mutex.requirements.mutex]
>and note that for "unlock()", there is the sentence "Preconditions: The
>calling thread owns the mutex."
>

And read the POSIX standard as well.

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

[Scott Lurndal]

Bonita Montero <Bonita....@gmail.com> writes:
>Am 03.11.2023 um 18:02 schrieb David Brown:
>
>> Please read <https://en.cppreference.com/w/cpp/thread/mutex/unlock>.
>> Note the sentence "The mutex must be locked by the current thread of
>> execution, otherwise, the behavior is undefined."
>
>Maybe, but I'm talking about how mutexes usually work internally.

Why does that matter? It's the behavior seen by the code
using the mutex that matters.

Undefined behavior isn't something an application can rely on.

You keep digging yourself deeper and deeper.

[Scott Lurndal]

And which operating system offers this soi disant 'benaphore' as a
synchronization mechanism?

[Bonita Montero]

Am 03.11.2023 um 19:54 schrieb Scott Lurndal:

> And which operating system offers this soi disant 'benaphore' as a
> synchronization mechanism?

Non-recursive mutexes mostly base on the same mechanisms since
an atomic add doesn't need looping.

[Kaz Kylheku]

On 2023-11-03, Bonita Montero <Bonita....@gmail.com> wrote:

An atomic counter, featuring a wait when the value is in a certain
range, is known as semaphore.

[Branimir Maksimovic]

On 2023-10-30, Bonita Montero <Bonita....@gmail.com> wrote:

> MSVC's C++20 semaphore class spins to acquire the semaphore;
> g++'s / libstdc++'s doesn't spin. I wote a little test program
> to rest how long it takes to flip to another thread and back
> with a binary_semaphore (always a counting_semaphore<1>).
> Here it is:
>
> #if defined(_WIN32)
> #include <Windows.h>
> #elif defined(__unix__)
> #include <sys/resource.h>
> #endif
> #include <iostream>
> #include <thread>
> #include <semaphore>
> #include <atomic>
> #include <utility>
> #include <vector>
>
> using namespace std;
>
> int main()
> {
> binary_semaphore
> semA( 1 ),
> semB( 0 );
> auto getTimes = []() -> pair<int64_t, int64_t>
> {
> #if defined(_WIN32)
> FILETIME ftDummy, ftKernel, ftUser;
> GetThreadTimes( GetCurrentThread(), &ftDummy, &ftDummy, &ftKernel,
> &ftUser );
> auto compose = []( FILETIME &ft ) { return
> ((uint64_t)ft.dwHighDateTime << 32 | ft.dwLowDateTime) * 100; };
> return { compose( ftKernel ), compose( ftUser ) };
> #elif defined(__unix__)
> rusage ru;
> getrusage( RUSAGE_THREAD, &ru );
> auto compose = []( timeval &tv ) -> int64_t { return
> (uint64_t)tv.tv_sec * 1'000'000'000u + (uint32_t)tv.tv_usec * 1'000u; };
> return { compose( ru.ru_stime ), compose( ru.ru_utime ) };
> #endif
> };
> atomic_int64_t
> aFlips( 0 ),
> aKernel( 0 ),
> aUser( 0 );
> atomic_bool stop( false );
> auto thr = [&]( binary_semaphore &semMe, binary_semaphore &semYou )
> {
> auto tBegin = getTimes();
> uint64_t f = 0;
> for( ; !stop.load( memory_order_relaxed ); ++f )
> semMe.acquire(),
> semYou.release();
> auto tEnd = getTimes();
> aFlips += f;
> aKernel += tEnd.first - tBegin.first;
> aUser += tEnd.second + tBegin.second;
> };
> vector<jthread> threads;
> threads.emplace_back( thr, ref( semA ), ref( semB ) );
> threads.emplace_back( thr, ref( semB ), ref( semA ) );
> this_thread::sleep_for( 1s );
> stop = true;
> threads.resize( 0 );
> double
> kernel = (double)aKernel,
> user = (double)aUser,
> total = kernel + user,
> flips = (double)aFlips;
> cout << user / total * 100.0 << "%" << endl;
> cout << total / flips << "ns" << endl;
> }
>
> Results unter Windows 11 on a AMD Ryzen 7950X (Zen4):
> 100%
> 89.3523ns
> So 100% of the CPU time is spent in user space and a flip back
> and forth takes 90ns.
> Results unter Ubuntu 20.04 on a AMD Threadripper 3990X (Zen2):
> 6.56209%
> 476.213ns
> So under Linux most of the time is spent in kernel space and I think
> about 0.5us, thats about 2000 clock cycles with full boost, isn't bad
> for an explicit kernel call.
> I think this userland spinning isn't really necessary because you
> normally a usual mutex and a condition_variable fits for everything
> you need. An explicit semaphore is rather needed if you build your
> own synchronization primitves on top of the semaphore. And if you do
> that you usually have your own spinning with that and you don't need
> further spinning if you want go into kernel mode. But this additional
> spinning actually doesn't really hurt since the kernel call itself
> costs a lot more.
>
maxa@Branimirs-MacBook-Air News % g++ -O2 run.cpp -o run -std=c++20
run.cpp:37:2: warning: non-void lambda does not return a value [-Wreturn-type]
};
^
1 warning generated.
bmaxa@Branimirs-MacBook-Air News % ./run
libc++abi: terminating
zsh: abort ./run

--

7-77-777, Evil Sinner!
https://www.linkedin.com/in/branimir-maksimovic-6762bbaa/

[Chris M. Thomasson]

On 11/3/2023 5:36 AM, Bonita Montero wrote:
> Am 01.11.2023 um 21:02 schrieb Chris M. Thomasson:
>
>> If you can avoid using a CAS, aka CMPXCHG over on intel, then do it!
>> Although, wrt intel, there is a way to use CMPXCHG without looping.
>
> I don't believe that, give me some code-example _here_. The expected
> value of a compare exchange might always have been asynchronously
> changed, so you need looping every time.
>
>> Think, strong CAS vs weak CAS...
>
> Strong CAS vs. weak CAS only makes a difference of architectures with
> LL/SC. With these architectures a CAS may fail although the actual
> data corresponds with the expected value because the cacheline might
> have been evicted in the meantime. compare_exchange_strong checks for
> this case and loops internally, whereas compare_exchange_weak gives a
> false result after one try.

Strong CAS cannot fail spuriously. Put on your thinking cap.

[Chris M. Thomasson]

Huh? A semaphore in userspace is doable. We use a kernel semaphore for
the slow paths.

[Chris M. Thomasson]

On 11/3/2023 2:13 AM, David Brown wrote:
> On 02/11/2023 21:12, Chris M. Thomasson wrote:
>> On 11/2/2023 8:34 AM, David Brown wrote:

>>> On 02/11/2023 15:58, Scott Lurndal wrote:
>>>> Bonita Montero <Bonita....@gmail.com> writes:

>>>>> Am 01.11.2023 um 20:58 schrieb Chris M. Thomasson:
>>>>>
>>>>>> The benaphore is a semaphore not a mutex! Fwiw, you can use any
>>>>>> semaphore as a binary semaphore for use as a mutex. Got it?
>>>>>
>>>>> A binary semaphore is also a mutex.
>>>>
>>>> No.  Each is distinct.
>>>>
>>>> It is correct, however, to say that both provide the same
>>>> functionality.
>>>>
>>>
>>> Both provide /similar/ functionality, but not necessarily the same.
>>> Different OS's differ in the details, but it is common for mutexes to
>>> have priority boosting if a high priority thread is waiting for a
>>> mutex currently held by a low priority thread.  Such boosting is
>>> normally not part of the functionality of a binary semaphore.  This
>>> makes them very distinctly different on such OS's - a mutex is a
>>> lock, a semaphore (binary or otherwise) is a signalling mechanism.
>>
>> Right. Basically, any thread/process can increment and/or decrement a
>> semaphore. This is different than pure mutex logic. Even if the mutex
>> uses a semaphore under the covers...
>>
>
> That's a very different issue - though of course it is an equally
> important distinction between mutexes and binary semaphores.  (And no, a
> mutex cannot be implemented using semaphores if the mutex has protection
> against priority inversion, and the semaphore does not.)

Agreed. Basically, the benaphore is a bakery algorithm. It has FIFO on
the mind... So, you are right.


>
>>>
>>> (I don't know if Windows makes such a distinction - it's not an OS
>>> you use when thread or process priority is important.  It is
>>> certainly common, though not universal, for RTOS's.  And while I
>>> don't know the details, I'd be surprised if Linux and other *nix's
>>> didn't have such a distinction.)
>>>
>>
>

[Chris M. Thomasson]

On 11/3/2023 3:55 AM, Bonita Montero wrote:
> Am 03.11.2023 um 10:15 schrieb David Brown:
>> On 02/11/2023 17:26, Bonita Montero wrote:
>>> Am 02.11.2023 um 17:00 schrieb Kaz Kylheku:
>>>
>>>> Locked isn't necessarily owned.
>>>> The semaphore does not record the ID of an owner.
>>>
>>> A non-recursive mutes also doesn't do this. The surrounding
>>> code itself is designed in a way that it behaves like an owner.
>>
>> Mutexes - recursive or non-recursive - /do/ record their owner when
>> the lock is taken. ...
>
> Absolutely not. You can take ownership of a mutex in one thread and
> release it in another thread.

Oh, really!?!?!? Yikes!

> The mentioned benaphore, which is the
> basic skeleton for all mutexes, is a good example for that.

Oh my. A benaphore is basically a userspace semaphore using a kernel
semaphore for slow paths.

[Chris M. Thomasson]

On 11/3/2023 8:49 AM, Bonita Montero wrote:
> Am 03.11.2023 um 16:35 schrieb David Brown:
>
>> And using the definitions held by most people involved (including the
>> C++ standard library, the Windows API, and AFAIK POSIX), mutexes have
>> ownership and semaphores do not. ...
>
> Mutexes only have ownership if they're recursive.

WHAT!!! ? ;^o

[Chris M. Thomasson]

On 11/3/2023 10:02 AM, David Brown wrote:
> On 03/11/2023 16:49, Bonita Montero wrote:
>> Am 03.11.2023 um 16:35 schrieb David Brown:
>>
>>> And using the definitions held by most people involved (including the
>>> C++ standard library, the Windows API, and AFAIK POSIX), mutexes have
>>> ownership and semaphores do not. ...
>>
>> Mutexes only have ownership if they're recursive. Otherwise you
>> can easily unlock a mutex which was locked in another thread.
>>
>
> Please read <https://en.cppreference.com/w/cpp/thread/mutex/unlock>.
> Note the sentence "The mutex must be locked by the current thread of
> execution, otherwise, the behavior is undefined."
>
> Please read the C++ standards, section [thread.mutex.requirements.mutex]
> and note that for "unlock()", there is the sentence "Preconditions: The
> calling thread owns the mutex."
>
> Please learn what "undefined behaviour" means, and what "preconditions"
> mean.
>
> Then come back and apologise.

If I wait for that day, well, I will most likely be dead.

[Chris M. Thomasson]

The Art of Trolling, 123, all is me...

[Chris M. Thomasson]

That should be framed! ;^O

[Chris M. Thomasson]

Oh shit. You have dug yourself into a really deep hole here, Bonita.

wow.

[Chris M. Thomasson]

Oh my god...

[Chris M. Thomasson]

On 11/1/2023 12:59 PM, Chris M. Thomasson wrote:
> On 11/1/2023 5:21 AM, Bonita Montero wrote:
>> Am 31.10.2023 um 21:59 schrieb Chris M. Thomasson:
>>
>>> Why do you say that?
>>
>> The article you mentioned is also discussed here:
>> https://stackoverflow.com/questions/1635416/are-benaphores-worth-implementing-on-modern-oss
>> The first replier says the same I said: its a normal mutex.
>>
>
> Huh? The benaphore is a semaphore! So, both of you are totally wrong
> here. Think about it...

Your theme song?

https://youtu.be/FE-hBbBBGBs

[Chris M. Thomasson]

CMPXCHG cannot fail spuriously. However, LL/SC can.

[Bonita Montero]

Youre telling things I've told above in a different way.

[Bonita Montero]

Am 03.11.2023 um 21:56 schrieb Kaz Kylheku:

> An atomic counter, featuring a wait when the value is in a certain
> range, is known as semaphore.

An atomic counter alone isn't sufficient for a semaphore because
there's no way to sleep or to be awakened with that.

[Bonita Montero]

Am 03.11.2023 um 23:19 schrieb Chris M. Thomasson:
> On 11/3/2023 8:49 AM, Bonita Montero wrote:
>> Am 03.11.2023 um 16:35 schrieb David Brown:
>>
>>> And using the definitions held by most people involved (including the
>>> C++ standard library, the Windows API, and AFAIK POSIX), mutexes have
>>> ownership and semaphores do not. ...
>>
>> Mutexes only have ownership if they're recursive.
>
> WHAT!!! ? ;^o

It't the surrounding code that "knows" that it is
an owner, not the mutex itself. A non-recurive mutex
just knows that it is owned, but not by whom.

[Bonita Montero]

The benaphore does know that it is owned, but not by whom.
Its the surrounding code that knows that it owns the mutex.

[Bonita Montero]

Am 03.11.2023 um 23:18 schrieb Chris M. Thomasson:

> Oh my. A benaphore is basically a userspace semaphore using a kernel
> semaphore for slow paths.

There isn't sth. like a userspace semaphore since with a sempahore
you need support to sleep or to be awakened.

[Bonita Montero]

Am 01.11.2023 um 20:59 schrieb Chris M. Thomasson:

> Huh? The benaphore is a semaphore! So, both of you are totally wrong
> here. Think about it...

Google for "benaphore mutex" and you'll find several refernces that a
benaphore is a mutex, including the two articles I've referred so far.

[Bonita Montero]

Am 03.11.2023 um 23:19 schrieb Chris M. Thomasson:

> On 11/3/2023 8:49 AM, Bonita Montero wrote:
>> Am 03.11.2023 um 16:35 schrieb David Brown:
>>
>>> And using the definitions held by most people involved (including the
>>> C++ standard library, the Windows API, and AFAIK POSIX), mutexes have
>>> ownership and semaphores do not. ...
>>
>> Mutexes only have ownership if they're recursive.
>
> WHAT!!! ? ;^o

It's not necessary to record ownership of a specific thread for a non
recursive mutex but just _that_ a mutex is ownend, and not by whom.
The benaphore can easily locked in one thread and unlocked in another
thread, although this usually doesn't happen.
It's just the surrounding code that successfully locked a mutex that
"knows" it is the owner.

[Bonita Montero]

Maybe I missed some header which is implicitly included with me.
The code compiles fine with g++, clang++, clang-cl and MSVC on
my PC.

[Bonita Montero]

Am 04.11.2023 um 10:19 schrieb Bonita Montero:

> Google for "benaphore mutex" ...
Or rather "benaphore mutex -semaphore".

[Scott Lurndal]

LL/SC is not compare and swap.

[Bonita Montero]

Cite where I said sth. opposite.

[Scott Lurndal]

"Chris M. Thomasson" <chris.m.t...@gmail.com> writes:

BTW - Compare and Swap was invented by an engineer at IBM -
CAS is a backronym, the inventors initials are CAS.

https://www.garlic.com/~lynn/2004l.html#56


"charlie had come up with compare and swap at the science scenter
http://www.garlic.com/~lynn/subtopic.html#545tech
based on a lot of work he was doing in fine grain locking (late 60s)
... and tried to get it into 370 architecture. POK architecture owners
came back and said it wasn't possible to justify a multiprocessor-specific
instruction for the 370 architecture (already having test&set) ... and that
to get it justified, it would be necessary to come up with a non-multiprocessor
use for the instruction. thus was born the description for multi-threaded
application use in non-locked regions .... when running on either
multiprocessor or non-multiprocessor machines. this was originally
included in the 370 prinicple of operations as programming notes
associated with the compare&swap instruction(s). the description has
since been expanded and moved to the principles of operation appendix.

note that the choice of compare and swap comes from needing a mnemonic
that matched charlie's initials (CAS). the mnemonic was slightly changed
for inclusion in 370 to CS (compare and swap) and CDS (compare double and swap).

the instructions have since been expanded for 64-bit operation and a
new "perform locked operation" has since been added.

[Scott Lurndal]

Sure there is. It's even obvious.

[David Brown]

On 03/11/2023 18:08, Bonita Montero wrote:
> Am 03.11.2023 um 18:02 schrieb David Brown:
>
>> Please read <https://en.cppreference.com/w/cpp/thread/mutex/unlock>.
>> Note the sentence "The mutex must be locked by the current thread of
>> execution, otherwise, the behavior is undefined."
>
> Maybe, but I'm talking about how mutexes usually work internally.
>

I think, from this thread, it is clear that you have no idea how mutexes
are used. I therefore assume you have no idea how they work internally.
And I am entirely confident that your idea of "usually" is limited to
one single OS.

>
>> Using a semaphore as a lock is not recommended because a semaphore
>> does not make a good lock.  A main reason for that is that it has no
>> concept of ownership. ...
>
> Mutexes also usually have no notion of ownership.
>

I stand corrected. Your idea of "usually" is limited to no OS in existence.

[Bonita Montero]

Am 04.11.2023 um 17:22 schrieb David Brown:

> I think, from this thread, it is clear that you have no idea how mutexes

> are used. ...

I use them every day and I've developed my own reader's-writer-lock.

> I stand corrected.  Your idea of "usually" is limited to no OS in
> existence.

A non-recurive mutex doensn't need to know which thread is the
owner, but just that there's an owner.

[Bonita Montero]

Not for Kaz.

[David Brown]

On 04/11/2023 17:35, Bonita Montero wrote:
> Am 04.11.2023 um 17:22 schrieb David Brown:
>
>> I think, from this thread, it is clear that you have no idea how
>> mutexes are used. ...
>
> I use them every day and I've developed my own reader's-writer-lock.
>

Do you do all your work relying on luck?

>> I stand corrected.  Your idea of "usually" is limited to no OS in
>> existence.
>
> A non-recurive mutex doensn't need to know which thread is the
> owner, but just that there's an owner.
>

No, it needs to know the owner - because only the owner is allowed to
release the lock.

I suppose you could make a half-arsed mutex implementation that relies
on programmers never making mistakes, and just let the nasal demons fly
when people like you can't read and follow specifications.

And even if you have such a poor mutex implementation, conceptually
there is always an owner when the lock is taken - that's the point of
the thing.

[Bonita Montero]

Am 04.11.2023 um 17:56 schrieb David Brown:


> No, it needs to know the owner - because only the owner is allowed to
> release the lock.

This is a superfluous check that does not determine function.

> I suppose you could make a half-arsed mutex implementation that relies
> on programmers never making mistakes, and just let the nasal demons fly
> when people like you can't read and follow specifications.

It may be possible to release a mutex from another thread, but as no
one does this this check doesn't make sense. That that much unlikely
that that happens that it doesn't make sense as a debugging aid, even
more in C++, where you can't forget unlocking inside the same thread
if you use a unique_lock<> or lock_guard<>.

[Chris M. Thomasson]

LL/SC can be used to implement a weak CAS. Also, wrt the algorithm, it
can be used to implement a strong CAS.

CMPXCHG over on intel cannot be used to implement a weak CAS.

[Kaz Kylheku]

You're not successfully making it appear as if I said that.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazi...@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

[Chris M. Thomasson]

Yup. I have actually conversed with Lynn over on comp.arch. Very smart
person loaded up with knowledge.

[Chris M. Thomasson]

The free pool manipulation in IBM's principle of operations, iirc, its
in an appendix.

[Bonita Montero]

Am 04.11.2023 um 17:03 schrieb Scott Lurndal:
> BTW - Compare and Swap was invented by an engineer at IBM -

> ...

The idea is not that complex that it would have been invented by
a lot of technichians later. I think that LL/SC is more sexy since
it allows lock-free stacks with one word.

[Chris M. Thomasson]

Just be careful wrt the reservation granularity. LL/SC can be prone to
livelock.

[Chris M. Thomasson]

On 11/4/2023 2:25 AM, Bonita Montero wrote:
> Am 03.11.2023 um 23:19 schrieb Chris M. Thomasson:
>> On 11/3/2023 8:49 AM, Bonita Montero wrote:
>>> Am 03.11.2023 um 16:35 schrieb David Brown:
>>>
>>>> And using the definitions held by most people involved (including
>>>> the C++ standard library, the Windows API, and AFAIK POSIX), mutexes
>>>> have ownership and semaphores do not. ...
>>>
>>> Mutexes only have ownership if they're recursive.
>>
>> WHAT!!! ? ;^o
>
> It's not necessary to record ownership of a specific thread for a non
> recursive mutex but just _that_ a mutex is ownend, and not by whom.
> The benaphore can easily locked in one thread and unlocked in another
> thread, although this usually doesn't happen.
> It's just the surrounding code that successfully locked a mutex that
> "knows" it is the owner.

The surrounding code is the mutex. It can use a kernel semaphore for
slow paths. You seem to be radically confused.

[Chris M. Thomasson]

Oh god. The benaphore is a semaphore. Mutex logic using a semaphore for
a slow path is different than a semaphore. God damn, man... You are
confused and/or trolling? Humm...

[Chris M. Thomasson]

Huh? The point of the benaphore (a semaphore) is to try to avoid going
into the kernel to sleep or to be awakened.

God damn it Bonita!