From: Anthony Williams (anthony_w.geo_at_[hidden])
Date: 2006-10-27 08:30:19
Anthony Williams <anthony_w.geo_at_[hidden]> writes:
> 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.
I was releasing the shared_semaphore too many times:
(waiting_reader+waiting_writers) instead of (waiting_reader+1), which meant
that there were extra spurious wake-ups waiting for readers if there were any
writers waiting.
Now the total time is comparable to the best of the rest, and the max wait is
lower.
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* semaphores[2];
void* &unlock_sem;
void* &exclusive_sem;
void release_waiters(state_data old_state)
{
if(old_state.exclusive_waiting)
{
bool const success=::boost::detail::ReleaseSemaphore(exclusive_sem,1,NULL)!=0;
BOOST_ASSERT(success);
}
if(old_state.shared_waiting || old_state.exclusive_waiting)
{
bool const success=::boost::detail::ReleaseSemaphore(unlock_sem,old_state.shared_waiting + (old_state.exclusive_waiting?1:0),NULL)!=0;
BOOST_ASSERT(success);
}
}
public:
read_write_mutex():
unlock_sem(semaphores[0]),
exclusive_sem(semaphores[1])
{
unlock_sem=::boost::detail::CreateSemaphoreA(NULL,0,LONG_MAX,NULL);
exclusive_sem=::boost::detail::CreateSemaphoreA(NULL,0,LONG_MAX,NULL);
state_data state_={0};
state=state_;
}
~read_write_mutex()
{
::boost::detail::CloseHandle(unlock_sem);
::boost::detail::CloseHandle(exclusive_sem);
}
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_sem,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;
}
bool const success2=::boost::detail::WaitForMultipleObjects(2,semaphores,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