Boost logo

Boost :

From: Alexander Terekhov (terekhov_at_[hidden])
Date: 2002-10-18 14:04:30


David Abrahams wrote:
>
> * On condition.html
>
> a. What is the effective difference between notify_one() and
> notify_all()? In the absence of any information about the
> underlying system's scheduling mechanism, it seems as though there
> is none: either way, one blocked thread will get to execute with
> the mutex locked. If there is a difference between the two in
> practice, the documentation should give some indication of it.

A) http://www.opengroup.org/onlinepubs/007904975/functions/pthread_cond_signal.html
   (don't miss "RATIONALE" bits)

B) http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz
   (Acrobat: "479 of 631", read on "futexes")

C) consider the following .cpp that might help you [as usual,
   modulo bugs and any thing(s) that I've myself missed and/
   or misunderstood] understand how it is all meant to work.

//=======================================================
// DESIGN-futex-CV.cpp DRAFT <mailto:terekhov_at_[hidden]>
//=======================================================

#include <cerrno>
#include <cassert>
#include <climits>
#include <pthread.h>

//*** ES aside for a moment...

//*** pthread mutex wrapper
class mutex {

  //*** unimplemented since it's non-copyable/non-copy-constructible
  mutex( const mutex& );
  mutex& operator=( const mutex& );

  pthread_mutex_t m_mutex;

public:

  //*** RAII scoped locking guard
  class guard {

    //*** unimplemented since it's non-copyable/non-copy-constructible
    guard( const guard& );
    guard& operator=( const guard& );

    mutex& m_mutex;

  public:

    guard( mutex& mtx ) : m_mutex(mtx) {
      m_mutex.lock();
    }

   ~guard() {
      m_mutex.unlock();
    }

    mutex& mutex_ref() { return m_mutex; }

    pthread_mutex_t& c_mutex_ref() { return m_mutex.c_mutex(); }

  }; //*** class mutex::guard

  //*** RAII scoped "unlocking"/release guard
  class release_guard {

    //*** unimplemented since it's non-copyable/non-copy-constructible
    release_guard( const release_guard& );
    release_guard& operator=( const release_guard& );

    mutex& m_mutex;

  public:

    release_guard( mutex::guard& guard ) : m_mutex(guard.mutex_ref()) {
      m_mutex.unlock();
    }

   ~release_guard() {
      m_mutex.lock();
    }

    mutex& mutex_ref() { return m_mutex; }

    pthread_mutex_t& c_mutex_ref() { return m_mutex.c_mutex(); }

  }; //*** class mutex::release_guard

  mutex() {
    int status = pthread_mutex_init( &m_mutex,0 );
    assert( !status );
  }

 ~mutex() {
    int status = pthread_mutex_destroy( &m_mutex );
    assert( !status );
  }

  void lock() {
    int status = pthread_mutex_lock( &m_mutex );
    assert( !status );
  }

  void unlock() {
    int status = pthread_mutex_unlock( &m_mutex );
    assert( !status );
  }

  pthread_mutex_t& c_mutex() { return m_mutex; }

}; //*** class mutex

//*** pthread condvar wrapper
class condvar {

  //*** unimplemented since it's non-copyable/non-copy-constructible
  condvar( const condvar& );
  condvar& operator=( const condvar& );

  pthread_cond_t m_condvar;

public:

  condvar() {
    int status = pthread_cond_init( &m_condvar,0 );
    assert( !status );
  }

 ~condvar() {
    int status = pthread_cond_destroy( &m_condvar );
    assert( !status );
  }

  void wait( mutex::guard& guard ) {
    int status = pthread_cond_wait( &m_condvar,&guard.c_mutex_ref() );
    assert( !status );
  }

  bool timedwait( mutex::guard& guard, const timespec& abstime ) {
    int status = pthread_cond_timedwait(
                    &m_condvar,&guard.c_mutex_ref(),&abstime );
    assert( !status || ETIMEDOUT == status );
    return ETIMEDOUT == status;
  }

  void broadcast() {
    int status = pthread_cond_broadcast( &m_condvar );
    assert( !status );
  }

}; //*** class condvar

//*** futex emulator
class futex {

  //*** unimplemented since it's non-copyable/non-copy-constructible
  futex( const futex& );
  futex& operator=( const futex& );

  //*** RAII helper [used inside {timed}wait() only]
  struct waiter {

    waiter( waiter*& queue ) : next(queue), pqueue(&queue) {
      queue = this;
    }

   ~waiter() {
      if ( !is_reset() ) { // timedout/canceled
        while ( *pqueue && this != *pqueue )
          pqueue = &(*pqueue)->next;
        assert( this == *pqueue );
        *pqueue = next;
      }
    }
            
    waiter* reset() {
      waiter* w = next;
      next = this;
      return w;
    }

    bool is_reset() {
      return this == next;
    }

    waiter* next;
    waiter** pqueue;

  }* m_queue;
  int m_value;
  mutex mutable m_mutex;
  condvar m_condvar;
  
public:

  futex() : m_queue(0), m_value(0), m_mutex(), m_condvar() {}
 ~futex() { assert( !m_queue ); }
 
  operator int() const {
    mutex::guard guard( m_mutex );
    return m_value;
  }

  futex& operator=( int value ) {
    mutex::guard guard( m_mutex );
    m_value = value;
    return *this;
  }

  futex& operator++() {
    mutex::guard guard( m_mutex );
    ++m_value;
    return *this;
  }

  futex& operator--() {
    mutex::guard guard( m_mutex );
    --m_value;
    return *this;
  }

  void wait( int value ) {
    mutex::guard guard( m_mutex );
    if ( value == m_value ) {
      waiter this_waiter( m_queue );
      do { m_condvar.wait( guard ); }
        while ( !this_waiter.is_reset() );
    }
  }

  bool timedwait( int value, const timespec& abstime ) {
    mutex::guard guard( m_mutex );
    if ( value == m_value ) {
      waiter this_waiter( m_queue );
      do { if ( m_condvar.timedwait( guard,abstime ) ) return true; }
        while ( !this_waiter.is_reset() );
    }
    return false;
  }

  void wake( unsigned int wakeups ) {
    mutex::guard guard( m_mutex );
    while ( m_queue && wakeups-- )
      m_queue = m_queue->reset();
    m_condvar.broadcast();
  }

}; //*** class futex

//*** RAII helper
class cancel_off_guard {

  //*** unimplemented since it's non-copyable/non-copy-constructible
  cancel_off_guard( const cancel_off_guard& );
  cancel_off_guard& operator=( const cancel_off_guard& );

  int m_old_cancel_state;

public:

  cancel_off_guard() {
    int status = pthread_setcancelstate( PTHREAD_CANCEL_DISABLE,
                                         &m_old_cancel_state );
    assert( !status );
  }

 ~cancel_off_guard() {
    int status = pthread_setcancelstate( m_old_cancel_state,
                                         &m_old_cancel_state );
    assert( !status );
  }

}; //*** class cancel_off_guard

//*** futex-based condvar implementation
class futex_condvar {

  //*** unimplemented since it's non-copyable/non-copy-constructible
  futex_condvar( const futex_condvar& );
  futex_condvar& operator=( const futex_condvar& );

  mutex m_mutex;
  futex m_futex;
  unsigned int m_wakeups;
  unsigned int m_waiters[2];

  //*** Less stress: MIN = INT_MIN and MAX = INT_MAX
  enum CONSTS { MIN = -2, MAX = 1, ALL = UINT_MAX };

  //*** End-Of-Cycle value
  int EOC() const { return (m_futex < 0) ? -1 : MAX; }

  //*** RAII helper [used inside {timed}wait() only]
  struct waiter {

    waiter( futex_condvar* fcv, mutex& mtx ) :
      m_fcv(fcv), m_mtx(mtx), m_ftx(fcv->enter_wait( mtx )) { }

   ~waiter() { m_fcv->leave_wait( m_ftx ); m_mtx.lock(); }

    int ftx() const { return m_ftx; }

    futex_condvar* m_fcv;
    mutex& m_mtx;
    int m_ftx;

  }; //*** struct futex_condvar::waiter

  friend struct waiter; // calls enter_wait()/leave_wait()

  int enter_wait( mutex& mtx ) {
    mutex::guard guard( m_mutex );
    mtx.unlock();
    ++m_waiters[ EOC() == m_futex ];
    return m_futex;
  }

  void leave_wait( int ftx ) {
    mutex::guard guard( m_mutex );
    if ( ftx != m_futex ) {
      assert( m_waiters[0] );
      --m_waiters[0];
      if ( 0 != m_wakeups &&
           0 == --m_wakeups &&
           EOC() == m_futex ) {
        m_futex = ( m_futex < 0 ) ? 0 : MIN;
        m_waiters[0] = m_wakeups = m_waiters[1];
        m_waiters[1] = 0;
        m_futex.wake( ALL );
      }
    }
    else
      --m_waiters[ EOC() == ftx ];
  }

public:

  futex_condvar() : m_mutex(), m_futex(), m_wakeups(0) {
    m_waiters[0] = m_waiters[1] = 0;
  }

 ~futex_condvar() {
    mutex::guard guard( m_mutex );
    assert( m_waiters[0] == m_wakeups );
    while ( m_waiters[0] ) {
      int ftx = m_futex = EOC();
      mutex::release_guard release_guard( guard );
      cancel_off_guard no_cancel;
      m_futex.wait( ftx );
    }
  }

  void wait( mutex& mtx ) {
    waiter this_waiter( this, mtx );
    m_futex.wait( this_waiter.ftx() );
  }

  bool timedwait( mutex& mtx, const timespec& abstime ) {
    waiter this_waiter( this, mtx );
    return m_futex.timedwait( this_waiter.ftx(), abstime );
  }

  void signal() {
    unsigned int wakeups;
    {
      mutex::guard guard( m_mutex );
      if ( 0 != (wakeups = m_waiters[0] > m_wakeups) ) {
        if ( EOC() == ++m_futex ) {
          wakeups = ALL;
          m_wakeups = m_waiters[0];
        }
        else
          ++m_wakeups;
      }
    }
    if ( wakeups )
      m_futex.wake( wakeups );
  }

  void broadcast() {
    bool wakeups;
    {
      mutex::guard guard( m_mutex );
      if ( false != (wakeups = m_waiters[0] > m_wakeups) ) {
        ++m_futex;
        m_wakeups = m_waiters[0];
      }
    }
    if ( wakeups )
      m_futex.wake( ALL );
  }
   
}; //*** class futex_condvar

//*** yet another "tennis" (but with futex_condvars this time)
#include <ctime>
#include <iostream>
using namespace std;

enum GAME_STATE {

[snip; see my other message that should contain this code]

regards,
alexander.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk