readme.cv

pthread source code,you can compile directly

README.CV -- Condition Variables
--------------------------------

The original implementation of condition variables in
pthreads-win32 was based on a discussion paper:

"Strategies for Implementing POSIX Condition Variables
on Win32": http://www.cs.wustl.edu/~schmidt/win32-cv-1.html

The changes suggested below were made on Feb 6 2001. This
file is included in the package for the benefit of anyone
interested in understanding the pthreads-win32 implementation
of condition variables and the (sometimes subtle) issues that
it attempts to resolve.

Thanks go to the individuals whose names appear throughout
the following text.

Ross Johnson

--------------------------------------------------------------------

fyi.. (more detailed problem description/demos + possible fix/patch)

regards,
alexander.


Alexander Terekhov
31.01.2001 17:43

To:   [e-mail]
cc:
From: Alexander Terekhov/Germany/IBM@IBMDE
Subject:  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 <[e-mail]> wrote:

> [e-mail] 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 correct
one (yes, now I see it :). However it requires from
signal/broadcast nothing more than to "{ return 0; }"
That is not the case for pthread-win32 and ACE
implementations. I do think that these implementations
(basically the same implementation) have some serious
problems with wait/signal/broadcast calls. I am looking
for help to clarify whether these problems are real
or not. I think that I can demonstrate what I mean
using 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;

}


int
main (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;

}


int
main (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;