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 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 decrement the waiters count * if we are canceled. */ if (ptw32_sem_timedwait (&(cv->sema), abstime) == -1) { result = PTW32_GET_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 = PTW32_GET_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 = PTW32_GET_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 = PTW32_GET_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! :)