Subject: Re: [boost] wait-free fast-pathed, bounded-time, 100% starvation-free rw-mutex...
From: Chris M. Thomasson (cristom_at_[hidden])
Date: 2009-08-25 13:16:19
"Anthony Williams" <anthony.ajw_at_[hidden]> wrote in message
> "Chris M. Thomasson" <cristom_at_[hidden]> writes:
>> I was wondering if the following invention of mine might be of use to
>> (please __read_all__; thank you)
> It certainly looks interesting. The current boost::shared_mutex
> implementation is rather heavyweight due to timed lock support.
Yes, adding support for timeouts can definitely complicate things.
> I see that you've submitted it to TBB.
I have not actually made a formal proposal yet.
> Are you still in a position to
> submit to Boost, or do you have to assign copyright to Intel?
> In terms of scheduling I see that if the mutex is locked for writing
> then waiting readers will take precedence over waiting writers, whilst
> when it is locked for reading then a waiting writer will block further
> readers, and the writer will take precedence.
> This puts the mutex in control of the scheduling, and does not allow the
> OS to select which thread to wake based on priorities. For example, if a
> writer holds the lock, and one of the waiting readers is low priority
> then it is given the lock when the writer unlocks, even if there is a
> high priority writer waiting. The high priority writer is then blocked
> until the low priority reader has completed its task.
You are correct wrt read-to-write contention. Write-to-write contention is
not bound to `SCHED_OTHER'. I could not really figure out a way to achieve
all of the the claimed properties (e.g., 100% starvation-free, bounded-time)
without doing the interleaving writes along with batches of reads. This does
not prove anything, but I know that it can outperform several native rwmutex
implementations (e.g., OpenSolaris, NPTL)...
> Whether or not that's a good thing is open for discussion.
Contention will not be good for real-time, while the fast-paths are
wait-free which is perfect for real-time. Funny. Perhaps it could be useful
to Boost with explicit documentation and/or even something in it's class
name (e.g., `fair_rwmutex')?
> I also note that there are no "try_wrlock()" or "try_rdlock()" functions.
I can do the `try_wrlock()' with something like (modulo typos):
bool fair_rwmutex::try_lock() throw()
assert(m_count < LONG_MAX);
if (InterlockedCompareExchange(&m_mtx, 0, 1) == 1)
assert(m_count > -1);
LONG count = InterlockedExchangeAdd(&m_count, -LONG_MAX);
if (count < LONG_MAX)
LONG_MAX - count) + LONG_MAX - count)
INFINITE) != WAIT_OBJECT_0)
As for `try_rdlock()', humm, that could look like (modulo typos):
bool fair_rwmutex::try_lock_shared() throw()
LONG cmp1, cmp2 = m_count;
cmp1 = cmp2;
if (cmp1 < 1)
cmp2 = InterlockedCompareExchange(&m_count, cmp1 - 1, cmp1);
} while (cmp1 != cmp2);
if ((cmp1 - 1) < 0)
if (WaitForSingleObject(m_rdwset, INFINITE) != WAIT_OBJECT_0)
> For integration with boost, it would be good if the write-lock member
> functions could be called "lock()" and "unlock()", whilst the read-lock
> member functions are called "lock_shared()" and "unlock_shared()". This
> would allow the existing RAII classes to be used with this new rwmutex
Okay. I will add the try lock functions and change the function names, and
re-name the class to `fair_rwmutex' to attempt to get across that it's
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk