README.CV -- Condition Variables--------------------------------The original implementation of condition variables inpthreads-win32 was based on a discussion paper:"Strategies for Implementing POSIX Condition Variableson Win32": http://www.cs.wustl.edu/~schmidt/win32-cv-1.htmlThe changes suggested below were made on Feb 6 2001. Thisfile is included in the package for the benefit of anyoneinterested in understanding the pthreads-win32 implementationof condition variables and the (sometimes subtle) issues thatit attempts to resolve.Thanks go to the individuals whose names appear throughoutthe following text.Ross Johnson--------------------------------------------------------------------fyi.. (more detailed problem description/demos + possible fix/patch)regards,alexander.Alexander Terekhov31.01.2001 17:43To:   ace-bugs@cs.wustl.educc:From: Alexander Terekhov/Germany/IBM@IBMDESubject:  Implementation of POSIX CVs: spur.wakeups/lost      signals/deadlocks/unfairness    ACE VERSION:        5.1.12 (pthread-win32 snapshot 2000-12-29)    HOST MACHINE and OPERATING SYSTEM:        IBM IntelliStation Z Pro, 2 x XEON 1GHz, Win2K    TARGET MACHINE and OPERATING SYSTEM, if different from HOST:    COMPILER NAME AND VERSION (AND PATCHLEVEL):        Microsoft Visual C++ 6.0    AREA/CLASS/EXAMPLE AFFECTED:        Implementation of POSIX condition variables - OS.cpp/.h    DOES THE PROBLEM AFFECT:        EXECUTION? YES!    SYNOPSIS:        a) spurious wakeups (minor problem)        b) lost signals        c) broadcast deadlock        d) unfairness (minor problem)    DESCRIPTION:        Please see attached copy of discussion thread        from comp.programming.threads for more details on        some reported problems. (i've also posted a "fyi"        message to ace-users a week or two ago but        unfortunately did not get any response so far).        It seems that current implementation suffers from        two essential problems:        1) cond.waiters_count does not accurately reflect           number of waiters blocked on semaphore - w/o           proper synchronisation that could result (in the           time window when counter is not accurate)           in spurious wakeups organised by subsequent           _signals  and _broadcasts.        2) Always having (with no e.g. copy_and_clear/..)           the same queue in use (semaphore+counter)           neither signal nor broadcast provide 'atomic'           behaviour with respect to other threads/subsequent           calls to signal/broadcast/wait.        Each problem and combination of both could produce        various nasty things:        a) spurious wakeups (minor problem)             it is possible that waiter(s) which was already             unblocked even so is still counted as blocked             waiter. signal and broadcast will release             semaphore which will produce a spurious wakeup             for a 'real' waiter coming later.        b) lost signals             signalling thread ends up consuming its own             signal. please see demo/discussion below.        c) broadcast deadlock             last_waiter processing code does not correctly             handle the case with multiple threads             waiting for the end of broadcast.             please see demo/discussion below.        d) unfairness (minor problem)             without SignalObjectAndWait some waiter(s)             may end up consuming broadcasted signals             multiple times (spurious wakeups) because waiter             thread(s) can be preempted before they call             semaphore wait (but after count++ and mtx.unlock).    REPEAT BY:        See below... run problem demos programs (tennis.cpp and        tennisb.cpp) number of times concurrently (on multiprocessor)        and in multiple sessions or just add a couple of "Sleep"s        as described in the attached copy of discussion thread        from comp.programming.threads    SAMPLE FIX/WORKAROUND:        See attached patch to pthread-win32.. well, I can not        claim that it is completely bug free but at least my        test and tests provided by pthreads-win32 seem to work.        Perhaps that will help.        regards,        alexander.>> Forum: comp.programming.threads>> Thread: pthread_cond_* implementation questions...David Schwartz <davids@webmaster.com> wrote:> terekhov@my-deja.com wrote:>>> BTW, could you please also share your view on other perceived>> "problems" such as nested broadcast deadlock, spurious wakeups>> and (the latest one) lost signals??>>I'm not sure what you mean. The standard allows an implementation>to do almost whatever it likes. In fact, you could implement>pthread_cond_wait by releasing the mutex, sleeping a random>amount of time, and then reacquiring the mutex. Of course,>this would be a pretty poor implementation, but any code that>didn't work under that implementation wouldn't be strictly>compliant.The implementation you suggested is indeed correctone (yes, now I see it :). However it requires fromsignal/broadcast nothing more than to "{ return 0; }"That is not the case for pthread-win32 and ACEimplementations. I do think that these implementations(basically the same implementation) have some seriousproblems with wait/signal/broadcast calls. I am lookingfor help to clarify whether these problems are realor not. I think that I can demonstrate what I meanusing one or two small sample programs....==========tennis.cpp==========#include "ace/Synch.h"#include "ace/Thread.h"enum GAME_STATE {  START_GAME,  PLAYER_A,     // Player A playes the ball  PLAYER_B,     // Player B playes the ball  GAME_OVER,  ONE_PLAYER_GONE,  BOTH_PLAYERS_GONE};enum GAME_STATE             eGameState;ACE_Mutex*                  pmtxGameStateLock;ACE_Condition< ACE_Mutex >* pcndGameStateChange;void*  playerA(    void* pParm  ){  // For access to game state variable  pmtxGameStateLock->acquire();  // Play loop  while ( eGameState < GAME_OVER ) {    // Play the ball    cout << endl << "PLAYER-A" << endl;    // Now its PLAYER-B's turn    eGameState = PLAYER_B;    // Signal to PLAYER-B that now it is his turn    pcndGameStateChange->signal();    // Wait until PLAYER-B finishes playing the ball    do {      pcndGameStateChange->wait();      if ( PLAYER_B == eGameState )        cout << endl << "----PLAYER-A: SPURIOUS WAKEUP!!!" << endl;    } while ( PLAYER_B == eGameState );  }  // PLAYER-A gone  eGameState = (GAME_STATE)(eGameState+1);  cout << endl << "PLAYER-A GONE" << endl;  // No more access to state variable needed  pmtxGameStateLock->release();  // Signal PLAYER-A gone event  pcndGameStateChange->broadcast();  return 0;}void*  playerB(    void* pParm  ){  // For access to game state variable  pmtxGameStateLock->acquire();  // Play loop  while ( eGameState < GAME_OVER ) {    // Play the ball    cout << endl << "PLAYER-B" << endl;    // Now its PLAYER-A's turn    eGameState = PLAYER_A;    // Signal to PLAYER-A that now it is his turn    pcndGameStateChange->signal();    // Wait until PLAYER-A finishes playing the ball    do {      pcndGameStateChange->wait();      if ( PLAYER_A == eGameState )        cout << endl << "----PLAYER-B: SPURIOUS WAKEUP!!!" << endl;    } while ( PLAYER_A == eGameState );  }  // PLAYER-B gone  eGameState = (GAME_STATE)(eGameState+1);  cout << endl << "PLAYER-B GONE" << endl;  // No more access to state variable needed  pmtxGameStateLock->release();  // Signal PLAYER-B gone event  pcndGameStateChange->broadcast();  return 0;}intmain (int, ACE_TCHAR *[]){  pmtxGameStateLock   = new ACE_Mutex();  pcndGameStateChange = new ACE_Condition< ACE_Mutex >( *pmtxGameStateLock);  // Set initial state  eGameState = START_GAME;  // Create players  ACE_Thread::spawn( playerA );  ACE_Thread::spawn( playerB );  // Give them 5 sec. to play  Sleep( 5000 );//sleep( 5 );  // Set game over state  pmtxGameStateLock->acquire();  eGameState = GAME_OVER;  // Let them know  pcndGameStateChange->broadcast();  // Wait for players to stop  do {    pcndGameStateChange->wait();  } while ( eGameState < BOTH_PLAYERS_GONE );  // Cleanup  cout << endl << "GAME OVER" << endl;  pmtxGameStateLock->release();  delete pcndGameStateChange;  delete pmtxGameStateLock;  return 0;}===========tennisb.cpp===========#include "ace/Synch.h"#include "ace/Thread.h"enum GAME_STATE {  START_GAME,  PLAYER_A,     // Player A playes the ball  PLAYER_B,     // Player B playes the ball  GAME_OVER,  ONE_PLAYER_GONE,  BOTH_PLAYERS_GONE};enum GAME_STATE             eGameState;ACE_Mutex*                  pmtxGameStateLock;ACE_Condition< ACE_Mutex >* pcndGameStateChange;void*  playerA(    void* pParm  ){  // For access to game state variable  pmtxGameStateLock->acquire();  // Play loop  while ( eGameState < GAME_OVER ) {    // Play the ball    cout << endl << "PLAYER-A" << endl;    // Now its PLAYER-B's turn    eGameState = PLAYER_B;    // Signal to PLAYER-B that now it is his turn    pcndGameStateChange->broadcast();    // Wait until PLAYER-B finishes playing the ball    do {      pcndGameStateChange->wait();      if ( PLAYER_B == eGameState )        cout << endl << "----PLAYER-A: SPURIOUS WAKEUP!!!" << endl;    } while ( PLAYER_B == eGameState );  }  // PLAYER-A gone  eGameState = (GAME_STATE)(eGameState+1);  cout << endl << "PLAYER-A GONE" << endl;  // No more access to state variable needed  pmtxGameStateLock->release();  // Signal PLAYER-A gone event  pcndGameStateChange->broadcast();  return 0;}void*  playerB(    void* pParm  ){  // For access to game state variable  pmtxGameStateLock->acquire();  // Play loop  while ( eGameState < GAME_OVER ) {    // Play the ball    cout << endl << "PLAYER-B" << endl;    // Now its PLAYER-A's turn    eGameState = PLAYER_A;    // Signal to PLAYER-A that now it is his turn    pcndGameStateChange->broadcast();    // Wait until PLAYER-A finishes playing the ball    do {      pcndGameStateChange->wait();      if ( PLAYER_A == eGameState )        cout << endl << "----PLAYER-B: SPURIOUS WAKEUP!!!" << endl;    } while ( PLAYER_A == eGameState );  }  // PLAYER-B gone  eGameState = (GAME_STATE)(eGameState+1);  cout << endl << "PLAYER-B GONE" << endl;  // No more access to state variable needed  pmtxGameStateLock->release();  // Signal PLAYER-B gone event  pcndGameStateChange->broadcast();  return 0;}intmain (int, ACE_TCHAR *[]){  pmtxGameStateLock   = new ACE_Mutex();  pcndGameStateChange = new ACE_Condition< ACE_Mutex >( *pmtxGameStateLock);  // Set initial state  eGameState = START_GAME;  // Create players  ACE_Thread::spawn( playerA );  ACE_Thread::spawn( playerB );  // Give them 5 sec. to play  Sleep( 5000 );//sleep( 5 );  // Make some noise  pmtxGameStateLock->acquire();  cout << endl << "---Noise ON..." << endl;  pmtxGameStateLock->release();  for ( int i = 0; i < 100000; i++ )    pcndGameStateChange->broadcast();  cout << endl << "---Noise OFF" << endl;  // Set game over state  pmtxGameStateLock->acquire();  eGameState = GAME_OVER;  cout << endl << "---Stopping the game..." << endl;  // Let them know  pcndGameStateChange->broadcast();  // Wait for players to stop  do {    pcndGameStateChange->wait();  } while ( eGameState < BOTH_PLAYERS_GONE );  // Cleanup  cout << endl << "GAME OVER" << endl;  pmtxGameStateLock->release();  delete pcndGameStateChange;  delete pmtxGameStateLock;  return 0;