Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #6326

Re: More precision about my new inventions of scalable algorithms..

Path csiph.com!aioe.org!NBiuIU74OKL7NpIOsbuNjQ.user.gioia.aioe.org.POSTED!not-for-mail
From "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Newsgroups comp.programming.threads, comp.lang.c++
Subject Re: More precision about my new inventions of scalable algorithms..
Date Fri, 19 Feb 2021 15:32:20 -0800
Organization Aioe.org NNTP Server
Lines 190
Message-ID <s0phq4$174o$1@gioia.aioe.org> (permalink)
References <a5d9ec4c-5dba-47a0-ba1b-5fa348a565b9n@googlegroups.com> <s0pe09$teu$1@dont-email.me> <s0pf7d$9le$1@gioia.aioe.org> <s0pg0a$d4k$1@dont-email.me>
NNTP-Posting-Host NBiuIU74OKL7NpIOsbuNjQ.user.gioia.aioe.org
Mime-Version 1.0
Content-Type text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding 7bit
X-Complaints-To abuse@aioe.org
User-Agent Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.7.1
X-Notice Filtered by postfilter v. 0.9.2
Content-Language en-US
Xref csiph.com comp.programming.threads:6326 comp.lang.c++:78478

Cross-posted to 2 groups.

Show key headers only | View raw

On 2/19/2021 3:01 PM, Bonita Montero wrote:
>>>> My below powerful inventions of LW_Fast_RWLockX and Fast_RWLockX 
>>>> that are two powerful scalable RWLocks that are FIFO fair
> 
>>> RW-locks are never fair.
> 
>> There are implementations that can be starvation free.
> 
> No, impossible. Readers can hold the lock as long as they
> want and starve out writers. And writers could do the same.

Check this out:

https://vorbrodt.blog/2019/02/14/read-write-mutex/

On older rwmutex I invented. Its simple, and is starvation free wrt 
reads and writes. Here is a simple Relacy test unit:

__________________________________
// Chris M. Thomassons RW Mutex


//#define RL_DEBUGBREAK_ON_ASSERT
//#define RL_MSVC_OUTPUT
//#define RL_FORCE_SEQ_CST
#include <relacy/relacy_std.hpp>
#include <cstdio>
#include <cstddef>




#if ! defined (NDEBUG)
#   define DBG_PRINTF(e) std::printf e
#else
#   define DBG_PRINTF(e) ((void)0)
#endif



struct semaphore
{
     HANDLE m_waitset;

     semaphore(LONG count)
     {
         m_waitset = CreateSemaphore(nullptr, count, LONG_MAX, nullptr);
     }

     ~semaphore()
     {
         CloseHandle(m_waitset);
     }

     void post(LONG count = 1)
     {
         ReleaseSemaphore(m_waitset, count, nullptr);
     }

     void wait()
     {
         WaitForSingleObject(m_waitset, INFINITE);
     }
};


class ct_rw_fast_mutex
{
public:
     ct_rw_fast_mutex()
         : m_wrstate(1), m_count(INT_MAX), m_rdwake(0),
         m_rdwset(0), m_wrwset(0), m_wrmtx(0) {}

     void read_lock()
     {
         if (m_count.fetch_add(-1, std::memory_order_acquire) < 1)
             m_rdwset.wait();
     }

     void read_unlock()
     {
         if (m_count.fetch_add(1, std::memory_order_release) < 0)
             if (m_rdwake.fetch_add(-1, std::memory_order_acq_rel) == 1)
                 m_wrwset.post();
     }

     void write_lock()
     {
         if (m_wrstate.fetch_sub(1, std::memory_order_acquire) < 1)
             m_wrmtx.wait();
         int count = m_count.fetch_add(-INT_MAX, std::memory_order_acquire);
         if (count < INT_MAX)
         {
             int rdwake = m_rdwake.fetch_add(INT_MAX - count, 
std::memory_order_acquire);
             if (rdwake + INT_MAX - count)
                 m_wrwset.wait();
         }
     }

     void write_unlock()
     {
         int count = m_count.fetch_add(INT_MAX, std::memory_order_release);
         if (count < 0)
             m_rdwset.post(-count);
         if (m_wrstate.fetch_add(1, std::memory_order_release) < 0)
             m_wrmtx.post();
     }

private:
     std::atomic<int> m_wrstate;
     std::atomic<int> m_count;
     std::atomic<int> m_rdwake;

     semaphore m_rdwset;
     semaphore m_wrwset;
     semaphore m_wrmtx;
};


#define ITERS 16
#define WRITERS 3
#define READERS 5
#define THREADS (WRITERS + READERS)


struct proxy_test
     : rl::test_suite<proxy_test, THREADS>
{
     ct_rw_fast_mutex m_rwmutex;
     VAR_T(int) m_shared;

     proxy_test() : m_shared(0) {}

     ~proxy_test() { RL_ASSERT(!VAR(m_shared)); }

     void thread(unsigned int tidx)
     {
         if (tidx < READERS)
         {
             // readers

             for (unsigned long i = 0; i < ITERS; ++i)
             {
                 m_rwmutex.read_lock();
                 int shared = VAR(m_shared);
                 m_rwmutex.read_unlock();

                 RL_ASSERT(shared > -1);
             }

         }

         else
         {
             // writers
             for (unsigned long i = 0; i < ITERS; ++i)
             {
                 m_rwmutex.write_lock();
                 ++VAR(m_shared);
                 m_rwmutex.write_unlock();

                 m_rwmutex.write_lock();
                 --VAR(m_shared);
                 m_rwmutex.write_unlock();
             }
         }
     }
};


int main()
{
     {
         rl::test_params p;

         p.iteration_count = 10000000;
         p.execution_depth_limit = 10000;
         //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<proxy_test>(p);
     }

     return 0;
}
__________________________________


Can you run it?

Back to comp.programming.threads | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

More precision about my new inventions of scalable algorithms.. Amine Moulay Ramdane <aminer68@gmail.com> - 2021-02-18 11:07 -0800
  Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-19 23:27 +0100
    Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-19 14:48 -0800
      Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-20 00:01 +0100
        Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-19 15:17 -0800
          Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-20 08:50 +0100
            Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-20 12:46 -0800
              Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-20 12:52 -0800
              Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-21 17:16 +0100
                Re: More precision about my new inventions of scalable algorithms.. Richard Damon <Richard@Damon-Family.org> - 2021-02-21 13:15 -0500
                Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-21 19:58 +0100
                Re: More precision about my new inventions of scalable algorithms.. Richard Damon <Richard@Damon-Family.org> - 2021-02-21 15:58 -0500
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-21 14:35 -0800
                Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-22 06:54 +0100
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-21 22:00 -0800
                Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-22 07:40 +0100
                Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-22 09:20 +0100
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-22 14:54 -0800
                Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-23 08:38 +0100
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-23 00:25 -0800
                Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-23 20:17 +0100
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-23 11:29 -0800
                Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-24 18:20 +0100
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-25 01:49 -0800
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-23 14:13 -0800
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-23 14:14 -0800
                Re: More precision about my new inventions of scalable algorithms.. Richard Damon <Richard@Damon-Family.org> - 2021-02-23 16:51 -0500
                Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-24 18:22 +0100
                Re: More precision about my new inventions of scalable algorithms.. Richard Damon <Richard@Damon-Family.org> - 2021-02-24 13:28 -0500
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-24 17:16 -0800
                Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-25 07:08 +0100
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-24 23:39 -0800
                Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-25 09:49 +0100
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-25 01:05 -0800
                Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-25 11:43 +0100
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-25 03:09 -0800
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-25 03:10 -0800
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-24 23:43 -0800
                Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-22 06:52 +0100
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-21 22:10 -0800
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-21 21:47 -0800
                Re: More precision about my new inventions of scalable algorithms.. Bonita Montero <Bonita.Montero@gmail.com> - 2021-02-22 06:51 +0100
                Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-21 22:01 -0800
        Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-19 15:32 -0800
          Re: More precision about my new inventions of scalable algorithms.. "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-02-19 15:37 -0800
      Re: More precision about my new inventions of scalable algorithms.. Amine Moulay Ramdane <aminer68@gmail.com> - 2021-02-19 15:14 -0800

csiph-web