Am 08.11.2023 um 20:49 schrieb Kaz Kylheku:

> No, the "monitor" idea you're proposing is different in this
> way.

That's not true. That spurious wakesups may happen with a mutex and
a condition variable are constituted in that both are separate enti-
ties. Spuriuos wakesups never happen with my implementation, but
stolen wakeups are still possible.

> Monitors as they are understood in computer science (first described by
> C. A. R. Hoare) do not combine the monitor and condition variables into
> one object; they are distinct entities: one monitor, zero to many
> conditions.

The way monitors work does not suggest an implementation, or they can
be based internally on a mutex and a condition variable, but if you
have a monitor that never has spurious wakeups, it is implemented
like mine.

> To avoid muddying the debate with nonstandard terminology, you might
> want to call your cockamamie idea "bonitor".

I've implemented a monitor without spurious wakeups.

On 2023-11-08, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 08.11.2023 um 19:16 schrieb Kaz Kylheku:
>
>> POSIX-style mutexes and condition variables are actually Mesa-style
>> monitors.
>
> A monitor is different because the mutex and condition variable
> is joined in a monitor which allows the shown optimization while
> waiting to be notified.

No, the "monitor" idea you're proposing is different in this
way.

Monitors as they are understood in computer science (first described by
C. A. R. Hoare) do not combine the monitor and condition variables into
one object; they are distinct entities: one monitor, zero to many
conditions.

To avoid muddying the debate with nonstandard terminology, you might
want to call your cockamamie idea "bonitor".

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

On 11/8/2023 11:56 AM, Bonita Montero wrote:
> Am 08.11.2023 um 20:49 schrieb Kaz Kylheku:
>
>> No, the "monitor" idea you're proposing is different in this
>> way.
>
> That's not true. That spurious wakesups may happen with a mutex and
> a condition variable are constituted in that both are separate enti-
> ties. Spuriuos wakesups never happen with my implementation, but
> stolen wakeups are still possible.
>
>> Monitors as they are understood in computer science (first described by
>> C. A. R. Hoare) do not combine the monitor and condition variables into
>> one object; they are distinct entities: one monitor, zero to many
>> conditions.
>
> The way monitors work does not suggest an implementation, or they can
> be based internally on a mutex and a condition variable, but if you
> have a monitor that never has spurious wakeups, it is implemented
> like mine.
>
>> To avoid muddying the debate with nonstandard terminology, you might
>> want to call your cockamamie idea "bonitor".
>
> I've implemented a monitor without spurious wakeups.
>

Yawn.

Java and .NET have monitor objects instead of a combination of mutexes
and condition variables. The advantage of a monitor object is that when
you wait for a monitor to be signalled you can wait for that and for the
mutexe's semaphore to be unlocked in _one_ step. With a condition varia-
ble you have first to wait for the notify()-semaphore to be signalled
and for the mutexe's lock in two steps.
The below code simply has a 32 or 64 bit atomic (depening on if the 64
bit variant is lock-free or not) and the lower half is the number of
threads waiting to enter the mutex part and the upper half is the num-
ber of threads waiting to be notified. As all threads wanting to be
notified are also waiting for the mutex the lower half is always >=
the upper half, which I check for in several asserts.
On Windows waiting to be notified and waiting to lock the mutex part
to be unlocked is done by WaitForMultipleObjects(). On Linux there's
no way to wait for mutliple kernel handles to be signalled, but there
are SystemV semaphore sets which may consist of several semaphores and
you may have multiple operations to proceed atomically on this set.
The drawback of combining the mutex and condition-variable parts is
that you can't have multiple conditions associated with the same mutex.

// monitor.h

#pragma once
#if defined(_WIN32)
#define NOMINMAX
#include <Windows.h>
#elif defined(__unix__)
#include <sys/types.h>
#include <sys/sem.h>
#include <sys/stat.h>
#else
#error unsupported platform
#endif
#include <atomic>
#include <semaphore>
#include <type_traits>
#if defined(_WIN32)
#include "xhandle.h"
#endif

struct monitor
{ monitor();
~monitor();
void lock();
void unlock();
void wait();
void notify();
void notify_all();
private:
inline static thread_local char t_dummy;
static constexpr bool USE64 = std::atomic_int64_t::is_always_lock_free;
using atomic_word_t = std::conditional_t<USE64, uint64_t, uint32_t>;
static constexpr unsigned BITS = USE64 ? 32 : 16;
static constexpr atomic_word_t
ENTER_VALUE = 1,
SIGNAL_VALUE = USE64 ? 1ull << 32 : 1,
ENTER_MASK = USE64 ? (uint32_t)-1 : (uint16_t)-1,
SIGNAL_MASK = USE64 ? (uint64_t)(uint32_t)-1 << 32 :
(uint32_t)(uint16_t)-1 << 16;
std::atomic<atomic_word_t> m_atomic;
std::atomic<char *> m_threadId;
std::atomic_uint32_t m_recCount;
#if defined(_WIN32)
static constexpr uint32_t SEM_MAX = std::numeric_limits<LONG>::max();
XHANDLE
m_xhEnterEvt,
m_xhSignalSem;
#elif defined(__unix__)
static constexpr uint32_t SEM_MAX = std::numeric_limits<short>::max();
int m_sems;
int semop( std::initializer_list<sembuf> sems );
#endif
};

// monitor.cpp

#include <iostream>
#include <limits>
#include <system_error>
#include <cassert>
#include "monitor.h"

using namespace std;

monitor::monitor() :
m_atomic( 0 ),
m_threadId( nullptr )
#if defined(_WIN32)
, m_xhEnterEvt( CreateEventA( nullptr, FALSE, FALSE, nullptr ) ),
m_xhSignalSem( CreateSemaphoreA( nullptr, 0, SEM_MAX, nullptr ) )
#elif defined(__unix__)
, m_sems( semget( IPC_PRIVATE, 2, S_IRUSR | S_IWUSR ) )
#endif
{ #if defined(_WIN32)
if( !m_xhEnterEvt.get() || !m_xhSignalSem.get() )
throw system_error( GetLastError(), system_category(), "can't
initialize monitor object" );
#elif defined(__unix__)
union semun { int val; void *p; } su;
su.val = 0;
#if defined(__linux__)
if( m_sems == -1 )
#else
if( m_sems == -1 || semctl( m_sems, 0, SETVAL, su ) == -1 || semctl(
m_sems, 1, SETVAL, su ) == -1 )
#endif
throw system_error( errno, system_category(), "can't initialize
monitor object" );
#endif
}

monitor::~monitor()
{ #if defined(__unix__)
int ret = semctl( m_sems, 0, IPC_RMID );
assert(ret != -1);
#endif
}

void monitor::lock()
{ if( m_threadId.load( memory_order_relaxed ) == &t_dummy )
{
uint32_t oldRecCount = m_recCount.load( memory_order_relaxed );
if( oldRecCount == (uint32_t)-1 )
throw system_error( (int)errc::result_out_of_range,
generic_category(), "montor's recursion count saturated" );
m_recCount.store( oldRecCount + 1, memory_order_relaxed );
return;
}
atomic_word_t ref = m_atomic.load( memory_order_relaxed );
do
{
if( (ref & ENTER_MASK) == ENTER_MASK )
throw system_error( (int)errc::result_out_of_range,
generic_category(), "montor's locker count saturated" );
assert((ref & ENTER_MASK) >= ref >> BITS);
} while( !m_atomic.compare_exchange_strong( ref, ref + 1,
memory_order_acquire, memory_order_relaxed ) );
auto initThread = [&]()
{
m_threadId.store( &t_dummy, memory_order_relaxed );
m_recCount.store( 0, memory_order_relaxed );
};
if( (ref & ENTER_MASK) == ref >> BITS ) [[likely]]
return initThread();
#if defined(_WIN32)
if( WaitForSingleObject( m_xhEnterEvt.get(), INFINITE ) != WAIT_OBJECT_0 )
terminate();
#elif defined(__unix__)
if( semop( { { 0, -1, 0 } } ) )
terminate();
#endif
initThread();
}

void monitor::unlock()
{ if( uint32_t rc; m_threadId.load( memory_order_relaxed ) == &t_dummy &&
(rc = m_recCount.load( memory_order_relaxed )) )
{
m_recCount.store( rc - 1, memory_order_relaxed );
return;
}
atomic_word_t ref = m_atomic.load( memory_order_relaxed );
assert((ref & ENTER_MASK) && m_threadId == &t_dummy);
m_threadId.store( nullptr, memory_order_relaxed );
do
assert((ref & ENTER_MASK) >= ref >> BITS);
while( !m_atomic.compare_exchange_strong( ref, ref - 1,
memory_order_release, memory_order_relaxed ) );
if( (ref & ENTER_MASK) == 1 ) [[likely]]
return;
#if defined(_WIN32)
if( !SetEvent( m_xhEnterEvt.get() ) )
terminate();
#elif defined(__unix__)
if( semop( { { 0, 1, IPC_NOWAIT } } ) )
terminate();
#endif
}

void monitor::wait()
{ assert(m_threadId == &t_dummy && !m_recCount);
m_threadId.store( nullptr, memory_order_relaxed );
atomic_word_t ref = m_atomic.load( memory_order_relaxed );
do
assert((ref & ENTER_MASK) > ref >> BITS);
while( !m_atomic.compare_exchange_strong( ref, ref + SIGNAL_VALUE,
memory_order_release, memory_order_relaxed ) );
if( (ref & ENTER_MASK) - (ref >> BITS) > 1 )
{
#if defined(_WIN32)
if( !SetEvent( m_xhEnterEvt.get() ) )
terminate();
#elif defined(__unix__)
if( semop( { { 0, 1, IPC_NOWAIT } } ) )
terminate();
#endif
}
#if defined(_WIN32)
HANDLE waitFor[2] { m_xhEnterEvt.get(), m_xhSignalSem.get() };
if( WaitForMultipleObjects( 2, waitFor, TRUE, INFINITE ) != WAIT_OBJECT_0 )
terminate();
#elif defined(__unix__)
if( semop( { { 0, -1, 0 }, { 1, -1, 0 } } ) )
terminate();
#endif
m_threadId.store( &t_dummy, memory_order_relaxed );
m_recCount.store( 0, memory_order_relaxed );
}

void monitor::notify()
{ atomic_word_t ref = m_atomic.load( memory_order_relaxed );
assert((ref & ENTER_MASK) > ref >> BITS && m_threadId == &t_dummy);
uint32_t n;
while( (n = (uint32_t)(ref >> BITS)) &&
!m_atomic.compare_exchange_strong( ref, ref - SIGNAL_VALUE,
memory_order_relaxed, memory_order_relaxed ) );
if( !(ref >> BITS) )
return;
#if defined(_WIN32)
if( !ReleaseSemaphore( m_xhSignalSem.get(), 1, nullptr ) )
terminate();
#elif defined(__unix__)
int ret;
do
ret = semop( { { 1, 1, IPC_NOWAIT } } );
while( ret == EAGAIN );
if( ret )
terminate();
#endif
}

void monitor::notify_all()
{ atomic_word_t ref = m_atomic.load( memory_order_relaxed );
assert((ref & ENTER_MASK) > ref >> BITS && m_threadId == &t_dummy);
uint32_t n;
while( (n = (uint32_t)(ref >> BITS)) &&
!m_atomic.compare_exchange_strong( ref, ref & ENTER_MASK,
memory_order_relaxed, memory_order_relaxed ) );
while( n )
{
uint32_t nRelease = n <= SEM_MAX ? n : SEM_MAX;
#if defined(_WIN32)
BOOL succ;
for( ; !(succ = ReleaseSemaphore( m_xhSignalSem.get(), nRelease,
nullptr )) && GetLastError() == ERROR_TOO_MANY_POSTS;
nRelease = nRelease > 1 ? nRelease / 2 : nRelease );
if( !succ )
terminate();
#elif defined(__unix__)
int ret;
for( ; (ret = semop( { { 1, (short)nRelease, IPC_NOWAIT } } )) == EAGAIN;
nRelease = nRelease > 1 ? nRelease / 2 : nRelease );
if( ret )
terminate();
#endif
n -= nRelease;
}
}

#if defined(__unix__)
int monitor::semop( initializer_list<sembuf> sems )
{ int ret;
while( (ret = ::semop( m_sems, const_cast<sembuf *>(sems.begin()),
sems.size() )) == EINTR );
return ret;
} #endif

On 11/8/2023 1:41 PM, Chris M. Thomasson wrote:
> On 11/8/2023 9:16 AM, Bonita Montero wrote:
>> Am 08.11.2023 um 15:56 schrieb Bonita Montero:
>>> Java and .NET have monitor objects instead of a combination of mutexes
>>> and condition variables. The advantage of a monitor object is that when
>>> you wait for a monitor to be signalled you can wait for that and for the
>>> mutexe's semaphore to be unlocked in _one_ step. With a condition varia-
>>> ble you have first to wait for the notify()-semaphore to be signalled
>>> and for the mutexe's lock in two steps.
>>> The below code simply has a 32 or 64 bit atomic (depening on if the 64
>>> bit variant is lock-free or not) and the lower half is the number of
>>> threads waiting to enter the mutex part and the upper half is the num-
>>> ber of threads waiting to be notified. As all threads wanting to be
>>> notified are also waiting for the mutex the lower half is always >=
>>> the upper half, which I check for in several asserts.
>>> On Windows waiting to be notified and waiting to lock the mutex part
>>> to be unlocked is done by WaitForMultipleObjects(). On Linux there's
>>> no way to wait for mutliple kernel handles to be signalled, but there
>>> are SystemV semaphore sets which may consist of several semaphores and
>>> you may have multiple operations to proceed atomically on this set.
>>> The drawback of combining the mutex and condition-variable parts is
>>> that you can't have multiple conditions associated with the same mutex.
>
> [snip code]
>
> Model it through Relacy Race Detector first, if you get any issues, we
> can work through them. ;^)
>
> https://github.com/dvyukov/relacy
>
>

There is no shame in using a race detector. If you want me to debug your
work, well, its not going to be for free. Believe it or not its not
exactly trivial. You already had to make corrections to your own code.

> while( ret == -1 && errno == EAGAIN );

Keep EINTR in mind.

Am 08.11.2023 um 15:56 schrieb Bonita Montero:
> Java and .NET have monitor objects instead of a combination of mutexes
> and condition variables. The advantage of a monitor object is that when
> you wait for a monitor to be signalled you can wait for that and for the
> mutexe's semaphore to be unlocked in _one_ step. With a condition varia-
> ble you have first to wait for the notify()-semaphore to be signalled
> and for the mutexe's lock in two steps.
> The below code simply has a 32 or 64 bit atomic (depening on if the 64
> bit variant is lock-free or not) and the lower half is the number of
> threads waiting to enter the mutex part and the upper half is the num-
> ber of threads waiting to be notified. As all threads wanting to be
> notified are also waiting for the mutex the lower half is always >=
> the upper half, which I check for in several asserts.
> On Windows waiting to be notified and waiting to lock the mutex part
> to be unlocked is done by WaitForMultipleObjects(). On Linux there's
> no way to wait for mutliple kernel handles to be signalled, but there
> are SystemV semaphore sets which may consist of several semaphores and
> you may have multiple operations to proceed atomically on this set.
> The drawback of combining the mutex and condition-variable parts is
> that you can't have multiple conditions associated with the same mutex.
>
>
> // monitor.h
>
> #pragma once
> #if defined(_WIN32)
>     #define NOMINMAX
>     #include <Windows.h>
> #elif defined(__unix__)
>     #include <sys/types.h>
>     #include <sys/sem.h>
>     #include <sys/stat.h>
> #else
>     #error unsupported platform
> #endif
> #include <atomic>
> #include <semaphore>
> #include <type_traits>
> #if defined(_WIN32)
>     #include "xhandle.h"
> #endif
>
> struct monitor
> {
>     monitor();
>     ~monitor();
>     void lock();
>     void unlock();
>     void wait();
>     void notify();
>     void notify_all();
> private:
>     inline static thread_local char t_dummy;
>     static constexpr bool USE64 =
> std::atomic_int64_t::is_always_lock_free;
>     using atomic_word_t = std::conditional_t<USE64, uint64_t, uint32_t>;
>     static constexpr unsigned BITS = USE64 ? 32 : 16;
>     static constexpr atomic_word_t
>         ENTER_VALUE = 1,
>         SIGNAL_VALUE = USE64 ? 1ull << 32 : 1,
>         ENTER_MASK = USE64 ? (uint32_t)-1 : (uint16_t)-1,
>         SIGNAL_MASK = USE64 ? (uint64_t)(uint32_t)-1 << 32 :
> (uint32_t)(uint16_t)-1 << 16;
>     std::atomic<atomic_word_t> m_atomic;
>     std::atomic<char *> m_threadId;
>     std::atomic_uint32_t m_recCount;
> #if defined(_WIN32)
>     static constexpr uint32_t SEM_MAX = std::numeric_limits<LONG>::max();
>     XHANDLE
>         m_xhEnterEvt,
>         m_xhSignalSem;
> #elif defined(__unix__)
>     static constexpr uint32_t SEM_MAX = std::numeric_limits<short>::max();
>     int m_sems;
>     int semop( std::initializer_list<sembuf> sems );
> #endif
> };
>
> // monitor.cpp
>
> #include <iostream>
> #include <limits>
> #include <system_error>
> #include <cassert>
> #include "monitor.h"
>
> using namespace std;
>
> monitor::monitor() :
>     m_atomic( 0 ),
>     m_threadId( nullptr )
> #if defined(_WIN32)
>     , m_xhEnterEvt( CreateEventA( nullptr, FALSE, FALSE, nullptr ) ),
>     m_xhSignalSem( CreateSemaphoreA( nullptr, 0, SEM_MAX, nullptr ) )
> #elif defined(__unix__)
>     , m_sems( semget( IPC_PRIVATE, 2, S_IRUSR | S_IWUSR ) )
> #endif
> {
> #if defined(_WIN32)
>     if( !m_xhEnterEvt.get() || !m_xhSignalSem.get() )
>         throw system_error( GetLastError(), system_category(), "can't
> initialize monitor object" );
> #elif defined(__unix__)
>     union semun { int val; void *p; } su;
>     su.val = 0;
>     #if defined(__linux__)
>     if( m_sems == -1 )
>     #else
>     if( m_sems == -1 || semctl( m_sems, 0, SETVAL, su ) == -1 ||
> semctl( m_sems, 1, SETVAL, su ) == -1 )
>     #endif
>         throw system_error( errno, system_category(), "can't initialize
> monitor object" );
> #endif
> }
>
> monitor::~monitor()
> {
> #if defined(__unix__)
>     int ret = semctl( m_sems, 0, IPC_RMID );
>     assert(ret != -1);
> #endif
> }
>
> void monitor::lock()
> {
>     if( m_threadId.load( memory_order_relaxed ) == &t_dummy )
>     {
>         uint32_t oldRecCount = m_recCount.load( memory_order_relaxed );
>         if( oldRecCount == (uint32_t)-1 )
>             throw system_error( (int)errc::result_out_of_range,
> generic_category(), "montor's recursion count saturated" );
>         m_recCount.store( oldRecCount + 1, memory_order_relaxed );
>         return;
>     }
>     atomic_word_t ref = m_atomic.load( memory_order_relaxed );
>     do
>     {
>         if( (ref & ENTER_MASK) == ENTER_MASK )
>             throw system_error( (int)errc::result_out_of_range,
> generic_category(), "montor's locker count saturated" );
>         assert((ref & ENTER_MASK) >= ref >> BITS);
>     } while( !m_atomic.compare_exchange_strong( ref, ref + 1,
> memory_order_acquire, memory_order_relaxed ) );
>     auto initThread = [&]()
>     {
>         m_threadId.store( &t_dummy, memory_order_relaxed );
>         m_recCount.store( 0, memory_order_relaxed );
>     };
>     if( (ref & ENTER_MASK) == ref >> BITS ) [[likely]]
>         return initThread();
> #if defined(_WIN32)
>     if( WaitForSingleObject( m_xhEnterEvt.get(), INFINITE ) !=
> WAIT_OBJECT_0 )
>         terminate();
> #elif defined(__unix__)
>     if( semop( { { 0, -1, 0 } } ) )
>         terminate();
> #endif
>     initThread();
> }
>
> void monitor::unlock()
> {
>     if( uint32_t rc; m_threadId.load( memory_order_relaxed ) ==
> &t_dummy && (rc = m_recCount.load( memory_order_relaxed )) )
>     {
>         m_recCount.store( rc - 1, memory_order_relaxed );
>         return;
>     }
>     atomic_word_t ref = m_atomic.load( memory_order_relaxed );
>     assert((ref & ENTER_MASK) && m_threadId == &t_dummy);
>     m_threadId.store( nullptr, memory_order_relaxed );
>     do
>         assert((ref & ENTER_MASK) >= ref >> BITS);
>     while( !m_atomic.compare_exchange_strong( ref, ref - 1,
> memory_order_release, memory_order_relaxed ) );
>     if( (ref & ENTER_MASK) == 1 ) [[likely]]
>         return;
> #if defined(_WIN32)
>     if( !SetEvent( m_xhEnterEvt.get() ) )
>         terminate();
> #elif defined(__unix__)
>     if( semop( { { 0, 1, IPC_NOWAIT } } ) )
>         terminate();
> #endif
> }
>
> void monitor::wait()
> {
>     assert(m_threadId == &t_dummy && !m_recCount);
>     m_threadId.store( nullptr, memory_order_relaxed );
>     atomic_word_t ref = m_atomic.load( memory_order_relaxed );
>     do
>         assert((ref & ENTER_MASK) > ref >> BITS);
>     while( !m_atomic.compare_exchange_strong( ref, ref + SIGNAL_VALUE,
> memory_order_release, memory_order_relaxed ) );
>     if( (ref & ENTER_MASK) - (ref >> BITS) > 1 )
>     {
> #if defined(_WIN32)
>         if( !SetEvent( m_xhEnterEvt.get() ) )
>             terminate();
> #elif defined(__unix__)
>         if( semop( { { 0, 1, IPC_NOWAIT } } ) )
>             terminate();
> #endif
>     }
> #if defined(_WIN32)
>     HANDLE waitFor[2] { m_xhEnterEvt.get(), m_xhSignalSem.get() };
>     if( WaitForMultipleObjects( 2, waitFor, TRUE, INFINITE ) !=
> WAIT_OBJECT_0 )
>         terminate();
> #elif defined(__unix__)
>     if( semop( { { 0, -1, 0 }, { 1, -1, 0 } } ) )
>         terminate();
> #endif
>     m_threadId.store( &t_dummy, memory_order_relaxed );
>     m_recCount.store( 0, memory_order_relaxed );
> }
>
> void monitor::notify()
> {
>     atomic_word_t ref = m_atomic.load( memory_order_relaxed );
>     assert((ref & ENTER_MASK) > ref >> BITS && m_threadId == &t_dummy);
>     uint32_t n;
>     while( (n = (uint32_t)(ref >> BITS)) &&
> !m_atomic.compare_exchange_strong( ref, ref - SIGNAL_VALUE,
> memory_order_relaxed, memory_order_relaxed ) );
>     if( !(ref >> BITS) )
>         return;
> #if defined(_WIN32)
>     if( !ReleaseSemaphore( m_xhSignalSem.get(), 1, nullptr ) )
>         terminate();
> #elif defined(__unix__)
>     int ret;
>     do
>         ret = semop( { { 1, 1, IPC_NOWAIT } } );
>     while( ret == EAGAIN );
while( ret == -1 && errno == EAGAIN );
>     if( ret )
>         terminate();
> #endif
> }
>
> void monitor::notify_all()
> {
>     atomic_word_t ref = m_atomic.load( memory_order_relaxed );
>     assert((ref & ENTER_MASK) > ref >> BITS && m_threadId == &t_dummy);
>     uint32_t n;
>     while( (n = (uint32_t)(ref >> BITS)) &&
> !m_atomic.compare_exchange_strong( ref, ref & ENTER_MASK,
> memory_order_relaxed, memory_order_relaxed ) );
>     while( n )
>     {
>         uint32_t nRelease = n <= SEM_MAX ? n : SEM_MAX;
> #if defined(_WIN32)
>         BOOL succ;
>         for( ; !(succ = ReleaseSemaphore( m_xhSignalSem.get(),
> nRelease, nullptr )) && GetLastError() == ERROR_TOO_MANY_POSTS;
>             nRelease = nRelease > 1 ? nRelease / 2 : nRelease );
>         if( !succ )
>             terminate();
> #elif defined(__unix__)
>         int ret;
>         for( ; (ret = semop( { { 1, (short)nRelease, IPC_NOWAIT } } ))
> == EAGAIN;
for( ; (ret = semop( { { 1, (short)nRelease, IPC_NOWAIT } } )) == -1 &&
errno == EAGAIN;

On 2023-11-08, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Java and .NET have monitor objects instead of a combination of mutexes
> and condition variables. The advantage of a monitor object is that when

POSIX-style mutexes and condition variables are actually Mesa-style
monitors.

Monitors were invented by C. A. R. Hoare ("Quicksort Guy") and another
collaborator whose name escapes me, in the context of some concurrent
Pascal experiment.

Hoare monitors make some ordering guarantees that the "Mesa semantics"
monitors do not. Something like that when you signal a condition
variable, a waiting thread gets in, and when it releases the mutex, the
original thread get back in (no competititon).

The paradigm is that there is one monitor and multiple conditions.

> you wait for a monitor to be signalled you can wait for that and for the
> mutexe's semaphore to be unlocked in _one_ step. With a condition varia-
> ble you have first to wait for the notify()-semaphore to be signalled
> and for the mutexe's lock in two steps.

That's an internal detail. In the POSIX API, you have pthread_cond_wait,
which looks like one operation to the caller.

It is not required to be implemented with semaphores.

> struct monitor
> {
> monitor();
> ~monitor();
> void lock();
> void unlock();
> void wait();
> void notify();
> void notify_all();

The problem is that you often want multiple condition variables with
one monitor. So this is a nonstarter.

I suggest you make an API where the wait operation has an "int cond_index"
parameter to select a condition variable.

The monitor object can be told at construction time how large a vector
of condition variables is required.

That still doesn't provide all the flexibility, but fits the common use
cases where you have a monitor plus a fixed number of condition
variables.

It doesn't work where you have a dynamic number of condition variables;
e.g. a dynamic set data structure has one monitor, plus a condition on
each node it contains.

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

Am 08.11.2023 um 19:16 schrieb Kaz Kylheku:

> POSIX-style mutexes and condition variables are actually Mesa-style
> monitors.

A monitor is different because the mutex and condition variable
is joined in a monitor which allows the shown optimization while
waiting to be notified.

> That's an internal detail. In the POSIX API, you have pthread_cond_wait,
> which looks like one operation to the caller.

The mentioned optimization isn't possible if you don't join the
mutex with the condition variable as I've shown; or more precisely
there's a limit on the number of conditions as explained below.

> The problem is that you often want multiple condition variables with
> one monitor. So this is a nonstarter.

If that would be often Java and .net would provide that.

> I suggest you make an API where the wait operation has an "int cond_index"
> parameter to select a condition variable.

I've got a value which is usually 64 bit where the lower half is the
numer if theads which want to have exclusive access to the mutex. The
upper half is the number of threads that want to be notified. I thought
I could split the 64 bit value in three parts, one for the first threads
and two for the latter two types of threads. But from my eperience with
Java and .net I thought that it doesn't happen often that you need two
separate monitors to have twoo conditions, so I dropped this idea.

> The monitor object can be told at construction time how large a vector
> of condition variables is required.

Then I'd had to make my atomic even more split and the number of
threads being able to register in the bitfields of the atomic would
be too limited. My code is to take advantage of the one-step approach
while waiting to be notified and if you need more conditions beyond
that you'd have to stick with the two kernel calls used with a normal
mutex and condition variable.

On 11/8/2023 9:16 AM, Bonita Montero wrote:
> Am 08.11.2023 um 15:56 schrieb Bonita Montero:
>> Java and .NET have monitor objects instead of a combination of mutexes
>> and condition variables. The advantage of a monitor object is that when
>> you wait for a monitor to be signalled you can wait for that and for the
>> mutexe's semaphore to be unlocked in _one_ step. With a condition varia-
>> ble you have first to wait for the notify()-semaphore to be signalled
>> and for the mutexe's lock in two steps.
>> The below code simply has a 32 or 64 bit atomic (depening on if the 64
>> bit variant is lock-free or not) and the lower half is the number of
>> threads waiting to enter the mutex part and the upper half is the num-
>> ber of threads waiting to be notified. As all threads wanting to be
>> notified are also waiting for the mutex the lower half is always >=
>> the upper half, which I check for in several asserts.
>> On Windows waiting to be notified and waiting to lock the mutex part
>> to be unlocked is done by WaitForMultipleObjects(). On Linux there's
>> no way to wait for mutliple kernel handles to be signalled, but there
>> are SystemV semaphore sets which may consist of several semaphores and
>> you may have multiple operations to proceed atomically on this set.
>> The drawback of combining the mutex and condition-variable parts is
>> that you can't have multiple conditions associated with the same mutex.

[snip code]

Model it through Relacy Race Detector first, if you get any issues, we
can work through them. ;^)

https://github.com/dvyukov/relacy

On 2023-11-08, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
> On 11/8/2023 11:56 AM, Bonita Montero wrote:
>> I've implemented a monitor without spurious wakeups.
>
> Yawn.

Funnier:

Amine Moulay Ramdane has written seven, likewise dead in the water.

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

On 2023-11-08, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 08.11.2023 um 20:49 schrieb Kaz Kylheku:
>
>> No, the "monitor" idea you're proposing is different in this
>> way.
>
> That's not true. That spurious wakesups may happen with a mutex and
> a condition variable are constituted in that both are separate enti-
> ties.

That doesn't follow. Hoare's original monitor implementation had
separate condition variables, yet no spurious wakeups.

In fact, the condition wait did not require loops! Just:

if (!whatever_condition)
monitor.wait(whatever_cond_var);

The thread waiting on the condition was guaranteed to get into
the monitor with the condition still true!

The reason we accept spurious wakeups is that the guarantee is not
efficient on systems with multiple processors, not because
we don't know how to code up the guarantee.

Spurious wakesup are part of the "Mesa semantics" of monitors
and condition variables, in contrast to the "Hoare semantics".

> I've implemented a monitor without spurious wakeups.

It doesn't look like a monitor, if it doesn't have multiple condition
variables. Maybe your approach can support that.

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

On 11/8/2023 11:56 AM, Bonita Montero wrote:
> Am 08.11.2023 um 20:49 schrieb Kaz Kylheku:
>
>> No, the "monitor" idea you're proposing is different in this
>> way.
>
> That's not true. That spurious wakesups may happen with a mutex and
> a condition variable are constituted in that both are separate enti-
> ties. Spuriuos wakesups never happen with my implementation, but
> stolen wakeups are still possible.
>
>> Monitors as they are understood in computer science (first described by
>> C. A. R. Hoare) do not combine the monitor and condition variables into
>> one object; they are distinct entities: one monitor, zero to many
>> conditions.

mutex and condition variables happen to be intimately interconnected.
Look up wait morphing...

>
> The way monitors work does not suggest an implementation, or they can
> be based internally on a mutex and a condition variable, but if you
> have a monitor that never has spurious wakeups, it is implemented
> like mine.
>
>> To avoid muddying the debate with nonstandard terminology, you might
>> want to call your cockamamie idea "bonitor".
>
> I've implemented a monitor without spurious wakeups.
>

Am 09.11.2023 um 00:25 schrieb Kaz Kylheku:

> Spurious wakesup are part of the "Mesa semantics" of monitors
> and condition variables, in contrast to the "Hoare semantics".

Hoare monitors suck since they are less efficient.

Am 09.11.2023 um 00:32 schrieb Chris M. Thomasson:

> mutex and condition variables happen to be intimately interconnected.
> Look up wait morphing...

With my implementation registering as a thread wanting to enter the
mutex and waiting to be notified is one atomic step. That's only
possible if they're one part.

On 11/8/2023 8:33 PM, Bonita Montero wrote:
> Am 09.11.2023 um 00:25 schrieb Kaz Kylheku:
>
>> Spurious wakesup are part of the "Mesa semantics" of monitors
>> and condition variables, in contrast to the "Hoare semantics".
>
> Hoare monitors suck since they are less efficient.

Humm... Are you okay Bonita? Anything wrong with you?

Am 08.11.2023 um 22:41 schrieb Chris M. Thomasson:

> Model it through Relacy Race Detector first, if you get any issues, we
> can work through them. ;^)
> https://github.com/dvyukov/relacy

You'd suggest Relacy for a hello world.

Am 08.11.2023 um 22:49 schrieb Chris M. Thomasson:

> Keep EINTR in mind.

EINTR is handled if you inspect my own semop overload function.

Am 09.11.2023 um 05:36 schrieb Chris M. Thomasson:

> Humm... Are you okay Bonita? Anything wrong with you?

Hoare monitors relase a waiting thread immediately after a notify()
and that's less efficient.

On 11/8/2023 1:49 PM, Chris M. Thomasson wrote:
> On 11/8/2023 1:41 PM, Chris M. Thomasson wrote:
>> On 11/8/2023 9:16 AM, Bonita Montero wrote:
>>> Am 08.11.2023 um 15:56 schrieb Bonita Montero:
>>>> Java and .NET have monitor objects instead of a combination of mutexes
>>>> and condition variables. The advantage of a monitor object is that when
>>>> you wait for a monitor to be signalled you can wait for that and for
>>>> the
>>>> mutexe's semaphore to be unlocked in _one_ step. With a condition
>>>> varia-
>>>> ble you have first to wait for the notify()-semaphore to be signalled
>>>> and for the mutexe's lock in two steps.
>>>> The below code simply has a 32 or 64 bit atomic (depening on if the 64
>>>> bit variant is lock-free or not) and the lower half is the number of
>>>> threads waiting to enter the mutex part and the upper half is the num-
>>>> ber of threads waiting to be notified. As all threads wanting to be
>>>> notified are also waiting for the mutex the lower half is always >=
>>>> the upper half, which I check for in several asserts.
>>>> On Windows waiting to be notified and waiting to lock the mutex part
>>>> to be unlocked is done by WaitForMultipleObjects(). On Linux there's
>>>> no way to wait for mutliple kernel handles to be signalled, but there
>>>> are SystemV semaphore sets which may consist of several semaphores and
>>>> you may have multiple operations to proceed atomically on this set.
>>>> The drawback of combining the mutex and condition-variable parts is
>>>> that you can't have multiple conditions associated with the same mutex.
>>
>> [snip code]
>>
>> Model it through Relacy Race Detector first, if you get any issues, we
>> can work through them. ;^)
>>
>> https://github.com/dvyukov/relacy
>>
>>
>
> There is no shame in using a race detector. If you want me to debug your
> work, well, its not going to be for free. Believe it or not its not
> exactly trivial. You already had to make corrections to your own code.
>
> > while( ret == -1 && errno == EAGAIN );
>
> Keep EINTR in mind.

Wrt your code:

https://youtu.be/0R6WIbx8ysE

On 11/8/2023 8:37 PM, Bonita Montero wrote:
> Am 08.11.2023 um 22:49 schrieb Chris M. Thomasson:
>
>> Keep EINTR in mind.
>
> EINTR is handled if you inspect my own semop overload function.
>

I actually might have some free time to blow on it later on tonight.
Humm... You are not exactly a fun person to work for.

On 11/8/2023 8:36 PM, Bonita Montero wrote:
> Am 08.11.2023 um 22:41 schrieb Chris M. Thomasson:
>
>> Model it through Relacy Race Detector first, if you get any issues, we
>> can work through them. ;^)
>> https://github.com/dvyukov/relacy
>
> You'd suggest Relacy for a hello world.
>
>

:^D

Hello world! Try to get it passing a Relacy test, if you are having
trouble, I can help you.

On 11/8/2023 8:38 PM, Bonita Montero wrote:
> Am 09.11.2023 um 05:36 schrieb Chris M. Thomasson:
>
>> Humm... Are you okay Bonita? Anything wrong with you?
>
> Hoare monitors relase a waiting thread immediately after a notify()
> and that's less efficient.
>

Yawn.

Am 09.11.2023 um 05:42 schrieb Chris M. Thomasson:
> On 11/8/2023 8:38 PM, Bonita Montero wrote:
>> Am 09.11.2023 um 05:36 schrieb Chris M. Thomasson:
>>
>>> Humm... Are you okay Bonita? Anything wrong with you?
>>
>> Hoare monitors relase a waiting thread immediately after a notify()
>> and that's less efficient.

> Yawn.

Re-acquiring the mutex part of a monitor after notify()
is an superfluous extra part that takes CPU time.

On 11/8/2023 3:51 PM, Kaz Kylheku wrote:
> On 2023-11-08, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
>> On 11/8/2023 11:56 AM, Bonita Montero wrote:
>>> I've implemented a monitor without spurious wakeups.
>>
>> Yawn.
>
> Funnier:
>
> Amine Moulay Ramdane has written seven, likewise dead in the water.
>

Actually, Amine had a couple of interesting ideas from years ago.
Therefore, I think that Amine just might be "smarter" than Bonita?

Still, wrt Anime, not sure if the ideas are original or from reading a
white paper.

On 11/8/2023 9:08 PM, Bonita Montero wrote:
> Am 09.11.2023 um 05:42 schrieb Chris M. Thomasson:
>> On 11/8/2023 8:38 PM, Bonita Montero wrote:
>>> Am 09.11.2023 um 05:36 schrieb Chris M. Thomasson:
>>>
>>>> Humm... Are you okay Bonita? Anything wrong with you?
>>>
>>> Hoare monitors relase a waiting thread immediately after a notify()
>>> and that's less efficient.
>
>> Yawn.
>
> Re-acquiring the mutex part of a monitor after notify()
> is an superfluous extra part that takes CPU time.

Look up wait morphing.