Impact of ReadWriteLocks on 'lock-free' sections?

General JUCE discussion
1

If I use ReadWriteLocks, and generally take a Read lock only, in the absence of WriteLocks occurring, will the code perform like lock-free code?

Bruce

2

Well, not really… It still uses normal mutexes internally to do what it needs to, it just uses them temporarily to check whether a more long-time lock is required.

3

OK, thanks. Maybe that’s a feature request, if it’s possible.

Bruce

4

Well, no - it could never be “lock free”, because it can, by definition, lock!

5

Yeah, yeah. I mean lock-free like in that using just readlocks would not block.

Maybe something clever with Atomics or the like - readers could check for positive values or something (and increment), and a write lock sets to negative.

Not that exactly - the writelock may never get a chance in that scenario, but something cleverer, more Julesy.

Bruce

6

Here’s my Read/Write lock code. It has some limitations and you will need to fix it to work in your environment for the missing objects:

.h

// Multiple-reader, single writer, write preferenced
// partially recursive mutex with a wait-free fast path.
//
class ReadWriteMutex
{
public:
  ReadWriteMutex ();
  ~ReadWriteMutex ();

  // Recursive.
  void enter_read () const;
  void exit_read () const;

  // Recursive.
  // Cannot hold a read lock when acquiring a write lock.
  void enter_write () const;
  void exit_write () const;

private:
  CacheLine::Padded <Mutex> m_mutex;
  mutable CacheLine::Padded <Atomic::Counter> m_writes;
  mutable CacheLine::Padded <Atomic::Counter> m_readers;
};

.cpp

ReadWriteMutex::ReadWriteMutex ()
{
}

ReadWriteMutex::~ReadWriteMutex ()
{
}

void ReadWriteMutex::enter_read () const
{
  for (;;)
  {
    // attempt the lock optimistically
    // THIS IS NOT CACHE-FRIENDLY!
    m_readers->addref ();

    // is there a writer?
    // THIS IS NOT CACHE-FRIENDLY!
    if (m_writes->is_signaled ())
    {
      // a writer exists, give up the read lock
      m_readers->release ();

      // block until the writer is done
      {
        Mutex::ScopedLockType lock (*m_mutex);
      }

      // now try the loop again
    }
    else
    {
      break;
    }
  }
}

void ReadWriteMutex::exit_read () const
{
  m_readers->release ();
}

void ReadWriteMutex::enter_write () const
{
  // Optimistically acquire the write lock.
  m_writes->addref ();

  // Go for the mutex.
  // Another writer might block us here.
  m_mutex->enter ();

  // Only one competing writer will get here,
  // but we don't know who, so we have to drain
  // readers no matter what. New readers will be
  // blocked by the mutex.
  //
  // Crafted to sometimes avoid the Delay ctor.
  //
  if (m_readers->is_signaled ())
  {
    LockFree::Delay delay; 
    do
    {
      delay.spin ();
    }
    while (m_readers->is_signaled ());
  }
}

void ReadWriteMutex::exit_write () const
{
  // Releasing the mutex first and then decrementing the
  // writer count allows another waiting writer to atomically
  // acquire the lock, thus starving readers. This fulfills
  // the write-preferencing requirement.

  m_mutex->exit ();

  m_writes->release ();
}

You will need this code for the “Atomic Counter”:

namespace Atomic {

// Tracks the amount of usage of a particular resource.
// The object is considered signaled if there are one or more uses
class Counter
{
public:
  Counter (int initialValue = 0) : m_value (initialValue) { }

  // Increments the usage count.
  // Returns true if the counter was previously non-signaled.
  inline bool addref () { return (++m_value) == 1; }

  // Decrements the usage count.
  // Returns true if the counter became non-signaled.
  inline bool release () { return (--m_value) == 0; }

  // Decrements the usage count and asserts that it a final release.
  inline void finalRelease ()
  {
#ifndef NDEBUG
    const bool final = release();
    vfassert (final);
#else
    release ();
#endif
  }

  // Returns the signaled state of the counter.
  // The caller must synchronize the value.
  inline bool is_reset () const { return m_value.get() == 0; }
  inline bool is_signaled () const { return m_value.get() > 0; }

  // Caller must synchronize.
  inline void set (int value) { m_value.set (value); }

  // for diagnostics ONLY!
  inline int get () const { return m_value.get(); }

private:
  JUCE_NAMESPACE::Atomic <int> m_value;
};

}

You might have to fix these things:

  • Remove the cache line padding template and change -> to . in calls
  • Namespace issue with Atomic
  • Other modifications to get it to compile

These are the limitations:

  • The write lock is not recursive (but the read lock is)
  • You cannot ‘upgrade’ a read lock into a write lock
  • You cannot hold the read lock and also go for the write lock
  • There is no “timed wait”, all enter_*() functions wait indefinitely
  • The lock is not “fair” between readers and writers, readers can be starved

The benefit is a “mostly” lock-free implementation, which is also wait-free in the fast path. The class is designed for heavy read access and infrequent write access. Or more to the point, many threads performing simultaneous reads, with the occasional write from a single thread.

This lock is “write preferenced” which means that a waiting writer will block new readers. Furthermore, when a write lock is released and there are other waiting writers, they will always get priority over waiting readers.

If you have trouble getting this working let me know here and I will reply.

7

Or more Vinn-like :smiley: :smiley: :smiley:

I doubt Jules would approve of my implementation as it is not really suitable for a general purpose library like Juce (due to the limitations I impose).

However, Bruce, your intuition is correct that clever usage of atomic counters can achieve a mostly lock-free and wait-free read/write lock.

8

Cool, thanks! I’ll see what I can pull out.

What do the: // Caller must synchronize. comments mean? Do the locks shown do what’s needed?

I may actually be able to author around my original issue, but this will be great to have in my toolbag.

Bruce

9

It means exactly that, the caller is responsible for using synchronization to make sure that the semantics of use are correct. My ReadWrite lock code correctly synchronizes when using the Counter, so yes the ReadWrite lock does what’s needed. However, if you use the Atomic::Counter object for rolling your own stuff you will need to handle synchronization.

For example ReadWriteMutex::enter_read() calls m_writes->is_signaled() to determine if there are pending writers. It is possible that the last pending writer could release its lock right after the call to is_signaled() returns. enter_read() handles this by looping. So it correctly synchronizes the return value of is_signaled().

Another option would be to take a mutex when calling is_reset() or is_signaled() but that would defeat the point of it all, which is to develop a (mostly) lock-free implementation.