Re: [boost] wait-free fast-pathed, bounded-time, 100% starvation-free rw-mutex...

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 
news:87fxbh1ccf.fsf_at_dell.justsoftwaresolutions.co.uk...
> "Chris M. Thomasson" <cristom_at_[hidden]> writes:
>
>> I was wondering if the following invention of mine might be of use to 
>> Boost:
>>
>> http://software.intel.com/en-us/forums/intel-threading-building-blocks/topic/65822
>> (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?

http://www.threadingbuildingblocks.org/contribution.php

> 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.

Yes.

> 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.

Absolutely!

:^)

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)
          {
              if (InterlockedExchangeAdd(&m_rdwake,
                      LONG_MAX - count) + LONG_MAX - count)
              {

                  if (WaitForSingleObject(m_wrwset,
                          INFINITE) != WAIT_OBJECT_0)
                  {
                      RWMUTEX_WIN_UNEXPECTED();
                  }
              }
          }

          return true;
      }

      return false;
  }
_________________________________________________________________________

As for `try_rdlock()', humm, that could look like (modulo typos):
_________________________________________________________________________
  bool fair_rwmutex::try_lock_shared() throw()
  {
      LONG cmp1, cmp2 = m_count;

      do
      {
          cmp1 = cmp2;

          if (cmp1 < 1)
          {
              return false;
          }

          cmp2 = InterlockedCompareExchange(&m_count, cmp1 - 1, cmp1);

      } while (cmp1 != cmp2);

      if ((cmp1 - 1) < 0)
      {
          if (WaitForSingleObject(m_rdwset, INFINITE) != WAIT_OBJECT_0)
          {
              RWMUTEX_WIN_UNEXPECTED();
          }
      }

      return true;
  }
_________________________________________________________________________

> 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
> type.

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 
`SCHED_OTHER'.