Eventcount with timeout

50 views
Skip to first unread message

Artur Brugeman

unread,
Dec 24, 2018, 12:30:03 AM12/24/18
to Scalable Synchronization Algorithms
Hi Dmitry,

I want to use your eventcount (took the source from intel forum). 

Currently I was using semaphores, which allowed me to set waiting timeout. 

Questions:
1. Is the source from intel forum 'the latest and stable'? You had a pretty long discussion there and I'm not sure the posted sources incorporated all the fixes.
2. Can eventcount support waiting timeouts? Can I just add 'timeout' param to prepare_wait and commit_wait and call 'sema.timedwait' instead of 'wait'? In fact I did just that and now I get segfaults here and there, so not sure it's the way to go.

Can you please share your thoughts on this?

Thanks a lot!
--
Artur   

Chris M. Thomasson

unread,
Dec 27, 2018, 6:32:04 PM12/27/18
to Scalable Synchronization Algorithms
Fwiw, a timed wait on an eventcount works as easily as spinning on it wrt not waiting on a kernel waitset at all. The predicate is the user algorithm itself. So, imagine if the waits never actually block, but spin around. Yet, everything still works. Fwiw, the following code, that should compile with Relacy, is the most simplistic eventcount I can imagine:
_________________________________
// Simple Event Count
// For Academic and Experimental things... 
// Beginner, Moderate?
// In Good Ol' Relacy! Nice as always.
//_______________________________________________


//#define RL_DEBUGBREAK_ON_ASSERT
//#define RL_MSVC_OUTPUT
//#define RL_FORCE_SEQ_CST
//#define RL_GC


#include <relacy/relacy_std.hpp>
#include <iostream>


// Simple macro based redirection of the verbose  std membars.
#define CT_MB_ACQ std::memory_order_acquire
#define CT_MB_REL std::memory_order_release
#define CT_MB_RLX std::memory_order_relaxed
#define CT_MB_ACQ_REL std::memory_order_acq_rel
#define CT_MB_SEQ_CST std::memory_order_seq_cst
#define CT_MB(mp_0) std::atomic_thread_fence(mp_0)


// Some global vars directing the show...
#define WORKERS 5
#define THREADS (WORKERS)


// old school
struct ct_ecount
{
    std::mutex m_mutex;
    std::condition_variable m_cond;
    std::atomic<unsigned int> m_waitbit;

    ct_ecount() : m_waitbit(0) {}

    void broadcast()
    {
        CT_MB(CT_MB_SEQ_CST);

        unsigned int waitbit = m_waitbit.load(CT_MB_RLX);
        if (! waitbit) return;

        m_mutex.lock($);
        m_waitbit.store(0, CT_MB_RLX);
        m_cond.notify_all($);
        m_mutex.unlock($);
    }


    void wait_begin()
    {
        m_mutex.lock($);
        m_waitbit.store(1, CT_MB_RLX);
        CT_MB(CT_MB_SEQ_CST);
    }


    void wait_cancel()
    {
        m_mutex.unlock($);
    }


    void wait_commit()
    {
        m_cond.wait(m_mutex, $);
        m_mutex.unlock($);
    }
};


// Relacy Multex Test...
struct ct_ecount_test
    : rl::test_suite<ct_ecount_test, THREADS>
{
    std::atomic<unsigned int> m_signal;
    ct_ecount g_ecount;

    ct_ecount_test() : m_signal(0) {}

    void thread(unsigned int tidx)
    {
        if (tidx < 2)
        {
            if (m_signal.fetch_add(1, CT_MB_RLX) == 1)
            {
                g_ecount.broadcast();
            }
        }

        else
        {
            unsigned int signal = 0;

            while ((signal = m_signal.load(CT_MB_RLX)) != 2)
            {
                g_ecount.wait_begin();
                signal = m_signal.load(CT_MB_RLX);

                if (signal == 2)
                {
                    g_ecount.wait_cancel();
                    break;
                }

                g_ecount.wait_commit();
            }
        }
    }
};



// Test away... Or fly? Humm...
int main()
{
    {
        rl::test_params p;

        p.iteration_count = 5000000;
        //p.execution_depth_limit = 33333;
        //p.search_type = rl::sched_bound;
        //p.search_type = rl::fair_full_search_scheduler_type;
        //p.search_type = rl::fair_context_bound_scheduler_type;

        rl::simulate<ct_ecount_test>(p);
    }

    return 0;
}
_________________________________

think if g_ecount.wait_commit(); was timed... It would still work as is. So, yes an eventcount can easily handle timed waits.

Artur Brugeman

unread,
Dec 28, 2018, 12:55:57 AM12/28/18
to Scalable Synchronization Algorithms
Hi Chris,

Thank you for your thoughts on this, my thinking was in line with yours and that's why I tried to add timed waiting in Dmitry's eventcount. I guess I need to spend some more time there and figure it out. 

Cheers,
Artur


On Friday, December 28, 2018 at 4:32:04 AM UTC+5, Chris M. Thomasson wrote:
On Sunday, December 23, 2018 at 9:30:03 PM UTC-8, Artur Brugeman wrote:
Hi Dmitry,

I want to use your eventcount (took the source from intel forum). 

Currently I was using semaphores, which allowed me to set waiting timeout. 

Questions:
1. Is the source from intel forum 'the latest and stable'? You had a pretty long discussion there and I'm not sure the posted sources incorporated all the fixes.
2. Can eventcount support waiting timeouts? Can I just add 'timeout' param to prepare_wait and commit_wait and call 'sema.timedwait' instead of 'wait'? In fact I did just that and now I get segfaults here and there, so not sure it's the way to go.

Can you please share your thoughts on this?

Thanks a lot!


Fwiw, a timed wait on an eventcount works as easily as spinning on it wrt not waiting on a kernel waitset at all. The predicate is the user algorithm itself. So, imagine if the waits never actually block, but spin around. Yet, everything still works. Fwiw, the following code, that should compile with Relacy, is the most simplistic eventcount I can imagine:
_________________________________
...............

Chris M. Thomasson

unread,
Dec 28, 2018, 3:25:26 AM12/28/18
to Scalable Synchronization Algorithms


On Thursday, December 27, 2018 at 9:55:57 PM UTC-8, Artur Brugeman wrote:
Hi Chris,

Thank you for your thoughts on this, my thinking was in line with yours and that's why I tried to add timed waiting in Dmitry's eventcount. I guess I need to spend some more time there and figure it out. 

Iirc, Dmitrys algo used some per-thread waitsets for an eventcount algo. Cannot remember right now if it is the same one you are referring to.

Fwiw, one can even spin on the lock for wait_begin, wrt something like:
________________
    bool wait_begin_try()
    {
        if (! m_mutex.try_lock($)) return false;
        m_waitbit.store(1, CT_MB_RLX);
        CT_MB(CT_MB_SEQ_CST);
        return true;
    }
________________

The predicate loop can look like:
________________
unsigned int signal = 0;

while ((signal = m_signal.load(CT_MB_RLX)) != 2)
{
    if (! g_ecount.wait_begin_try())
    {
        rl::yield(1, $);
        continue;
    }

    signal = m_signal.load(CT_MB_RLX);

    if (signal == 2)
    {
        g_ecount.wait_cancel();
        break;
    }

    g_ecount.wait_commit();
}
________________

It can even be adaptive in nature where one can fail the try_lock a couple of times, then just lock the sucker!

;^)
Reply all
Reply to author
Forward
0 new messages