Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming.threads > #6326
| 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 | 2021-02-19 15:32 -0800 |
| Organization | Aioe.org NNTP Server |
| 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> |
Cross-posted to 2 groups.
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
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