[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]

Re:DESIGN-condvar



phil-list redhat com schrieb am 13.10.02 15:16:05:
[...]
> < I apologize in advance for something obviously erroneous/silly,
>   but after 2x~3.* hours thinking about it, here's what I've got. >
> 
> What about the following futex-based-CV pseudocode? ...

< got another spare hour or two >

//============================================
// FutexCV.cpp: futex-emulator + CV + 'tennis'
//============================================

#include <assert.h>
#include <limits.h>
#include <pthread.h>

//*** 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(); }

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

  }; //*** class mutex::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() );
    assert( !status );
  }

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

}; //*** class condvar

//*** futex emulator (timedwait aside [for now])
class futex {

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

  struct waiter {
    waiter( waiter*& queue ) : next(queue) { queue = this; }
    waiter* reset() { waiter* w = next; next = this; return w; }
    bool is_reset() { return this == next; }
    waiter* next;
  }*            m_queue;
  unsigned 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 unsigned int() const { 
    mutex::guard guard( m_mutex );
    return m_value; 
  }

  futex& operator=( unsigned 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( unsigned 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() );
    }
  }

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

}; //*** class futex

//*** 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& );

  futex        m_futex;
  mutex        m_mutex;
  bool         m_cycle;
  unsigned int m_wakers;  
  unsigned int m_sleepers[2];

  enum CONSTS { MAX = 2, ALL = UINT_MAX };

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

  //*** RAII helper [used inside 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(); }

    unsigned int ftx() const { return m_ftx; }

    futex_condvar* m_fcv;
    mutex&         m_mtx;
    unsigned int   m_ftx;

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

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

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

  void leave_wait( unsigned int ftx ) {
    mutex::guard guard( m_mutex );
    if ( ftx != m_futex ) {
      --m_sleepers[0];
      if ( 0 !=   m_wakers && 
           0 == --m_wakers && 
           EOC() == m_futex ) {
        m_futex = ( m_cycle = !m_cycle ) ? MAX-1 : 1;
        m_sleepers[0] = m_wakers = m_sleepers[1];
        m_sleepers[1] = 0;
        m_futex.wake( ALL );
      }
    }
    else
      --m_sleepers[ EOC() == m_futex ];
  } 

  unsigned int signal_wakeups() {
    mutex::guard guard( m_mutex );
    if ( m_sleepers[0] <= m_wakers ) 
      return 0;
    if ( m_cycle ? 0 == --m_futex : MAX == ++m_futex ) {
      m_wakers = m_sleepers[0];
      return ALL;
    }
    ++m_wakers;
    return 1;
  }

  unsigned int broadcast_wakeups() {
    mutex::guard guard( m_mutex );
    if ( m_sleepers[0] <= m_wakers ) 
      return 0;
    if ( m_cycle ) 
      --m_futex; 
    else 
      ++m_futex;
    m_wakers = m_sleepers[0];
    return ALL;
  }

  void sync_dtor() {
    mutex::guard guard( m_mutex );
    assert( m_sleepers[0] == m_wakers );
    while ( m_sleepers[0] ) {
      unsigned int ftx = m_futex = EOC();
      m_mutex.unlock();
      m_futex.wait( ftx );
      m_mutex.lock();
    }
  }

public:

  futex_condvar() : m_futex(), m_mutex(), m_cycle(0), m_wakers(0) {
    m_sleepers[0] = m_sleepers[1] = 0;
  }

 ~futex_condvar() {
    sync_dtor();
  }

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

  void signal() {
    if ( unsigned int count = signal_wakeups() )
      m_futex.wake( count );
  }

  void broadcast() {
    if ( unsigned int count = broadcast_wakeups() )
      m_futex.wake( count );
  }
   
};

//*** yet another "tennis" (but with futex_condvar this time)
#include <unistd.h>
#include <iostream>

enum GAME_STATE {

  START_GAME,
  PLAYER_A,     // Player A plays the ball
  PLAYER_B,     // Player B plays the ball
  GAME_OVER,
  ONE_PLAYER_GONE,
  BOTH_PLAYERS_GONE

}             eGameState;
mutex         mtxGameStateLock;
futex_condvar cndGameStateChange;

const char* id( GAME_STATE ePlayer ) {
  assert( PLAYER_A == ePlayer || PLAYER_B == ePlayer );
  return ( PLAYER_A == ePlayer ) ? "PLAYER A" : "PLAYER B";
}

GAME_STATE another( GAME_STATE ePlayer ) {
  assert( PLAYER_A == ePlayer || PLAYER_B == ePlayer );
  return ( PLAYER_A == ePlayer ) ? PLAYER_B : PLAYER_A;
}

extern "C" void* play( void* pPlayer ) {
  GAME_STATE ePlayer = *static_cast< GAME_STATE* >( pPlayer );
  mutex::guard guard( mtxGameStateLock );
  while ( eGameState < GAME_OVER ) {
    cout << id( ePlayer ) << "\n";
    eGameState = another( ePlayer );
    cndGameStateChange.signal();
    do { 
      cndGameStateChange.wait( mtxGameStateLock );
      if ( another( ePlayer ) == eGameState )
        cout << "\n----" << id( ePlayer ) << ": SPURIOUS WAKEUP!!!\n";
    } while ( another( ePlayer ) == eGameState );
  }
  eGameState = static_cast< GAME_STATE >( eGameState+1 );
  cout << id( ePlayer ) << " GONE\n";
  cndGameStateChange.broadcast();
  return 0;
}

GAME_STATE ePlayerA = PLAYER_A;
GAME_STATE ePlayerB = PLAYER_B;

int main() {
  pthread_t thid;
  eGameState = START_GAME;
  pthread_create( &thid,0,play,static_cast< void* >( &ePlayerA ) );
  pthread_create( &thid,0,play,static_cast< void* >( &ePlayerB ) );
  sleep( 1 );
  mutex::guard guard( mtxGameStateLock );
  eGameState = GAME_OVER;
  cndGameStateChange.broadcast();
  do { cndGameStateChange.wait( mtxGameStateLock ); }
    while ( BOTH_PLAYERS_GONE != eGameState );
  cout << "\nGAME OVER\n";
}

regards,
alexander.

________________________________________________________________
Keine verlorenen Lotto-Quittungen, keine vergessenen Gewinne mehr! 
Beim WEB.DE Lottoservice: http://tippen2.web.de/?x=13






[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]