Re: C++1x: lock-free algos and blocking
"Dmitriy Vyukov" <dvyukov@gmail.com> wrote in message
news:fcbdaa78-a0f5-4ffc-99c6-4331e4575aee@v25g2000yqk.googlegroups.com...
C++1x provides a complete toolset for lock-based programming: mutex
for ensuring consistency and condition variable for blocking/
signaling.
However, as for lock-free (non-blocking) programming C++1x provides
only atomics for ensuring consistency. And what about thread blocking/
signaling? Condition variables are of no help here, because they
require the state to be protected by a mutex. Yes, some lock-free
algorithms do not require blocking (for example, hash map). But things
like producer-consumer queues, work-stealing deques, etc, do require
some primitives for thread blocking/signaling.
I would like to hear from some people close to the committee on this.
How it's intended I must handle this?
Yes, I can build a semaphore from mutex+condvar+counter. And then
build blocking/signaling logic on top of the semaphore. However IMHO
it's (1) a kind of suboptimal from performance point of view and (2)
everybody will have to build it's own semaphore.
For example, Java provides thread park/unpark primitives for that
purpose, which is a kind of semaphore associated with every thread
with sticky signals and a maximum value of 1. IMHO, it's not the way
to go for C++1x, because one will have to pass thread objects
everywhere.
Thank you.
Humm. Well, the "simplest" algorithm I know of is basically equal to the
original eventcount algorithm I posted here, except it uses different
waitbit value and increments the counter by an even number:
<pseudo-code typed in newsreader; please forgive any typos>
___________________________________________________________________
class eventcount
{
public:
typedef unsigned long key_type;
private:
mutable std::atomic<key_type> m_count;
std::mutex m_mutex;
std::condition_variable m_cond;
private:
void prv_signal(key_type key)
{
if (key & 1)
{
m_mutex.lock($);
while (! m_count($).compare_exchange_weak(
key,
(key + 2) & ~1,
std::memory_order_seq_cst));
m_mutex.unlock($);
m_cond.notify_all($);
}
}
public:
eventcount()
: m_count(0)
{
}
public:
key_type get() const
{
return m_count($).fetch_or(1, std::memory_order_acquire);
}
void signal()
{
prv_signal(m_count($).fetch_add(0, std::memory_order_seq_cst));
}
void signal_relaxed()
{
prv_signal(m_count($).load(std::memory_order_relaxed));
}
void wait(key_type cmp)
{
m_mutex.lock($);
key_type cur = m_count($).load(std::memory_order_seq_cst);
if ((cur & ~1) == (cmp & ~1))
{
m_cond.wait(m_mutex, $);
}
m_mutex.unlock($);
}
};
___________________________________________________________________
Should something like this be standardized? I am not so sure here simply
because one can rather easily use C++1x to create a 100% portable
implementation of an eventcount... Humm...