diff options
| author | rpj <rpj> | 2002-02-11 01:53:22 +0000 |
|---|---|---|
| committer | rpj <rpj> | 2002-02-11 01:53:22 +0000 |
| commit | e6f1797e9e9925ae7f9dda54806ef8f52ae3ed07 (patch) | |
| tree | c513bf622584d48383ce9d167159c81baa71b3f9 /README.CV | |
| parent | 1cf6fdda9842e5b728cdce93683292f4380a4572 (diff) | |
Splitting files. See ChangeLog file for details.
Diffstat (limited to 'README.CV')
| -rw-r--r-- | README.CV | 6072 |
1 files changed, 3036 insertions, 3036 deletions
@@ -1,3036 +1,3036 @@ -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: ace-bugs@cs.wustl.edu
-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 <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 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;
-
-}
-.
-.
-.
-David Schwartz <davids@webmaster.com> wrote:
->> > It's compliant
->>
->> That is really good.
->
->> Tomorrow (I have to go urgently now) I will try to
->> demonstrate the lost-signal "problem" of current
->> pthread-win32 and ACE-(variant w/o SingleObjectAndWait)
->> implementations: players start suddenly drop their balls :-)
->> (with no change in source code).
->
->Signals aren't lost, they're going to the main thread,
->which isn't coded correctly to handle them. Try this:
->
-> // Wait for players to stop
-> do {
->
-> pthread_cond_wait( &cndGameStateChange,&mtxGameStateLock );
->printf("Main thread stole a signal\n");
->
-> } while ( eGameState < BOTH_PLAYERS_GONE );
->
->I bet everytime you thing a signal is lost, you'll see that printf.
->The signal isn't lost, it was stolen by another thread.
-
-well, you can probably loose your bet.. it was indeed stolen
-by "another" thread but not the one you seem to think of.
-
-I think that what actually happens is the following:
-
-H:\SA\UXX\pt\PTHREADS\TESTS>tennis3.exe
-
-PLAYER-A
-
-PLAYER-B
-
-----PLAYER-B: SPURIOUS WAKEUP!!!
-
-PLAYER-A GONE
-
-PLAYER-B GONE
-
-GAME OVER
-
-H:\SA\UXX\pt\PTHREADS\TESTS>
-
-here you can see that PLAYER-B after playing his first
-ball (which came via signal from PLAYER-A) just dropped
-it down. What happened is that his signal to player A
-was consumed as spurious wakeup by himself (player B).
-
-The implementation has a problem:
-
-================
-waiting threads:
-================
-
-{ /** Critical Section
-
- inc cond.waiters_count
-
-}
-
- /*
- /* Atomic only if using Win32 SignalObjectAndWait
- /*
- cond.mtx.release
-
- /*** ^^-- A THREAD WHICH DID SIGNAL MAY ACQUIRE THE MUTEX,
- /*** GO INTO WAIT ON THE SAME CONDITION AND OVERTAKE
- /*** ORIGINAL WAITER(S) CONSUMING ITS OWN SIGNAL!
-
- cond.sem.wait
-
-Player-A after playing game's initial ball went into
-wait (called _wait) but was pre-empted before reaching
-wait semaphore. He was counted as waiter but was not
-actually waiting/blocked yet.
-
-===============
-signal threads:
-===============
-
-{ /** Critical Section
-
- waiters_count = cond.waiters_count
-
-}
-
- if ( waiters_count != 0 )
-
- sem.post 1
-
- endif
-
-Player-B after he received signal/ball from Player A
-called _signal. The _signal did see that there was
-one waiter blocked on the condition (Player-A) and
-released the semaphore.. (but it did not unblock
-Player-A because he was not actually blocked).
-Player-B thread continued its execution, called _wait,
-was counted as second waiter BUT was allowed to slip
-through opened semaphore gate (which was opened for
-Player-B) and received his own signal. Player B remained
-blocked followed by Player A. Deadlock happened which
-lasted until main thread came in and said game over.
-
-It seems to me that the implementation fails to
-correctly implement the following statement
-from specification:
-
-http://www.opengroup.org/
-onlinepubs/007908799/xsh/pthread_cond_wait.html
-
-"These functions atomically release mutex and cause
-the calling thread to block on the condition variable
-cond; atomically here means "atomically with respect
-to access by another thread to the mutex and then the
-condition variable". That is, if another thread is
-able to acquire the mutex after the about-to-block
-thread has released it, then a subsequent call to
-pthread_cond_signal() or pthread_cond_broadcast()
-in that thread behaves as if it were issued after
-the about-to-block thread has blocked."
-
-Question: Am I right?
-
-(I produced the program output above by simply
-adding ?Sleep( 1 )?:
-
-================
-waiting threads:
-================
-
-{ /** Critical Section
-
- inc cond.waiters_count
-
-}
-
- /*
- /* Atomic only if using Win32 SignalObjectAndWait
- /*
- cond.mtx.release
-
-Sleep( 1 ); // Win32
-
- /*** ^^-- A THREAD WHICH DID SIGNAL MAY ACQUIRE THE MUTEX,
- /*** GO INTO WAIT ON THE SAME CONDITION AND OVERTAKE
- /*** ORIGINAL WAITER(S) CONSUMING ITS OWN SIGNAL!
-
- cond.sem.wait
-
-to the source code of pthread-win32 implementation:
-
-http://sources.redhat.com/cgi-bin/cvsweb.cgi/pthreads/
-condvar.c?rev=1.36&content-type=text/
-x-cvsweb-markup&cvsroot=pthreads-win32
-
-
- /*
- * We keep the lock held just long enough to increment the count of
- * waiters by one (above).
- * Note that we can't keep it held across the
- * call to sem_wait since that will deadlock other calls
- * to pthread_cond_signal
- */
- cleanup_args.mutexPtr = mutex;
- cleanup_args.cv = cv;
- cleanup_args.resultPtr = &result;
-
- pthread_cleanup_push (ptw32_cond_wait_cleanup, (void *)
-&cleanup_args);
-
- if ((result = pthread_mutex_unlock (mutex)) == 0)
- {((result
-Sleep( 1 ); // @AT
-
- /*
- * Wait to be awakened by
- * pthread_cond_signal, or
- * pthread_cond_broadcast, or
- * a timeout
- *
- * Note:
- * ptw32_sem_timedwait is a cancelation point,
- * hence providing the
- * mechanism for making pthread_cond_wait a cancelation
- * point. We use the cleanup mechanism to ensure we
- * re-lock the mutex and decrement the waiters count
- * if we are canceled.
- */
- if (ptw32_sem_timedwait (&(cv->sema), abstime) == -1) {
- result = errno;
- }
- }
-
- pthread_cleanup_pop (1); /* Always cleanup */
-
-
-BTW, on my system (2 CPUs) I can manage to get
-signals lost even without any source code modification
-if I run the tennis program many times in different
-shell sessions.
-.
-.
-.
-David Schwartz <davids@webmaster.com> wrote:
->terekhov@my-deja.com wrote:
->
->> well, it might be that the program is in fact buggy.
->> but you did not show me any bug.
->
->You're right. I was close but not dead on. I was correct, however,
->that the code is buggy because it uses 'pthread_cond_signal' even
->though not any thread waiting on the condition variable can do the
->job. I was wrong in which thread could be waiting on the cv but
->unable to do the job.
-
-Okay, lets change 'pthread_cond_signal' to 'pthread_cond_broadcast'
-but also add some noise from main() right before declaring the game
-to be over (I need it in order to demonstrate another problem of
-pthread-win32/ACE implementations - broadcast deadlock)...
-.
-.
-.
-It is my understanding of POSIX conditions,
-that on correct implementation added noise
-in form of unnecessary broadcasts from main,
-should not break the tennis program. The
-only 'side effect' of added noise on correct
-implementation would be 'spurious wakeups' of
-players (in fact they are not spurious,
-players just see them as spurious) unblocked,
-not by another player but by main before
-another player had a chance to acquire the
-mutex and change the game state variable:
-.
-.
-.
-
-PLAYER-B
-
-PLAYER-A
-
----Noise ON...
-
-PLAYER-B
-
-PLAYER-A
-
-.
-.
-.
-
-PLAYER-B
-
-PLAYER-A
-
-----PLAYER-A: SPURIOUS WAKEUP!!!
-
-PLAYER-B
-
-PLAYER-A
-
----Noise OFF
-
-PLAYER-B
-
----Stopping the game...
-
-PLAYER-A GONE
-
-PLAYER-B GONE
-
-GAME OVER
-
-H:\SA\UXX\pt\PTHREADS\TESTS>
-
-On pthread-win32/ACE implementations the
-program could stall:
-
-.
-.
-.
-
-PLAYER-A
-
-PLAYER-B
-
-PLAYER-A
-
-PLAYER-B
-
-PLAYER-A
-
-PLAYER-B
-
-PLAYER-A
-
-PLAYER-B
-
----Noise ON...
-
-PLAYER-A
-
----Noise OFF
-^C
-H:\SA\UXX\pt\PTHREADS\TESTS>
-
-
-The implementation has problems:
-
-================
-waiting threads:
-================
-
-{ /** Critical Section
-
- inc cond.waiters_count
-
-}
-
- /*
- /* Atomic only if using Win32 SignalObjectAndWait
- /*
- cond.mtx.release
- cond.sem.wait
-
- /*** ^^-- WAITER CAN BE PREEMPTED AFTER BEING UNBLOCKED...
-
-{ /** Critical Section
-
- dec cond.waiters_count
-
- /*** ^^- ...AND BEFORE DECREMENTING THE COUNT (1)
-
- last_waiter = ( cond.was_broadcast &&
- cond.waiters_count == 0 )
-
- if ( last_waiter )
-
- cond.was_broadcast = FALSE
-
- endif
-
-}
-
- if ( last_waiter )
-
- /*
- /* Atomic only if using Win32 SignalObjectAndWait
- /*
- cond.auto_reset_event_or_sem.post /* Event for Win32
- cond.mtx.acquire
-
- /*** ^^-- ...AND BEFORE CALL TO mtx.acquire (2)
-
- /*** ^^-- NESTED BROADCASTS RESULT IN A DEADLOCK
-
-
- else
-
- cond.mtx.acquire
-
- /*** ^^-- ...AND BEFORE CALL TO mtx.acquire (3)
-
- endif
-
-
-==================
-broadcast threads:
-==================
-
-{ /** Critical Section
-
- waiters_count = cond.waiters_count
-
- if ( waiters_count != 0 )
-
- cond.was_broadcast = TRUE
-
- endif
-
-}
-
-if ( waiters_count != 0 )
-
- cond.sem.post waiters_count
-
- /*** ^^^^^--- SPURIOUS WAKEUPS DUE TO (1)
-
- cond.auto_reset_event_or_sem.wait /* Event for Win32
-
- /*** ^^^^^--- DEADLOCK FOR FURTHER BROADCASTS IF THEY
- HAPPEN TO GO INTO WAIT WHILE PREVIOUS
- BROADCAST IS STILL IN PROGRESS/WAITING
-
-endif
-
-a) cond.waiters_count does not accurately reflect
-number of waiters blocked on semaphore - that could
-result (in the time window when counter is not accurate)
-in spurios wakeups organised by subsequent _signals
-and _broadcasts. From standard compliance point of view
-that is OK but that could be a real problem from
-performance/efficiency point of view.
-
-b) If subsequent broadcast happen to go into wait on
-cond.auto_reset_event_or_sem before previous
-broadcast was unblocked from cond.auto_reset_event_or_sem
-by its last waiter, one of two blocked threads will
-remain blocked because last_waiter processing code
-fails to unblock both threads.
-
-In the situation with tennisb.c the Player-B was put
-in a deadlock by noise (broadcast) coming from main
-thread. And since Player-B holds the game state
-mutex when it calls broadcast, the whole program
-stalled: Player-A was deadlocked on mutex and
-main thread after finishing with producing the noise
-was deadlocked on mutex too (needed to declare the
-game over)
-
-(I produced the program output above by simply
-adding ?Sleep( 1 )?:
-
-==================
-broadcast threads:
-==================
-
-{ /** Critical Section
-
- waiters_count = cond.waiters_count
-
- if ( waiters_count != 0 )
-
- cond.was_broadcast = TRUE
-
- endif
-
-}
-
-if ( waiters_count != 0 )
-
-Sleep( 1 ); //Win32
-
- cond.sem.post waiters_count
-
- /*** ^^^^^--- SPURIOUS WAKEUPS DUE TO (1)
-
- cond.auto_reset_event_or_sem.wait /* Event for Win32
-
- /*** ^^^^^--- DEADLOCK FOR FURTHER BROADCASTS IF THEY
- HAPPEN TO GO INTO WAIT WHILE PREVIOUS
- BROADCAST IS STILL IN PROGRESS/WAITING
-
-endif
-
-to the source code of pthread-win32 implementation:
-
-http://sources.redhat.com/cgi-bin/cvsweb.cgi/pthreads/
-condvar.c?rev=1.36&content-type=text/
-x-cvsweb-markup&cvsroot=pthreads-win32
-
- if (wereWaiters)
- {(wereWaiters)sroot=pthreads-win32eb.cgi/pthreads/Yem...m
- /*
- * Wake up all waiters
- */
-
-Sleep( 1 ); //@AT
-
-#ifdef NEED_SEM
-
- result = (ptw32_increase_semaphore( &cv->sema, cv->waiters )
- ? 0
- : EINVAL);
-
-#else /* NEED_SEM */
-
- result = (ReleaseSemaphore( cv->sema, cv->waiters, NULL )
- ? 0
- : EINVAL);
-
-#endif /* NEED_SEM */
-
- }
-
- (void) pthread_mutex_unlock(&(cv->waitersLock));
-
- if (wereWaiters && result == 0)
- {(wereWaiters
- /*
- * Wait for all the awakened threads to acquire their part of
- * the counting semaphore
- */
-
- if (WaitForSingleObject (cv->waitersDone, INFINITE)
- == WAIT_OBJECT_0)
- {
- result = 0;
- }
- else
- {
- result = EINVAL;
- }
-
- }
-
- return (result);
-
-}
-
-BTW, on my system (2 CPUs) I can manage to get
-the program stalled even without any source code
-modification if I run the tennisb program many
-times in different shell sessions.
-
-===================
-pthread-win32 patch
-===================
-struct pthread_cond_t_ {
- long nWaitersBlocked; /* Number of threads blocked
-*/
- long nWaitersUnblocked; /* Number of threads unblocked
-*/
- long nWaitersToUnblock; /* Number of threads to unblock
-*/
- sem_t semBlockQueue; /* Queue up threads waiting for the
-*/
- /* condition to become signalled
-*/
- sem_t semBlockLock; /* Semaphore that guards access to
-*/
- /* | waiters blocked count/block queue
-*/
- /* +-> Mandatory Sync.LEVEL-1
-*/
- pthread_mutex_t mtxUnblockLock; /* Mutex that guards access to
-*/
- /* | waiters (to)unblock(ed) counts
-*/
- /* +-> Optional* Sync.LEVEL-2
-*/
-}; /* Opt*) for _timedwait and
-cancellation*/
-
-int
-pthread_cond_init (pthread_cond_t * cond, const pthread_condattr_t * attr)
- int result = EAGAIN;
- pthread_cond_t cv = NULL;
-
- if (cond == NULL)
- {(cond
- return EINVAL;
- }
-
- if ((attr != NULL && *attr != NULL) &&
- ((*attr)->pshared == PTHREAD_PROCESS_SHARED))
- {
- /*
- * Creating condition variable that can be shared between
- * processes.
- */
- result = ENOSYS;
-
- goto FAIL0;
- }
-
- cv = (pthread_cond_t) calloc (1, sizeof (*cv));
-
- if (cv == NULL)
- {(cv
- result = ENOMEM;
- goto FAIL0;
- }
-
- cv->nWaitersBlocked = 0;
- cv->nWaitersUnblocked = 0;
- cv->nWaitersToUnblock = 0;
-
- if (sem_init (&(cv->semBlockLock), 0, 1) != 0)
- {(sem_init
- goto FAIL0;
- }
-
- if (sem_init (&(cv->semBlockQueue), 0, 0) != 0)
- {(sem_init
- goto FAIL1;
- }
-
- if (pthread_mutex_init (&(cv->mtxUnblockLock), 0) != 0)
- {(pthread_mutex_init
- goto FAIL2;
- }
-
-
- result = 0;
-
- goto DONE;
-
- /*
- * -------------
- * Failed...
- * -------------
- */
-FAIL2:
- (void) sem_destroy (&(cv->semBlockQueue));
-
-FAIL1:
- (void) sem_destroy (&(cv->semBlockLock));
-
-FAIL0:
-DONE:
- *cond = cv;
-
- return (result);
-
-} /* pthread_cond_init */
-
-int
-pthread_cond_destroy (pthread_cond_t * cond)
-{
- int result = 0;
- pthread_cond_t cv;
-
- /*
- * Assuming any race condition here is harmless.
- */
- if (cond == NULL
- || *cond == NULL)
- {
- return EINVAL;
- }
-
- if (*cond != (pthread_cond_t) PTW32_OBJECT_AUTO_INIT)
- {(*cond
- cv = *cond;
-
- /*
- * Synchronize access to waiters blocked count (LEVEL-1)
- */
- if (sem_wait(&(cv->semBlockLock)) != 0)
- {(sem_wait(&(cv->semBlockLock))
- return errno;
- }
-
- /*
- * Synchronize access to waiters (to)unblock(ed) counts (LEVEL-2)
- */
- if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0)
- {((result
- (void) sem_post(&(cv->semBlockLock));
- return result;
- }
-
- /*
- * Check whether cv is still busy (still has waiters blocked)
- */
- if (cv->nWaitersBlocked - cv->nWaitersUnblocked > 0)
- {(cv->nWaitersBlocked
- (void) sem_post(&(cv->semBlockLock));
- (void) pthread_mutex_unlock(&(cv->mtxUnblockLock));
- return EBUSY;
- }
-
- /*
- * Now it is safe to destroy
- */
- (void) sem_destroy (&(cv->semBlockLock));
- (void) sem_destroy (&(cv->semBlockQueue));
- (void) pthread_mutex_unlock (&(cv->mtxUnblockLock));
- (void) pthread_mutex_destroy (&(cv->mtxUnblockLock));
-
- free(cv);
- *cond = NULL;
- }
- else
- {
- /*
- * See notes in ptw32_cond_check_need_init() above also.
- */
- EnterCriticalSection(&ptw32_cond_test_init_lock);
-
- /*
- * Check again.
- */
- if (*cond == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT)
- {(*cond
- /*
- * This is all we need to do to destroy a statically
- * initialised cond that has not yet been used (initialised).
- * If we get to here, another thread
- * waiting to initialise this cond will get an EINVAL.
- */
- *cond = NULL;
- }
- else
- {
- /*
- * The cv has been initialised while we were waiting
- * so assume it's in use.
- */
- result = EBUSY;
- }
-
- LeaveCriticalSection(&ptw32_cond_test_init_lock);
- }
-
- return (result);
-}
-
-/*
- * Arguments for cond_wait_cleanup, since we can only pass a
- * single void * to it.
- */
-typedef struct {
- pthread_mutex_t * mutexPtr;
- pthread_cond_t cv;
- int * resultPtr;
-} ptw32_cond_wait_cleanup_args_t;
-
-static void
-ptw32_cond_wait_cleanup(void * args)
-{
- ptw32_cond_wait_cleanup_args_t * cleanup_args =
-(ptw32_cond_wait_cleanup_args_t *) args;
- pthread_cond_t cv = cleanup_args->cv;
- int * resultPtr = cleanup_args->resultPtr;
- int eLastSignal; /* enum: 1=yes 0=no -1=cancelled/timedout w/o signal(s)
-*/
- int result;
-
- /*
- * Whether we got here as a result of signal/broadcast or because of
- * timeout on wait or thread cancellation we indicate that we are no
- * longer waiting. The waiter is responsible for adjusting waiters
- * (to)unblock(ed) counts (protected by unblock lock).
- * Unblock lock/Sync.LEVEL-2 supports _timedwait and cancellation.
- */
- if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0)
- {((result
- *resultPtr = result;
- return;
- }
-
- cv->nWaitersUnblocked++;
-
- eLastSignal = (cv->nWaitersToUnblock == 0) ?
- -1 : (--cv->nWaitersToUnblock == 0);
-
- /*
- * No more LEVEL-2 access to waiters (to)unblock(ed) counts needed
- */
- if ((result = pthread_mutex_unlock(&(cv->mtxUnblockLock))) != 0)
- {((result
- *resultPtr = result;
- return;
- }
-
- /*
- * If last signal...
- */
- if (eLastSignal == 1)
- {(eLastSignal
- /*
- * ...it means that we have end of 'atomic' signal/broadcast
- */
- if (sem_post(&(cv->semBlockLock)) != 0)
- {(sem_post(&(cv->semBlockLock))
- *resultPtr = errno;
- return;
- }
- }
- /*
- * If not last signal and not timed out/cancelled wait w/o signal...
- */
- else if (eLastSignal == 0)
- {
- /*
- * ...it means that next waiter can go through semaphore
- */
- if (sem_post(&(cv->semBlockQueue)) != 0)
- {(sem_post(&(cv->semBlockQueue))
- *resultPtr = errno;
- return;
- }
- }
-
- /*
- * XSH: Upon successful return, the mutex has been locked and is owned
- * by the calling thread
- */
- if ((result = pthread_mutex_lock(cleanup_args->mutexPtr)) != 0)
- {((result
- *resultPtr = result;
- }
-
-} /* ptw32_cond_wait_cleanup */
-
-static int
-ptw32_cond_timedwait (pthread_cond_t * cond,
- pthread_mutex_t * mutex,
- const struct timespec *abstime)
-{
- int result = 0;
- pthread_cond_t cv;
- ptw32_cond_wait_cleanup_args_t cleanup_args;
-
- if (cond == NULL || *cond == NULL)
- {(cond
- return EINVAL;
- }
-
- /*
- * We do a quick check to see if we need to do more work
- * to initialise a static condition variable. We check
- * again inside the guarded section of ptw32_cond_check_need_init()
- * to avoid race conditions.
- */
- if (*cond == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT)
- {(*cond
- result = ptw32_cond_check_need_init(cond);
- }
-
- if (result != 0 && result != EBUSY)
- {(result
- return result;
- }
-
- cv = *cond;
-
- /*
- * Synchronize access to waiters blocked count (LEVEL-1)
- */
- if (sem_wait(&(cv->semBlockLock)) != 0)
- {(sem_wait(&(cv->semBlockLock))
- return errno;
- }
-
- cv->nWaitersBlocked++;
-
- /*
- * Thats it. Counted means waiting, no more access needed
- */
- if (sem_post(&(cv->semBlockLock)) != 0)
- {(sem_post(&(cv->semBlockLock))
- return errno;
- }
-
- /*
- * Setup this waiter cleanup handler
- */
- cleanup_args.mutexPtr = mutex;
- cleanup_args.cv = cv;
- cleanup_args.resultPtr = &result;
-
- pthread_cleanup_push (ptw32_cond_wait_cleanup, (void *) &cleanup_args);
-
- /*
- * Now we can release 'mutex' and...
- */
- if ((result = pthread_mutex_unlock (mutex)) == 0)
- {((result
-
- /*
- * ...wait to be awakened by
- * pthread_cond_signal, or
- * pthread_cond_broadcast, or
- * timeout, or
- * thread cancellation
- *
- * Note:
- *
- * ptw32_sem_timedwait is a cancellation point,
- * hence providing the mechanism for making
- * pthread_cond_wait a cancellation point.
- * We use the cleanup mechanism to ensure we
- * re-lock the mutex and adjust (to)unblock(ed) waiters
- * counts if we are cancelled, timed out or signalled.
- */
- if (ptw32_sem_timedwait (&(cv->semBlockQueue), abstime) != 0)
- {(ptw32_sem_timedwait
- result = errno;
- }
- }
-
- /*
- * Always cleanup
- */
- pthread_cleanup_pop (1);
-
-
- /*
- * "result" can be modified by the cleanup handler.
- */
- return (result);
-
-} /* ptw32_cond_timedwait */
-
-
-static int
-ptw32_cond_unblock (pthread_cond_t * cond,
- int unblockAll)
-{
- int result;
- pthread_cond_t cv;
-
- if (cond == NULL || *cond == NULL)
- {(cond
- return EINVAL;
- }
-
- cv = *cond;
-
- /*
- * No-op if the CV is static and hasn't been initialised yet.
- * Assuming that any race condition is harmless.
- */
- if (cv == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT)
- {(cv
- return 0;
- }
-
- /*
- * Synchronize access to waiters blocked count (LEVEL-1)
- */
- if (sem_wait(&(cv->semBlockLock)) != 0)
- {(sem_wait(&(cv->semBlockLock))
- return errno;
- }
-
- /*
- * Synchronize access to waiters (to)unblock(ed) counts (LEVEL-2)
- * This sync.level supports _timedwait and cancellation
- */
- if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0)
- {((result
- return result;
- }
-
- /*
- * Adjust waiters blocked and unblocked counts (collect garbage)
- */
- if (cv->nWaitersUnblocked != 0)
- {(cv->nWaitersUnblocked
- cv->nWaitersBlocked -= cv->nWaitersUnblocked;
- cv->nWaitersUnblocked = 0;
- }
-
- /*
- * If (after adjustment) there are still some waiters blocked counted...
- */
- if ( cv->nWaitersBlocked > 0)
- {(
- /*
- * We will unblock first waiter and leave semBlockLock/LEVEL-1 locked
- * LEVEL-1 access is left disabled until last signal/unblock
-completes
- */
- cv->nWaitersToUnblock = (unblockAll) ? cv->nWaitersBlocked : 1;
-
- /*
- * No more LEVEL-2 access to waiters (to)unblock(ed) counts needed
- * This sync.level supports _timedwait and cancellation
- */
- if ((result = pthread_mutex_unlock(&(cv->mtxUnblockLock))) != 0)
- {((result
- return result;
- }
-
-
- /*
- * Now, with LEVEL-2 lock released let first waiter go through
-semaphore
- */
- if (sem_post(&(cv->semBlockQueue)) != 0)
- {(sem_post(&(cv->semBlockQueue))
- return errno;
- }
- }
- /*
- * No waiter blocked - no more LEVEL-1 access to blocked count needed...
- */
- else if (sem_post(&(cv->semBlockLock)) != 0)
- {
- return errno;
- }
- /*
- * ...and no more LEVEL-2 access to waiters (to)unblock(ed) counts needed
-too
- * This sync.level supports _timedwait and cancellation
- */
- else
- {
- result = pthread_mutex_unlock(&(cv->mtxUnblockLock));
- }
-
- return(result);
-
-} /* ptw32_cond_unblock */
-
-int
-pthread_cond_wait (pthread_cond_t * cond,
- pthread_mutex_t * mutex)
-{
- /* The NULL abstime arg means INFINITE waiting. */
- return(ptw32_cond_timedwait(cond, mutex, NULL));
-} /* pthread_cond_wait */
-
-
-int
-pthread_cond_timedwait (pthread_cond_t * cond,
- pthread_mutex_t * mutex,
- const struct timespec *abstime)
-{
- if (abstime == NULL)
- {(abstime
- return EINVAL;
- }
-
- return(ptw32_cond_timedwait(cond, mutex, abstime));
-} /* pthread_cond_timedwait */
-
-
-int
-pthread_cond_signal (pthread_cond_t * cond)
-{
- /* The '0'(FALSE) unblockAll arg means unblock ONE waiter. */
- return(ptw32_cond_unblock(cond, 0));
-} /* pthread_cond_signal */
-
-int
-pthread_cond_broadcast (pthread_cond_t * cond)
-{
- /* The '1'(TRUE) unblockAll arg means unblock ALL waiters. */
- return(ptw32_cond_unblock(cond, 1));
-} /* pthread_cond_broadcast */
-
-
-
-
-TEREKHOV@de.ibm.com on 17.01.2001 01:00:57
-
-Please respond to TEREKHOV@de.ibm.com
-
-To: pthreads-win32@sourceware.cygnus.com
-cc: schmidt@uci.edu
-Subject: win32 conditions: sem+counter+event = broadcast_deadlock +
- spur.wakeup/unfairness/incorrectness ??
-
-
-
-
-
-
-
-Hi,
-
-Problem 1: broadcast_deadlock
-
-It seems that current implementation does not provide "atomic"
-broadcasts. That may lead to "nested" broadcasts... and it seems
-that nested case is not handled correctly -> producing a broadcast
-DEADLOCK as a result.
-
-Scenario:
-
-N (>1) waiting threads W1..N are blocked (in _wait) on condition's
-semaphore.
-
-Thread B1 calls pthread_cond_broadcast, which results in "releasing" N
-W threads via incrementing semaphore counter by N (stored in
-cv->waiters) BUT cv->waiters counter does not change!! The caller
-thread B1 remains blocked on cv->waitersDone event (auto-reset!!) BUT
-condition is not protected from starting another broadcast (when called
-on another thread) while still waiting for the "old" broadcast to
-complete on thread B1.
-
-M (>=0, <N) W threads are fast enough to go thru their _wait call and
-decrement cv->waiters counter.
-
-L (N-M) "late" waiter W threads are a) still blocked/not returned from
-their semaphore wait call or b) were preempted after sem_wait but before
-lock( &cv->waitersLock ) or c) are blocked on cv->waitersLock.
-
-cv->waiters is still > 0 (= L).
-
-Another thread B2 (or some W thread from M group) calls
-pthread_cond_broadcast and gains access to counter... neither a) nor b)
-prevent thread B2 in pthread_cond_broadcast from gaining access to
-counter and starting another broadcast ( for c) - it depends on
-cv->waitersLock scheduling rules: FIFO=OK, PRTY=PROBLEM,... )
-
-That call to pthread_cond_broadcast (on thread B2) will result in
-incrementing semaphore by cv->waiters (=L) which is INCORRECT (all
-W1..N were in fact already released by thread B1) and waiting on
-_auto-reset_ event cv->waitersDone which is DEADLY WRONG (produces a
-deadlock)...
-
-All late W1..L threads now have a chance to complete their _wait call.
-Last W_L thread sets an auto-reselt event cv->waitersDone which will
-release either B1 or B2 leaving one of B threads in a deadlock.
-
-Problem 2: spur.wakeup/unfairness/incorrectness
-
-It seems that:
-
-a) because of the same problem with counter which does not reflect the
-actual number of NOT RELEASED waiters, the signal call may increment
-a semaphore counter w/o having a waiter blocked on it. That will result
-in (best case) spurious wake ups - performance degradation due to
-unnecessary context switches and predicate re-checks and (in worth case)
-unfairness/incorrectness problem - see b)
-
-b) neither signal nor broadcast prevent other threads - "new waiters"
-(and in the case of signal, the caller thread as well) from going into
-_wait and overtaking "old" waiters (already released but still not returned
-from sem_wait on condition's semaphore). Win semaphore just [API DOC]:
-"Maintains a count between zero and some maximum value, limiting the number
-of threads that are simultaneously accessing a shared resource." Calling
-ReleaseSemaphore does not imply (at least not documented) that on return
-from ReleaseSemaphore all waiters will in fact become released (returned
-from their Wait... call) and/or that new waiters calling Wait... afterwards
-will become less importance. It is NOT documented to be an atomic release
-of
-waiters... And even if it would be there is still a problem with a thread
-being preempted after Wait on semaphore and before Wait on cv->waitersLock
-and scheduling rules for cv->waitersLock itself
-(??WaitForMultipleObjects??)
-That may result in unfairness/incorrectness problem as described
-for SetEvent impl. in "Strategies for Implementing POSIX Condition
-Variables
-on Win32": http://www.cs.wustl.edu/~schmidt/win32-cv-1.html
-
-Unfairness -- The semantics of the POSIX pthread_cond_broadcast function is
-to wake up all threads currently blocked in wait calls on the condition
-variable. The awakened threads then compete for the external_mutex. To
-ensure
-fairness, all of these threads should be released from their
-pthread_cond_wait calls and allowed to recheck their condition expressions
-before other threads can successfully complete a wait on the condition
-variable.
-
-Unfortunately, the SetEvent implementation above does not guarantee that
-all
-threads sleeping on the condition variable when cond_broadcast is called
-will
-acquire the external_mutex and check their condition expressions. Although
-the Pthreads specification does not mandate this degree of fairness, the
-lack of fairness can cause starvation.
-
-To illustrate the unfairness problem, imagine there are 2 threads, C1 and
-C2,
-that are blocked in pthread_cond_wait on condition variable not_empty_ that
-is guarding a thread-safe message queue. Another thread, P1 then places two
-messages onto the queue and calls pthread_cond_broadcast. If C1 returns
-from
-pthread_cond_wait, dequeues and processes the message, and immediately
-waits
-again then it and only it may end up acquiring both messages. Thus, C2 will
-never get a chance to dequeue a message and run.
-
-The following illustrates the sequence of events:
-
-1. Thread C1 attempts to dequeue and waits on CV non_empty_
-2. Thread C2 attempts to dequeue and waits on CV non_empty_
-3. Thread P1 enqueues 2 messages and broadcasts to CV not_empty_
-4. Thread P1 exits
-5. Thread C1 wakes up from CV not_empty_, dequeues a message and runs
-6. Thread C1 waits again on CV not_empty_, immediately dequeues the 2nd
- message and runs
-7. Thread C1 exits
-8. Thread C2 is the only thread left and blocks forever since
- not_empty_ will never be signaled
-
-Depending on the algorithm being implemented, this lack of fairness may
-yield
-concurrent programs that have subtle bugs. Of course, application
-developers
-should not rely on the fairness semantics of pthread_cond_broadcast.
-However,
-there are many cases where fair implementations of condition variables can
-simplify application code.
-
-Incorrectness -- A variation on the unfairness problem described above
-occurs
-when a third consumer thread, C3, is allowed to slip through even though it
-was not waiting on condition variable not_empty_ when a broadcast occurred.
-
-To illustrate this, we will use the same scenario as above: 2 threads, C1
-and
-C2, are blocked dequeuing messages from the message queue. Another thread,
-P1
-then places two messages onto the queue and calls pthread_cond_broadcast.
-C1
-returns from pthread_cond_wait, dequeues and processes the message. At this
-time, C3 acquires the external_mutex, calls pthread_cond_wait and waits on
-the events in WaitForMultipleObjects. Since C2 has not had a chance to run
-yet, the BROADCAST event is still signaled. C3 then returns from
-WaitForMultipleObjects, and dequeues and processes the message in the
-queue.
-Thus, C2 will never get a chance to dequeue a message and run.
-
-The following illustrates the sequence of events:
-
-1. Thread C1 attempts to dequeue and waits on CV non_empty_
-2. Thread C2 attempts to dequeue and waits on CV non_empty_
-3. Thread P1 enqueues 2 messages and broadcasts to CV not_empty_
-4. Thread P1 exits
-5. Thread C1 wakes up from CV not_empty_, dequeues a message and runs
-6. Thread C1 exits
-7. Thread C3 waits on CV not_empty_, immediately dequeues the 2nd
- message and runs
-8. Thread C3 exits
-9. Thread C2 is the only thread left and blocks forever since
- not_empty_ will never be signaled
-
-In the above case, a thread that was not waiting on the condition variable
-when a broadcast occurred was allowed to proceed. This leads to incorrect
-semantics for a condition variable.
-
-
-COMMENTS???
-
-regards,
-alexander.
-
------------------------------------------------------------------------------
-
-Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_*
- implementation questions
-Date: Wed, 21 Feb 2001 11:54:47 +0100
-From: TEREKHOV@de.ibm.com
-To: lthomas@arbitrade.com
-CC: rpj@ise.canberra.edu.au, Thomas Pfaff <tpfaff@gmx.net>,
- Nanbor Wang <nanbor@cs.wustl.edu>
-
-Hi Louis,
-
-generation number 8..
-
-had some time to revisit timeouts/spurious wakeup problem..
-found some bugs (in 7.b/c/d) and something to improve
-(7a - using IPC semaphores but it should speedup Win32
-version as well).
-
-regards,
-alexander.
-
----------- Algorithm 8a / IMPL_SEM,UNBLOCK_STRATEGY == UNBLOCK_ALL ------
-given:
-semBlockLock - bin.semaphore
-semBlockQueue - semaphore
-mtxExternal - mutex or CS
-mtxUnblockLock - mutex or CS
-nWaitersGone - int
-nWaitersBlocked - int
-nWaitersToUnblock - int
-
-wait( timeout ) {
-
- [auto: register int result ] // error checking omitted
- [auto: register int nSignalsWasLeft ]
- [auto: register int nWaitersWasGone ]
-
- sem_wait( semBlockLock );
- nWaitersBlocked++;
- sem_post( semBlockLock );
-
- unlock( mtxExternal );
- bTimedOut = sem_wait( semBlockQueue,timeout );
-
- lock( mtxUnblockLock );
- if ( 0 != (nSignalsWasLeft = nWaitersToUnblock) ) {
- if ( bTimeout ) { // timeout (or canceled)
- if ( 0 != nWaitersBlocked ) {
- nWaitersBlocked--;
- }
- else {
- nWaitersGone++; // count spurious wakeups
- }
- }
- if ( 0 == --nWaitersToUnblock ) {
- if ( 0 != nWaitersBlocked ) {
- sem_post( semBlockLock ); // open the gate
- nSignalsWasLeft = 0; // do not open the gate below
-again
- }
- else if ( 0 != (nWaitersWasGone = nWaitersGone) ) {
- nWaitersGone = 0;
- }
- }
- }
- else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious
-semaphore :-)
- sem_wait( semBlockLock );
- nWaitersBlocked -= nWaitersGone; // something is going on here -
-test of timeouts? :-)
- sem_post( semBlockLock );
- nWaitersGone = 0;
- }
- unlock( mtxUnblockLock );
-
- if ( 1 == nSignalsWasLeft ) {
- if ( 0 != nWaitersWasGone ) {
- // sem_adjust( -nWaitersWasGone );
- while ( nWaitersWasGone-- ) {
- sem_wait( semBlockLock ); // better now than spurious
-later
- }
- }
- sem_post( semBlockLock ); // open the gate
- }
-
- lock( mtxExternal );
-
- return ( bTimedOut ) ? ETIMEOUT : 0;
-}
-
-signal(bAll) {
-
- [auto: register int result ]
- [auto: register int nSignalsToIssue]
-
- lock( mtxUnblockLock );
-
- if ( 0 != nWaitersToUnblock ) { // the gate is closed!!!
- if ( 0 == nWaitersBlocked ) { // NO-OP
- return unlock( mtxUnblockLock );
- }
- if (bAll) {
- nWaitersToUnblock += nSignalsToIssue=nWaitersBlocked;
- nWaitersBlocked = 0;
- }
- else {
- nSignalsToIssue = 1;
- nWaitersToUnblock++;
- nWaitersBlocked--;
- }
- }
- else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION!
- sem_wait( semBlockLock ); // close the gate
- if ( 0 != nWaitersGone ) {
- nWaitersBlocked -= nWaitersGone;
- nWaitersGone = 0;
- }
- if (bAll) {
- nSignalsToIssue = nWaitersToUnblock = nWaitersBlocked;
- nWaitersBlocked = 0;
- }
- else {
- nSignalsToIssue = nWaitersToUnblock = 1;
- nWaitersBlocked--;
- }
- }
- else { // NO-OP
- return unlock( mtxUnblockLock );
- }
-
- unlock( mtxUnblockLock );
- sem_post( semBlockQueue,nSignalsToIssue );
- return result;
-}
-
----------- Algorithm 8b / IMPL_SEM,UNBLOCK_STRATEGY == UNBLOCK_ONEBYONE
-------
-given:
-semBlockLock - bin.semaphore
-semBlockQueue - bin.semaphore
-mtxExternal - mutex or CS
-mtxUnblockLock - mutex or CS
-nWaitersGone - int
-nWaitersBlocked - int
-nWaitersToUnblock - int
-
-wait( timeout ) {
-
- [auto: register int result ] // error checking omitted
- [auto: register int nWaitersWasGone ]
- [auto: register int nSignalsWasLeft ]
-
- sem_wait( semBlockLock );
- nWaitersBlocked++;
- sem_post( semBlockLock );
-
- unlock( mtxExternal );
- bTimedOut = sem_wait( semBlockQueue,timeout );
-
- lock( mtxUnblockLock );
- if ( 0 != (nSignalsWasLeft = nWaitersToUnblock) ) {
- if ( bTimeout ) { // timeout (or canceled)
- if ( 0 != nWaitersBlocked ) {
- nWaitersBlocked--;
- nSignalsWasLeft = 0; // do not unblock next waiter
-below (already unblocked)
- }
- else {
- nWaitersGone = 1; // spurious wakeup pending!!
- }
- }
- if ( 0 == --nWaitersToUnblock &&
- if ( 0 != nWaitersBlocked ) {
- sem_post( semBlockLock ); // open the gate
- nSignalsWasLeft = 0; // do not open the gate below
-again
- }
- else if ( 0 != (nWaitersWasGone = nWaitersGone) ) {
- nWaitersGone = 0;
- }
- }
- }
- else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious
-semaphore :-)
- sem_wait( semBlockLock );
- nWaitersBlocked -= nWaitersGone; // something is going on here -
-test of timeouts? :-)
- sem_post( semBlockLock );
- nWaitersGone = 0;
- }
- unlock( mtxUnblockLock );
-
- if ( 1 == nSignalsWasLeft ) {
- if ( 0 != nWaitersWasGone ) {
- // sem_adjust( -1 );
- sem_wait( semBlockQueue ); // better now than spurious
-later
- }
- sem_post( semBlockLock ); // open the gate
- }
- else if ( 0 != nSignalsWasLeft ) {
- sem_post( semBlockQueue ); // unblock next waiter
- }
-
- lock( mtxExternal );
-
- return ( bTimedOut ) ? ETIMEOUT : 0;
-}
-
-signal(bAll) {
-
- [auto: register int result ]
-
- lock( mtxUnblockLock );
-
- if ( 0 != nWaitersToUnblock ) { // the gate is closed!!!
- if ( 0 == nWaitersBlocked ) { // NO-OP
- return unlock( mtxUnblockLock );
- }
- if (bAll) {
- nWaitersToUnblock += nWaitersBlocked;
- nWaitersBlocked = 0;
- }
- else {
- nWaitersToUnblock++;
- nWaitersBlocked--;
- }
- unlock( mtxUnblockLock );
- }
- else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION!
- sem_wait( semBlockLock ); // close the gate
- if ( 0 != nWaitersGone ) {
- nWaitersBlocked -= nWaitersGone;
- nWaitersGone = 0;
- }
- if (bAll) {
- nWaitersToUnblock = nWaitersBlocked;
- nWaitersBlocked = 0;
- }
- else {
- nWaitersToUnblock = 1;
- nWaitersBlocked--;
- }
- unlock( mtxUnblockLock );
- sem_post( semBlockQueue );
- }
- else { // NO-OP
- unlock( mtxUnblockLock );
- }
-
- return result;
-}
-
----------- Algorithm 8c / IMPL_EVENT,UNBLOCK_STRATEGY == UNBLOCK_ONEBYONE
----------
-given:
-hevBlockLock - auto-reset event
-hevBlockQueue - auto-reset event
-mtxExternal - mutex or CS
-mtxUnblockLock - mutex or CS
-nWaitersGone - int
-nWaitersBlocked - int
-nWaitersToUnblock - int
-
-wait( timeout ) {
-
- [auto: register int result ] // error checking omitted
- [auto: register int nSignalsWasLeft ]
- [auto: register int nWaitersWasGone ]
-
- wait( hevBlockLock,INFINITE );
- nWaitersBlocked++;
- set_event( hevBlockLock );
-
- unlock( mtxExternal );
- bTimedOut = wait( hevBlockQueue,timeout );
-
- lock( mtxUnblockLock );
- if ( 0 != (SignalsWasLeft = nWaitersToUnblock) ) {
- if ( bTimeout ) { // timeout (or canceled)
- if ( 0 != nWaitersBlocked ) {
- nWaitersBlocked--;
- nSignalsWasLeft = 0; // do not unblock next waiter
-below (already unblocked)
- }
- else {
- nWaitersGone = 1; // spurious wakeup pending!!
- }
- }
- if ( 0 == --nWaitersToUnblock )
- if ( 0 != nWaitersBlocked ) {
- set_event( hevBlockLock ); // open the gate
- nSignalsWasLeft = 0; // do not open the gate below
-again
- }
- else if ( 0 != (nWaitersWasGone = nWaitersGone) ) {
- nWaitersGone = 0;
- }
- }
- }
- else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious
-event :-)
- wait( hevBlockLock,INFINITE );
- nWaitersBlocked -= nWaitersGone; // something is going on here -
-test of timeouts? :-)
- set_event( hevBlockLock );
- nWaitersGone = 0;
- }
- unlock( mtxUnblockLock );
-
- if ( 1 == nSignalsWasLeft ) {
- if ( 0 != nWaitersWasGone ) {
- reset_event( hevBlockQueue ); // better now than spurious
-later
- }
- set_event( hevBlockLock ); // open the gate
- }
- else if ( 0 != nSignalsWasLeft ) {
- set_event( hevBlockQueue ); // unblock next waiter
- }
-
- lock( mtxExternal );
-
- return ( bTimedOut ) ? ETIMEOUT : 0;
-}
-
-signal(bAll) {
-
- [auto: register int result ]
-
- lock( mtxUnblockLock );
-
- if ( 0 != nWaitersToUnblock ) { // the gate is closed!!!
- if ( 0 == nWaitersBlocked ) { // NO-OP
- return unlock( mtxUnblockLock );
- }
- if (bAll) {
- nWaitersToUnblock += nWaitersBlocked;
- nWaitersBlocked = 0;
- }
- else {
- nWaitersToUnblock++;
- nWaitersBlocked--;
- }
- unlock( mtxUnblockLock );
- }
- else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION!
- wait( hevBlockLock,INFINITE ); // close the gate
- if ( 0 != nWaitersGone ) {
- nWaitersBlocked -= nWaitersGone;
- nWaitersGone = 0;
- }
- if (bAll) {
- nWaitersToUnblock = nWaitersBlocked;
- nWaitersBlocked = 0;
- }
- else {
- nWaitersToUnblock = 1;
- nWaitersBlocked--;
- }
- unlock( mtxUnblockLock );
- set_event( hevBlockQueue );
- }
- else { // NO-OP
- unlock( mtxUnblockLock );
- }
-
- return result;
-}
-
----------- Algorithm 8d / IMPL_EVENT,UNBLOCK_STRATEGY == UNBLOCK_ALL ------
-given:
-hevBlockLock - auto-reset event
-hevBlockQueueS - auto-reset event // for signals
-hevBlockQueueB - manual-reset even // for broadcasts
-mtxExternal - mutex or CS
-mtxUnblockLock - mutex or CS
-eBroadcast - int // 0: no broadcast, 1: broadcast, 2:
-broadcast after signal(s)
-nWaitersGone - int
-nWaitersBlocked - int
-nWaitersToUnblock - int
-
-wait( timeout ) {
-
- [auto: register int result ] // error checking omitted
- [auto: register int eWasBroadcast ]
- [auto: register int nSignalsWasLeft ]
- [auto: register int nWaitersWasGone ]
-
- wait( hevBlockLock,INFINITE );
- nWaitersBlocked++;
- set_event( hevBlockLock );
-
- unlock( mtxExternal );
- bTimedOut = waitformultiple( hevBlockQueueS,hevBlockQueueB,timeout,ONE );
-
- lock( mtxUnblockLock );
- if ( 0 != (SignalsWasLeft = nWaitersToUnblock) ) {
- if ( bTimeout ) { // timeout (or canceled)
- if ( 0 != nWaitersBlocked ) {
- nWaitersBlocked--;
- nSignalsWasLeft = 0; // do not unblock next waiter
-below (already unblocked)
- }
- else if ( 1 != eBroadcast ) {
- nWaitersGone = 1;
- }
- }
- if ( 0 == --nWaitersToUnblock ) {
- if ( 0 != nWaitersBlocked ) {
- set_event( hevBlockLock ); // open the gate
- nSignalsWasLeft = 0; // do not open the gate below
-again
- }
- else {
- if ( 0 != (eWasBroadcast = eBroadcast) ) {
- eBroadcast = 0;
- }
- if ( 0 != (nWaitersWasGone = nWaitersGone ) {
- nWaitersGone = 0;
- }
- }
- }
- else if ( 0 != eBroadcast ) {
- nSignalsWasLeft = 0; // do not unblock next waiter
-below (already unblocked)
- }
- }
- else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious
-event :-)
- wait( hevBlockLock,INFINITE );
- nWaitersBlocked -= nWaitersGone; // something is going on here -
-test of timeouts? :-)
- set_event( hevBlockLock );
- nWaitersGone = 0;
- }
- unlock( mtxUnblockLock );
-
- if ( 1 == nSignalsWasLeft ) {
- if ( 0 != eWasBroadcast ) {
- reset_event( hevBlockQueueB );
- }
- if ( 0 != nWaitersWasGone ) {
- reset_event( hevBlockQueueS ); // better now than spurious
-later
- }
- set_event( hevBlockLock ); // open the gate
- }
- else if ( 0 != nSignalsWasLeft ) {
- set_event( hevBlockQueueS ); // unblock next waiter
- }
-
- lock( mtxExternal );
-
- return ( bTimedOut ) ? ETIMEOUT : 0;
-}
-
-signal(bAll) {
-
- [auto: register int result ]
- [auto: register HANDLE hevBlockQueue ]
-
- lock( mtxUnblockLock );
-
- if ( 0 != nWaitersToUnblock ) { // the gate is closed!!!
- if ( 0 == nWaitersBlocked ) { // NO-OP
- return unlock( mtxUnblockLock );
- }
- if (bAll) {
- nWaitersToUnblock += nWaitersBlocked;
- nWaitersBlocked = 0;
- eBroadcast = 2;
- hevBlockQueue = hevBlockQueueB;
- }
- else {
- nWaitersToUnblock++;
- nWaitersBlocked--;
- return unlock( mtxUnblockLock );
- }
- }
- else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION!
- wait( hevBlockLock,INFINITE ); // close the gate
- if ( 0 != nWaitersGone ) {
- nWaitersBlocked -= nWaitersGone;
- nWaitersGone = 0;
- }
- if (bAll) {
- nWaitersToUnblock = nWaitersBlocked;
- nWaitersBlocked = 0;
- eBroadcast = 1;
- hevBlockQueue = hevBlockQueueB;
- }
- else {
- nWaitersToUnblock = 1;
- nWaitersBlocked--;
- hevBlockQueue = hevBlockQueueS;
- }
- }
- else { // NO-OP
- return unlock( mtxUnblockLock );
- }
-
- unlock( mtxUnblockLock );
- set_event( hevBlockQueue );
- return result;
-}
----------------------- Forwarded by Alexander Terekhov/Germany/IBM on
-02/21/2001 09:13 AM ---------------------------
-
-Alexander Terekhov
-02/20/2001 04:33 PM
-
-To: Louis Thomas <lthomas@arbitrade.com>
-cc:
-
-From: Alexander Terekhov/Germany/IBM@IBMDE
-Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_* implementatio
- n questions
-Importance: Normal
-
->Sorry, gotta take a break and work on something else for a while.
->Real work
->calls, unfortunately. I'll get back to you in two or three days.
-
-ok. no problem. here is some more stuff for pauses you might have
-in between :)
-
----------- Algorithm 7d / IMPL_EVENT,UNBLOCK_STRATEGY == UNBLOCK_ALL ------
-given:
-hevBlockLock - auto-reset event
-hevBlockQueueS - auto-reset event // for signals
-hevBlockQueueB - manual-reset even // for broadcasts
-mtxExternal - mutex or CS
-mtxUnblockLock - mutex or CS
-bBroadcast - int
-nWaitersGone - int
-nWaitersBlocked - int
-nWaitersToUnblock - int
-
-wait( timeout ) {
-
- [auto: register int result ] // error checking omitted
- [auto: register int bWasBroadcast ]
- [auto: register int nSignalsWasLeft ]
-
- wait( hevBlockLock,INFINITE );
- nWaitersBlocked++;
- set_event( hevBlockLock );
-
- unlock( mtxExternal );
- bTimedOut = waitformultiple( hevBlockQueueS,hevBlockQueueB,timeout,ONE );
-
- lock( mtxUnblockLock );
- if ( 0 != (SignalsWasLeft = nWaitersToUnblock) ) {
- if ( bTimeout ) { // timeout (or canceled)
- if ( 0 != nWaitersBlocked ) {
- nWaitersBlocked--;
- nSignalsWasLeft = 0; // do not unblock next waiter
-below (already unblocked)
- }
- else if ( !bBroadcast ) {
- wait( hevBlockQueueS,INFINITE ); // better now than spurious
-later
- }
- }
- if ( 0 == --nWaitersToUnblock ) {
- if ( 0 != nWaitersBlocked ) {
- if ( bBroadcast ) {
- reset_event( hevBlockQueueB );
- bBroadcast = false;
- }
- set_event( hevBlockLock ); // open the gate
- nSignalsWasLeft = 0; // do not open the gate below
-again
- }
- else if ( false != (bWasBroadcast = bBroadcast) ) {
- bBroadcast = false;
- }
- }
- else {
- bWasBroadcast = bBroadcast;
- }
- }
- else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious
-event :-)
- wait( hevBlockLock,INFINITE );
- nWaitersBlocked -= nWaitersGone; // something is going on here -
-test of timeouts? :-)
- set_event( hevBlockLock );
- nWaitersGone = 0;
- }
- unlock( mtxUnblockLock );
-
- if ( 1 == nSignalsWasLeft ) {
- if ( bWasBroadcast ) {
- reset_event( hevBlockQueueB );
- }
- set_event( hevBlockLock ); // open the gate
- }
- else if ( 0 != nSignalsWasLeft && !bWasBroadcast ) {
- set_event( hevBlockQueueS ); // unblock next waiter
- }
-
- lock( mtxExternal );
-
- return ( bTimedOut ) ? ETIMEOUT : 0;
-}
-
-signal(bAll) {
-
- [auto: register int result ]
- [auto: register HANDLE hevBlockQueue ]
-
- lock( mtxUnblockLock );
-
- if ( 0 != nWaitersToUnblock ) { // the gate is closed!!!
- if ( 0 == nWaitersBlocked ) { // NO-OP
- return unlock( mtxUnblockLock );
- }
- if (bAll) {
- nWaitersToUnblock += nWaitersBlocked;
- nWaitersBlocked = 0;
- bBroadcast = true;
- hevBlockQueue = hevBlockQueueB;
- }
- else {
- nWaitersToUnblock++;
- nWaitersBlocked--;
- return unlock( mtxUnblockLock );
- }
- }
- else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION!
- wait( hevBlockLock,INFINITE ); // close the gate
- if ( 0 != nWaitersGone ) {
- nWaitersBlocked -= nWaitersGone;
- nWaitersGone = 0;
- }
- if (bAll) {
- nWaitersToUnblock = nWaitersBlocked;
- nWaitersBlocked = 0;
- bBroadcast = true;
- hevBlockQueue = hevBlockQueueB;
- }
- else {
- nWaitersToUnblock = 1;
- nWaitersBlocked--;
- hevBlockQueue = hevBlockQueueS;
- }
- }
- else { // NO-OP
- return unlock( mtxUnblockLock );
- }
-
- unlock( mtxUnblockLock );
- set_event( hevBlockQueue );
- return result;
-}
-
-
-----------------------------------------------------------------------------
-
-Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_* implementatio
- n questions
-Date: Mon, 26 Feb 2001 22:20:12 -0600
-From: Louis Thomas <lthomas@arbitrade.com>
-To: "'TEREKHOV@de.ibm.com'" <TEREKHOV@de.ibm.com>
-CC: rpj@ise.canberra.edu.au, Thomas Pfaff <tpfaff@gmx.net>,
- Nanbor Wang
- <nanbor@cs.wustl.edu>
-
-Sorry all. Busy week.
-
-> this insures the fairness
-> which POSIX does not (e.g. two subsequent broadcasts - the gate does
-insure
-> that first wave waiters will start the race for the mutex before waiters
-> from the second wave - Linux pthreads process/unblock both waves
-> concurrently...)
-
-I'm not sure how we are any more fair about this than Linux. We certainly
-don't guarantee that the threads released by the first broadcast will get
-the external mutex before the threads of the second wave. In fact, it is
-possible that those threads will never get the external mutex if there is
-enough contention for it.
-
-> e.g. i was thinking about implementation with a pool of
-> N semaphores/counters [...]
-
-I considered that too. The problem is as you mentioned in a). You really
-need to assign threads to semaphores once you know how you want to wake them
-up, not when they first begin waiting which is the only time you can assign
-them.
-
-> well, i am not quite sure that i've fully understood your scenario,
-
-Hmm. Well, it think it's an important example, so I'll try again. First, we
-have thread A which we KNOW is waiting on a condition. As soon as it becomes
-unblocked for any reason, we will know because it will set a flag. Since the
-flag is not set, we are 100% confident that thread A is waiting on the
-condition. We have another thread, thread B, which has acquired the mutex
-and is about to wait on the condition. Thus it is pretty clear that at any
-point, either just A is waiting, or A and B are waiting. Now thread C comes
-along. C is about to do a broadcast on the condition. A broadcast is
-guaranteed to unblock all threads currently waiting on a condition, right?
-Again, we said that either just A is waiting, or A and B are both waiting.
-So, when C does its broadcast, depending upon whether B has started waiting
-or not, thread C will unblock A or unblock A and B. Either way, C must
-unblock A, right?
-
-Now, you said anything that happens is correct so long as a) "a signal is
-not lost between unlocking the mutex and waiting on the condition" and b) "a
-thread must not steal a signal it sent", correct? Requirement b) is easy to
-satisfy: in this scenario, thread C will never wait on the condition, so it
-won't steal any signals. Requirement a) is not hard either. The only way we
-could fail to meet requirement a) in this scenario is if thread B was
-started waiting but didn't wake up because a signal was lost. This will not
-happen.
-
-Now, here is what happens. Assume thread C beats thread B. Thread C looks to
-see how many threads are waiting on the condition. Thread C sees just one
-thread, thread A, waiting. It does a broadcast waking up just one thread
-because just one thread is waiting. Next, before A can become unblocked,
-thread B begins waiting. Now there are two threads waiting, but only one
-will be unblocked. Suppose B wins. B will become unblocked. A will not
-become unblocked, because C only unblocked one thread (sema_post cond, 1).
-So at the end, B finishes and A remains blocked.
-
-We have met both of your requirements, so by your rules, this is an
-acceptable outcome. However, I think that the spec says this is an
-unacceptable outcome! We know for certain that A was waiting and that C did
-a broadcast, but A did not become unblocked! Yet, the spec says that a
-broadcast wakes up all waiting threads. This did not happen. Do you agree
-that this shows your rules are not strict enough?
-
-> and what about N2? :) this one does allow almost everything.
-
-Don't get me started about rule #2. I'll NEVER advocate an algorithm that
-uses rule 2 as an excuse to suck!
-
-> but it is done (decrement)under mutex protection - this is not a subject
-> of a race condition.
-
-You are correct. My mistake.
-
-> i would remove "_bTimedOut=false".. after all, it was a real timeout..
-
-I disagree. A thread that can't successfully retract its waiter status can't
-really have timed out. If a thread can't return without executing extra code
-to deal with the fact that someone tried to unblock it, I think it is a poor
-idea to pretend we
-didn't realize someone was trying to signal us. After all, a signal is more
-important than a time out.
-
-> when nSignaled != 0, it is possible to update nWaiters (--) and do not
-> touch nGone
-
-I realize this, but I was thinking that writing it the other ways saves
-another if statement.
-
-> adjust only if nGone != 0 and save one cache memory write - probably much
-slower than 'if'
-
-Hmm. You are probably right.
-
-> well, in a strange (e.g. timeout test) program you may (theoretically)
-> have an overflow of nWaiters/nGone counters (with waiters repeatedly
-timing
-> out and no signals at all).
-
-Also true. Not only that, but you also have the possibility that one could
-overflow the number of waiters as well! However, considering the limit you
-have chosen for nWaitersGone, I suppose it is unlikely that anyone would be
-able to get INT_MAX/2 threads waiting on a single condition. :)
-
-Analysis of 8a:
-
-It looks correct to me.
-
-What are IPC semaphores?
-
-In the line where you state, "else if ( nWaitersBlocked > nWaitersGone ) {
-// HARMLESS RACE CONDITION!" there is no race condition for nWaitersGone
-because nWaitersGone is never modified without holding mtxUnblockLock. You
-are correct that there is a harmless race on nWaitersBlocked, which can
-increase and make the condition become true just after we check it. If this
-happens, we interpret it as the wait starting after the signal.
-
-I like your optimization of this. You could improve Alg. 6 as follows:
----------- Algorithm 6b ----------
-signal(bAll) {
- _nSig=0
- lock counters
- // this is safe because nWaiting can only be decremented by a thread that
- // owns counters and nGone can only be changed by a thread that owns
-counters.
- if (nWaiting>nGone) {
- if (0==nSignaled) {
- sema_wait gate // close gate if not already closed
- }
- if (nGone>0) {
- nWaiting-=nGone
- nGone=0
- }
- _nSig=bAll?nWaiting:1
- nSignaled+=_nSig
- nWaiting-=_nSig
- }
- unlock counters
- if (0!=_nSig) {
- sema_post queue, _nSig
- }
-}
----------- ---------- ----------
-I guess this wouldn't apply to Alg 8a because nWaitersGone changes meanings
-depending upon whether the gate is open or closed.
-
-In the loop "while ( nWaitersWasGone-- ) {" you do a sema_wait on
-semBlockLock. Perhaps waiting on semBlockQueue would be a better idea.
-
-What have you gained by making the last thread to be signaled do the waits
-for all the timed out threads, besides added complexity? It took me a long
-time to figure out what your objective was with this, to realize you were
-using nWaitersGone to mean two different things, and to verify that you
-hadn't introduced any bug by doing this. Even now I'm not 100% sure.
-
-What has all this playing about with nWaitersGone really gained us besides a
-lot of complexity (it is much harder to verify that this solution is
-correct), execution overhead (we now have a lot more if statements to
-evaluate), and space overhead (more space for the extra code, and another
-integer in our data)? We did manage to save a lock/unlock pair in an
-uncommon case (when a time out occurs) at the above mentioned expenses in
-the common cases.
-
-As for 8b, c, and d, they look ok though I haven't studied them thoroughly.
-What would you use them for?
-
- Later,
- -Louis! :)
-
------------------------------------------------------------------------------
-
-Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_* implementatio
- n questions
-Date: Tue, 27 Feb 2001 15:51:28 +0100
-From: TEREKHOV@de.ibm.com
-To: Louis Thomas <lthomas@arbitrade.com>
-CC: rpj@ise.canberra.edu.au, Thomas Pfaff <tpfaff@gmx.net>,
- Nanbor Wang <nanbor@cs.wustl.edu>
-
-Hi Louis,
-
->> that first wave waiters will start the race for the mutex before waiters
->> from the second wave - Linux pthreads process/unblock both waves
->> concurrently...)
->
->I'm not sure how we are any more fair about this than Linux. We certainly
->don't guarantee that the threads released by the first broadcast will get
->the external mutex before the threads of the second wave. In fact, it is
->possible that those threads will never get the external mutex if there is
->enough contention for it.
-
-correct. but gate is nevertheless more fair than Linux because of the
-barrier it establishes between two races (1st and 2nd wave waiters) for
-the mutex which under 'normal' circumstances (e.g. all threads of equal
-priorities,..) will 'probably' result in fair behaviour with respect to
-mutex ownership.
-
->> well, i am not quite sure that i've fully understood your scenario,
->
->Hmm. Well, it think it's an important example, so I'll try again. ...
-
-ok. now i seem to understand this example. well, now it seems to me
-that the only meaningful rule is just:
-
-a) "a signal is not lost between unlocking the mutex and waiting on the
-condition"
-
-and that the rule
-
-b) "a thread must not steal a signal it sent"
-
-is not needed at all because a thread which violates b) also violates a).
-
-i'll try to explain..
-
-i think that the most important thing is how POSIX defines waiter's
-visibility:
-
-"if another thread is able to acquire the mutex after the about-to-block
-thread
-has released it, then a subsequent call to pthread_cond_signal() or
-pthread_cond_broadcast() in that thread behaves as if it were issued after
-the about-to-block thread has blocked. "
-
-my understanding is the following:
-
-1) there is no guarantees whatsoever with respect to whether
-signal/broadcast
-will actually unblock any 'waiter' if it is done w/o acquiring the mutex
-first
-(note that a thread may release it before signal/broadcast - it does not
-matter).
-
-2) it is guaranteed that waiters become 'visible' - eligible for unblock as
-soon
-as signalling thread acquires the mutex (but not before!!)
-
-so..
-
->So, when C does its broadcast, depending upon whether B has started
-waiting
->or not, thread C will unblock A or unblock A and B. Either way, C must
->unblock A, right?
-
-right. but only if C did acquire the mutex prior to broadcast (it may
-release it before broadcast as well).
-
-implementation will violate waiters visibility rule (signal will become
-lost)
-if C will not unblock A.
-
->Now, here is what happens. Assume thread C beats thread B. Thread C looks
-to
->see how many threads are waiting on the condition. Thread C sees just one
->thread, thread A, waiting. It does a broadcast waking up just one thread
->because just one thread is waiting. Next, before A can become unblocked,
->thread B begins waiting. Now there are two threads waiting, but only one
->will be unblocked. Suppose B wins. B will become unblocked. A will not
->become unblocked, because C only unblocked one thread (sema_post cond, 1).
->So at the end, B finishes and A remains blocked.
-
-thread C did acquire the mutex ("Thread C sees just one thread, thread A,
-waiting"). beginning from that moment it is guaranteed that subsequent
-broadcast will unblock A. Otherwise we will have a lost signal with respect
-to A. I do think that it does not matter whether the signal was physically
-(completely) lost or was just stolen by another thread (B) - in both cases
-it was simply lost with respect to A.
-
->..Do you agree that this shows your rules are not strict enough?
-
-probably the opposite.. :-) i think that it shows that the only meaningful
-rule is
-
-a) "a signal is not lost between unlocking the mutex and waiting on the
-condition"
-
-with clarification of waiters visibility as defined by POSIX above.
-
->> i would remove "_bTimedOut=false".. after all, it was a real timeout..
->
->I disagree. A thread that can't successfully retract its waiter status
-can't
->really have timed out. If a thread can't return without executing extra
-code
->to deal with the fact that someone tried to unblock it, I think it is a
-poor
->idea to pretend we
->didn't realize someone was trying to signal us. After all, a signal is
-more
->important than a time out.
-
-a) POSIX does allow timed out thread to consume a signal (cancelled is
-not).
-b) ETIMEDOUT status just says that: "The time specified by abstime to
-pthread_cond_timedwait() has passed."
-c) it seem to me that hiding timeouts would violate "The
-pthread_cond_timedwait()
-function is the same as pthread_cond_wait() except that an error is
-returned if
-the absolute time specified by abstime passes (that is, system time equals
-or
-exceeds abstime) before the condition cond is signaled or broadcasted"
-because
-the abs. time did really pass before cond was signaled (waiter was
-released via semaphore). however, if it really matters, i could imaging
-that we
-can save an abs. time of signal/broadcast and compare it with timeout after
-unblock to find out whether it was a 'real' timeout or not. absent this
-check
-i do think that hiding timeouts would result in technical violation of
-specification.. but i think that this check is not important and we can
-simply
-trust timeout error code provided by wait since we are not trying to make
-'hard' realtime implementation.
-
->What are IPC semaphores?
-
-<sys/sem.h>
-int semctl(int, int, int, ...);
-int semget(key_t, int, int);
-int semop(int, struct sembuf *, size_t);
-
-they support adjustment of semaphore counter (semvalue)
-in one single call - imaging Win32 ReleaseSemaphore( hsem,-N )
-
->In the line where you state, "else if ( nWaitersBlocked > nWaitersGone ) {
->// HARMLESS RACE CONDITION!" there is no race condition for nWaitersGone
->because nWaitersGone is never modified without holding mtxUnblockLock. You
->are correct that there is a harmless race on nWaitersBlocked, which can
->increase and make the condition become true just after we check it. If
-this
->happens, we interpret it as the wait starting after the signal.
-
-well, the reason why i've asked on comp.programming.threads whether this
-race
-condition is harmless or not is that in order to be harmless it should not
-violate the waiters visibility rule (see above). Fortunately, we increment
-the counter under protection of external mutex.. so that any (signalling)
-thread which will acquire the mutex next, should see the updated counter
-(in signal) according to POSIX memory visibility rules and mutexes
-(memory barriers). But i am not so sure how it actually works on
-Win32/INTEL
-which does not explicitly define any memory visibility rules :(
-
->I like your optimization of this. You could improve Alg. 6 as follows:
->---------- Algorithm 6b ----------
->signal(bAll) {
-> _nSig=0
-> lock counters
-> // this is safe because nWaiting can only be decremented by a thread
-that
-> // owns counters and nGone can only be changed by a thread that owns
->counters.
-> if (nWaiting>nGone) {
-> if (0==nSignaled) {
-> sema_wait gate // close gate if not already closed
-> }
-> if (nGone>0) {
-> nWaiting-=nGone
-> nGone=0
-> }
-> _nSig=bAll?nWaiting:1
-> nSignaled+=_nSig
-> nWaiting-=_nSig
-> }
-> unlock counters
-> if (0!=_nSig) {
-> sema_post queue, _nSig
-> }
->}
->---------- ---------- ----------
->I guess this wouldn't apply to Alg 8a because nWaitersGone changes
-meanings
->depending upon whether the gate is open or closed.
-
-agree.
-
->In the loop "while ( nWaitersWasGone-- ) {" you do a sema_wait on
->semBlockLock. Perhaps waiting on semBlockQueue would be a better idea.
-
-you are correct. my mistake.
-
->What have you gained by making the last thread to be signaled do the waits
->for all the timed out threads, besides added complexity? It took me a long
->time to figure out what your objective was with this, to realize you were
->using nWaitersGone to mean two different things, and to verify that you
->hadn't introduced any bug by doing this. Even now I'm not 100% sure.
->
->What has all this playing about with nWaitersGone really gained us besides
-a
->lot of complexity (it is much harder to verify that this solution is
->correct), execution overhead (we now have a lot more if statements to
->evaluate), and space overhead (more space for the extra code, and another
->integer in our data)? We did manage to save a lock/unlock pair in an
->uncommon case (when a time out occurs) at the above mentioned expenses in
->the common cases.
-
-well, please consider the following:
-
-1) with multiple waiters unblocked (but some timed out) the trick with
-counter
-seem to ensure potentially higher level of concurrency by not delaying
-most of unblocked waiters for semaphore cleanup - only the last one
-will be delayed but all others would already contend/acquire/release
-the external mutex - the critical section protected by mtxUnblockLock is
-made smaller (increment + couple of IFs is faster than system/kernel call)
-which i think is good in general. however, you are right, this is done
-at expense of 'normal' waiters..
-
-2) some semaphore APIs (e.g. POSIX IPC sems) do allow to adjust the
-semaphore counter in one call => less system/kernel calls.. imagine:
-
-if ( 1 == nSignalsWasLeft ) {
- if ( 0 != nWaitersWasGone ) {
- ReleaseSemaphore( semBlockQueue,-nWaitersWasGone ); // better now
-than spurious later
- }
- sem_post( semBlockLock ); // open the gate
- }
-
-3) even on win32 a single thread doing multiple cleanup calls (to wait)
-will probably result in faster execution (because of processor caching)
-than multiple threads each doing a single call to wait.
-
->As for 8b, c, and d, they look ok though I haven't studied them
-thoroughly.
->What would you use them for?
-
-8b) for semaphores which do not allow to unblock multiple waiters
-in a single call to post/release (e.g. POSIX realtime semaphores -
-<semaphore.h>)
-
-8c/8d) for WinCE prior to 3.0 (WinCE 3.0 does have semaphores)
-
-ok. so, which one is the 'final' algorithm(s) which we should use in
-pthreads-win32??
-
-regards,
-alexander.
-
-----------------------------------------------------------------------------
-
-Louis Thomas <lthomas@arbitrade.com> on 02/27/2001 05:20:12 AM
-
-Please respond to Louis Thomas <lthomas@arbitrade.com>
-
-To: Alexander Terekhov/Germany/IBM@IBMDE
-cc: rpj@ise.canberra.edu.au, Thomas Pfaff <tpfaff@gmx.net>, Nanbor Wang
- <nanbor@cs.wustl.edu>
-Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_* implementatio
- n questions
-
-Sorry all. Busy week.
-
-> this insures the fairness
-> which POSIX does not (e.g. two subsequent broadcasts - the gate does
-insure
-> that first wave waiters will start the race for the mutex before waiters
-> from the second wave - Linux pthreads process/unblock both waves
-> concurrently...)
-
-I'm not sure how we are any more fair about this than Linux. We certainly
-don't guarantee that the threads released by the first broadcast will get
-the external mutex before the threads of the second wave. In fact, it is
-possible that those threads will never get the external mutex if there is
-enough contention for it.
-
-> e.g. i was thinking about implementation with a pool of
-> N semaphores/counters [...]
-
-I considered that too. The problem is as you mentioned in a). You really
-need to assign threads to semaphores once you know how you want to wake
-them
-up, not when they first begin waiting which is the only time you can assign
-them.
-
-> well, i am not quite sure that i've fully understood your scenario,
-
-Hmm. Well, it think it's an important example, so I'll try again. First, we
-have thread A which we KNOW is waiting on a condition. As soon as it
-becomes
-unblocked for any reason, we will know because it will set a flag. Since
-the
-flag is not set, we are 100% confident that thread A is waiting on the
-condition. We have another thread, thread B, which has acquired the mutex
-and is about to wait on the condition. Thus it is pretty clear that at any
-point, either just A is waiting, or A and B are waiting. Now thread C comes
-along. C is about to do a broadcast on the condition. A broadcast is
-guaranteed to unblock all threads currently waiting on a condition, right?
-Again, we said that either just A is waiting, or A and B are both waiting.
-So, when C does its broadcast, depending upon whether B has started waiting
-or not, thread C will unblock A or unblock A and B. Either way, C must
-unblock A, right?
-
-Now, you said anything that happens is correct so long as a) "a signal is
-not lost between unlocking the mutex and waiting on the condition" and b)
-"a
-thread must not steal a signal it sent", correct? Requirement b) is easy to
-satisfy: in this scenario, thread C will never wait on the condition, so it
-won't steal any signals. Requirement a) is not hard either. The only way
-we
-could fail to meet requirement a) in this scenario is if thread B was
-started waiting but didn't wake up because a signal was lost. This will not
-happen.
-
-Now, here is what happens. Assume thread C beats thread B. Thread C looks
-to
-see how many threads are waiting on the condition. Thread C sees just one
-thread, thread A, waiting. It does a broadcast waking up just one thread
-because just one thread is waiting. Next, before A can become unblocked,
-thread B begins waiting. Now there are two threads waiting, but only one
-will be unblocked. Suppose B wins. B will become unblocked. A will not
-become unblocked, because C only unblocked one thread (sema_post cond, 1).
-So at the end, B finishes and A remains blocked.
-
-We have met both of your requirements, so by your rules, this is an
-acceptable outcome. However, I think that the spec says this is an
-unacceptable outcome! We know for certain that A was waiting and that C did
-a broadcast, but A did not become unblocked! Yet, the spec says that a
-broadcast wakes up all waiting threads. This did not happen. Do you agree
-that this shows your rules are not strict enough?
-
-> and what about N2? :) this one does allow almost everything.
-
-Don't get me started about rule #2. I'll NEVER advocate an algorithm that
-uses rule 2 as an excuse to suck!
-
-> but it is done (decrement)under mutex protection - this is not a subject
-> of a race condition.
-
-You are correct. My mistake.
-
-> i would remove "_bTimedOut=false".. after all, it was a real timeout..
-
-I disagree. A thread that can't successfully retract its waiter status
-can't
-really have timed out. If a thread can't return without executing extra
-code
-to deal with the fact that someone tried to unblock it, I think it is a
-poor
-idea to pretend we
-didn't realize someone was trying to signal us. After all, a signal is more
-important than a time out.
-
-> when nSignaled != 0, it is possible to update nWaiters (--) and do not
-> touch nGone
-
-I realize this, but I was thinking that writing it the other ways saves
-another if statement.
-
-> adjust only if nGone != 0 and save one cache memory write - probably much
-slower than 'if'
-
-Hmm. You are probably right.
-
-> well, in a strange (e.g. timeout test) program you may (theoretically)
-> have an overflow of nWaiters/nGone counters (with waiters repeatedly
-timing
-> out and no signals at all).
-
-Also true. Not only that, but you also have the possibility that one could
-overflow the number of waiters as well! However, considering the limit you
-have chosen for nWaitersGone, I suppose it is unlikely that anyone would be
-able to get INT_MAX/2 threads waiting on a single condition. :)
-
-Analysis of 8a:
-
-It looks correct to me.
-
-What are IPC semaphores?
-
-In the line where you state, "else if ( nWaitersBlocked > nWaitersGone ) {
-// HARMLESS RACE CONDITION!" there is no race condition for nWaitersGone
-because nWaitersGone is never modified without holding mtxUnblockLock. You
-are correct that there is a harmless race on nWaitersBlocked, which can
-increase and make the condition become true just after we check it. If this
-happens, we interpret it as the wait starting after the signal.
-
-I like your optimization of this. You could improve Alg. 6 as follows:
----------- Algorithm 6b ----------
-signal(bAll) {
- _nSig=0
- lock counters
- // this is safe because nWaiting can only be decremented by a thread that
- // owns counters and nGone can only be changed by a thread that owns
-counters.
- if (nWaiting>nGone) {
- if (0==nSignaled) {
- sema_wait gate // close gate if not already closed
- }
- if (nGone>0) {
- nWaiting-=nGone
- nGone=0
- }
- _nSig=bAll?nWaiting:1
- nSignaled+=_nSig
- nWaiting-=_nSig
- }
- unlock counters
- if (0!=_nSig) {
- sema_post queue, _nSig
- }
-}
----------- ---------- ----------
-I guess this wouldn't apply to Alg 8a because nWaitersGone changes meanings
-depending upon whether the gate is open or closed.
-
-In the loop "while ( nWaitersWasGone-- ) {" you do a sema_wait on
-semBlockLock. Perhaps waiting on semBlockQueue would be a better idea.
-
-What have you gained by making the last thread to be signaled do the waits
-for all the timed out threads, besides added complexity? It took me a long
-time to figure out what your objective was with this, to realize you were
-using nWaitersGone to mean two different things, and to verify that you
-hadn't introduced any bug by doing this. Even now I'm not 100% sure.
-
-What has all this playing about with nWaitersGone really gained us besides
-a
-lot of complexity (it is much harder to verify that this solution is
-correct), execution overhead (we now have a lot more if statements to
-evaluate), and space overhead (more space for the extra code, and another
-integer in our data)? We did manage to save a lock/unlock pair in an
-uncommon case (when a time out occurs) at the above mentioned expenses in
-the common cases.
-
-As for 8b, c, and d, they look ok though I haven't studied them thoroughly.
-What would you use them for?
-
- Later,
- -Louis! :)
-
+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: ace-bugs@cs.wustl.edu +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 <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 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; + +} +. +. +. +David Schwartz <davids@webmaster.com> wrote: +>> > It's compliant +>> +>> That is really good. +> +>> Tomorrow (I have to go urgently now) I will try to +>> demonstrate the lost-signal "problem" of current +>> pthread-win32 and ACE-(variant w/o SingleObjectAndWait) +>> implementations: players start suddenly drop their balls :-) +>> (with no change in source code). +> +>Signals aren't lost, they're going to the main thread, +>which isn't coded correctly to handle them. Try this: +> +> // Wait for players to stop +> do { +> +> pthread_cond_wait( &cndGameStateChange,&mtxGameStateLock ); +>printf("Main thread stole a signal\n"); +> +> } while ( eGameState < BOTH_PLAYERS_GONE ); +> +>I bet everytime you thing a signal is lost, you'll see that printf. +>The signal isn't lost, it was stolen by another thread. + +well, you can probably loose your bet.. it was indeed stolen +by "another" thread but not the one you seem to think of. + +I think that what actually happens is the following: + +H:\SA\UXX\pt\PTHREADS\TESTS>tennis3.exe + +PLAYER-A + +PLAYER-B + +----PLAYER-B: SPURIOUS WAKEUP!!! + +PLAYER-A GONE + +PLAYER-B GONE + +GAME OVER + +H:\SA\UXX\pt\PTHREADS\TESTS> + +here you can see that PLAYER-B after playing his first +ball (which came via signal from PLAYER-A) just dropped +it down. What happened is that his signal to player A +was consumed as spurious wakeup by himself (player B). + +The implementation has a problem: + +================ +waiting threads: +================ + +{ /** Critical Section + + inc cond.waiters_count + +} + + /* + /* Atomic only if using Win32 SignalObjectAndWait + /* + cond.mtx.release + + /*** ^^-- A THREAD WHICH DID SIGNAL MAY ACQUIRE THE MUTEX, + /*** GO INTO WAIT ON THE SAME CONDITION AND OVERTAKE + /*** ORIGINAL WAITER(S) CONSUMING ITS OWN SIGNAL! + + cond.sem.wait + +Player-A after playing game's initial ball went into +wait (called _wait) but was pre-empted before reaching +wait semaphore. He was counted as waiter but was not +actually waiting/blocked yet. + +=============== +signal threads: +=============== + +{ /** Critical Section + + waiters_count = cond.waiters_count + +} + + if ( waiters_count != 0 ) + + sem.post 1 + + endif + +Player-B after he received signal/ball from Player A +called _signal. The _signal did see that there was +one waiter blocked on the condition (Player-A) and +released the semaphore.. (but it did not unblock +Player-A because he was not actually blocked). +Player-B thread continued its execution, called _wait, +was counted as second waiter BUT was allowed to slip +through opened semaphore gate (which was opened for +Player-B) and received his own signal. Player B remained +blocked followed by Player A. Deadlock happened which +lasted until main thread came in and said game over. + +It seems to me that the implementation fails to +correctly implement the following statement +from specification: + +http://www.opengroup.org/ +onlinepubs/007908799/xsh/pthread_cond_wait.html + +"These functions atomically release mutex and cause +the calling thread to block on the condition variable +cond; atomically here means "atomically with respect +to access by another thread to the mutex and then the +condition variable". That is, if another thread is +able to acquire the mutex after the about-to-block +thread has released it, then a subsequent call to +pthread_cond_signal() or pthread_cond_broadcast() +in that thread behaves as if it were issued after +the about-to-block thread has blocked." + +Question: Am I right? + +(I produced the program output above by simply +adding ?Sleep( 1 )?: + +================ +waiting threads: +================ + +{ /** Critical Section + + inc cond.waiters_count + +} + + /* + /* Atomic only if using Win32 SignalObjectAndWait + /* + cond.mtx.release + +Sleep( 1 ); // Win32 + + /*** ^^-- A THREAD WHICH DID SIGNAL MAY ACQUIRE THE MUTEX, + /*** GO INTO WAIT ON THE SAME CONDITION AND OVERTAKE + /*** ORIGINAL WAITER(S) CONSUMING ITS OWN SIGNAL! + + cond.sem.wait + +to the source code of pthread-win32 implementation: + +http://sources.redhat.com/cgi-bin/cvsweb.cgi/pthreads/ +condvar.c?rev=1.36&content-type=text/ +x-cvsweb-markup&cvsroot=pthreads-win32 + + + /* + * We keep the lock held just long enough to increment the count of + * waiters by one (above). + * Note that we can't keep it held across the + * call to sem_wait since that will deadlock other calls + * to pthread_cond_signal + */ + cleanup_args.mutexPtr = mutex; + cleanup_args.cv = cv; + cleanup_args.resultPtr = &result; + + pthread_cleanup_push (ptw32_cond_wait_cleanup, (void *) +&cleanup_args); + + if ((result = pthread_mutex_unlock (mutex)) == 0) + {((result +Sleep( 1 ); // @AT + + /* + * Wait to be awakened by + * pthread_cond_signal, or + * pthread_cond_broadcast, or + * a timeout + * + * Note: + * ptw32_sem_timedwait is a cancelation point, + * hence providing the + * mechanism for making pthread_cond_wait a cancelation + * point. We use the cleanup mechanism to ensure we + * re-lock the mutex and decrement the waiters count + * if we are canceled. + */ + if (ptw32_sem_timedwait (&(cv->sema), abstime) == -1) { + result = errno; + } + } + + pthread_cleanup_pop (1); /* Always cleanup */ + + +BTW, on my system (2 CPUs) I can manage to get +signals lost even without any source code modification +if I run the tennis program many times in different +shell sessions. +. +. +. +David Schwartz <davids@webmaster.com> wrote: +>terekhov@my-deja.com wrote: +> +>> well, it might be that the program is in fact buggy. +>> but you did not show me any bug. +> +>You're right. I was close but not dead on. I was correct, however, +>that the code is buggy because it uses 'pthread_cond_signal' even +>though not any thread waiting on the condition variable can do the +>job. I was wrong in which thread could be waiting on the cv but +>unable to do the job. + +Okay, lets change 'pthread_cond_signal' to 'pthread_cond_broadcast' +but also add some noise from main() right before declaring the game +to be over (I need it in order to demonstrate another problem of +pthread-win32/ACE implementations - broadcast deadlock)... +. +. +. +It is my understanding of POSIX conditions, +that on correct implementation added noise +in form of unnecessary broadcasts from main, +should not break the tennis program. The +only 'side effect' of added noise on correct +implementation would be 'spurious wakeups' of +players (in fact they are not spurious, +players just see them as spurious) unblocked, +not by another player but by main before +another player had a chance to acquire the +mutex and change the game state variable: +. +. +. + +PLAYER-B + +PLAYER-A + +---Noise ON... + +PLAYER-B + +PLAYER-A + +. +. +. + +PLAYER-B + +PLAYER-A + +----PLAYER-A: SPURIOUS WAKEUP!!! + +PLAYER-B + +PLAYER-A + +---Noise OFF + +PLAYER-B + +---Stopping the game... + +PLAYER-A GONE + +PLAYER-B GONE + +GAME OVER + +H:\SA\UXX\pt\PTHREADS\TESTS> + +On pthread-win32/ACE implementations the +program could stall: + +. +. +. + +PLAYER-A + +PLAYER-B + +PLAYER-A + +PLAYER-B + +PLAYER-A + +PLAYER-B + +PLAYER-A + +PLAYER-B + +---Noise ON... + +PLAYER-A + +---Noise OFF +^C +H:\SA\UXX\pt\PTHREADS\TESTS> + + +The implementation has problems: + +================ +waiting threads: +================ + +{ /** Critical Section + + inc cond.waiters_count + +} + + /* + /* Atomic only if using Win32 SignalObjectAndWait + /* + cond.mtx.release + cond.sem.wait + + /*** ^^-- WAITER CAN BE PREEMPTED AFTER BEING UNBLOCKED... + +{ /** Critical Section + + dec cond.waiters_count + + /*** ^^- ...AND BEFORE DECREMENTING THE COUNT (1) + + last_waiter = ( cond.was_broadcast && + cond.waiters_count == 0 ) + + if ( last_waiter ) + + cond.was_broadcast = FALSE + + endif + +} + + if ( last_waiter ) + + /* + /* Atomic only if using Win32 SignalObjectAndWait + /* + cond.auto_reset_event_or_sem.post /* Event for Win32 + cond.mtx.acquire + + /*** ^^-- ...AND BEFORE CALL TO mtx.acquire (2) + + /*** ^^-- NESTED BROADCASTS RESULT IN A DEADLOCK + + + else + + cond.mtx.acquire + + /*** ^^-- ...AND BEFORE CALL TO mtx.acquire (3) + + endif + + +================== +broadcast threads: +================== + +{ /** Critical Section + + waiters_count = cond.waiters_count + + if ( waiters_count != 0 ) + + cond.was_broadcast = TRUE + + endif + +} + +if ( waiters_count != 0 ) + + cond.sem.post waiters_count + + /*** ^^^^^--- SPURIOUS WAKEUPS DUE TO (1) + + cond.auto_reset_event_or_sem.wait /* Event for Win32 + + /*** ^^^^^--- DEADLOCK FOR FURTHER BROADCASTS IF THEY + HAPPEN TO GO INTO WAIT WHILE PREVIOUS + BROADCAST IS STILL IN PROGRESS/WAITING + +endif + +a) cond.waiters_count does not accurately reflect +number of waiters blocked on semaphore - that could +result (in the time window when counter is not accurate) +in spurios wakeups organised by subsequent _signals +and _broadcasts. From standard compliance point of view +that is OK but that could be a real problem from +performance/efficiency point of view. + +b) If subsequent broadcast happen to go into wait on +cond.auto_reset_event_or_sem before previous +broadcast was unblocked from cond.auto_reset_event_or_sem +by its last waiter, one of two blocked threads will +remain blocked because last_waiter processing code +fails to unblock both threads. + +In the situation with tennisb.c the Player-B was put +in a deadlock by noise (broadcast) coming from main +thread. And since Player-B holds the game state +mutex when it calls broadcast, the whole program +stalled: Player-A was deadlocked on mutex and +main thread after finishing with producing the noise +was deadlocked on mutex too (needed to declare the +game over) + +(I produced the program output above by simply +adding ?Sleep( 1 )?: + +================== +broadcast threads: +================== + +{ /** Critical Section + + waiters_count = cond.waiters_count + + if ( waiters_count != 0 ) + + cond.was_broadcast = TRUE + + endif + +} + +if ( waiters_count != 0 ) + +Sleep( 1 ); //Win32 + + cond.sem.post waiters_count + + /*** ^^^^^--- SPURIOUS WAKEUPS DUE TO (1) + + cond.auto_reset_event_or_sem.wait /* Event for Win32 + + /*** ^^^^^--- DEADLOCK FOR FURTHER BROADCASTS IF THEY + HAPPEN TO GO INTO WAIT WHILE PREVIOUS + BROADCAST IS STILL IN PROGRESS/WAITING + +endif + +to the source code of pthread-win32 implementation: + +http://sources.redhat.com/cgi-bin/cvsweb.cgi/pthreads/ +condvar.c?rev=1.36&content-type=text/ +x-cvsweb-markup&cvsroot=pthreads-win32 + + if (wereWaiters) + {(wereWaiters)sroot=pthreads-win32eb.cgi/pthreads/Yem...m + /* + * Wake up all waiters + */ + +Sleep( 1 ); //@AT + +#ifdef NEED_SEM + + result = (ptw32_increase_semaphore( &cv->sema, cv->waiters ) + ? 0 + : EINVAL); + +#else /* NEED_SEM */ + + result = (ReleaseSemaphore( cv->sema, cv->waiters, NULL ) + ? 0 + : EINVAL); + +#endif /* NEED_SEM */ + + } + + (void) pthread_mutex_unlock(&(cv->waitersLock)); + + if (wereWaiters && result == 0) + {(wereWaiters + /* + * Wait for all the awakened threads to acquire their part of + * the counting semaphore + */ + + if (WaitForSingleObject (cv->waitersDone, INFINITE) + == WAIT_OBJECT_0) + { + result = 0; + } + else + { + result = EINVAL; + } + + } + + return (result); + +} + +BTW, on my system (2 CPUs) I can manage to get +the program stalled even without any source code +modification if I run the tennisb program many +times in different shell sessions. + +=================== +pthread-win32 patch +=================== +struct pthread_cond_t_ { + long nWaitersBlocked; /* Number of threads blocked +*/ + long nWaitersUnblocked; /* Number of threads unblocked +*/ + long nWaitersToUnblock; /* Number of threads to unblock +*/ + sem_t semBlockQueue; /* Queue up threads waiting for the +*/ + /* condition to become signalled +*/ + sem_t semBlockLock; /* Semaphore that guards access to +*/ + /* | waiters blocked count/block queue +*/ + /* +-> Mandatory Sync.LEVEL-1 +*/ + pthread_mutex_t mtxUnblockLock; /* Mutex that guards access to +*/ + /* | waiters (to)unblock(ed) counts +*/ + /* +-> Optional* Sync.LEVEL-2 +*/ +}; /* Opt*) for _timedwait and +cancellation*/ + +int +pthread_cond_init (pthread_cond_t * cond, const pthread_condattr_t * attr) + int result = EAGAIN; + pthread_cond_t cv = NULL; + + if (cond == NULL) + {(cond + return EINVAL; + } + + if ((attr != NULL && *attr != NULL) && + ((*attr)->pshared == PTHREAD_PROCESS_SHARED)) + { + /* + * Creating condition variable that can be shared between + * processes. + */ + result = ENOSYS; + + goto FAIL0; + } + + cv = (pthread_cond_t) calloc (1, sizeof (*cv)); + + if (cv == NULL) + {(cv + result = ENOMEM; + goto FAIL0; + } + + cv->nWaitersBlocked = 0; + cv->nWaitersUnblocked = 0; + cv->nWaitersToUnblock = 0; + + if (sem_init (&(cv->semBlockLock), 0, 1) != 0) + {(sem_init + goto FAIL0; + } + + if (sem_init (&(cv->semBlockQueue), 0, 0) != 0) + {(sem_init + goto FAIL1; + } + + if (pthread_mutex_init (&(cv->mtxUnblockLock), 0) != 0) + {(pthread_mutex_init + goto FAIL2; + } + + + result = 0; + + goto DONE; + + /* + * ------------- + * Failed... + * ------------- + */ +FAIL2: + (void) sem_destroy (&(cv->semBlockQueue)); + +FAIL1: + (void) sem_destroy (&(cv->semBlockLock)); + +FAIL0: +DONE: + *cond = cv; + + return (result); + +} /* pthread_cond_init */ + +int +pthread_cond_destroy (pthread_cond_t * cond) +{ + int result = 0; + pthread_cond_t cv; + + /* + * Assuming any race condition here is harmless. + */ + if (cond == NULL + || *cond == NULL) + { + return EINVAL; + } + + if (*cond != (pthread_cond_t) PTW32_OBJECT_AUTO_INIT) + {(*cond + cv = *cond; + + /* + * Synchronize access to waiters blocked count (LEVEL-1) + */ + if (sem_wait(&(cv->semBlockLock)) != 0) + {(sem_wait(&(cv->semBlockLock)) + return errno; + } + + /* + * Synchronize access to waiters (to)unblock(ed) counts (LEVEL-2) + */ + if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0) + {((result + (void) sem_post(&(cv->semBlockLock)); + return result; + } + + /* + * Check whether cv is still busy (still has waiters blocked) + */ + if (cv->nWaitersBlocked - cv->nWaitersUnblocked > 0) + {(cv->nWaitersBlocked + (void) sem_post(&(cv->semBlockLock)); + (void) pthread_mutex_unlock(&(cv->mtxUnblockLock)); + return EBUSY; + } + + /* + * Now it is safe to destroy + */ + (void) sem_destroy (&(cv->semBlockLock)); + (void) sem_destroy (&(cv->semBlockQueue)); + (void) pthread_mutex_unlock (&(cv->mtxUnblockLock)); + (void) pthread_mutex_destroy (&(cv->mtxUnblockLock)); + + free(cv); + *cond = NULL; + } + else + { + /* + * See notes in ptw32_cond_check_need_init() above also. + */ + EnterCriticalSection(&ptw32_cond_test_init_lock); + + /* + * Check again. + */ + if (*cond == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT) + {(*cond + /* + * This is all we need to do to destroy a statically + * initialised cond that has not yet been used (initialised). + * If we get to here, another thread + * waiting to initialise this cond will get an EINVAL. + */ + *cond = NULL; + } + else + { + /* + * The cv has been initialised while we were waiting + * so assume it's in use. + */ + result = EBUSY; + } + + LeaveCriticalSection(&ptw32_cond_test_init_lock); + } + + return (result); +} + +/* + * Arguments for cond_wait_cleanup, since we can only pass a + * single void * to it. + */ +typedef struct { + pthread_mutex_t * mutexPtr; + pthread_cond_t cv; + int * resultPtr; +} ptw32_cond_wait_cleanup_args_t; + +static void +ptw32_cond_wait_cleanup(void * args) +{ + ptw32_cond_wait_cleanup_args_t * cleanup_args = +(ptw32_cond_wait_cleanup_args_t *) args; + pthread_cond_t cv = cleanup_args->cv; + int * resultPtr = cleanup_args->resultPtr; + int eLastSignal; /* enum: 1=yes 0=no -1=cancelled/timedout w/o signal(s) +*/ + int result; + + /* + * Whether we got here as a result of signal/broadcast or because of + * timeout on wait or thread cancellation we indicate that we are no + * longer waiting. The waiter is responsible for adjusting waiters + * (to)unblock(ed) counts (protected by unblock lock). + * Unblock lock/Sync.LEVEL-2 supports _timedwait and cancellation. + */ + if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0) + {((result + *resultPtr = result; + return; + } + + cv->nWaitersUnblocked++; + + eLastSignal = (cv->nWaitersToUnblock == 0) ? + -1 : (--cv->nWaitersToUnblock == 0); + + /* + * No more LEVEL-2 access to waiters (to)unblock(ed) counts needed + */ + if ((result = pthread_mutex_unlock(&(cv->mtxUnblockLock))) != 0) + {((result + *resultPtr = result; + return; + } + + /* + * If last signal... + */ + if (eLastSignal == 1) + {(eLastSignal + /* + * ...it means that we have end of 'atomic' signal/broadcast + */ + if (sem_post(&(cv->semBlockLock)) != 0) + {(sem_post(&(cv->semBlockLock)) + *resultPtr = errno; + return; + } + } + /* + * If not last signal and not timed out/cancelled wait w/o signal... + */ + else if (eLastSignal == 0) + { + /* + * ...it means that next waiter can go through semaphore + */ + if (sem_post(&(cv->semBlockQueue)) != 0) + {(sem_post(&(cv->semBlockQueue)) + *resultPtr = errno; + return; + } + } + + /* + * XSH: Upon successful return, the mutex has been locked and is owned + * by the calling thread + */ + if ((result = pthread_mutex_lock(cleanup_args->mutexPtr)) != 0) + {((result + *resultPtr = result; + } + +} /* ptw32_cond_wait_cleanup */ + +static int +ptw32_cond_timedwait (pthread_cond_t * cond, + pthread_mutex_t * mutex, + const struct timespec *abstime) +{ + int result = 0; + pthread_cond_t cv; + ptw32_cond_wait_cleanup_args_t cleanup_args; + + if (cond == NULL || *cond == NULL) + {(cond + return EINVAL; + } + + /* + * We do a quick check to see if we need to do more work + * to initialise a static condition variable. We check + * again inside the guarded section of ptw32_cond_check_need_init() + * to avoid race conditions. + */ + if (*cond == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT) + {(*cond + result = ptw32_cond_check_need_init(cond); + } + + if (result != 0 && result != EBUSY) + {(result + return result; + } + + cv = *cond; + + /* + * Synchronize access to waiters blocked count (LEVEL-1) + */ + if (sem_wait(&(cv->semBlockLock)) != 0) + {(sem_wait(&(cv->semBlockLock)) + return errno; + } + + cv->nWaitersBlocked++; + + /* + * Thats it. Counted means waiting, no more access needed + */ + if (sem_post(&(cv->semBlockLock)) != 0) + {(sem_post(&(cv->semBlockLock)) + return errno; + } + + /* + * Setup this waiter cleanup handler + */ + cleanup_args.mutexPtr = mutex; + cleanup_args.cv = cv; + cleanup_args.resultPtr = &result; + + pthread_cleanup_push (ptw32_cond_wait_cleanup, (void *) &cleanup_args); + + /* + * Now we can release 'mutex' and... + */ + if ((result = pthread_mutex_unlock (mutex)) == 0) + {((result + + /* + * ...wait to be awakened by + * pthread_cond_signal, or + * pthread_cond_broadcast, or + * timeout, or + * thread cancellation + * + * Note: + * + * ptw32_sem_timedwait is a cancellation point, + * hence providing the mechanism for making + * pthread_cond_wait a cancellation point. + * We use the cleanup mechanism to ensure we + * re-lock the mutex and adjust (to)unblock(ed) waiters + * counts if we are cancelled, timed out or signalled. + */ + if (ptw32_sem_timedwait (&(cv->semBlockQueue), abstime) != 0) + {(ptw32_sem_timedwait + result = errno; + } + } + + /* + * Always cleanup + */ + pthread_cleanup_pop (1); + + + /* + * "result" can be modified by the cleanup handler. + */ + return (result); + +} /* ptw32_cond_timedwait */ + + +static int +ptw32_cond_unblock (pthread_cond_t * cond, + int unblockAll) +{ + int result; + pthread_cond_t cv; + + if (cond == NULL || *cond == NULL) + {(cond + return EINVAL; + } + + cv = *cond; + + /* + * No-op if the CV is static and hasn't been initialised yet. + * Assuming that any race condition is harmless. + */ + if (cv == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT) + {(cv + return 0; + } + + /* + * Synchronize access to waiters blocked count (LEVEL-1) + */ + if (sem_wait(&(cv->semBlockLock)) != 0) + {(sem_wait(&(cv->semBlockLock)) + return errno; + } + + /* + * Synchronize access to waiters (to)unblock(ed) counts (LEVEL-2) + * This sync.level supports _timedwait and cancellation + */ + if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0) + {((result + return result; + } + + /* + * Adjust waiters blocked and unblocked counts (collect garbage) + */ + if (cv->nWaitersUnblocked != 0) + {(cv->nWaitersUnblocked + cv->nWaitersBlocked -= cv->nWaitersUnblocked; + cv->nWaitersUnblocked = 0; + } + + /* + * If (after adjustment) there are still some waiters blocked counted... + */ + if ( cv->nWaitersBlocked > 0) + {( + /* + * We will unblock first waiter and leave semBlockLock/LEVEL-1 locked + * LEVEL-1 access is left disabled until last signal/unblock +completes + */ + cv->nWaitersToUnblock = (unblockAll) ? cv->nWaitersBlocked : 1; + + /* + * No more LEVEL-2 access to waiters (to)unblock(ed) counts needed + * This sync.level supports _timedwait and cancellation + */ + if ((result = pthread_mutex_unlock(&(cv->mtxUnblockLock))) != 0) + {((result + return result; + } + + + /* + * Now, with LEVEL-2 lock released let first waiter go through +semaphore + */ + if (sem_post(&(cv->semBlockQueue)) != 0) + {(sem_post(&(cv->semBlockQueue)) + return errno; + } + } + /* + * No waiter blocked - no more LEVEL-1 access to blocked count needed... + */ + else if (sem_post(&(cv->semBlockLock)) != 0) + { + return errno; + } + /* + * ...and no more LEVEL-2 access to waiters (to)unblock(ed) counts needed +too + * This sync.level supports _timedwait and cancellation + */ + else + { + result = pthread_mutex_unlock(&(cv->mtxUnblockLock)); + } + + return(result); + +} /* ptw32_cond_unblock */ + +int +pthread_cond_wait (pthread_cond_t * cond, + pthread_mutex_t * mutex) +{ + /* The NULL abstime arg means INFINITE waiting. */ + return(ptw32_cond_timedwait(cond, mutex, NULL)); +} /* pthread_cond_wait */ + + +int +pthread_cond_timedwait (pthread_cond_t * cond, + pthread_mutex_t * mutex, + const struct timespec *abstime) +{ + if (abstime == NULL) + {(abstime + return EINVAL; + } + + return(ptw32_cond_timedwait(cond, mutex, abstime)); +} /* pthread_cond_timedwait */ + + +int +pthread_cond_signal (pthread_cond_t * cond) +{ + /* The '0'(FALSE) unblockAll arg means unblock ONE waiter. */ + return(ptw32_cond_unblock(cond, 0)); +} /* pthread_cond_signal */ + +int +pthread_cond_broadcast (pthread_cond_t * cond) +{ + /* The '1'(TRUE) unblockAll arg means unblock ALL waiters. */ + return(ptw32_cond_unblock(cond, 1)); +} /* pthread_cond_broadcast */ + + + + +TEREKHOV@de.ibm.com on 17.01.2001 01:00:57 + +Please respond to TEREKHOV@de.ibm.com + +To: pthreads-win32@sourceware.cygnus.com +cc: schmidt@uci.edu +Subject: win32 conditions: sem+counter+event = broadcast_deadlock + + spur.wakeup/unfairness/incorrectness ?? + + + + + + + +Hi, + +Problem 1: broadcast_deadlock + +It seems that current implementation does not provide "atomic" +broadcasts. That may lead to "nested" broadcasts... and it seems +that nested case is not handled correctly -> producing a broadcast +DEADLOCK as a result. + +Scenario: + +N (>1) waiting threads W1..N are blocked (in _wait) on condition's +semaphore. + +Thread B1 calls pthread_cond_broadcast, which results in "releasing" N +W threads via incrementing semaphore counter by N (stored in +cv->waiters) BUT cv->waiters counter does not change!! The caller +thread B1 remains blocked on cv->waitersDone event (auto-reset!!) BUT +condition is not protected from starting another broadcast (when called +on another thread) while still waiting for the "old" broadcast to +complete on thread B1. + +M (>=0, <N) W threads are fast enough to go thru their _wait call and +decrement cv->waiters counter. + +L (N-M) "late" waiter W threads are a) still blocked/not returned from +their semaphore wait call or b) were preempted after sem_wait but before +lock( &cv->waitersLock ) or c) are blocked on cv->waitersLock. + +cv->waiters is still > 0 (= L). + +Another thread B2 (or some W thread from M group) calls +pthread_cond_broadcast and gains access to counter... neither a) nor b) +prevent thread B2 in pthread_cond_broadcast from gaining access to +counter and starting another broadcast ( for c) - it depends on +cv->waitersLock scheduling rules: FIFO=OK, PRTY=PROBLEM,... ) + +That call to pthread_cond_broadcast (on thread B2) will result in +incrementing semaphore by cv->waiters (=L) which is INCORRECT (all +W1..N were in fact already released by thread B1) and waiting on +_auto-reset_ event cv->waitersDone which is DEADLY WRONG (produces a +deadlock)... + +All late W1..L threads now have a chance to complete their _wait call. +Last W_L thread sets an auto-reselt event cv->waitersDone which will +release either B1 or B2 leaving one of B threads in a deadlock. + +Problem 2: spur.wakeup/unfairness/incorrectness + +It seems that: + +a) because of the same problem with counter which does not reflect the +actual number of NOT RELEASED waiters, the signal call may increment +a semaphore counter w/o having a waiter blocked on it. That will result +in (best case) spurious wake ups - performance degradation due to +unnecessary context switches and predicate re-checks and (in worth case) +unfairness/incorrectness problem - see b) + +b) neither signal nor broadcast prevent other threads - "new waiters" +(and in the case of signal, the caller thread as well) from going into +_wait and overtaking "old" waiters (already released but still not returned +from sem_wait on condition's semaphore). Win semaphore just [API DOC]: +"Maintains a count between zero and some maximum value, limiting the number +of threads that are simultaneously accessing a shared resource." Calling +ReleaseSemaphore does not imply (at least not documented) that on return +from ReleaseSemaphore all waiters will in fact become released (returned +from their Wait... call) and/or that new waiters calling Wait... afterwards +will become less importance. It is NOT documented to be an atomic release +of +waiters... And even if it would be there is still a problem with a thread +being preempted after Wait on semaphore and before Wait on cv->waitersLock +and scheduling rules for cv->waitersLock itself +(??WaitForMultipleObjects??) +That may result in unfairness/incorrectness problem as described +for SetEvent impl. in "Strategies for Implementing POSIX Condition +Variables +on Win32": http://www.cs.wustl.edu/~schmidt/win32-cv-1.html + +Unfairness -- The semantics of the POSIX pthread_cond_broadcast function is +to wake up all threads currently blocked in wait calls on the condition +variable. The awakened threads then compete for the external_mutex. To +ensure +fairness, all of these threads should be released from their +pthread_cond_wait calls and allowed to recheck their condition expressions +before other threads can successfully complete a wait on the condition +variable. + +Unfortunately, the SetEvent implementation above does not guarantee that +all +threads sleeping on the condition variable when cond_broadcast is called +will +acquire the external_mutex and check their condition expressions. Although +the Pthreads specification does not mandate this degree of fairness, the +lack of fairness can cause starvation. + +To illustrate the unfairness problem, imagine there are 2 threads, C1 and +C2, +that are blocked in pthread_cond_wait on condition variable not_empty_ that +is guarding a thread-safe message queue. Another thread, P1 then places two +messages onto the queue and calls pthread_cond_broadcast. If C1 returns +from +pthread_cond_wait, dequeues and processes the message, and immediately +waits +again then it and only it may end up acquiring both messages. Thus, C2 will +never get a chance to dequeue a message and run. + +The following illustrates the sequence of events: + +1. Thread C1 attempts to dequeue and waits on CV non_empty_ +2. Thread C2 attempts to dequeue and waits on CV non_empty_ +3. Thread P1 enqueues 2 messages and broadcasts to CV not_empty_ +4. Thread P1 exits +5. Thread C1 wakes up from CV not_empty_, dequeues a message and runs +6. Thread C1 waits again on CV not_empty_, immediately dequeues the 2nd + message and runs +7. Thread C1 exits +8. Thread C2 is the only thread left and blocks forever since + not_empty_ will never be signaled + +Depending on the algorithm being implemented, this lack of fairness may +yield +concurrent programs that have subtle bugs. Of course, application +developers +should not rely on the fairness semantics of pthread_cond_broadcast. +However, +there are many cases where fair implementations of condition variables can +simplify application code. + +Incorrectness -- A variation on the unfairness problem described above +occurs +when a third consumer thread, C3, is allowed to slip through even though it +was not waiting on condition variable not_empty_ when a broadcast occurred. + +To illustrate this, we will use the same scenario as above: 2 threads, C1 +and +C2, are blocked dequeuing messages from the message queue. Another thread, +P1 +then places two messages onto the queue and calls pthread_cond_broadcast. +C1 +returns from pthread_cond_wait, dequeues and processes the message. At this +time, C3 acquires the external_mutex, calls pthread_cond_wait and waits on +the events in WaitForMultipleObjects. Since C2 has not had a chance to run +yet, the BROADCAST event is still signaled. C3 then returns from +WaitForMultipleObjects, and dequeues and processes the message in the +queue. +Thus, C2 will never get a chance to dequeue a message and run. + +The following illustrates the sequence of events: + +1. Thread C1 attempts to dequeue and waits on CV non_empty_ +2. Thread C2 attempts to dequeue and waits on CV non_empty_ +3. Thread P1 enqueues 2 messages and broadcasts to CV not_empty_ +4. Thread P1 exits +5. Thread C1 wakes up from CV not_empty_, dequeues a message and runs +6. Thread C1 exits +7. Thread C3 waits on CV not_empty_, immediately dequeues the 2nd + message and runs +8. Thread C3 exits +9. Thread C2 is the only thread left and blocks forever since + not_empty_ will never be signaled + +In the above case, a thread that was not waiting on the condition variable +when a broadcast occurred was allowed to proceed. This leads to incorrect +semantics for a condition variable. + + +COMMENTS??? + +regards, +alexander. + +----------------------------------------------------------------------------- + +Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_* + implementation questions +Date: Wed, 21 Feb 2001 11:54:47 +0100 +From: TEREKHOV@de.ibm.com +To: lthomas@arbitrade.com +CC: rpj@ise.canberra.edu.au, Thomas Pfaff <tpfaff@gmx.net>, + Nanbor Wang <nanbor@cs.wustl.edu> + +Hi Louis, + +generation number 8.. + +had some time to revisit timeouts/spurious wakeup problem.. +found some bugs (in 7.b/c/d) and something to improve +(7a - using IPC semaphores but it should speedup Win32 +version as well). + +regards, +alexander. + +---------- Algorithm 8a / IMPL_SEM,UNBLOCK_STRATEGY == UNBLOCK_ALL ------ +given: +semBlockLock - bin.semaphore +semBlockQueue - semaphore +mtxExternal - mutex or CS +mtxUnblockLock - mutex or CS +nWaitersGone - int +nWaitersBlocked - int +nWaitersToUnblock - int + +wait( timeout ) { + + [auto: register int result ] // error checking omitted + [auto: register int nSignalsWasLeft ] + [auto: register int nWaitersWasGone ] + + sem_wait( semBlockLock ); + nWaitersBlocked++; + sem_post( semBlockLock ); + + unlock( mtxExternal ); + bTimedOut = sem_wait( semBlockQueue,timeout ); + + lock( mtxUnblockLock ); + if ( 0 != (nSignalsWasLeft = nWaitersToUnblock) ) { + if ( bTimeout ) { // timeout (or canceled) + if ( 0 != nWaitersBlocked ) { + nWaitersBlocked--; + } + else { + nWaitersGone++; // count spurious wakeups + } + } + if ( 0 == --nWaitersToUnblock ) { + if ( 0 != nWaitersBlocked ) { + sem_post( semBlockLock ); // open the gate + nSignalsWasLeft = 0; // do not open the gate below +again + } + else if ( 0 != (nWaitersWasGone = nWaitersGone) ) { + nWaitersGone = 0; + } + } + } + else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious +semaphore :-) + sem_wait( semBlockLock ); + nWaitersBlocked -= nWaitersGone; // something is going on here - +test of timeouts? :-) + sem_post( semBlockLock ); + nWaitersGone = 0; + } + unlock( mtxUnblockLock ); + + if ( 1 == nSignalsWasLeft ) { + if ( 0 != nWaitersWasGone ) { + // sem_adjust( -nWaitersWasGone ); + while ( nWaitersWasGone-- ) { + sem_wait( semBlockLock ); // better now than spurious +later + } + } + sem_post( semBlockLock ); // open the gate + } + + lock( mtxExternal ); + + return ( bTimedOut ) ? ETIMEOUT : 0; +} + +signal(bAll) { + + [auto: register int result ] + [auto: register int nSignalsToIssue] + + lock( mtxUnblockLock ); + + if ( 0 != nWaitersToUnblock ) { // the gate is closed!!! + if ( 0 == nWaitersBlocked ) { // NO-OP + return unlock( mtxUnblockLock ); + } + if (bAll) { + nWaitersToUnblock += nSignalsToIssue=nWaitersBlocked; + nWaitersBlocked = 0; + } + else { + nSignalsToIssue = 1; + nWaitersToUnblock++; + nWaitersBlocked--; + } + } + else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION! + sem_wait( semBlockLock ); // close the gate + if ( 0 != nWaitersGone ) { + nWaitersBlocked -= nWaitersGone; + nWaitersGone = 0; + } + if (bAll) { + nSignalsToIssue = nWaitersToUnblock = nWaitersBlocked; + nWaitersBlocked = 0; + } + else { + nSignalsToIssue = nWaitersToUnblock = 1; + nWaitersBlocked--; + } + } + else { // NO-OP + return unlock( mtxUnblockLock ); + } + + unlock( mtxUnblockLock ); + sem_post( semBlockQueue,nSignalsToIssue ); + return result; +} + +---------- Algorithm 8b / IMPL_SEM,UNBLOCK_STRATEGY == UNBLOCK_ONEBYONE +------ +given: +semBlockLock - bin.semaphore +semBlockQueue - bin.semaphore +mtxExternal - mutex or CS +mtxUnblockLock - mutex or CS +nWaitersGone - int +nWaitersBlocked - int +nWaitersToUnblock - int + +wait( timeout ) { + + [auto: register int result ] // error checking omitted + [auto: register int nWaitersWasGone ] + [auto: register int nSignalsWasLeft ] + + sem_wait( semBlockLock ); + nWaitersBlocked++; + sem_post( semBlockLock ); + + unlock( mtxExternal ); + bTimedOut = sem_wait( semBlockQueue,timeout ); + + lock( mtxUnblockLock ); + if ( 0 != (nSignalsWasLeft = nWaitersToUnblock) ) { + if ( bTimeout ) { // timeout (or canceled) + if ( 0 != nWaitersBlocked ) { + nWaitersBlocked--; + nSignalsWasLeft = 0; // do not unblock next waiter +below (already unblocked) + } + else { + nWaitersGone = 1; // spurious wakeup pending!! + } + } + if ( 0 == --nWaitersToUnblock && + if ( 0 != nWaitersBlocked ) { + sem_post( semBlockLock ); // open the gate + nSignalsWasLeft = 0; // do not open the gate below +again + } + else if ( 0 != (nWaitersWasGone = nWaitersGone) ) { + nWaitersGone = 0; + } + } + } + else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious +semaphore :-) + sem_wait( semBlockLock ); + nWaitersBlocked -= nWaitersGone; // something is going on here - +test of timeouts? :-) + sem_post( semBlockLock ); + nWaitersGone = 0; + } + unlock( mtxUnblockLock ); + + if ( 1 == nSignalsWasLeft ) { + if ( 0 != nWaitersWasGone ) { + // sem_adjust( -1 ); + sem_wait( semBlockQueue ); // better now than spurious +later + } + sem_post( semBlockLock ); // open the gate + } + else if ( 0 != nSignalsWasLeft ) { + sem_post( semBlockQueue ); // unblock next waiter + } + + lock( mtxExternal ); + + return ( bTimedOut ) ? ETIMEOUT : 0; +} + +signal(bAll) { + + [auto: register int result ] + + lock( mtxUnblockLock ); + + if ( 0 != nWaitersToUnblock ) { // the gate is closed!!! + if ( 0 == nWaitersBlocked ) { // NO-OP + return unlock( mtxUnblockLock ); + } + if (bAll) { + nWaitersToUnblock += nWaitersBlocked; + nWaitersBlocked = 0; + } + else { + nWaitersToUnblock++; + nWaitersBlocked--; + } + unlock( mtxUnblockLock ); + } + else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION! + sem_wait( semBlockLock ); // close the gate + if ( 0 != nWaitersGone ) { + nWaitersBlocked -= nWaitersGone; + nWaitersGone = 0; + } + if (bAll) { + nWaitersToUnblock = nWaitersBlocked; + nWaitersBlocked = 0; + } + else { + nWaitersToUnblock = 1; + nWaitersBlocked--; + } + unlock( mtxUnblockLock ); + sem_post( semBlockQueue ); + } + else { // NO-OP + unlock( mtxUnblockLock ); + } + + return result; +} + +---------- Algorithm 8c / IMPL_EVENT,UNBLOCK_STRATEGY == UNBLOCK_ONEBYONE +--------- +given: +hevBlockLock - auto-reset event +hevBlockQueue - auto-reset event +mtxExternal - mutex or CS +mtxUnblockLock - mutex or CS +nWaitersGone - int +nWaitersBlocked - int +nWaitersToUnblock - int + +wait( timeout ) { + + [auto: register int result ] // error checking omitted + [auto: register int nSignalsWasLeft ] + [auto: register int nWaitersWasGone ] + + wait( hevBlockLock,INFINITE ); + nWaitersBlocked++; + set_event( hevBlockLock ); + + unlock( mtxExternal ); + bTimedOut = wait( hevBlockQueue,timeout ); + + lock( mtxUnblockLock ); + if ( 0 != (SignalsWasLeft = nWaitersToUnblock) ) { + if ( bTimeout ) { // timeout (or canceled) + if ( 0 != nWaitersBlocked ) { + nWaitersBlocked--; + nSignalsWasLeft = 0; // do not unblock next waiter +below (already unblocked) + } + else { + nWaitersGone = 1; // spurious wakeup pending!! + } + } + if ( 0 == --nWaitersToUnblock ) + if ( 0 != nWaitersBlocked ) { + set_event( hevBlockLock ); // open the gate + nSignalsWasLeft = 0; // do not open the gate below +again + } + else if ( 0 != (nWaitersWasGone = nWaitersGone) ) { + nWaitersGone = 0; + } + } + } + else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious +event :-) + wait( hevBlockLock,INFINITE ); + nWaitersBlocked -= nWaitersGone; // something is going on here - +test of timeouts? :-) + set_event( hevBlockLock ); + nWaitersGone = 0; + } + unlock( mtxUnblockLock ); + + if ( 1 == nSignalsWasLeft ) { + if ( 0 != nWaitersWasGone ) { + reset_event( hevBlockQueue ); // better now than spurious +later + } + set_event( hevBlockLock ); // open the gate + } + else if ( 0 != nSignalsWasLeft ) { + set_event( hevBlockQueue ); // unblock next waiter + } + + lock( mtxExternal ); + + return ( bTimedOut ) ? ETIMEOUT : 0; +} + +signal(bAll) { + + [auto: register int result ] + + lock( mtxUnblockLock ); + + if ( 0 != nWaitersToUnblock ) { // the gate is closed!!! + if ( 0 == nWaitersBlocked ) { // NO-OP + return unlock( mtxUnblockLock ); + } + if (bAll) { + nWaitersToUnblock += nWaitersBlocked; + nWaitersBlocked = 0; + } + else { + nWaitersToUnblock++; + nWaitersBlocked--; + } + unlock( mtxUnblockLock ); + } + else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION! + wait( hevBlockLock,INFINITE ); // close the gate + if ( 0 != nWaitersGone ) { + nWaitersBlocked -= nWaitersGone; + nWaitersGone = 0; + } + if (bAll) { + nWaitersToUnblock = nWaitersBlocked; + nWaitersBlocked = 0; + } + else { + nWaitersToUnblock = 1; + nWaitersBlocked--; + } + unlock( mtxUnblockLock ); + set_event( hevBlockQueue ); + } + else { // NO-OP + unlock( mtxUnblockLock ); + } + + return result; +} + +---------- Algorithm 8d / IMPL_EVENT,UNBLOCK_STRATEGY == UNBLOCK_ALL ------ +given: +hevBlockLock - auto-reset event +hevBlockQueueS - auto-reset event // for signals +hevBlockQueueB - manual-reset even // for broadcasts +mtxExternal - mutex or CS +mtxUnblockLock - mutex or CS +eBroadcast - int // 0: no broadcast, 1: broadcast, 2: +broadcast after signal(s) +nWaitersGone - int +nWaitersBlocked - int +nWaitersToUnblock - int + +wait( timeout ) { + + [auto: register int result ] // error checking omitted + [auto: register int eWasBroadcast ] + [auto: register int nSignalsWasLeft ] + [auto: register int nWaitersWasGone ] + + wait( hevBlockLock,INFINITE ); + nWaitersBlocked++; + set_event( hevBlockLock ); + + unlock( mtxExternal ); + bTimedOut = waitformultiple( hevBlockQueueS,hevBlockQueueB,timeout,ONE ); + + lock( mtxUnblockLock ); + if ( 0 != (SignalsWasLeft = nWaitersToUnblock) ) { + if ( bTimeout ) { // timeout (or canceled) + if ( 0 != nWaitersBlocked ) { + nWaitersBlocked--; + nSignalsWasLeft = 0; // do not unblock next waiter +below (already unblocked) + } + else if ( 1 != eBroadcast ) { + nWaitersGone = 1; + } + } + if ( 0 == --nWaitersToUnblock ) { + if ( 0 != nWaitersBlocked ) { + set_event( hevBlockLock ); // open the gate + nSignalsWasLeft = 0; // do not open the gate below +again + } + else { + if ( 0 != (eWasBroadcast = eBroadcast) ) { + eBroadcast = 0; + } + if ( 0 != (nWaitersWasGone = nWaitersGone ) { + nWaitersGone = 0; + } + } + } + else if ( 0 != eBroadcast ) { + nSignalsWasLeft = 0; // do not unblock next waiter +below (already unblocked) + } + } + else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious +event :-) + wait( hevBlockLock,INFINITE ); + nWaitersBlocked -= nWaitersGone; // something is going on here - +test of timeouts? :-) + set_event( hevBlockLock ); + nWaitersGone = 0; + } + unlock( mtxUnblockLock ); + + if ( 1 == nSignalsWasLeft ) { + if ( 0 != eWasBroadcast ) { + reset_event( hevBlockQueueB ); + } + if ( 0 != nWaitersWasGone ) { + reset_event( hevBlockQueueS ); // better now than spurious +later + } + set_event( hevBlockLock ); // open the gate + } + else if ( 0 != nSignalsWasLeft ) { + set_event( hevBlockQueueS ); // unblock next waiter + } + + lock( mtxExternal ); + + return ( bTimedOut ) ? ETIMEOUT : 0; +} + +signal(bAll) { + + [auto: register int result ] + [auto: register HANDLE hevBlockQueue ] + + lock( mtxUnblockLock ); + + if ( 0 != nWaitersToUnblock ) { // the gate is closed!!! + if ( 0 == nWaitersBlocked ) { // NO-OP + return unlock( mtxUnblockLock ); + } + if (bAll) { + nWaitersToUnblock += nWaitersBlocked; + nWaitersBlocked = 0; + eBroadcast = 2; + hevBlockQueue = hevBlockQueueB; + } + else { + nWaitersToUnblock++; + nWaitersBlocked--; + return unlock( mtxUnblockLock ); + } + } + else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION! + wait( hevBlockLock,INFINITE ); // close the gate + if ( 0 != nWaitersGone ) { + nWaitersBlocked -= nWaitersGone; + nWaitersGone = 0; + } + if (bAll) { + nWaitersToUnblock = nWaitersBlocked; + nWaitersBlocked = 0; + eBroadcast = 1; + hevBlockQueue = hevBlockQueueB; + } + else { + nWaitersToUnblock = 1; + nWaitersBlocked--; + hevBlockQueue = hevBlockQueueS; + } + } + else { // NO-OP + return unlock( mtxUnblockLock ); + } + + unlock( mtxUnblockLock ); + set_event( hevBlockQueue ); + return result; +} +---------------------- Forwarded by Alexander Terekhov/Germany/IBM on +02/21/2001 09:13 AM --------------------------- + +Alexander Terekhov +02/20/2001 04:33 PM + +To: Louis Thomas <lthomas@arbitrade.com> +cc: + +From: Alexander Terekhov/Germany/IBM@IBMDE +Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_* implementatio + n questions +Importance: Normal + +>Sorry, gotta take a break and work on something else for a while. +>Real work +>calls, unfortunately. I'll get back to you in two or three days. + +ok. no problem. here is some more stuff for pauses you might have +in between :) + +---------- Algorithm 7d / IMPL_EVENT,UNBLOCK_STRATEGY == UNBLOCK_ALL ------ +given: +hevBlockLock - auto-reset event +hevBlockQueueS - auto-reset event // for signals +hevBlockQueueB - manual-reset even // for broadcasts +mtxExternal - mutex or CS +mtxUnblockLock - mutex or CS +bBroadcast - int +nWaitersGone - int +nWaitersBlocked - int +nWaitersToUnblock - int + +wait( timeout ) { + + [auto: register int result ] // error checking omitted + [auto: register int bWasBroadcast ] + [auto: register int nSignalsWasLeft ] + + wait( hevBlockLock,INFINITE ); + nWaitersBlocked++; + set_event( hevBlockLock ); + + unlock( mtxExternal ); + bTimedOut = waitformultiple( hevBlockQueueS,hevBlockQueueB,timeout,ONE ); + + lock( mtxUnblockLock ); + if ( 0 != (SignalsWasLeft = nWaitersToUnblock) ) { + if ( bTimeout ) { // timeout (or canceled) + if ( 0 != nWaitersBlocked ) { + nWaitersBlocked--; + nSignalsWasLeft = 0; // do not unblock next waiter +below (already unblocked) + } + else if ( !bBroadcast ) { + wait( hevBlockQueueS,INFINITE ); // better now than spurious +later + } + } + if ( 0 == --nWaitersToUnblock ) { + if ( 0 != nWaitersBlocked ) { + if ( bBroadcast ) { + reset_event( hevBlockQueueB ); + bBroadcast = false; + } + set_event( hevBlockLock ); // open the gate + nSignalsWasLeft = 0; // do not open the gate below +again + } + else if ( false != (bWasBroadcast = bBroadcast) ) { + bBroadcast = false; + } + } + else { + bWasBroadcast = bBroadcast; + } + } + else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious +event :-) + wait( hevBlockLock,INFINITE ); + nWaitersBlocked -= nWaitersGone; // something is going on here - +test of timeouts? :-) + set_event( hevBlockLock ); + nWaitersGone = 0; + } + unlock( mtxUnblockLock ); + + if ( 1 == nSignalsWasLeft ) { + if ( bWasBroadcast ) { + reset_event( hevBlockQueueB ); + } + set_event( hevBlockLock ); // open the gate + } + else if ( 0 != nSignalsWasLeft && !bWasBroadcast ) { + set_event( hevBlockQueueS ); // unblock next waiter + } + + lock( mtxExternal ); + + return ( bTimedOut ) ? ETIMEOUT : 0; +} + +signal(bAll) { + + [auto: register int result ] + [auto: register HANDLE hevBlockQueue ] + + lock( mtxUnblockLock ); + + if ( 0 != nWaitersToUnblock ) { // the gate is closed!!! + if ( 0 == nWaitersBlocked ) { // NO-OP + return unlock( mtxUnblockLock ); + } + if (bAll) { + nWaitersToUnblock += nWaitersBlocked; + nWaitersBlocked = 0; + bBroadcast = true; + hevBlockQueue = hevBlockQueueB; + } + else { + nWaitersToUnblock++; + nWaitersBlocked--; + return unlock( mtxUnblockLock ); + } + } + else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION! + wait( hevBlockLock,INFINITE ); // close the gate + if ( 0 != nWaitersGone ) { + nWaitersBlocked -= nWaitersGone; + nWaitersGone = 0; + } + if (bAll) { + nWaitersToUnblock = nWaitersBlocked; + nWaitersBlocked = 0; + bBroadcast = true; + hevBlockQueue = hevBlockQueueB; + } + else { + nWaitersToUnblock = 1; + nWaitersBlocked--; + hevBlockQueue = hevBlockQueueS; + } + } + else { // NO-OP + return unlock( mtxUnblockLock ); + } + + unlock( mtxUnblockLock ); + set_event( hevBlockQueue ); + return result; +} + + +---------------------------------------------------------------------------- + +Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_* implementatio + n questions +Date: Mon, 26 Feb 2001 22:20:12 -0600 +From: Louis Thomas <lthomas@arbitrade.com> +To: "'TEREKHOV@de.ibm.com'" <TEREKHOV@de.ibm.com> +CC: rpj@ise.canberra.edu.au, Thomas Pfaff <tpfaff@gmx.net>, + Nanbor Wang + <nanbor@cs.wustl.edu> + +Sorry all. Busy week. + +> this insures the fairness +> which POSIX does not (e.g. two subsequent broadcasts - the gate does +insure +> that first wave waiters will start the race for the mutex before waiters +> from the second wave - Linux pthreads process/unblock both waves +> concurrently...) + +I'm not sure how we are any more fair about this than Linux. We certainly +don't guarantee that the threads released by the first broadcast will get +the external mutex before the threads of the second wave. In fact, it is +possible that those threads will never get the external mutex if there is +enough contention for it. + +> e.g. i was thinking about implementation with a pool of +> N semaphores/counters [...] + +I considered that too. The problem is as you mentioned in a). You really +need to assign threads to semaphores once you know how you want to wake them +up, not when they first begin waiting which is the only time you can assign +them. + +> well, i am not quite sure that i've fully understood your scenario, + +Hmm. Well, it think it's an important example, so I'll try again. First, we +have thread A which we KNOW is waiting on a condition. As soon as it becomes +unblocked for any reason, we will know because it will set a flag. Since the +flag is not set, we are 100% confident that thread A is waiting on the +condition. We have another thread, thread B, which has acquired the mutex +and is about to wait on the condition. Thus it is pretty clear that at any +point, either just A is waiting, or A and B are waiting. Now thread C comes +along. C is about to do a broadcast on the condition. A broadcast is +guaranteed to unblock all threads currently waiting on a condition, right? +Again, we said that either just A is waiting, or A and B are both waiting. +So, when C does its broadcast, depending upon whether B has started waiting +or not, thread C will unblock A or unblock A and B. Either way, C must +unblock A, right? + +Now, you said anything that happens is correct so long as a) "a signal is +not lost between unlocking the mutex and waiting on the condition" and b) "a +thread must not steal a signal it sent", correct? Requirement b) is easy to +satisfy: in this scenario, thread C will never wait on the condition, so it +won't steal any signals. Requirement a) is not hard either. The only way we +could fail to meet requirement a) in this scenario is if thread B was +started waiting but didn't wake up because a signal was lost. This will not +happen. + +Now, here is what happens. Assume thread C beats thread B. Thread C looks to +see how many threads are waiting on the condition. Thread C sees just one +thread, thread A, waiting. It does a broadcast waking up just one thread +because just one thread is waiting. Next, before A can become unblocked, +thread B begins waiting. Now there are two threads waiting, but only one +will be unblocked. Suppose B wins. B will become unblocked. A will not +become unblocked, because C only unblocked one thread (sema_post cond, 1). +So at the end, B finishes and A remains blocked. + +We have met both of your requirements, so by your rules, this is an +acceptable outcome. However, I think that the spec says this is an +unacceptable outcome! We know for certain that A was waiting and that C did +a broadcast, but A did not become unblocked! Yet, the spec says that a +broadcast wakes up all waiting threads. This did not happen. Do you agree +that this shows your rules are not strict enough? + +> and what about N2? :) this one does allow almost everything. + +Don't get me started about rule #2. I'll NEVER advocate an algorithm that +uses rule 2 as an excuse to suck! + +> but it is done (decrement)under mutex protection - this is not a subject +> of a race condition. + +You are correct. My mistake. + +> i would remove "_bTimedOut=false".. after all, it was a real timeout.. + +I disagree. A thread that can't successfully retract its waiter status can't +really have timed out. If a thread can't return without executing extra code +to deal with the fact that someone tried to unblock it, I think it is a poor +idea to pretend we +didn't realize someone was trying to signal us. After all, a signal is more +important than a time out. + +> when nSignaled != 0, it is possible to update nWaiters (--) and do not +> touch nGone + +I realize this, but I was thinking that writing it the other ways saves +another if statement. + +> adjust only if nGone != 0 and save one cache memory write - probably much +slower than 'if' + +Hmm. You are probably right. + +> well, in a strange (e.g. timeout test) program you may (theoretically) +> have an overflow of nWaiters/nGone counters (with waiters repeatedly +timing +> out and no signals at all). + +Also true. Not only that, but you also have the possibility that one could +overflow the number of waiters as well! However, considering the limit you +have chosen for nWaitersGone, I suppose it is unlikely that anyone would be +able to get INT_MAX/2 threads waiting on a single condition. :) + +Analysis of 8a: + +It looks correct to me. + +What are IPC semaphores? + +In the line where you state, "else if ( nWaitersBlocked > nWaitersGone ) { +// HARMLESS RACE CONDITION!" there is no race condition for nWaitersGone +because nWaitersGone is never modified without holding mtxUnblockLock. You +are correct that there is a harmless race on nWaitersBlocked, which can +increase and make the condition become true just after we check it. If this +happens, we interpret it as the wait starting after the signal. + +I like your optimization of this. You could improve Alg. 6 as follows: +---------- Algorithm 6b ---------- +signal(bAll) { + _nSig=0 + lock counters + // this is safe because nWaiting can only be decremented by a thread that + // owns counters and nGone can only be changed by a thread that owns +counters. + if (nWaiting>nGone) { + if (0==nSignaled) { + sema_wait gate // close gate if not already closed + } + if (nGone>0) { + nWaiting-=nGone + nGone=0 + } + _nSig=bAll?nWaiting:1 + nSignaled+=_nSig + nWaiting-=_nSig + } + unlock counters + if (0!=_nSig) { + sema_post queue, _nSig + } +} +---------- ---------- ---------- +I guess this wouldn't apply to Alg 8a because nWaitersGone changes meanings +depending upon whether the gate is open or closed. + +In the loop "while ( nWaitersWasGone-- ) {" you do a sema_wait on +semBlockLock. Perhaps waiting on semBlockQueue would be a better idea. + +What have you gained by making the last thread to be signaled do the waits +for all the timed out threads, besides added complexity? It took me a long +time to figure out what your objective was with this, to realize you were +using nWaitersGone to mean two different things, and to verify that you +hadn't introduced any bug by doing this. Even now I'm not 100% sure. + +What has all this playing about with nWaitersGone really gained us besides a +lot of complexity (it is much harder to verify that this solution is +correct), execution overhead (we now have a lot more if statements to +evaluate), and space overhead (more space for the extra code, and another +integer in our data)? We did manage to save a lock/unlock pair in an +uncommon case (when a time out occurs) at the above mentioned expenses in +the common cases. + +As for 8b, c, and d, they look ok though I haven't studied them thoroughly. +What would you use them for? + + Later, + -Louis! :) + +----------------------------------------------------------------------------- + +Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_* implementatio + n questions +Date: Tue, 27 Feb 2001 15:51:28 +0100 +From: TEREKHOV@de.ibm.com +To: Louis Thomas <lthomas@arbitrade.com> +CC: rpj@ise.canberra.edu.au, Thomas Pfaff <tpfaff@gmx.net>, + Nanbor Wang <nanbor@cs.wustl.edu> + +Hi Louis, + +>> that first wave waiters will start the race for the mutex before waiters +>> from the second wave - Linux pthreads process/unblock both waves +>> concurrently...) +> +>I'm not sure how we are any more fair about this than Linux. We certainly +>don't guarantee that the threads released by the first broadcast will get +>the external mutex before the threads of the second wave. In fact, it is +>possible that those threads will never get the external mutex if there is +>enough contention for it. + +correct. but gate is nevertheless more fair than Linux because of the +barrier it establishes between two races (1st and 2nd wave waiters) for +the mutex which under 'normal' circumstances (e.g. all threads of equal +priorities,..) will 'probably' result in fair behaviour with respect to +mutex ownership. + +>> well, i am not quite sure that i've fully understood your scenario, +> +>Hmm. Well, it think it's an important example, so I'll try again. ... + +ok. now i seem to understand this example. well, now it seems to me +that the only meaningful rule is just: + +a) "a signal is not lost between unlocking the mutex and waiting on the +condition" + +and that the rule + +b) "a thread must not steal a signal it sent" + +is not needed at all because a thread which violates b) also violates a). + +i'll try to explain.. + +i think that the most important thing is how POSIX defines waiter's +visibility: + +"if another thread is able to acquire the mutex after the about-to-block +thread +has released it, then a subsequent call to pthread_cond_signal() or +pthread_cond_broadcast() in that thread behaves as if it were issued after +the about-to-block thread has blocked. " + +my understanding is the following: + +1) there is no guarantees whatsoever with respect to whether +signal/broadcast +will actually unblock any 'waiter' if it is done w/o acquiring the mutex +first +(note that a thread may release it before signal/broadcast - it does not +matter). + +2) it is guaranteed that waiters become 'visible' - eligible for unblock as +soon +as signalling thread acquires the mutex (but not before!!) + +so.. + +>So, when C does its broadcast, depending upon whether B has started +waiting +>or not, thread C will unblock A or unblock A and B. Either way, C must +>unblock A, right? + +right. but only if C did acquire the mutex prior to broadcast (it may +release it before broadcast as well). + +implementation will violate waiters visibility rule (signal will become +lost) +if C will not unblock A. + +>Now, here is what happens. Assume thread C beats thread B. Thread C looks +to +>see how many threads are waiting on the condition. Thread C sees just one +>thread, thread A, waiting. It does a broadcast waking up just one thread +>because just one thread is waiting. Next, before A can become unblocked, +>thread B begins waiting. Now there are two threads waiting, but only one +>will be unblocked. Suppose B wins. B will become unblocked. A will not +>become unblocked, because C only unblocked one thread (sema_post cond, 1). +>So at the end, B finishes and A remains blocked. + +thread C did acquire the mutex ("Thread C sees just one thread, thread A, +waiting"). beginning from that moment it is guaranteed that subsequent +broadcast will unblock A. Otherwise we will have a lost signal with respect +to A. I do think that it does not matter whether the signal was physically +(completely) lost or was just stolen by another thread (B) - in both cases +it was simply lost with respect to A. + +>..Do you agree that this shows your rules are not strict enough? + +probably the opposite.. :-) i think that it shows that the only meaningful +rule is + +a) "a signal is not lost between unlocking the mutex and waiting on the +condition" + +with clarification of waiters visibility as defined by POSIX above. + +>> i would remove "_bTimedOut=false".. after all, it was a real timeout.. +> +>I disagree. A thread that can't successfully retract its waiter status +can't +>really have timed out. If a thread can't return without executing extra +code +>to deal with the fact that someone tried to unblock it, I think it is a +poor +>idea to pretend we +>didn't realize someone was trying to signal us. After all, a signal is +more +>important than a time out. + +a) POSIX does allow timed out thread to consume a signal (cancelled is +not). +b) ETIMEDOUT status just says that: "The time specified by abstime to +pthread_cond_timedwait() has passed." +c) it seem to me that hiding timeouts would violate "The +pthread_cond_timedwait() +function is the same as pthread_cond_wait() except that an error is +returned if +the absolute time specified by abstime passes (that is, system time equals +or +exceeds abstime) before the condition cond is signaled or broadcasted" +because +the abs. time did really pass before cond was signaled (waiter was +released via semaphore). however, if it really matters, i could imaging +that we +can save an abs. time of signal/broadcast and compare it with timeout after +unblock to find out whether it was a 'real' timeout or not. absent this +check +i do think that hiding timeouts would result in technical violation of +specification.. but i think that this check is not important and we can +simply +trust timeout error code provided by wait since we are not trying to make +'hard' realtime implementation. + +>What are IPC semaphores? + +<sys/sem.h> +int semctl(int, int, int, ...); +int semget(key_t, int, int); +int semop(int, struct sembuf *, size_t); + +they support adjustment of semaphore counter (semvalue) +in one single call - imaging Win32 ReleaseSemaphore( hsem,-N ) + +>In the line where you state, "else if ( nWaitersBlocked > nWaitersGone ) { +>// HARMLESS RACE CONDITION!" there is no race condition for nWaitersGone +>because nWaitersGone is never modified without holding mtxUnblockLock. You +>are correct that there is a harmless race on nWaitersBlocked, which can +>increase and make the condition become true just after we check it. If +this +>happens, we interpret it as the wait starting after the signal. + +well, the reason why i've asked on comp.programming.threads whether this +race +condition is harmless or not is that in order to be harmless it should not +violate the waiters visibility rule (see above). Fortunately, we increment +the counter under protection of external mutex.. so that any (signalling) +thread which will acquire the mutex next, should see the updated counter +(in signal) according to POSIX memory visibility rules and mutexes +(memory barriers). But i am not so sure how it actually works on +Win32/INTEL +which does not explicitly define any memory visibility rules :( + +>I like your optimization of this. You could improve Alg. 6 as follows: +>---------- Algorithm 6b ---------- +>signal(bAll) { +> _nSig=0 +> lock counters +> // this is safe because nWaiting can only be decremented by a thread +that +> // owns counters and nGone can only be changed by a thread that owns +>counters. +> if (nWaiting>nGone) { +> if (0==nSignaled) { +> sema_wait gate // close gate if not already closed +> } +> if (nGone>0) { +> nWaiting-=nGone +> nGone=0 +> } +> _nSig=bAll?nWaiting:1 +> nSignaled+=_nSig +> nWaiting-=_nSig +> } +> unlock counters +> if (0!=_nSig) { +> sema_post queue, _nSig +> } +>} +>---------- ---------- ---------- +>I guess this wouldn't apply to Alg 8a because nWaitersGone changes +meanings +>depending upon whether the gate is open or closed. + +agree. + +>In the loop "while ( nWaitersWasGone-- ) {" you do a sema_wait on +>semBlockLock. Perhaps waiting on semBlockQueue would be a better idea. + +you are correct. my mistake. + +>What have you gained by making the last thread to be signaled do the waits +>for all the timed out threads, besides added complexity? It took me a long +>time to figure out what your objective was with this, to realize you were +>using nWaitersGone to mean two different things, and to verify that you +>hadn't introduced any bug by doing this. Even now I'm not 100% sure. +> +>What has all this playing about with nWaitersGone really gained us besides +a +>lot of complexity (it is much harder to verify that this solution is +>correct), execution overhead (we now have a lot more if statements to +>evaluate), and space overhead (more space for the extra code, and another +>integer in our data)? We did manage to save a lock/unlock pair in an +>uncommon case (when a time out occurs) at the above mentioned expenses in +>the common cases. + +well, please consider the following: + +1) with multiple waiters unblocked (but some timed out) the trick with +counter +seem to ensure potentially higher level of concurrency by not delaying +most of unblocked waiters for semaphore cleanup - only the last one +will be delayed but all others would already contend/acquire/release +the external mutex - the critical section protected by mtxUnblockLock is +made smaller (increment + couple of IFs is faster than system/kernel call) +which i think is good in general. however, you are right, this is done +at expense of 'normal' waiters.. + +2) some semaphore APIs (e.g. POSIX IPC sems) do allow to adjust the +semaphore counter in one call => less system/kernel calls.. imagine: + +if ( 1 == nSignalsWasLeft ) { + if ( 0 != nWaitersWasGone ) { + ReleaseSemaphore( semBlockQueue,-nWaitersWasGone ); // better now +than spurious later + } + sem_post( semBlockLock ); // open the gate + } + +3) even on win32 a single thread doing multiple cleanup calls (to wait) +will probably result in faster execution (because of processor caching) +than multiple threads each doing a single call to wait. + +>As for 8b, c, and d, they look ok though I haven't studied them +thoroughly. +>What would you use them for? + +8b) for semaphores which do not allow to unblock multiple waiters +in a single call to post/release (e.g. POSIX realtime semaphores - +<semaphore.h>) + +8c/8d) for WinCE prior to 3.0 (WinCE 3.0 does have semaphores) + +ok. so, which one is the 'final' algorithm(s) which we should use in +pthreads-win32?? + +regards, +alexander. + +---------------------------------------------------------------------------- + +Louis Thomas <lthomas@arbitrade.com> on 02/27/2001 05:20:12 AM + +Please respond to Louis Thomas <lthomas@arbitrade.com> + +To: Alexander Terekhov/Germany/IBM@IBMDE +cc: rpj@ise.canberra.edu.au, Thomas Pfaff <tpfaff@gmx.net>, Nanbor Wang + <nanbor@cs.wustl.edu> +Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_* implementatio + n questions + +Sorry all. Busy week. + +> this insures the fairness +> which POSIX does not (e.g. two subsequent broadcasts - the gate does +insure +> that first wave waiters will start the race for the mutex before waiters +> from the second wave - Linux pthreads process/unblock both waves +> concurrently...) + +I'm not sure how we are any more fair about this than Linux. We certainly +don't guarantee that the threads released by the first broadcast will get +the external mutex before the threads of the second wave. In fact, it is +possible that those threads will never get the external mutex if there is +enough contention for it. + +> e.g. i was thinking about implementation with a pool of +> N semaphores/counters [...] + +I considered that too. The problem is as you mentioned in a). You really +need to assign threads to semaphores once you know how you want to wake +them +up, not when they first begin waiting which is the only time you can assign +them. + +> well, i am not quite sure that i've fully understood your scenario, + +Hmm. Well, it think it's an important example, so I'll try again. First, we +have thread A which we KNOW is waiting on a condition. As soon as it +becomes +unblocked for any reason, we will know because it will set a flag. Since +the +flag is not set, we are 100% confident that thread A is waiting on the +condition. We have another thread, thread B, which has acquired the mutex +and is about to wait on the condition. Thus it is pretty clear that at any +point, either just A is waiting, or A and B are waiting. Now thread C comes +along. C is about to do a broadcast on the condition. A broadcast is +guaranteed to unblock all threads currently waiting on a condition, right? +Again, we said that either just A is waiting, or A and B are both waiting. +So, when C does its broadcast, depending upon whether B has started waiting +or not, thread C will unblock A or unblock A and B. Either way, C must +unblock A, right? + +Now, you said anything that happens is correct so long as a) "a signal is +not lost between unlocking the mutex and waiting on the condition" and b) +"a +thread must not steal a signal it sent", correct? Requirement b) is easy to +satisfy: in this scenario, thread C will never wait on the condition, so it +won't steal any signals. Requirement a) is not hard either. The only way +we +could fail to meet requirement a) in this scenario is if thread B was +started waiting but didn't wake up because a signal was lost. This will not +happen. + +Now, here is what happens. Assume thread C beats thread B. Thread C looks +to +see how many threads are waiting on the condition. Thread C sees just one +thread, thread A, waiting. It does a broadcast waking up just one thread +because just one thread is waiting. Next, before A can become unblocked, +thread B begins waiting. Now there are two threads waiting, but only one +will be unblocked. Suppose B wins. B will become unblocked. A will not +become unblocked, because C only unblocked one thread (sema_post cond, 1). +So at the end, B finishes and A remains blocked. + +We have met both of your requirements, so by your rules, this is an +acceptable outcome. However, I think that the spec says this is an +unacceptable outcome! We know for certain that A was waiting and that C did +a broadcast, but A did not become unblocked! Yet, the spec says that a +broadcast wakes up all waiting threads. This did not happen. Do you agree +that this shows your rules are not strict enough? + +> and what about N2? :) this one does allow almost everything. + +Don't get me started about rule #2. I'll NEVER advocate an algorithm that +uses rule 2 as an excuse to suck! + +> but it is done (decrement)under mutex protection - this is not a subject +> of a race condition. + +You are correct. My mistake. + +> i would remove "_bTimedOut=false".. after all, it was a real timeout.. + +I disagree. A thread that can't successfully retract its waiter status +can't +really have timed out. If a thread can't return without executing extra +code +to deal with the fact that someone tried to unblock it, I think it is a +poor +idea to pretend we +didn't realize someone was trying to signal us. After all, a signal is more +important than a time out. + +> when nSignaled != 0, it is possible to update nWaiters (--) and do not +> touch nGone + +I realize this, but I was thinking that writing it the other ways saves +another if statement. + +> adjust only if nGone != 0 and save one cache memory write - probably much +slower than 'if' + +Hmm. You are probably right. + +> well, in a strange (e.g. timeout test) program you may (theoretically) +> have an overflow of nWaiters/nGone counters (with waiters repeatedly +timing +> out and no signals at all). + +Also true. Not only that, but you also have the possibility that one could +overflow the number of waiters as well! However, considering the limit you +have chosen for nWaitersGone, I suppose it is unlikely that anyone would be +able to get INT_MAX/2 threads waiting on a single condition. :) + +Analysis of 8a: + +It looks correct to me. + +What are IPC semaphores? + +In the line where you state, "else if ( nWaitersBlocked > nWaitersGone ) { +// HARMLESS RACE CONDITION!" there is no race condition for nWaitersGone +because nWaitersGone is never modified without holding mtxUnblockLock. You +are correct that there is a harmless race on nWaitersBlocked, which can +increase and make the condition become true just after we check it. If this +happens, we interpret it as the wait starting after the signal. + +I like your optimization of this. You could improve Alg. 6 as follows: +---------- Algorithm 6b ---------- +signal(bAll) { + _nSig=0 + lock counters + // this is safe because nWaiting can only be decremented by a thread that + // owns counters and nGone can only be changed by a thread that owns +counters. + if (nWaiting>nGone) { + if (0==nSignaled) { + sema_wait gate // close gate if not already closed + } + if (nGone>0) { + nWaiting-=nGone + nGone=0 + } + _nSig=bAll?nWaiting:1 + nSignaled+=_nSig + nWaiting-=_nSig + } + unlock counters + if (0!=_nSig) { + sema_post queue, _nSig + } +} +---------- ---------- ---------- +I guess this wouldn't apply to Alg 8a because nWaitersGone changes meanings +depending upon whether the gate is open or closed. + +In the loop "while ( nWaitersWasGone-- ) {" you do a sema_wait on +semBlockLock. Perhaps waiting on semBlockQueue would be a better idea. + +What have you gained by making the last thread to be signaled do the waits +for all the timed out threads, besides added complexity? It took me a long +time to figure out what your objective was with this, to realize you were +using nWaitersGone to mean two different things, and to verify that you +hadn't introduced any bug by doing this. Even now I'm not 100% sure. + +What has all this playing about with nWaitersGone really gained us besides +a +lot of complexity (it is much harder to verify that this solution is +correct), execution overhead (we now have a lot more if statements to +evaluate), and space overhead (more space for the extra code, and another +integer in our data)? We did manage to save a lock/unlock pair in an +uncommon case (when a time out occurs) at the above mentioned expenses in +the common cases. + +As for 8b, c, and d, they look ok though I haven't studied them thoroughly. +What would you use them for? + + Later, + -Louis! :) + |