Re: Not keen on Boost.Threads? [was: name of the "thread" type]

From: Alexander Terekhov (terekhov_at_[hidden])
Date: 2001-07-04 03:55:02

> > http://www.acm.org/classics/feb96/
> >
> > "Monitors: An Operating System Structuring Concept
> >  C.A.R Hoare..."
>
> Thanks. This seems to be another case of me reinventing the wheel. :-)
> What he's describing there seems to be the concept I put in my thread
> library under the name Flag.

i do not think so.. condition variables are stateless and
they are working together with mutex providing atomic
unlock_and_wait semantics (with respect to other threads
and CV/mutex).

your Flag is actually an event (either auto-reset or manual):

  >the current state of my threads library can be found at:
  >http://storm.net.nz/~ross/c++/rs_threads.tgz

  Flag::Flag(bool broadcast):
    imp_(new Imp_) {
      imp_->event = CreateEvent(0, broadcast, false, 0);
      if (imp_->event == 0)
        throw Error("Failed to create flag\n" + windows_error_message());
    }

which was probably "invented" by Microsoft ;)

note that auto-reset event is simply a binary semaphore.
manual-reset events also have state. it is really difficult
to use events due to all sorts of race conditions with
respect to "program" state and event state. consider
the following ReadWrite lock code from your library:

  /*private*/ struct ReadWrite::Imp_ {
    HANDLE free;             // Signalled while no locks held
    CRITICAL_SECTION mutex;
    long readers;            // -1 if write-locked
  };

  ReadWrite::ReadWrite():
    imp_(new Imp_) {
      imp_->readers = 0;
      imp_->free = CreateEvent(0, true, false, 0);
      if (imp_->free == 0)
        throw Error("Failed to create read/write lock\n" +
windows_error_message());
      InitializeCriticalSection(&imp_->mutex);
    }

  void ReadWrite::read_lock() {
    while (!try_read_lock())
      if (WaitForSingleObject(imp_->free, INFINITE) == WAIT_FAILED)
        throw Error("Failed to acquire read lock\n" + windows_error_message
());
  }

  bool ReadWrite::try_read_lock() {
    EnterCriticalSection(&imp_->mutex);
    bool ok(imp_->readers >= 0);
    int rc(1);
    if (ok) {
      ++imp_->readers;
      rc = ResetEvent(imp_->free);
    }
    LeaveCriticalSection(&imp_->mutex);
    if (rc == 0)
      throw Error("Failed to acquire read lock\n" + windows_error_message
());
    return ok;
  }

  void ReadWrite::unlock() {
    EnterCriticalSection(&imp_->mutex);
    if (imp_->readers > 0)
      --imp_->readers;
    else
      ++imp_->readers;
    int rc(1);
    if (imp_->readers == 0)
      rc = SetEvent(imp_->free);
    LeaveCriticalSection(&imp_->mutex);
    if (rc == 0)
      throw Error("Failed to release read/write lock\n" +
windows_error_message());
  }

in the situation when

a) writer holds the lock
b) one reader is blocked on event
c) N other readers were preempted after try_read_lock
   and before WaitForSingleObject(imp_->free

when writer unlocks, he will set event which will unblock
reader b). however, since that reader will "immediately"
reset event, all c) readers could end up blocked on event
until reader b) unlocks. with all excessive synchronisation
you have (a lot of synch/set/reset calls) your event based
ReadWrite lock could fail to provide read concurrency,
which is only one problem among others..

regards,
alexander.

ps. consider the following algorithm without CVs,
and with "no read/write preference" policy; pseudo-code):

---------- Algorithm 1a / IMPL_SEM ----------

given:
mtxEntryLock - mutex or CS (or bin.semaphore/auto-reset event)
mtxReadExitLock - mutex or CS (or bin.semaphore/auto-reset event)
semWriteAccessGranted - bin.semaphore (or auto-reset event)
nReadEntryCount - int
nReadExitCount - int
nReadTriedCount - int
nWriteAccessCount - int

rdlock() {

  [auto: register int result]     // error checking omitted
                                  // code for recursive readlocks omitted
  lock( mtxEntryLock );

  if ( INT_MAX == ++nReadEntryCount ) {
    lock( mtxReadExitLock );
    nReadEntryCount -= nReadExitCount;
    nReadExitCount = 0;
    unlock( mtxReadExitLock );
  }

  unlock( mtxEntryLock );

}

tryrdlock() {

  [auto: register int result]     // error checking omitted
                                  // code for recursive readlocks omitted

  lock( mtxReadExitLock );

  //!!! RACE CONDITION WITH RESPECT TO nWriteAccessCount
  //!!! harmless under Win32 (atomic int store/load)
  if ( nWriteAccessCount > 0 ||   // writer holds the rwlock
       nReadExitCount    < 0 ) {  // writer blocked on rwlock
    unlock( mtxReadExitLock );
    return EBUSY;
  }

  nReadTriedCount++;

  unlock( mtxReadExitLock );

}

wrlock() {

  [auto: register int result]     // error checking omitted

  lock( mtxEntryLock );

  if ( 0 == nWriteAccessCount ) {

    lock( mtxReadExitLock );

    if ( 0 != nReadExitCount ) {
      nReadEntryCount -= nReadExitCount;
      nReadExitCount = 0;
    }

    if ( 0 != nReadTriedCount ) {
      nReadEntryCount += nReadTriedCount;
      nReadTriedCount = 0;
    }

    if ( 0 != nReadEntryCount ) {

      nReadExitCount = -nReadEntryCount;
      nReadEntryCount = 0;
      unlock( mtxReadExitLock )
      sem_wait( semWriteAccessGranted );

    }
    else {
      nWriteAccessCount = 1;
      unlock( mtxReadExitLock )
    }

  }
  else {                         // recursive write locking
    nWriteAccessCount++;         // via recursive mtxEntryLock
  }
}

trywrlock() {

  [auto: register int result]     // error checking omitted

  if ( EBUSY == trylock( mtxEntryLock ) ) {
    return EBUSY;
  }

  if ( 0 != nWriteAccessCount ) {
    unlock( mtxEntryLock );
    return EBUSY;
  }

  lock( mtxReadExitLock );

  if ( 0 != nReadExitCount ) {
    nReadEntryCount -= nReadExitCount;
    nReadExitCount = 0;
  }

  if ( 0 != nReadTriedCount ) {
    nReadEntryCount += nReadTriedCount;
    nReadTriedCount = 0;
  }

  if ( 0 != nReadEntryCount ) {
    unlock( mtxReadExitLock );
    unlock( mtxEntryLock );
    return EBUSY;
  }

  nWriteAccessCount = 1;

  unlock( mtxReadExitLock );
}

unlock() {

  [auto: register int result           ] // error checking omitted
  [auto: register int bGrantWriteAccess]
                                         // code for recursive readlocks
omitted

  if ( 0 == nWriteAccessCount ) {
    lock( mtxReadExitLock );
    if ( 0 == nReadTriedCount ) {
      if ( 0 == ++nReadExitCount ) {
        nWriteAccessCount = 1;
        bGrantWriteAccess = true;
      }
      else {
        bGrantWriteAccess = false;
      }
    }
    else {
      nReadTriedCount--;
      bGrantWriteAccess = false;
    }
    unlock( mtxReadExitLock );
    if ( bGrantWriteAccess ) {
      sem_post( semWriteAccessGranted );
    }
  }
  else {
    nWriteAccessCount--;
    unlock( mtxEntryLock );
  }
}