|
|
Boost : |
From: Anthony Williams (anthony_w.geo_at_[hidden])
Date: 2006-10-27 07:41:54
"Peter Dimov" <pdimov_at_[hidden]> writes:
> I finally managed to match the "naive" implementation with a "fancy"
> semaphore-based scheme. The basic algorithm is that each unlock unblocks one
> waiting thread; the twist is that if the thread that wakes up is a reader,
> it then unblocks all waiters. When a writer wakes up, it doesn't unblock
> anyone, since it is on its way to exclusive access anyway. I haven't
> reviewed the code for subtle correctness issues, though; no time for that
> now. :-/
Sorry Peter, but this deadlocks in my tests.
I have a new algorithm, posted below, that wakes all readers and one writer
when either the last reader or the only writer releases the lock.
I can't seem to get consistency in my tests, even when nothing else is
running. However, it seems like my algorithm has a lower max wait time, but
higher average wait time compared to yours/Chris' earlier algorithms. It
performs better than my earlier attempts on all counts.
I'll see if I can cut down that average.
Anthony
--
Anthony Williams
Software Developer
Just Software Solutions Ltd
http://www.justsoftwaresolutions.co.uk
#ifndef BOOST_THREAD_WIN32_READ_WRITE_MUTEX_HPP
#define BOOST_THREAD_WIN32_READ_WRITE_MUTEX_HPP
#include <boost/assert.hpp>
#include <boost/detail/interlocked.hpp>
#include <boost/thread/win32/thread_primitives.hpp>
#include <boost/thread/win32/interlocked_read.hpp>
#include <boost/static_assert.hpp>
#include <limits.h>
namespace boost
{
class read_write_mutex
{
private:
struct state_data
{
unsigned shared_count:10;
unsigned shared_waiting:10;
unsigned exclusive:1;
unsigned exclusive_waiting:10;
unsigned exclusive_waiting_blocked:1;
friend bool operator==(state_data const& lhs,state_data const& rhs)
{
return *reinterpret_cast<unsigned const*>(&lhs)==*reinterpret_cast<unsigned const*>(&rhs);
}
};
template<typename T>
T interlocked_compare_exchange(T* target,T new_value,T comparand)
{
BOOST_STATIC_ASSERT(sizeof(T)==sizeof(long));
long const res=BOOST_INTERLOCKED_COMPARE_EXCHANGE(reinterpret_cast<long*>(target),
*reinterpret_cast<long*>(&new_value),
*reinterpret_cast<long*>(&comparand));
return *reinterpret_cast<T const*>(&res);
}
state_data state;
void* unlock_event;
void* exclusive_event;
void release_waiters(state_data old_state)
{
if(old_state.exclusive_waiting)
{
bool const success=::boost::detail::ReleaseSemaphore(exclusive_event,1,NULL)!=0;
BOOST_ASSERT(success);
}
if(old_state.shared_waiting || old_state.exclusive_waiting)
{
bool const success=::boost::detail::ReleaseSemaphore(unlock_event,old_state.shared_waiting + old_state.exclusive_waiting,NULL)!=0;
BOOST_ASSERT(success);
}
}
public:
read_write_mutex():
unlock_event(::boost::detail::CreateSemaphoreA(NULL,0,LONG_MAX,NULL)),
exclusive_event(::boost::detail::CreateSemaphoreA(NULL,0,LONG_MAX,NULL))
{
state_data state_={0};
state=state_;
}
~read_write_mutex()
{
::boost::detail::CloseHandle(unlock_event);
::boost::detail::CloseHandle(exclusive_event);
}
void lock_shareable()
{
while(true)
{
state_data old_state=state;
do
{
state_data new_state=old_state;
if(new_state.exclusive || new_state.exclusive_waiting_blocked)
{
++new_state.shared_waiting;
}
else
{
++new_state.shared_count;
}
state_data const current_state=interlocked_compare_exchange(&state,new_state,old_state);
if(current_state==old_state)
{
break;
}
old_state=current_state;
}
while(true);
if(!(old_state.exclusive| old_state.exclusive_waiting_blocked))
{
return;
}
unsigned long const res=::boost::detail::WaitForSingleObject(unlock_event,BOOST_INFINITE);
BOOST_ASSERT(res==0);
}
}
void unlock_shareable()
{
state_data old_state=state;
do
{
state_data new_state=old_state;
bool const last_reader=!--new_state.shared_count;
if(last_reader)
{
if(new_state.exclusive_waiting)
{
--new_state.exclusive_waiting;
new_state.exclusive_waiting_blocked=false;
}
new_state.shared_waiting=0;
}
state_data const current_state=interlocked_compare_exchange(&state,new_state,old_state);
if(current_state==old_state)
{
if(last_reader)
{
release_waiters(old_state);
}
break;
}
old_state=current_state;
}
while(true);
}
void lock()
{
while(true)
{
state_data old_state=state;
do
{
state_data new_state=old_state;
if(new_state.shared_count || new_state.exclusive)
{
++new_state.exclusive_waiting;
new_state.exclusive_waiting_blocked=true;
}
else
{
new_state.exclusive=true;
}
state_data const current_state=interlocked_compare_exchange(&state,new_state,old_state);
if(current_state==old_state)
{
break;
}
old_state=current_state;
}
while(true);
if(!old_state.shared_count && !old_state.exclusive)
{
break;
}
void* const handles[2]={exclusive_event,unlock_event};
bool const success2=::boost::detail::WaitForMultipleObjects(2,handles,true,BOOST_INFINITE)<2;
BOOST_ASSERT(success2);
}
}
void unlock()
{
state_data old_state=state;
do
{
state_data new_state=old_state;
new_state.exclusive=false;
if(new_state.exclusive_waiting)
{
--new_state.exclusive_waiting;
new_state.exclusive_waiting_blocked=false;
}
new_state.shared_waiting=0;
state_data const current_state=interlocked_compare_exchange(&state,new_state,old_state);
if(current_state==old_state)
{
break;
}
old_state=current_state;
}
while(true);
release_waiters(old_state);
}
class scoped_read_lock
{
read_write_mutex& m;
public:
scoped_read_lock(read_write_mutex& m_):
m(m_)
{
m.lock_shareable();
}
~scoped_read_lock()
{
m.unlock_shareable();
}
};
class scoped_write_lock
{
read_write_mutex& m;
bool locked;
public:
scoped_write_lock(read_write_mutex& m_):
m(m_),locked(false)
{
lock();
}
void lock()
{
m.lock();
locked=true;
}
void unlock()
{
m.unlock();
locked=false;
}
~scoped_write_lock()
{
if(locked)
{
unlock();
}
}
};
};
}
#endif
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk