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

DESIGN-condvar



<DESIGN-condvar.txt>

Conditional Variable pseudocode.
================================

       int pthread_cond_timedwait (pthread_cond_t *cv, pthread_mutex_t *mutex);
       int pthread_cond_signal    (pthread_cond_t *cv);
       int pthread_cond_broadcast (pthread_cond_t *cv);

struct pthread_cond_t {

   unsigned int lock:

         internal mutex

   unsigned int nr_wakers:

         number of threads signalled to be woken up.   

   unsigned int nr_sleepers:

         number of threads waiting for the cv.

}

#define ALL_THREADS (1 << (BITS_PER_LONG-1))

cond_wait_timeout(cv, mutex, timeout):
{
   lll_lock(cv->lock);
   mutex_unlock(mutex);

   cv->nr_sleepers++;
   for (;;) {

       if (cv->nr_wakers) {
           cv->nr_wakers--;
           break;
       }
       val = cv->nr_wakers;

       lll_unlock(cv->lock);

       ret = FUTEX WAIT (cv->nr_wakers, val, timeout)

       lll_lock(cv->lock);

       if (ret == TIMEOUT)
         break;
       ret = 0;
   }
   if (!--cv->nr_sleepers)
     cv->nr_wakers = 0; /* no memory of wakeups */
   mutex_lock(mutex);
   lll_unlock(cv->lock);

   return ret;
}

cond_signal(cv)
{
   int do_wakeup = 0;

   lll_lock(cv->lock);
   if (cv->nr_sleepers) {
     if (!++cv->nr_wakers) /* overflow detection for the nutcase */
       cv->nr_wakers = ALL_THREADS;
     do_wakeup = 1;
   }
   lll_unlock(cv->lock);
   if (do_wakeup)
     FUTEX WAKE (cv->nr_wakers, 1)
}

cond_broadcast(cv)
{
   int do_wakeup = 0;

   lll_lock(cv->lock);
   if (cv->nr_sleepers) {
     cv->nr_wakers |= ALL_THREADS;
     do_wakeup = 1;
   }
   lll_unlock(cv->lock);
   if (do_wakeup)
     FUTEX WAKE (cv->nr_wakers, ALL_THREADS);
}

weaknesses of the implementation:

 it might generate spurious wakeups in the broadcast case, but those are
 allowed by POSIX.

</DESIGN-condvar.txt>

Now consider the following "example":


=====================================
tennis.c
=====================================
#include <stdio.h>
#include <pthread.h>

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

};

enum GAME_STATE eGameState;
pthread_mutex_t mtxGameStateLock;
pthread_cond_t  cndGameStateChange;

void*
  playerA(
    void* pParm
  )
{

  pthread_mutex_lock( &mtxGameStateLock );

  // Game loop
  while ( eGameState < GAME_OVER ) {

    // Play the ball
    printf( "\nPLAYER-A\n" );

    // Now it is PLAYER-B's turn
    eGameState = PLAYER_B;

    // Signal it to PLAYER-B
    pthread_cond_signal( &cndGameStateChange );

    // Wait until PLAYER-B finishes playing the ball
    do {

      pthread_cond_wait( &cndGameStateChange,&mtxGameStateLock );

      if ( PLAYER_B == eGameState )
        printf( "\n----PLAYER-A: SPURIOUS WAKEUP!!!\n" );

    } while ( PLAYER_B == eGameState ); 
  }

  // PLAYER-A gone
  eGameState++;
  printf( "\nPLAYER-A GONE\n" );

  // Both players gone?
  if ( BOTH_PLAYERS_GONE == eGameState )
    pthread_cond_signal( &cndGameStateChange );

  pthread_mutex_unlock( &mtxGameStateLock );

  return 0;

}

void*
  playerB(
    void* pParm
  )
{

  pthread_mutex_lock( &mtxGameStateLock );

  // Game loop
  while ( eGameState < GAME_OVER ) {

    // Play the ball
    printf( "\nPLAYER-B\n" );

    // Now its PLAYER-A's turn
    eGameState = PLAYER_A;

    // Signal it to PLAYER-A
    pthread_cond_signal( &cndGameStateChange );

    // Wait until PLAYER-A finishes playing the ball
    do {

      pthread_cond_wait( &cndGameStateChange,&mtxGameStateLock );

      if ( PLAYER_A == eGameState )
        printf( "\n----PLAYER-B: SPURIOUS WAKEUP!!!\n" );

    } while ( PLAYER_A == eGameState ); 
  }

  // PLAYER-B gone
  eGameState++;
  printf( "\nPLAYER-B GONE\n" );

  // Both players gone?
  if ( BOTH_PLAYERS_GONE == eGameState )
    pthread_cond_signal( &cndGameStateChange );

  pthread_mutex_unlock( &mtxGameStateLock );

  return 0;

}


int
  main()
{

  pthread_t thid;

  pthread_mutex_init( &mtxGameStateLock,0 );
  pthread_cond_init( &cndGameStateChange,0 );

  // Set initial state
  eGameState = START_GAME;

  // Create players
  pthread_create( &thid,0,playerA,0 );
  pthread_create( &thid,0,playerB,0 );

  // Give them 5 sec. to play
  //Sleep( 1000 ); //Win32
  sleep( 1 );

  // Set game over state
  pthread_mutex_lock( &mtxGameStateLock );
  eGameState = GAME_OVER;

  // Signal game over
  pthread_cond_broadcast( &cndGameStateChange );

  // Wait for players to stop
  do {

    pthread_cond_wait( &cndGameStateChange,&mtxGameStateLock );

  } while ( eGameState != BOTH_PLAYERS_GONE );

  // Thats it
  printf( "\nGAME OVER\n" );
  pthread_mutex_unlock( &mtxGameStateLock );
  pthread_cond_destroy( &cndGameStateChange );
  pthread_mutex_destroy( &mtxGameStateLock );

  return 0;

}

Questions:
----------

Q1) Are you sure that given the current CV design, it's 
    really guranteed that a player just can't consume his 
    own signal as spurious wakeup... resulting in a sort 
    of deadlock (until the main/initial thread would come
    it and resolve it declaring game over)?

Q2) POSIX does require that deleting a condition variable 
    after final signaling should be OK/safe(*). Are you 
    sure that this would actually work under the current 
    DESIGN-condvar?

Q3) Don't you think that < see cond_wait_timeout() >

       lll_lock(cv->lock);
       mutex_unlock(mutex);
       ....
       lll_unlock(cv->lock);

       ret = FUTEX WAIT (cv->nr_wakers, val, timeout)

       lll_lock(cv->lock);
       ....
       mutex_lock(mutex);
       lll_unlock(cv->lock);

    is kinda "deadlock-prone"? Shouldn't it rather:

       lll_lock(cv->lock);
       mutex_unlock(mutex);
       ....
       lll_unlock(cv->lock);

       ret = FUTEX WAIT (cv->nr_wakers, val, timeout)

       lll_lock(cv->lock);
       ....
       lll_unlock(cv->lock);
       mutex_lock(mutex);

    <?>

TIA.

regards,
alexander.

(*) http://www.opengroup.org/onlinepubs/007904975/functions/pthread_cond_destroy.html

"....
 It shall be safe to destroy an initialized condition variable upon which 
 no threads are currently blocked. 
 ....
 The following sections are informative.

 EXAMPLES
 
 A condition variable can be destroyed immediately after all the threads 
 that are blocked on it are awakened. For example, consider the following 
 code:

 struct list {
     pthread_mutex_t lm;
     ...
 }

 struct elt {
     key k;
     int busy;
     pthread_cond_t notbusy;
     ...
 }

 /* Find a list element and reserve it. */
 struct elt *
 list_find(struct list *lp, key k)
 {
     struct elt *ep;

     pthread_mutex_lock(&lp->lm);
     while ((ep = find_elt(l, k) != NULL) && ep->busy)
         pthread_cond_wait(&ep->notbusy, &lp->lm);
     if (ep != NULL)
         ep->busy = 1;
     pthread_mutex_unlock(&lp->lm);
     return(ep);
 }

 delete_elt(struct list *lp, struct elt *ep)
 {
     pthread_mutex_lock(&lp->lm);
     assert(ep->busy);
     ... remove ep from list ...
     ep->busy = 0;  /* Paranoid. */
 (A) pthread_cond_broadcast(&ep->notbusy);
     pthread_mutex_unlock(&lp->lm);
 (B) pthread_cond_destroy(&rp->notbusy);
     free(ep);
 }
 
 In this example, the condition variable and its list element may be 
 freed (line B) immediately after all threads waiting for it are awakened 
 (line A), since the mutex and the code ensure that no other thread can 
 touch the element to be deleted.
 ...."

______________________________________________________________________________
Virenschutz inklusive: Bei WEB.DE FreeMail konnen Sie jeden
Dateianhang auf Viren prufen http://freemail.web.de/?mc=021130





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