%%rwlock using basic mutex #untested

Q: implement a simple read/write lock using a basic mutex provided by a basic thread library.

I feel some minimum fairness is needed. You don’t want a writer thread to keep waiting for a long time while readers come and go, as if the writer is a second-class citizen.

Ashish pointed out a bug, so now, all 4 methods must acquire _police from onset, before reading/writing  internal shared data.

#include <cassert>
using namespace std;
class mutex{ //this class should be provided to us
public:
  void release();
  void acquire();
};

class raiiLock{//when an instance goes out of scope on the stack, dtor will release the lock
  mutex * const _lock;
public:
  raiiLock(mutex * m) : _lock(m){
    _lock->acquire();
  }
  ~raiiLock(){
    _lock->release();
  }
};

/*This implementation favors writers to readers, assuming write is more urgent.
Reader starvation is considered tolerable.

Since there are 2 mutexes involved, we will always acquire the police first. Helps prevent deadlocks

-- Target Usage Scenario --
Imagine a data table that any thread can read in the absence of concurrent updates,
but only one writer thread at a time can update.
*/
class rwlock{
  rwlock(rwlock const & other); //disabled
  rwlock & operator =(rwlock const & other); //disabled

  // data members
  mutex * const _mutex; //used by writers only, never by readers
  mutex * const _police; // controls modifications to internal data members
  size_t const _permits; // max number of concurrent readers allowed in theory
  size_t _available; // available permits, controlled by the police
  size_t _waitingWriters; // controlled by the police
public:
  // note dtor will be synthesized, which will do nothing if all data members are primitives or pointers
  // note no-arg ctor is not allowed.
  rwlock(mutex * m,
                mutex * police,
                size_t maxPermits):
    _mutex(m),
    _police(police),
    _permits  (maxPermits),
    _available(maxPermits),
    _waitingWriters(0){}

  void release1permit(){
    raiiLock autoLock(_police); //blocking briefly
    _available ++;
    if (_available == _permits && _waitingWriters){
      //wake up one of the writers, perhaps using a conditional variable tied to _police mutex
    }
  }
  void releaseWriterLock(){
    raiiLock autoLock(_police); //blocking briefly
    _available = _permits;
    _mutex->release();
    if (_waitingWriters){
      //wake up one of the writers, perhaps using a conditional variable tied to _police mutex
    }
  }
  char try_acquire1permit(){ // non-blocking
    //As Ashish pointed out, _police need to be acquired before 
    //checking _waitingWriters and _available. Any access to shared internal
    //data needs police protection.
    raiiLock autoLock(_police); //blocking briefly
    if (_waitingWriters) return 'w'; //immediately reject this
    // reader's request if there's any waiting writer.
    // Therefore, any subsequent reader requests will not affect the waiting writers.
    if (_available == 0 ) return 'a';

    assert( _available > 0 && _waitingWriters == 0);
    _available --;
    return '0'; // 0 means safe to read the protected data table
  }
  void acquireWriterLock(){ // blocking
    raiiLock autoLock(_police); //blocking briefly
    _waitingWriters ++ ; //Subsequent readers will be rejected, to avoid writer starvation
    while(_available < _permits){
      //block in some kind of waiting room perhaps using a conditional variable tied to _police mutex
    }
    assert (_available == _permits);
    _mutex->acquire(); // should never block
    _available = 0;
    _waitingWriters --;
    // now the current thread is free to update the table
  }
};
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s