From e6f1797e9e9925ae7f9dda54806ef8f52ae3ed07 Mon Sep 17 00:00:00 2001 From: rpj Date: Mon, 11 Feb 2002 01:53:22 +0000 Subject: Splitting files. See ChangeLog file for details. --- README.CV | 6072 ++++++++++++++++++++++++++++++------------------------------- 1 file changed, 3036 insertions(+), 3036 deletions(-) (limited to 'README.CV') diff --git a/README.CV b/README.CV index 522fa60..698728b 100644 --- a/README.CV +++ b/README.CV @@ -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 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 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 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, 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 , - Nanbor Wang - -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 -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 -To: "'TEREKHOV@de.ibm.com'" -CC: rpj@ise.canberra.edu.au, Thomas Pfaff , - Nanbor Wang - - -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 -CC: rpj@ise.canberra.edu.au, Thomas Pfaff , - Nanbor Wang - -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? - - -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 - -) - -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 on 02/27/2001 05:20:12 AM - -Please respond to Louis Thomas - -To: Alexander Terekhov/Germany/IBM@IBMDE -cc: rpj@ise.canberra.edu.au, Thomas Pfaff , Nanbor Wang - -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 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 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 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, 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 , + Nanbor Wang + +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 +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 +To: "'TEREKHOV@de.ibm.com'" +CC: rpj@ise.canberra.edu.au, Thomas Pfaff , + Nanbor Wang + + +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 +CC: rpj@ise.canberra.edu.au, Thomas Pfaff , + Nanbor Wang + +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? + + +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 - +) + +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 on 02/27/2001 05:20:12 AM + +Please respond to Louis Thomas + +To: Alexander Terekhov/Germany/IBM@IBMDE +cc: rpj@ise.canberra.edu.au, Thomas Pfaff , Nanbor Wang + +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! :) + -- cgit v1.2.3