Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Groups keyboard shortcuts have been updated
Dismiss
See shortcuts

A Java- / .NET-like monitor

721 views
Skip to first unread message

Bonita Montero

unread,
Nov 8, 2023, 10:28:08 PM11/8/23
to
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

Bonita Montero

unread,
Nov 8, 2023, 10:28:23 PM11/8/23
to
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.


Bonita Montero

unread,
Nov 8, 2023, 10:28:36 PM11/8/23
to
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;

Kaz Kylheku

unread,
Nov 8, 2023, 10:28:45 PM11/8/23
to
On 2023-11-08, Bonita Montero <Bonita....@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: @Kazi...@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

Bonita Montero

unread,
Nov 8, 2023, 10:28:46 PM11/8/23
to
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.

Kaz Kylheku

unread,
Nov 8, 2023, 10:29:01 PM11/8/23
to
On 2023-11-08, Bonita Montero <Bonita....@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".

Chris M. Thomasson

unread,
Nov 8, 2023, 10:29:07 PM11/8/23
to
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.

Chris M. Thomasson

unread,
Nov 8, 2023, 10:29:11 PM11/8/23
to
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.

Kaz Kylheku

unread,
Nov 8, 2023, 10:29:30 PM11/8/23
to
On 2023-11-08, Bonita Montero <Bonita....@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.

Kaz Kylheku

unread,
Nov 8, 2023, 10:29:31 PM11/8/23
to
On 2023-11-08, Chris M. Thomasson <chris.m.t...@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.

Chris M. Thomasson

unread,
Nov 8, 2023, 10:29:38 PM11/8/23
to
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...

Chris M. Thomasson

unread,
Nov 8, 2023, 10:29:44 PM11/8/23
to
On 11/8/2023 11:56 AM, Bonita Montero wrote:
Yawn.

Bonita Montero

unread,
Nov 8, 2023, 11:34:13 PM11/8/23
to
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.

Bonita Montero

unread,
Nov 8, 2023, 11:36:06 PM11/8/23
to
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.

Chris M. Thomasson

unread,
Nov 8, 2023, 11:37:11 PM11/8/23
to
Humm... Are you okay Bonita? Anything wrong with you?

Bonita Montero

unread,
Nov 8, 2023, 11:37:16 PM11/8/23
to
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.


Bonita Montero

unread,
Nov 8, 2023, 11:38:11 PM11/8/23
to
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.

Bonita Montero

unread,
Nov 8, 2023, 11:39:12 PM11/8/23
to
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.

Chris M. Thomasson

unread,
Nov 8, 2023, 11:40:42 PM11/8/23
to
Wrt your code:

https://youtu.be/0R6WIbx8ysE

Chris M. Thomasson

unread,
Nov 8, 2023, 11:41:55 PM11/8/23
to
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.

Chris M. Thomasson

unread,
Nov 8, 2023, 11:42:29 PM11/8/23
to
:^D

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

Chris M. Thomasson

unread,
Nov 8, 2023, 11:42:46 PM11/8/23
to
Yawn.

Bonita Montero

unread,
Nov 9, 2023, 12:09:14 AM11/9/23
to
Re-acquiring the mutex part of a monitor after notify()
is an superfluous extra part that takes CPU time.

Chris M. Thomasson

unread,
Nov 9, 2023, 12:11:43 AM11/9/23
to
On 11/8/2023 3:51 PM, Kaz Kylheku wrote:
> On 2023-11-08, Chris M. Thomasson <chris.m.t...@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.

Chris M. Thomasson

unread,
Nov 9, 2023, 12:12:26 AM11/9/23
to
Look up wait morphing.

Chris M. Thomasson

unread,
Nov 9, 2023, 12:13:41 AM11/9/23
to
Well, I am referring to times of contention.

Bonita Montero

unread,
Nov 9, 2023, 12:18:26 AM11/9/23
to
Wait morphing isn't implemented with glibc's condition variables.
My code doen't need that because I'm sleeping on the condvar part
and on the mutex part in *one* step.

Kaz Kylheku

unread,
Nov 9, 2023, 12:18:31 AM11/9/23
to
Hoare gave us the concept of monitors and condition variables,
which deserves respect.

The original variant is semantically useful; the guarantees that it
provides can make it easier to reason about correctness.

It's something to know about as part of a well-rounded education
in concurrent programming.

Chris M. Thomasson

unread,
Nov 9, 2023, 12:19:05 AM11/9/23
to
Humm... Sounds good. However, I need to try it out. Also, if you don't
mind I might actually model it in relacy.

Chris M. Thomasson

unread,
Nov 9, 2023, 12:19:44 AM11/9/23
to
On 11/8/2023 9:17 PM, Kaz Kylheku wrote:
> On 2023-11-09, Bonita Montero <Bonita....@gmail.com> 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.
>
> Hoare gave us the concept of monitors and condition variables,
> which deserves respect.
>
> The original variant is semantically useful; the guarantees that it
> provides can make it easier to reason about correctness.
>
> It's something to know about as part of a well-rounded education
> in concurrent programming.
>

I concur with that assessment.

Bonita Montero

unread,
Nov 9, 2023, 12:20:58 AM11/9/23
to
Am 09.11.2023 um 06:17 schrieb Kaz Kylheku:

> Hoare gave us the concept of monitors and condition variables,
> which deserves respect.

Hoare monitors are less efficient since they give up ownership
of the mutex part while notifying. That are two kernel calls
which could be prevented.

Chris M. Thomasson

unread,
Nov 9, 2023, 12:21:17 AM11/9/23
to
I wonder if Bontia is pushing things to a borderline. Heck, he/she is
almost making me want to work on it!!!

https://youtu.be/rSaC-YbSDpo

Chris M. Thomasson

unread,
Nov 9, 2023, 12:21:49 AM11/9/23
to
On 11/8/2023 9:19 PM, Bonita Montero wrote:
Avoiding Kernel calls is great.com.

Bonita Montero

unread,
Nov 9, 2023, 12:23:09 AM11/9/23
to
Am 09.11.2023 um 06:17 schrieb Chris M. Thomasson:

> Humm... Sounds good. However, I need to try it out. Also, if you don't
> mind I might actually model it in relacy.

I've witten my own unit test. The Win32 code worked immediately,
but the SysV-code didn't work immediately also because I forgot
to have IPC_NOWAIT while releasing a semaphore. Why is there a
way to wait for the release of a mutex to be accepted by another
thread ? Who comes up with that ?

Chris M. Thomasson

unread,
Nov 9, 2023, 12:28:42 AM11/9/23
to
Well, invvvho, it might be prudent of me to model it in Relacy. The act
of me porting your work over into its logic base is going to get me
really intimate with your code.

Bonita Montero

unread,
Nov 9, 2023, 12:30:33 AM11/9/23
to
Am 09.11.2023 um 06:27 schrieb Chris M. Thomasson:

> Well, invvvho, it might be prudent of me to model it in Relacy.
> The act of me porting your work over into its logic base is
> going to get me really intimate with your code.

Just reading the code is easier.

Chris M. Thomasson

unread,
Nov 9, 2023, 12:31:12 AM11/9/23
to
Can you feel me? lol. ;^)

I have to work on some of my fractal IFS right now, but, I will try to
port your work over to Relacy. Fwiw, here is a taste of some work I ave
to do right now:

https://paulbourke.net/fractals/multijulia

I am trying to create a nice volumetric form of it.

Chris M. Thomasson

unread,
Nov 9, 2023, 12:31:51 AM11/9/23
to
Yup. Porting your code to Relacy is going to force me to read every damn
line of your code. So, touche?

Chris M. Thomasson

unread,
Nov 9, 2023, 12:33:32 AM11/9/23
to

Bonita Montero

unread,
Nov 9, 2023, 12:34:57 AM11/9/23
to
Am 09.11.2023 um 06:31 schrieb Chris M. Thomasson:

> Yup. Porting your code to Relacy is going to force me to read every damn
> line of your code. So, touche?

Reading the code doesn't hurt since the functions are short.

Chris M. Thomasson

unread,
Nov 9, 2023, 12:36:35 AM11/9/23
to
Wait morphing is a way that shows how interconnected a mutex actually is
with a condition variable...

Chris M. Thomasson

unread,
Nov 9, 2023, 12:37:28 AM11/9/23
to
Porting your code to Relacy makes me read every damn line. You masking
is interesting.

Bonita Montero

unread,
Nov 9, 2023, 12:40:28 AM11/9/23
to
Am 09.11.2023 um 06:35 schrieb Chris M. Thomasson:

> Wait morphing is a way that shows how interconnected a mutex actually is
> with a condition variable...

As you can derive from what I said I know what wait morphing is.
I think wait morphing could be prevented unter systems supporting
SysV seamphores by allocating a semaphore set of two semaphores
for each mutex and leaving the second unused until you have a
condition variable.

Bonita Montero

unread,
Nov 9, 2023, 12:41:33 AM11/9/23
to
Am 09.11.2023 um 06:36 schrieb Chris M. Thomasson:

> Porting your code to Relacy makes me read every damn line.
> You masking is interesting.

My code is understandable if you know MT-primitives
and SysV-IPC. There's nothing "damn" with my code.

Chris M. Thomasson

unread,
Nov 9, 2023, 12:41:34 AM11/9/23
to
Can you move waitsets over from mutex to futex and vise versa?

Chris M. Thomasson

unread,
Nov 9, 2023, 12:42:41 AM11/9/23
to
This is in the kernel...

Chris M. Thomasson

unread,
Nov 9, 2023, 12:42:53 AM11/9/23
to
Oh well, like I said, you seem to be a fun person to work with...

Bonita Montero

unread,
Nov 9, 2023, 12:43:05 AM11/9/23
to
Am 09.11.2023 um 06:40 schrieb Chris M. Thomasson:

> Can you move waitsets over from mutex to futex and vise versa?

glibc doesn't do this either.

Chris M. Thomasson

unread,
Nov 9, 2023, 12:44:43 AM11/9/23
to
Wait morphing is not in the realm of the compiler. It's in the kernel.

Chris M. Thomasson

unread,
Nov 9, 2023, 12:45:24 AM11/9/23
to
OOPS! I thought you were talking about gcc. Sorry Bonita!

Bonita Montero

unread,
Nov 9, 2023, 12:46:14 AM11/9/23