Asymmetric rw_mutex with atomic-free fast-path for readers

[Dmitriy V'jukov]

[Cross-post from USENET comp.programming.threads]
http://groups.google.ru/group/comp.programming.threads/browse_frm/thread/8c6c19698964d1f6

rw_mutex with costless read_lock()/read_unlock()
All overhead is moved to writer side (therefore called 'asymmetric')

Based on my previous ideas:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/1348064e4838e871
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/b7d3b8c08f9ca3c6

And uses this epoch auto detection algorithm:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/f8f78ff07df6df5f

Now asymmetric rw_mutex is free of any caveats like possible
deadlocks. And not use any OS/hardware specific features.

Implementation:

int const max_reader_count = 1024;

// unique thread index (0 .. (max_reader_count - 1))
__declspec(thread) int current_thread_index;

class arw_mutex_t
{
private:
CRITICAL_SECTION cs;
// private flag for every reader
bool volatile reader_inside [max_reader_count];
bool volatile writer_pending;

public:
arw_mutex_t()
{
InitializeCriticalSection(&cs);
writer_pending = false;
for (int i = 0; i != max_reader_count; ++i)
reader_inside[i] = false;
}

void reader_lock()
{
reader_inside[current_thread_index] = true;
// no explicit #StoreLoad
// but it will be implicitly executed
// by sys_synch() in writer_lock()
if (writer_pending)
{
// if writer is pending
// than signal that we see it
// and wait for writer to complete
reader_inside[current_thread_index] = false;
EnterCriticalSection(&cs);
reader_inside[current_thread_index] = true;
LeaveCriticalSection(&cs);
}
// need to order user code inside critical section
// acquire compiler barrier
_ReadWriteBarrier();
}

void reader_unlock()
{
// need to order user code inside critical section
// release compiler barrier
_ReadWriteBarrier();
reader_inside[current_thread_index] = false;
}

void writer_lock()
{
EnterCriticalSection(&cs);
// set that we are waiting
writer_pending = true;
// all magic is here:
// implicitly execute full memory barrier
// on all other processors
sys_synch();
// here we are sure that:
// (1) writer will see (reader_inside[i] == true)
// or (2) reader will see (writer_pending == true)
// so no race conditions
for (int i = 0; i != max_reader_count; ++i)
{
// wait for all readers to complete
while (reader_inside[i])
SwitchToThread();
}
}

void writer_unlock()
{
writer_pending = false;
LeaveCriticalSection(&cs);
}

};

Dmitriy V'jukov

[Dmitriy V'jukov]

On Feb 3, 5:36 am, "Dmitriy V'jukov" <dvyu...@gmail.com> wrote:

> And uses this epoch auto detection algorithm:http://groups.google.com/group/comp.programming.threads/browse_frm/th...

One can use any epoch detection logic with this algorithm:
FlushProcessWriteBuffers() (WinAPI), rcu_synchronize() (linux kernel),
signal
to every thread (unix), APC to every thread (WinAPI), polling of
thread/processor activity, IPI/x-calls, thread suspend/resume,
mprotect()/VirtualAlloc() etc.
Main point - epoch detection logic must be completely automatic and
must not
require any explicit participation from user threads. Otherwise this
can cause deadlocks.

Dmitriy V'jukov

[Dmitriy V'jukov]

On Feb 3, 5:36 am, "Dmitriy V'jukov" <dvyu...@gmail.com> wrote:

> rw_mutex with costless read_lock()/read_unlock()
> All overhead is moved to writer side (therefore called 'asymmetric')

It recalls David Dice's 'Asymmetric Dekker Synchronization':
http://home.comcast.net/~pjbishop/Dave/Asymmetric-Dekker-Synchronization.txt
I see David is subscribed to this group along with 10 other courageous
members :)

Imho, reader-writer mutex is somewhat more applicable that 'two-
thread' Dekker mutex...
Btw, I develop it independently from scratch :)

Dmitriy V'jukov