1README.CV -- Condition Variables 2-------------------------------- 3 4The original implementation of condition variables in 5pthreads-win32 was based on a discussion paper: 6 7"Strategies for Implementing POSIX Condition Variables 8on Win32": http://www.cs.wustl.edu/~schmidt/win32-cv-1.html 9 10The changes suggested below were made on Feb 6 2001. This 11file is included in the package for the benefit of anyone 12interested in understanding the pthreads-win32 implementation 13of condition variables and the (sometimes subtle) issues that 14it attempts to resolve. 15 16Thanks go to the individuals whose names appear throughout 17the following text. 18 19Ross Johnson 20 21-------------------------------------------------------------------- 22 23fyi.. (more detailed problem description/demos + possible fix/patch) 24 25regards, 26alexander. 27 28 29Alexander Terekhov 3031.01.2001 17:43 31 32To: ace-bugs@cs.wustl.edu 33cc: 34From: Alexander Terekhov/Germany/IBM@IBMDE 35Subject: Implementation of POSIX CVs: spur.wakeups/lost 36 signals/deadlocks/unfairness 37 38 39 40 ACE VERSION: 41 42 5.1.12 (pthread-win32 snapshot 2000-12-29) 43 44 HOST MACHINE and OPERATING SYSTEM: 45 46 IBM IntelliStation Z Pro, 2 x XEON 1GHz, Win2K 47 48 TARGET MACHINE and OPERATING SYSTEM, if different from HOST: 49 COMPILER NAME AND VERSION (AND PATCHLEVEL): 50 51 Microsoft Visual C++ 6.0 52 53 AREA/CLASS/EXAMPLE AFFECTED: 54 55 Implementation of POSIX condition variables - OS.cpp/.h 56 57 DOES THE PROBLEM AFFECT: 58 59 EXECUTION? YES! 60 61 SYNOPSIS: 62 63 a) spurious wakeups (minor problem) 64 b) lost signals 65 c) broadcast deadlock 66 d) unfairness (minor problem) 67 68 DESCRIPTION: 69 70 Please see attached copy of discussion thread 71 from comp.programming.threads for more details on 72 some reported problems. (i've also posted a "fyi" 73 message to ace-users a week or two ago but 74 unfortunately did not get any response so far). 75 76 It seems that current implementation suffers from 77 two essential problems: 78 79 1) cond.waiters_count does not accurately reflect 80 number of waiters blocked on semaphore - w/o 81 proper synchronisation that could result (in the 82 time window when counter is not accurate) 83 in spurious wakeups organised by subsequent 84 _signals and _broadcasts. 85 86 2) Always having (with no e.g. copy_and_clear/..) 87 the same queue in use (semaphore+counter) 88 neither signal nor broadcast provide 'atomic' 89 behaviour with respect to other threads/subsequent 90 calls to signal/broadcast/wait. 91 92 Each problem and combination of both could produce 93 various nasty things: 94 95 a) spurious wakeups (minor problem) 96 97 it is possible that waiter(s) which was already 98 unblocked even so is still counted as blocked 99 waiter. signal and broadcast will release 100 semaphore which will produce a spurious wakeup 101 for a 'real' waiter coming later. 102 103 b) lost signals 104 105 signalling thread ends up consuming its own 106 signal. please see demo/discussion below. 107 108 c) broadcast deadlock 109 110 last_waiter processing code does not correctly 111 handle the case with multiple threads 112 waiting for the end of broadcast. 113 please see demo/discussion below. 114 115 d) unfairness (minor problem) 116 117 without SignalObjectAndWait some waiter(s) 118 may end up consuming broadcasted signals 119 multiple times (spurious wakeups) because waiter 120 thread(s) can be preempted before they call 121 semaphore wait (but after count++ and mtx.unlock). 122 123 REPEAT BY: 124 125 See below... run problem demos programs (tennis.cpp and 126 tennisb.cpp) number of times concurrently (on multiprocessor) 127 and in multiple sessions or just add a couple of "Sleep"s 128 as described in the attached copy of discussion thread 129 from comp.programming.threads 130 131 SAMPLE FIX/WORKAROUND: 132 133 See attached patch to pthread-win32.. well, I can not 134 claim that it is completely bug free but at least my 135 test and tests provided by pthreads-win32 seem to work. 136 Perhaps that will help. 137 138 regards, 139 alexander. 140 141 142>> Forum: comp.programming.threads 143>> Thread: pthread_cond_* implementation questions 144. 145. 146. 147David Schwartz <davids@webmaster.com> wrote: 148 149> terekhov@my-deja.com wrote: 150> 151>> BTW, could you please also share your view on other perceived 152>> "problems" such as nested broadcast deadlock, spurious wakeups 153>> and (the latest one) lost signals?? 154> 155>I'm not sure what you mean. The standard allows an implementation 156>to do almost whatever it likes. In fact, you could implement 157>pthread_cond_wait by releasing the mutex, sleeping a random 158>amount of time, and then reacquiring the mutex. Of course, 159>this would be a pretty poor implementation, but any code that 160>didn't work under that implementation wouldn't be strictly 161>compliant. 162 163The implementation you suggested is indeed correct 164one (yes, now I see it :). However it requires from 165signal/broadcast nothing more than to "{ return 0; }" 166That is not the case for pthread-win32 and ACE 167implementations. I do think that these implementations 168(basically the same implementation) have some serious 169problems with wait/signal/broadcast calls. I am looking 170for help to clarify whether these problems are real 171or not. I think that I can demonstrate what I mean 172using one or two small sample programs. 173. 174. 175. 176========== 177tennis.cpp 178========== 179 180#include "ace/Synch.h" 181#include "ace/Thread.h" 182 183enum GAME_STATE { 184 185 START_GAME, 186 PLAYER_A, // Player A playes the ball 187 PLAYER_B, // Player B playes the ball 188 GAME_OVER, 189 ONE_PLAYER_GONE, 190 BOTH_PLAYERS_GONE 191 192}; 193 194enum GAME_STATE eGameState; 195ACE_Mutex* pmtxGameStateLock; 196ACE_Condition< ACE_Mutex >* pcndGameStateChange; 197 198void* 199 playerA( 200 void* pParm 201 ) 202{ 203 204 // For access to game state variable 205 pmtxGameStateLock->acquire(); 206 207 // Play loop 208 while ( eGameState < GAME_OVER ) { 209 210 // Play the ball 211 cout << endl << "PLAYER-A" << endl; 212 213 // Now its PLAYER-B's turn 214 eGameState = PLAYER_B; 215 216 // Signal to PLAYER-B that now it is his turn 217 pcndGameStateChange->signal(); 218 219 // Wait until PLAYER-B finishes playing the ball 220 do { 221 222 pcndGameStateChange->wait(); 223 224 if ( PLAYER_B == eGameState ) 225 cout << endl << "----PLAYER-A: SPURIOUS WAKEUP!!!" << endl; 226 227 } while ( PLAYER_B == eGameState ); 228 229 } 230 231 // PLAYER-A gone 232 eGameState = (GAME_STATE)(eGameState+1); 233 cout << endl << "PLAYER-A GONE" << endl; 234 235 // No more access to state variable needed 236 pmtxGameStateLock->release(); 237 238 // Signal PLAYER-A gone event 239 pcndGameStateChange->broadcast(); 240 241 return 0; 242 243} 244 245void* 246 playerB( 247 void* pParm 248 ) 249{ 250 251 // For access to game state variable 252 pmtxGameStateLock->acquire(); 253 254 // Play loop 255 while ( eGameState < GAME_OVER ) { 256 257 // Play the ball 258 cout << endl << "PLAYER-B" << endl; 259 260 // Now its PLAYER-A's turn 261 eGameState = PLAYER_A; 262 263 // Signal to PLAYER-A that now it is his turn 264 pcndGameStateChange->signal(); 265 266 // Wait until PLAYER-A finishes playing the ball 267 do { 268 269 pcndGameStateChange->wait(); 270 271 if ( PLAYER_A == eGameState ) 272 cout << endl << "----PLAYER-B: SPURIOUS WAKEUP!!!" << endl; 273 274 } while ( PLAYER_A == eGameState ); 275 276 } 277 278 // PLAYER-B gone 279 eGameState = (GAME_STATE)(eGameState+1); 280 cout << endl << "PLAYER-B GONE" << endl; 281 282 // No more access to state variable needed 283 pmtxGameStateLock->release(); 284 285 // Signal PLAYER-B gone event 286 pcndGameStateChange->broadcast(); 287 288 return 0; 289 290} 291 292 293int 294main (int, ACE_TCHAR *[]) 295{ 296 297 pmtxGameStateLock = new ACE_Mutex(); 298 pcndGameStateChange = new ACE_Condition< ACE_Mutex >( *pmtxGameStateLock 299); 300 301 // Set initial state 302 eGameState = START_GAME; 303 304 // Create players 305 ACE_Thread::spawn( playerA ); 306 ACE_Thread::spawn( playerB ); 307 308 // Give them 5 sec. to play 309 Sleep( 5000 );//sleep( 5 ); 310 311 // Set game over state 312 pmtxGameStateLock->acquire(); 313 eGameState = GAME_OVER; 314 315 // Let them know 316 pcndGameStateChange->broadcast(); 317 318 // Wait for players to stop 319 do { 320 321 pcndGameStateChange->wait(); 322 323 } while ( eGameState < BOTH_PLAYERS_GONE ); 324 325 // Cleanup 326 cout << endl << "GAME OVER" << endl; 327 pmtxGameStateLock->release(); 328 delete pcndGameStateChange; 329 delete pmtxGameStateLock; 330 331 return 0; 332 333} 334 335=========== 336tennisb.cpp 337=========== 338#include "ace/Synch.h" 339#include "ace/Thread.h" 340 341enum GAME_STATE { 342 343 START_GAME, 344 PLAYER_A, // Player A playes the ball 345 PLAYER_B, // Player B playes the ball 346 GAME_OVER, 347 ONE_PLAYER_GONE, 348 BOTH_PLAYERS_GONE 349 350}; 351 352enum GAME_STATE eGameState; 353ACE_Mutex* pmtxGameStateLock; 354ACE_Condition< ACE_Mutex >* pcndGameStateChange; 355 356void* 357 playerA( 358 void* pParm 359 ) 360{ 361 362 // For access to game state variable 363 pmtxGameStateLock->acquire(); 364 365 // Play loop 366 while ( eGameState < GAME_OVER ) { 367 368 // Play the ball 369 cout << endl << "PLAYER-A" << endl; 370 371 // Now its PLAYER-B's turn 372 eGameState = PLAYER_B; 373 374 // Signal to PLAYER-B that now it is his turn 375 pcndGameStateChange->broadcast(); 376 377 // Wait until PLAYER-B finishes playing the ball 378 do { 379 380 pcndGameStateChange->wait(); 381 382 if ( PLAYER_B == eGameState ) 383 cout << endl << "----PLAYER-A: SPURIOUS WAKEUP!!!" << endl; 384 385 } while ( PLAYER_B == eGameState ); 386 387 } 388 389 // PLAYER-A gone 390 eGameState = (GAME_STATE)(eGameState+1); 391 cout << endl << "PLAYER-A GONE" << endl; 392 393 // No more access to state variable needed 394 pmtxGameStateLock->release(); 395 396 // Signal PLAYER-A gone event 397 pcndGameStateChange->broadcast(); 398 399 return 0; 400 401} 402 403void* 404 playerB( 405 void* pParm 406 ) 407{ 408 409 // For access to game state variable 410 pmtxGameStateLock->acquire(); 411 412 // Play loop 413 while ( eGameState < GAME_OVER ) { 414 415 // Play the ball 416 cout << endl << "PLAYER-B" << endl; 417 418 // Now its PLAYER-A's turn 419 eGameState = PLAYER_A; 420 421 // Signal to PLAYER-A that now it is his turn 422 pcndGameStateChange->broadcast(); 423 424 // Wait until PLAYER-A finishes playing the ball 425 do { 426 427 pcndGameStateChange->wait(); 428 429 if ( PLAYER_A == eGameState ) 430 cout << endl << "----PLAYER-B: SPURIOUS WAKEUP!!!" << endl; 431 432 } while ( PLAYER_A == eGameState ); 433 434 } 435 436 // PLAYER-B gone 437 eGameState = (GAME_STATE)(eGameState+1); 438 cout << endl << "PLAYER-B GONE" << endl; 439 440 // No more access to state variable needed 441 pmtxGameStateLock->release(); 442 443 // Signal PLAYER-B gone event 444 pcndGameStateChange->broadcast(); 445 446 return 0; 447 448} 449 450 451int 452main (int, ACE_TCHAR *[]) 453{ 454 455 pmtxGameStateLock = new ACE_Mutex(); 456 pcndGameStateChange = new ACE_Condition< ACE_Mutex >( *pmtxGameStateLock 457); 458 459 // Set initial state 460 eGameState = START_GAME; 461 462 // Create players 463 ACE_Thread::spawn( playerA ); 464 ACE_Thread::spawn( playerB ); 465 466 // Give them 5 sec. to play 467 Sleep( 5000 );//sleep( 5 ); 468 469 // Make some noise 470 pmtxGameStateLock->acquire(); 471 cout << endl << "---Noise ON..." << endl; 472 pmtxGameStateLock->release(); 473 for ( int i = 0; i < 100000; i++ ) 474 pcndGameStateChange->broadcast(); 475 cout << endl << "---Noise OFF" << endl; 476 477 // Set game over state 478 pmtxGameStateLock->acquire(); 479 eGameState = GAME_OVER; 480 cout << endl << "---Stopping the game..." << endl; 481 482 // Let them know 483 pcndGameStateChange->broadcast(); 484 485 // Wait for players to stop 486 do { 487 488 pcndGameStateChange->wait(); 489 490 } while ( eGameState < BOTH_PLAYERS_GONE ); 491 492 // Cleanup 493 cout << endl << "GAME OVER" << endl; 494 pmtxGameStateLock->release(); 495 delete pcndGameStateChange; 496 delete pmtxGameStateLock; 497 498 return 0; 499 500} 501. 502. 503. 504David Schwartz <davids@webmaster.com> wrote: 505>> > It's compliant 506>> 507>> That is really good. 508> 509>> Tomorrow (I have to go urgently now) I will try to 510>> demonstrate the lost-signal "problem" of current 511>> pthread-win32 and ACE-(variant w/o SingleObjectAndWait) 512>> implementations: players start suddenly drop their balls :-) 513>> (with no change in source code). 514> 515>Signals aren't lost, they're going to the main thread, 516>which isn't coded correctly to handle them. Try this: 517> 518> // Wait for players to stop 519> do { 520> 521> pthread_cond_wait( &cndGameStateChange,&mtxGameStateLock ); 522>printf("Main thread stole a signal\n"); 523> 524> } while ( eGameState < BOTH_PLAYERS_GONE ); 525> 526>I bet everytime you thing a signal is lost, you'll see that printf. 527>The signal isn't lost, it was stolen by another thread. 528 529well, you can probably loose your bet.. it was indeed stolen 530by "another" thread but not the one you seem to think of. 531 532I think that what actually happens is the following: 533 534H:\SA\UXX\pt\PTHREADS\TESTS>tennis3.exe 535 536PLAYER-A 537 538PLAYER-B 539 540----PLAYER-B: SPURIOUS WAKEUP!!! 541 542PLAYER-A GONE 543 544PLAYER-B GONE 545 546GAME OVER 547 548H:\SA\UXX\pt\PTHREADS\TESTS> 549 550here you can see that PLAYER-B after playing his first 551ball (which came via signal from PLAYER-A) just dropped 552it down. What happened is that his signal to player A 553was consumed as spurious wakeup by himself (player B). 554 555The implementation has a problem: 556 557================ 558waiting threads: 559================ 560 561{ /** Critical Section 562 563 inc cond.waiters_count 564 565} 566 567 /* 568 /* Atomic only if using Win32 SignalObjectAndWait 569 /* 570 cond.mtx.release 571 572 /*** ^^-- A THREAD WHICH DID SIGNAL MAY ACQUIRE THE MUTEX, 573 /*** GO INTO WAIT ON THE SAME CONDITION AND OVERTAKE 574 /*** ORIGINAL WAITER(S) CONSUMING ITS OWN SIGNAL! 575 576 cond.sem.wait 577 578Player-A after playing game's initial ball went into 579wait (called _wait) but was pre-empted before reaching 580wait semaphore. He was counted as waiter but was not 581actually waiting/blocked yet. 582 583=============== 584signal threads: 585=============== 586 587{ /** Critical Section 588 589 waiters_count = cond.waiters_count 590 591} 592 593 if ( waiters_count != 0 ) 594 595 sem.post 1 596 597 endif 598 599Player-B after he received signal/ball from Player A 600called _signal. The _signal did see that there was 601one waiter blocked on the condition (Player-A) and 602released the semaphore.. (but it did not unblock 603Player-A because he was not actually blocked). 604Player-B thread continued its execution, called _wait, 605was counted as second waiter BUT was allowed to slip 606through opened semaphore gate (which was opened for 607Player-B) and received his own signal. Player B remained 608blocked followed by Player A. Deadlock happened which 609lasted until main thread came in and said game over. 610 611It seems to me that the implementation fails to 612correctly implement the following statement 613from specification: 614 615http://www.opengroup.org/ 616onlinepubs/007908799/xsh/pthread_cond_wait.html 617 618"These functions atomically release mutex and cause 619the calling thread to block on the condition variable 620cond; atomically here means "atomically with respect 621to access by another thread to the mutex and then the 622condition variable". That is, if another thread is 623able to acquire the mutex after the about-to-block 624thread has released it, then a subsequent call to 625pthread_cond_signal() or pthread_cond_broadcast() 626in that thread behaves as if it were issued after 627the about-to-block thread has blocked." 628 629Question: Am I right? 630 631(I produced the program output above by simply 632adding ?Sleep( 1 )?: 633 634================ 635waiting threads: 636================ 637 638{ /** Critical Section 639 640 inc cond.waiters_count 641 642} 643 644 /* 645 /* Atomic only if using Win32 SignalObjectAndWait 646 /* 647 cond.mtx.release 648 649Sleep( 1 ); // Win32 650 651 /*** ^^-- A THREAD WHICH DID SIGNAL MAY ACQUIRE THE MUTEX, 652 /*** GO INTO WAIT ON THE SAME CONDITION AND OVERTAKE 653 /*** ORIGINAL WAITER(S) CONSUMING ITS OWN SIGNAL! 654 655 cond.sem.wait 656 657to the source code of pthread-win32 implementation: 658 659http://sources.redhat.com/cgi-bin/cvsweb.cgi/pthreads/ 660condvar.c?rev=1.36&content-type=text/ 661x-cvsweb-markup&cvsroot=pthreads-win32 662 663 664 /* 665 * We keep the lock held just long enough to increment the count of 666 * waiters by one (above). 667 * Note that we can't keep it held across the 668 * call to sem_wait since that will deadlock other calls 669 * to pthread_cond_signal 670 */ 671 cleanup_args.mutexPtr = mutex; 672 cleanup_args.cv = cv; 673 cleanup_args.resultPtr = &result; 674 675 pthread_cleanup_push (ptw32_cond_wait_cleanup, (void *) 676&cleanup_args); 677 678 if ((result = pthread_mutex_unlock (mutex)) == 0) 679 {((result 680Sleep( 1 ); // @AT 681 682 /* 683 * Wait to be awakened by 684 * pthread_cond_signal, or 685 * pthread_cond_broadcast, or 686 * a timeout 687 * 688 * Note: 689 * ptw32_sem_timedwait is a cancelation point, 690 * hence providing the 691 * mechanism for making pthread_cond_wait a cancelation 692 * point. We use the cleanup mechanism to ensure we 693 * re-lock the mutex and decrement the waiters count 694 * if we are canceled. 695 */ 696 if (ptw32_sem_timedwait (&(cv->sema), abstime) == -1) { 697 result = errno; 698 } 699 } 700 701 pthread_cleanup_pop (1); /* Always cleanup */ 702 703 704BTW, on my system (2 CPUs) I can manage to get 705signals lost even without any source code modification 706if I run the tennis program many times in different 707shell sessions. 708. 709. 710. 711David Schwartz <davids@webmaster.com> wrote: 712>terekhov@my-deja.com wrote: 713> 714>> well, it might be that the program is in fact buggy. 715>> but you did not show me any bug. 716> 717>You're right. I was close but not dead on. I was correct, however, 718>that the code is buggy because it uses 'pthread_cond_signal' even 719>though not any thread waiting on the condition variable can do the 720>job. I was wrong in which thread could be waiting on the cv but 721>unable to do the job. 722 723Okay, lets change 'pthread_cond_signal' to 'pthread_cond_broadcast' 724but also add some noise from main() right before declaring the game 725to be over (I need it in order to demonstrate another problem of 726pthread-win32/ACE implementations - broadcast deadlock)... 727. 728. 729. 730It is my understanding of POSIX conditions, 731that on correct implementation added noise 732in form of unnecessary broadcasts from main, 733should not break the tennis program. The 734only 'side effect' of added noise on correct 735implementation would be 'spurious wakeups' of 736players (in fact they are not spurious, 737players just see them as spurious) unblocked, 738not by another player but by main before 739another player had a chance to acquire the 740mutex and change the game state variable: 741. 742. 743. 744 745PLAYER-B 746 747PLAYER-A 748 749---Noise ON... 750 751PLAYER-B 752 753PLAYER-A 754 755. 756. 757. 758 759PLAYER-B 760 761PLAYER-A 762 763----PLAYER-A: SPURIOUS WAKEUP!!! 764 765PLAYER-B 766 767PLAYER-A 768 769---Noise OFF 770 771PLAYER-B 772 773---Stopping the game... 774 775PLAYER-A GONE 776 777PLAYER-B GONE 778 779GAME OVER 780 781H:\SA\UXX\pt\PTHREADS\TESTS> 782 783On pthread-win32/ACE implementations the 784program could stall: 785 786. 787. 788. 789 790PLAYER-A 791 792PLAYER-B 793 794PLAYER-A 795 796PLAYER-B 797 798PLAYER-A 799 800PLAYER-B 801 802PLAYER-A 803 804PLAYER-B 805 806---Noise ON... 807 808PLAYER-A 809 810---Noise OFF 811^C 812H:\SA\UXX\pt\PTHREADS\TESTS> 813 814 815The implementation has problems: 816 817================ 818waiting threads: 819================ 820 821{ /** Critical Section 822 823 inc cond.waiters_count 824 825} 826 827 /* 828 /* Atomic only if using Win32 SignalObjectAndWait 829 /* 830 cond.mtx.release 831 cond.sem.wait 832 833 /*** ^^-- WAITER CAN BE PREEMPTED AFTER BEING UNBLOCKED... 834 835{ /** Critical Section 836 837 dec cond.waiters_count 838 839 /*** ^^- ...AND BEFORE DECREMENTING THE COUNT (1) 840 841 last_waiter = ( cond.was_broadcast && 842 cond.waiters_count == 0 ) 843 844 if ( last_waiter ) 845 846 cond.was_broadcast = FALSE 847 848 endif 849 850} 851 852 if ( last_waiter ) 853 854 /* 855 /* Atomic only if using Win32 SignalObjectAndWait 856 /* 857 cond.auto_reset_event_or_sem.post /* Event for Win32 858 cond.mtx.acquire 859 860 /*** ^^-- ...AND BEFORE CALL TO mtx.acquire (2) 861 862 /*** ^^-- NESTED BROADCASTS RESULT IN A DEADLOCK 863 864 865 else 866 867 cond.mtx.acquire 868 869 /*** ^^-- ...AND BEFORE CALL TO mtx.acquire (3) 870 871 endif 872 873 874================== 875broadcast threads: 876================== 877 878{ /** Critical Section 879 880 waiters_count = cond.waiters_count 881 882 if ( waiters_count != 0 ) 883 884 cond.was_broadcast = TRUE 885 886 endif 887 888} 889 890if ( waiters_count != 0 ) 891 892 cond.sem.post waiters_count 893 894 /*** ^^^^^--- SPURIOUS WAKEUPS DUE TO (1) 895 896 cond.auto_reset_event_or_sem.wait /* Event for Win32 897 898 /*** ^^^^^--- DEADLOCK FOR FURTHER BROADCASTS IF THEY 899 HAPPEN TO GO INTO WAIT WHILE PREVIOUS 900 BROADCAST IS STILL IN PROGRESS/WAITING 901 902endif 903 904a) cond.waiters_count does not accurately reflect 905number of waiters blocked on semaphore - that could 906result (in the time window when counter is not accurate) 907in spurios wakeups organised by subsequent _signals 908and _broadcasts. From standard compliance point of view 909that is OK but that could be a real problem from 910performance/efficiency point of view. 911 912b) If subsequent broadcast happen to go into wait on 913cond.auto_reset_event_or_sem before previous 914broadcast was unblocked from cond.auto_reset_event_or_sem 915by its last waiter, one of two blocked threads will 916remain blocked because last_waiter processing code 917fails to unblock both threads. 918 919In the situation with tennisb.c the Player-B was put 920in a deadlock by noise (broadcast) coming from main 921thread. And since Player-B holds the game state 922mutex when it calls broadcast, the whole program 923stalled: Player-A was deadlocked on mutex and 924main thread after finishing with producing the noise 925was deadlocked on mutex too (needed to declare the 926game over) 927 928(I produced the program output above by simply 929adding ?Sleep( 1 )?: 930 931================== 932broadcast threads: 933================== 934 935{ /** Critical Section 936 937 waiters_count = cond.waiters_count 938 939 if ( waiters_count != 0 ) 940 941 cond.was_broadcast = TRUE 942 943 endif 944 945} 946 947if ( waiters_count != 0 ) 948 949Sleep( 1 ); //Win32 950 951 cond.sem.post waiters_count 952 953 /*** ^^^^^--- SPURIOUS WAKEUPS DUE TO (1) 954 955 cond.auto_reset_event_or_sem.wait /* Event for Win32 956 957 /*** ^^^^^--- DEADLOCK FOR FURTHER BROADCASTS IF THEY 958 HAPPEN TO GO INTO WAIT WHILE PREVIOUS 959 BROADCAST IS STILL IN PROGRESS/WAITING 960 961endif 962 963to the source code of pthread-win32 implementation: 964 965http://sources.redhat.com/cgi-bin/cvsweb.cgi/pthreads/ 966condvar.c?rev=1.36&content-type=text/ 967x-cvsweb-markup&cvsroot=pthreads-win32 968 969 if (wereWaiters) 970 {(wereWaiters)sroot=pthreads-win32eb.cgi/pthreads/Yem...m 971 /* 972 * Wake up all waiters 973 */ 974 975Sleep( 1 ); //@AT 976 977#ifdef NEED_SEM 978 979 result = (ptw32_increase_semaphore( &cv->sema, cv->waiters ) 980 ? 0 981 : EINVAL); 982 983#else /* NEED_SEM */ 984 985 result = (ReleaseSemaphore( cv->sema, cv->waiters, NULL ) 986 ? 0 987 : EINVAL); 988 989#endif /* NEED_SEM */ 990 991 } 992 993 (void) pthread_mutex_unlock(&(cv->waitersLock)); 994 995 if (wereWaiters && result == 0) 996 {(wereWaiters 997 /* 998 * Wait for all the awakened threads to acquire their part of 999 * the counting semaphore 1000 */ 1001 1002 if (WaitForSingleObject (cv->waitersDone, INFINITE) 1003 == WAIT_OBJECT_0) 1004 { 1005 result = 0; 1006 } 1007 else 1008 { 1009 result = EINVAL; 1010 } 1011 1012 } 1013 1014 return (result); 1015 1016} 1017 1018BTW, on my system (2 CPUs) I can manage to get 1019the program stalled even without any source code 1020modification if I run the tennisb program many 1021times in different shell sessions. 1022 1023=================== 1024pthread-win32 patch 1025=================== 1026struct pthread_cond_t_ { 1027 long nWaitersBlocked; /* Number of threads blocked 1028*/ 1029 long nWaitersUnblocked; /* Number of threads unblocked 1030*/ 1031 long nWaitersToUnblock; /* Number of threads to unblock 1032*/ 1033 sem_t semBlockQueue; /* Queue up threads waiting for the 1034*/ 1035 /* condition to become signalled 1036*/ 1037 sem_t semBlockLock; /* Semaphore that guards access to 1038*/ 1039 /* | waiters blocked count/block queue 1040*/ 1041 /* +-> Mandatory Sync.LEVEL-1 1042*/ 1043 pthread_mutex_t mtxUnblockLock; /* Mutex that guards access to 1044*/ 1045 /* | waiters (to)unblock(ed) counts 1046*/ 1047 /* +-> Optional* Sync.LEVEL-2 1048*/ 1049}; /* Opt*) for _timedwait and 1050cancellation*/ 1051 1052int 1053pthread_cond_init (pthread_cond_t * cond, const pthread_condattr_t * attr) 1054 int result = EAGAIN; 1055 pthread_cond_t cv = NULL; 1056 1057 if (cond == NULL) 1058 {(cond 1059 return EINVAL; 1060 } 1061 1062 if ((attr != NULL && *attr != NULL) && 1063 ((*attr)->pshared == PTHREAD_PROCESS_SHARED)) 1064 { 1065 /* 1066 * Creating condition variable that can be shared between 1067 * processes. 1068 */ 1069 result = ENOSYS; 1070 1071 goto FAIL0; 1072 } 1073 1074 cv = (pthread_cond_t) calloc (1, sizeof (*cv)); 1075 1076 if (cv == NULL) 1077 {(cv 1078 result = ENOMEM; 1079 goto FAIL0; 1080 } 1081 1082 cv->nWaitersBlocked = 0; 1083 cv->nWaitersUnblocked = 0; 1084 cv->nWaitersToUnblock = 0; 1085 1086 if (sem_init (&(cv->semBlockLock), 0, 1) != 0) 1087 {(sem_init 1088 goto FAIL0; 1089 } 1090 1091 if (sem_init (&(cv->semBlockQueue), 0, 0) != 0) 1092 {(sem_init 1093 goto FAIL1; 1094 } 1095 1096 if (pthread_mutex_init (&(cv->mtxUnblockLock), 0) != 0) 1097 {(pthread_mutex_init 1098 goto FAIL2; 1099 } 1100 1101 1102 result = 0; 1103 1104 goto DONE; 1105 1106 /* 1107 * ------------- 1108 * Failed... 1109 * ------------- 1110 */ 1111FAIL2: 1112 (void) sem_destroy (&(cv->semBlockQueue)); 1113 1114FAIL1: 1115 (void) sem_destroy (&(cv->semBlockLock)); 1116 1117FAIL0: 1118DONE: 1119 *cond = cv; 1120 1121 return (result); 1122 1123} /* pthread_cond_init */ 1124 1125int 1126pthread_cond_destroy (pthread_cond_t * cond) 1127{ 1128 int result = 0; 1129 pthread_cond_t cv; 1130 1131 /* 1132 * Assuming any race condition here is harmless. 1133 */ 1134 if (cond == NULL 1135 || *cond == NULL) 1136 { 1137 return EINVAL; 1138 } 1139 1140 if (*cond != (pthread_cond_t) PTW32_OBJECT_AUTO_INIT) 1141 {(*cond 1142 cv = *cond; 1143 1144 /* 1145 * Synchronize access to waiters blocked count (LEVEL-1) 1146 */ 1147 if (sem_wait(&(cv->semBlockLock)) != 0) 1148 {(sem_wait(&(cv->semBlockLock)) 1149 return errno; 1150 } 1151 1152 /* 1153 * Synchronize access to waiters (to)unblock(ed) counts (LEVEL-2) 1154 */ 1155 if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0) 1156 {((result 1157 (void) sem_post(&(cv->semBlockLock)); 1158 return result; 1159 } 1160 1161 /* 1162 * Check whether cv is still busy (still has waiters blocked) 1163 */ 1164 if (cv->nWaitersBlocked - cv->nWaitersUnblocked > 0) 1165 {(cv->nWaitersBlocked 1166 (void) sem_post(&(cv->semBlockLock)); 1167 (void) pthread_mutex_unlock(&(cv->mtxUnblockLock)); 1168 return EBUSY; 1169 } 1170 1171 /* 1172 * Now it is safe to destroy 1173 */ 1174 (void) sem_destroy (&(cv->semBlockLock)); 1175 (void) sem_destroy (&(cv->semBlockQueue)); 1176 (void) pthread_mutex_unlock (&(cv->mtxUnblockLock)); 1177 (void) pthread_mutex_destroy (&(cv->mtxUnblockLock)); 1178 1179 free(cv); 1180 *cond = NULL; 1181 } 1182 else 1183 { 1184 /* 1185 * See notes in ptw32_cond_check_need_init() above also. 1186 */ 1187 EnterCriticalSection(&ptw32_cond_test_init_lock); 1188 1189 /* 1190 * Check again. 1191 */ 1192 if (*cond == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT) 1193 {(*cond 1194 /* 1195 * This is all we need to do to destroy a statically 1196 * initialised cond that has not yet been used (initialised). 1197 * If we get to here, another thread 1198 * waiting to initialise this cond will get an EINVAL. 1199 */ 1200 *cond = NULL; 1201 } 1202 else 1203 { 1204 /* 1205 * The cv has been initialised while we were waiting 1206 * so assume it's in use. 1207 */ 1208 result = EBUSY; 1209 } 1210 1211 LeaveCriticalSection(&ptw32_cond_test_init_lock); 1212 } 1213 1214 return (result); 1215} 1216 1217/* 1218 * Arguments for cond_wait_cleanup, since we can only pass a 1219 * single void * to it. 1220 */ 1221typedef struct { 1222 pthread_mutex_t * mutexPtr; 1223 pthread_cond_t cv; 1224 int * resultPtr; 1225} ptw32_cond_wait_cleanup_args_t; 1226 1227static void 1228ptw32_cond_wait_cleanup(void * args) 1229{ 1230 ptw32_cond_wait_cleanup_args_t * cleanup_args = 1231(ptw32_cond_wait_cleanup_args_t *) args; 1232 pthread_cond_t cv = cleanup_args->cv; 1233 int * resultPtr = cleanup_args->resultPtr; 1234 int eLastSignal; /* enum: 1=yes 0=no -1=cancelled/timedout w/o signal(s) 1235*/ 1236 int result; 1237 1238 /* 1239 * Whether we got here as a result of signal/broadcast or because of 1240 * timeout on wait or thread cancellation we indicate that we are no 1241 * longer waiting. The waiter is responsible for adjusting waiters 1242 * (to)unblock(ed) counts (protected by unblock lock). 1243 * Unblock lock/Sync.LEVEL-2 supports _timedwait and cancellation. 1244 */ 1245 if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0) 1246 {((result 1247 *resultPtr = result; 1248 return; 1249 } 1250 1251 cv->nWaitersUnblocked++; 1252 1253 eLastSignal = (cv->nWaitersToUnblock == 0) ? 1254 -1 : (--cv->nWaitersToUnblock == 0); 1255 1256 /* 1257 * No more LEVEL-2 access to waiters (to)unblock(ed) counts needed 1258 */ 1259 if ((result = pthread_mutex_unlock(&(cv->mtxUnblockLock))) != 0) 1260 {((result 1261 *resultPtr = result; 1262 return; 1263 } 1264 1265 /* 1266 * If last signal... 1267 */ 1268 if (eLastSignal == 1) 1269 {(eLastSignal 1270 /* 1271 * ...it means that we have end of 'atomic' signal/broadcast 1272 */ 1273 if (sem_post(&(cv->semBlockLock)) != 0) 1274 {(sem_post(&(cv->semBlockLock)) 1275 *resultPtr = errno; 1276 return; 1277 } 1278 } 1279 /* 1280 * If not last signal and not timed out/cancelled wait w/o signal... 1281 */ 1282 else if (eLastSignal == 0) 1283 { 1284 /* 1285 * ...it means that next waiter can go through semaphore 1286 */ 1287 if (sem_post(&(cv->semBlockQueue)) != 0) 1288 {(sem_post(&(cv->semBlockQueue)) 1289 *resultPtr = errno; 1290 return; 1291 } 1292 } 1293 1294 /* 1295 * XSH: Upon successful return, the mutex has been locked and is owned 1296 * by the calling thread 1297 */ 1298 if ((result = pthread_mutex_lock(cleanup_args->mutexPtr)) != 0) 1299 {((result 1300 *resultPtr = result; 1301 } 1302 1303} /* ptw32_cond_wait_cleanup */ 1304 1305static int 1306ptw32_cond_timedwait (pthread_cond_t * cond, 1307 pthread_mutex_t * mutex, 1308 const struct timespec *abstime) 1309{ 1310 int result = 0; 1311 pthread_cond_t cv; 1312 ptw32_cond_wait_cleanup_args_t cleanup_args; 1313 1314 if (cond == NULL || *cond == NULL) 1315 {(cond 1316 return EINVAL; 1317 } 1318 1319 /* 1320 * We do a quick check to see if we need to do more work 1321 * to initialise a static condition variable. We check 1322 * again inside the guarded section of ptw32_cond_check_need_init() 1323 * to avoid race conditions. 1324 */ 1325 if (*cond == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT) 1326 {(*cond 1327 result = ptw32_cond_check_need_init(cond); 1328 } 1329 1330 if (result != 0 && result != EBUSY) 1331 {(result 1332 return result; 1333 } 1334 1335 cv = *cond; 1336 1337 /* 1338 * Synchronize access to waiters blocked count (LEVEL-1) 1339 */ 1340 if (sem_wait(&(cv->semBlockLock)) != 0) 1341 {(sem_wait(&(cv->semBlockLock)) 1342 return errno; 1343 } 1344 1345 cv->nWaitersBlocked++; 1346 1347 /* 1348 * Thats it. Counted means waiting, no more access needed 1349 */ 1350 if (sem_post(&(cv->semBlockLock)) != 0) 1351 {(sem_post(&(cv->semBlockLock)) 1352 return errno; 1353 } 1354 1355 /* 1356 * Setup this waiter cleanup handler 1357 */ 1358 cleanup_args.mutexPtr = mutex; 1359 cleanup_args.cv = cv; 1360 cleanup_args.resultPtr = &result; 1361 1362 pthread_cleanup_push (ptw32_cond_wait_cleanup, (void *) &cleanup_args); 1363 1364 /* 1365 * Now we can release 'mutex' and... 1366 */ 1367 if ((result = pthread_mutex_unlock (mutex)) == 0) 1368 {((result 1369 1370 /* 1371 * ...wait to be awakened by 1372 * pthread_cond_signal, or 1373 * pthread_cond_broadcast, or 1374 * timeout, or 1375 * thread cancellation 1376 * 1377 * Note: 1378 * 1379 * ptw32_sem_timedwait is a cancellation point, 1380 * hence providing the mechanism for making 1381 * pthread_cond_wait a cancellation point. 1382 * We use the cleanup mechanism to ensure we 1383 * re-lock the mutex and adjust (to)unblock(ed) waiters 1384 * counts if we are cancelled, timed out or signalled. 1385 */ 1386 if (ptw32_sem_timedwait (&(cv->semBlockQueue), abstime) != 0) 1387 {(ptw32_sem_timedwait 1388 result = errno; 1389 } 1390 } 1391 1392 /* 1393 * Always cleanup 1394 */ 1395 pthread_cleanup_pop (1); 1396 1397 1398 /* 1399 * "result" can be modified by the cleanup handler. 1400 */ 1401 return (result); 1402 1403} /* ptw32_cond_timedwait */ 1404 1405 1406static int 1407ptw32_cond_unblock (pthread_cond_t * cond, 1408 int unblockAll) 1409{ 1410 int result; 1411 pthread_cond_t cv; 1412 1413 if (cond == NULL || *cond == NULL) 1414 {(cond 1415 return EINVAL; 1416 } 1417 1418 cv = *cond; 1419 1420 /* 1421 * No-op if the CV is static and hasn't been initialised yet. 1422 * Assuming that any race condition is harmless. 1423 */ 1424 if (cv == (pthread_cond_t) PTW32_OBJECT_AUTO_INIT) 1425 {(cv 1426 return 0; 1427 } 1428 1429 /* 1430 * Synchronize access to waiters blocked count (LEVEL-1) 1431 */ 1432 if (sem_wait(&(cv->semBlockLock)) != 0) 1433 {(sem_wait(&(cv->semBlockLock)) 1434 return errno; 1435 } 1436 1437 /* 1438 * Synchronize access to waiters (to)unblock(ed) counts (LEVEL-2) 1439 * This sync.level supports _timedwait and cancellation 1440 */ 1441 if ((result = pthread_mutex_lock(&(cv->mtxUnblockLock))) != 0) 1442 {((result 1443 return result; 1444 } 1445 1446 /* 1447 * Adjust waiters blocked and unblocked counts (collect garbage) 1448 */ 1449 if (cv->nWaitersUnblocked != 0) 1450 {(cv->nWaitersUnblocked 1451 cv->nWaitersBlocked -= cv->nWaitersUnblocked; 1452 cv->nWaitersUnblocked = 0; 1453 } 1454 1455 /* 1456 * If (after adjustment) there are still some waiters blocked counted... 1457 */ 1458 if ( cv->nWaitersBlocked > 0) 1459 {( 1460 /* 1461 * We will unblock first waiter and leave semBlockLock/LEVEL-1 locked 1462 * LEVEL-1 access is left disabled until last signal/unblock 1463completes 1464 */ 1465 cv->nWaitersToUnblock = (unblockAll) ? cv->nWaitersBlocked : 1; 1466 1467 /* 1468 * No more LEVEL-2 access to waiters (to)unblock(ed) counts needed 1469 * This sync.level supports _timedwait and cancellation 1470 */ 1471 if ((result = pthread_mutex_unlock(&(cv->mtxUnblockLock))) != 0) 1472 {((result 1473 return result; 1474 } 1475 1476 1477 /* 1478 * Now, with LEVEL-2 lock released let first waiter go through 1479semaphore 1480 */ 1481 if (sem_post(&(cv->semBlockQueue)) != 0) 1482 {(sem_post(&(cv->semBlockQueue)) 1483 return errno; 1484 } 1485 } 1486 /* 1487 * No waiter blocked - no more LEVEL-1 access to blocked count needed... 1488 */ 1489 else if (sem_post(&(cv->semBlockLock)) != 0) 1490 { 1491 return errno; 1492 } 1493 /* 1494 * ...and no more LEVEL-2 access to waiters (to)unblock(ed) counts needed 1495too 1496 * This sync.level supports _timedwait and cancellation 1497 */ 1498 else 1499 { 1500 result = pthread_mutex_unlock(&(cv->mtxUnblockLock)); 1501 } 1502 1503 return(result); 1504 1505} /* ptw32_cond_unblock */ 1506 1507int 1508pthread_cond_wait (pthread_cond_t * cond, 1509 pthread_mutex_t * mutex) 1510{ 1511 /* The NULL abstime arg means INFINITE waiting. */ 1512 return(ptw32_cond_timedwait(cond, mutex, NULL)); 1513} /* pthread_cond_wait */ 1514 1515 1516int 1517pthread_cond_timedwait (pthread_cond_t * cond, 1518 pthread_mutex_t * mutex, 1519 const struct timespec *abstime) 1520{ 1521 if (abstime == NULL) 1522 {(abstime 1523 return EINVAL; 1524 } 1525 1526 return(ptw32_cond_timedwait(cond, mutex, abstime)); 1527} /* pthread_cond_timedwait */ 1528 1529 1530int 1531pthread_cond_signal (pthread_cond_t * cond) 1532{ 1533 /* The '0'(FALSE) unblockAll arg means unblock ONE waiter. */ 1534 return(ptw32_cond_unblock(cond, 0)); 1535} /* pthread_cond_signal */ 1536 1537int 1538pthread_cond_broadcast (pthread_cond_t * cond) 1539{ 1540 /* The '1'(TRUE) unblockAll arg means unblock ALL waiters. */ 1541 return(ptw32_cond_unblock(cond, 1)); 1542} /* pthread_cond_broadcast */ 1543 1544 1545 1546 1547TEREKHOV@de.ibm.com on 17.01.2001 01:00:57 1548 1549Please respond to TEREKHOV@de.ibm.com 1550 1551To: pthreads-win32@sourceware.cygnus.com 1552cc: schmidt@uci.edu 1553Subject: win32 conditions: sem+counter+event = broadcast_deadlock + 1554 spur.wakeup/unfairness/incorrectness ?? 1555 1556 1557 1558 1559 1560 1561 1562Hi, 1563 1564Problem 1: broadcast_deadlock 1565 1566It seems that current implementation does not provide "atomic" 1567broadcasts. That may lead to "nested" broadcasts... and it seems 1568that nested case is not handled correctly -> producing a broadcast 1569DEADLOCK as a result. 1570 1571Scenario: 1572 1573N (>1) waiting threads W1..N are blocked (in _wait) on condition's 1574semaphore. 1575 1576Thread B1 calls pthread_cond_broadcast, which results in "releasing" N 1577W threads via incrementing semaphore counter by N (stored in 1578cv->waiters) BUT cv->waiters counter does not change!! The caller 1579thread B1 remains blocked on cv->waitersDone event (auto-reset!!) BUT 1580condition is not protected from starting another broadcast (when called 1581on another thread) while still waiting for the "old" broadcast to 1582complete on thread B1. 1583 1584M (>=0, <N) W threads are fast enough to go thru their _wait call and 1585decrement cv->waiters counter. 1586 1587L (N-M) "late" waiter W threads are a) still blocked/not returned from 1588their semaphore wait call or b) were preempted after sem_wait but before 1589lock( &cv->waitersLock ) or c) are blocked on cv->waitersLock. 1590 1591cv->waiters is still > 0 (= L). 1592 1593Another thread B2 (or some W thread from M group) calls 1594pthread_cond_broadcast and gains access to counter... neither a) nor b) 1595prevent thread B2 in pthread_cond_broadcast from gaining access to 1596counter and starting another broadcast ( for c) - it depends on 1597cv->waitersLock scheduling rules: FIFO=OK, PRTY=PROBLEM,... ) 1598 1599That call to pthread_cond_broadcast (on thread B2) will result in 1600incrementing semaphore by cv->waiters (=L) which is INCORRECT (all 1601W1..N were in fact already released by thread B1) and waiting on 1602_auto-reset_ event cv->waitersDone which is DEADLY WRONG (produces a 1603deadlock)... 1604 1605All late W1..L threads now have a chance to complete their _wait call. 1606Last W_L thread sets an auto-reselt event cv->waitersDone which will 1607release either B1 or B2 leaving one of B threads in a deadlock. 1608 1609Problem 2: spur.wakeup/unfairness/incorrectness 1610 1611It seems that: 1612 1613a) because of the same problem with counter which does not reflect the 1614actual number of NOT RELEASED waiters, the signal call may increment 1615a semaphore counter w/o having a waiter blocked on it. That will result 1616in (best case) spurious wake ups - performance degradation due to 1617unnecessary context switches and predicate re-checks and (in worth case) 1618unfairness/incorrectness problem - see b) 1619 1620b) neither signal nor broadcast prevent other threads - "new waiters" 1621(and in the case of signal, the caller thread as well) from going into 1622_wait and overtaking "old" waiters (already released but still not returned 1623from sem_wait on condition's semaphore). Win semaphore just [API DOC]: 1624"Maintains a count between zero and some maximum value, limiting the number 1625of threads that are simultaneously accessing a shared resource." Calling 1626ReleaseSemaphore does not imply (at least not documented) that on return 1627from ReleaseSemaphore all waiters will in fact become released (returned 1628from their Wait... call) and/or that new waiters calling Wait... afterwards 1629will become less importance. It is NOT documented to be an atomic release 1630of 1631waiters... And even if it would be there is still a problem with a thread 1632being preempted after Wait on semaphore and before Wait on cv->waitersLock 1633and scheduling rules for cv->waitersLock itself 1634(??WaitForMultipleObjects??) 1635That may result in unfairness/incorrectness problem as described 1636for SetEvent impl. in "Strategies for Implementing POSIX Condition 1637Variables 1638on Win32": http://www.cs.wustl.edu/~schmidt/win32-cv-1.html 1639 1640Unfairness -- The semantics of the POSIX pthread_cond_broadcast function is 1641to wake up all threads currently blocked in wait calls on the condition 1642variable. The awakened threads then compete for the external_mutex. To 1643ensure 1644fairness, all of these threads should be released from their 1645pthread_cond_wait calls and allowed to recheck their condition expressions 1646before other threads can successfully complete a wait on the condition 1647variable. 1648 1649Unfortunately, the SetEvent implementation above does not guarantee that 1650all 1651threads sleeping on the condition variable when cond_broadcast is called 1652will 1653acquire the external_mutex and check their condition expressions. Although 1654the Pthreads specification does not mandate this degree of fairness, the 1655lack of fairness can cause starvation. 1656 1657To illustrate the unfairness problem, imagine there are 2 threads, C1 and 1658C2, 1659that are blocked in pthread_cond_wait on condition variable not_empty_ that 1660is guarding a thread-safe message queue. Another thread, P1 then places two 1661messages onto the queue and calls pthread_cond_broadcast. If C1 returns 1662from 1663pthread_cond_wait, dequeues and processes the message, and immediately 1664waits 1665again then it and only it may end up acquiring both messages. Thus, C2 will 1666never get a chance to dequeue a message and run. 1667 1668The following illustrates the sequence of events: 1669 16701. Thread C1 attempts to dequeue and waits on CV non_empty_ 16712. Thread C2 attempts to dequeue and waits on CV non_empty_ 16723. Thread P1 enqueues 2 messages and broadcasts to CV not_empty_ 16734. Thread P1 exits 16745. Thread C1 wakes up from CV not_empty_, dequeues a message and runs 16756. Thread C1 waits again on CV not_empty_, immediately dequeues the 2nd 1676 message and runs 16777. Thread C1 exits 16788. Thread C2 is the only thread left and blocks forever since 1679 not_empty_ will never be signaled 1680 1681Depending on the algorithm being implemented, this lack of fairness may 1682yield 1683concurrent programs that have subtle bugs. Of course, application 1684developers 1685should not rely on the fairness semantics of pthread_cond_broadcast. 1686However, 1687there are many cases where fair implementations of condition variables can 1688simplify application code. 1689 1690Incorrectness -- A variation on the unfairness problem described above 1691occurs 1692when a third consumer thread, C3, is allowed to slip through even though it 1693was not waiting on condition variable not_empty_ when a broadcast occurred. 1694 1695To illustrate this, we will use the same scenario as above: 2 threads, C1 1696and 1697C2, are blocked dequeuing messages from the message queue. Another thread, 1698P1 1699then places two messages onto the queue and calls pthread_cond_broadcast. 1700C1 1701returns from pthread_cond_wait, dequeues and processes the message. At this 1702time, C3 acquires the external_mutex, calls pthread_cond_wait and waits on 1703the events in WaitForMultipleObjects. Since C2 has not had a chance to run 1704yet, the BROADCAST event is still signaled. C3 then returns from 1705WaitForMultipleObjects, and dequeues and processes the message in the 1706queue. 1707Thus, C2 will never get a chance to dequeue a message and run. 1708 1709The following illustrates the sequence of events: 1710 17111. Thread C1 attempts to dequeue and waits on CV non_empty_ 17122. Thread C2 attempts to dequeue and waits on CV non_empty_ 17133. Thread P1 enqueues 2 messages and broadcasts to CV not_empty_ 17144. Thread P1 exits 17155. Thread C1 wakes up from CV not_empty_, dequeues a message and runs 17166. Thread C1 exits 17177. Thread C3 waits on CV not_empty_, immediately dequeues the 2nd 1718 message and runs 17198. Thread C3 exits 17209. Thread C2 is the only thread left and blocks forever since 1721 not_empty_ will never be signaled 1722 1723In the above case, a thread that was not waiting on the condition variable 1724when a broadcast occurred was allowed to proceed. This leads to incorrect 1725semantics for a condition variable. 1726 1727 1728COMMENTS??? 1729 1730regards, 1731alexander. 1732 1733----------------------------------------------------------------------------- 1734 1735Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_* 1736 implementation questions 1737Date: Wed, 21 Feb 2001 11:54:47 +0100 1738From: TEREKHOV@de.ibm.com 1739To: lthomas@arbitrade.com 1740CC: rpj@ise.canberra.edu.au, Thomas Pfaff <tpfaff@gmx.net>, 1741 Nanbor Wang <nanbor@cs.wustl.edu> 1742 1743Hi Louis, 1744 1745generation number 8.. 1746 1747had some time to revisit timeouts/spurious wakeup problem.. 1748found some bugs (in 7.b/c/d) and something to improve 1749(7a - using IPC semaphores but it should speedup Win32 1750version as well). 1751 1752regards, 1753alexander. 1754 1755---------- Algorithm 8a / IMPL_SEM,UNBLOCK_STRATEGY == UNBLOCK_ALL ------ 1756given: 1757semBlockLock - bin.semaphore 1758semBlockQueue - semaphore 1759mtxExternal - mutex or CS 1760mtxUnblockLock - mutex or CS 1761nWaitersGone - int 1762nWaitersBlocked - int 1763nWaitersToUnblock - int 1764 1765wait( timeout ) { 1766 1767 [auto: register int result ] // error checking omitted 1768 [auto: register int nSignalsWasLeft ] 1769 [auto: register int nWaitersWasGone ] 1770 1771 sem_wait( semBlockLock ); 1772 nWaitersBlocked++; 1773 sem_post( semBlockLock ); 1774 1775 unlock( mtxExternal ); 1776 bTimedOut = sem_wait( semBlockQueue,timeout ); 1777 1778 lock( mtxUnblockLock ); 1779 if ( 0 != (nSignalsWasLeft = nWaitersToUnblock) ) { 1780 if ( bTimeout ) { // timeout (or canceled) 1781 if ( 0 != nWaitersBlocked ) { 1782 nWaitersBlocked--; 1783 } 1784 else { 1785 nWaitersGone++; // count spurious wakeups 1786 } 1787 } 1788 if ( 0 == --nWaitersToUnblock ) { 1789 if ( 0 != nWaitersBlocked ) { 1790 sem_post( semBlockLock ); // open the gate 1791 nSignalsWasLeft = 0; // do not open the gate below 1792again 1793 } 1794 else if ( 0 != (nWaitersWasGone = nWaitersGone) ) { 1795 nWaitersGone = 0; 1796 } 1797 } 1798 } 1799 else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious 1800semaphore :-) 1801 sem_wait( semBlockLock ); 1802 nWaitersBlocked -= nWaitersGone; // something is going on here - 1803test of timeouts? :-) 1804 sem_post( semBlockLock ); 1805 nWaitersGone = 0; 1806 } 1807 unlock( mtxUnblockLock ); 1808 1809 if ( 1 == nSignalsWasLeft ) { 1810 if ( 0 != nWaitersWasGone ) { 1811 // sem_adjust( -nWaitersWasGone ); 1812 while ( nWaitersWasGone-- ) { 1813 sem_wait( semBlockLock ); // better now than spurious 1814later 1815 } 1816 } 1817 sem_post( semBlockLock ); // open the gate 1818 } 1819 1820 lock( mtxExternal ); 1821 1822 return ( bTimedOut ) ? ETIMEOUT : 0; 1823} 1824 1825signal(bAll) { 1826 1827 [auto: register int result ] 1828 [auto: register int nSignalsToIssue] 1829 1830 lock( mtxUnblockLock ); 1831 1832 if ( 0 != nWaitersToUnblock ) { // the gate is closed!!! 1833 if ( 0 == nWaitersBlocked ) { // NO-OP 1834 return unlock( mtxUnblockLock ); 1835 } 1836 if (bAll) { 1837 nWaitersToUnblock += nSignalsToIssue=nWaitersBlocked; 1838 nWaitersBlocked = 0; 1839 } 1840 else { 1841 nSignalsToIssue = 1; 1842 nWaitersToUnblock++; 1843 nWaitersBlocked--; 1844 } 1845 } 1846 else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION! 1847 sem_wait( semBlockLock ); // close the gate 1848 if ( 0 != nWaitersGone ) { 1849 nWaitersBlocked -= nWaitersGone; 1850 nWaitersGone = 0; 1851 } 1852 if (bAll) { 1853 nSignalsToIssue = nWaitersToUnblock = nWaitersBlocked; 1854 nWaitersBlocked = 0; 1855 } 1856 else { 1857 nSignalsToIssue = nWaitersToUnblock = 1; 1858 nWaitersBlocked--; 1859 } 1860 } 1861 else { // NO-OP 1862 return unlock( mtxUnblockLock ); 1863 } 1864 1865 unlock( mtxUnblockLock ); 1866 sem_post( semBlockQueue,nSignalsToIssue ); 1867 return result; 1868} 1869 1870---------- Algorithm 8b / IMPL_SEM,UNBLOCK_STRATEGY == UNBLOCK_ONEBYONE 1871------ 1872given: 1873semBlockLock - bin.semaphore 1874semBlockQueue - bin.semaphore 1875mtxExternal - mutex or CS 1876mtxUnblockLock - mutex or CS 1877nWaitersGone - int 1878nWaitersBlocked - int 1879nWaitersToUnblock - int 1880 1881wait( timeout ) { 1882 1883 [auto: register int result ] // error checking omitted 1884 [auto: register int nWaitersWasGone ] 1885 [auto: register int nSignalsWasLeft ] 1886 1887 sem_wait( semBlockLock ); 1888 nWaitersBlocked++; 1889 sem_post( semBlockLock ); 1890 1891 unlock( mtxExternal ); 1892 bTimedOut = sem_wait( semBlockQueue,timeout ); 1893 1894 lock( mtxUnblockLock ); 1895 if ( 0 != (nSignalsWasLeft = nWaitersToUnblock) ) { 1896 if ( bTimeout ) { // timeout (or canceled) 1897 if ( 0 != nWaitersBlocked ) { 1898 nWaitersBlocked--; 1899 nSignalsWasLeft = 0; // do not unblock next waiter 1900below (already unblocked) 1901 } 1902 else { 1903 nWaitersGone = 1; // spurious wakeup pending!! 1904 } 1905 } 1906 if ( 0 == --nWaitersToUnblock && 1907 if ( 0 != nWaitersBlocked ) { 1908 sem_post( semBlockLock ); // open the gate 1909 nSignalsWasLeft = 0; // do not open the gate below 1910again 1911 } 1912 else if ( 0 != (nWaitersWasGone = nWaitersGone) ) { 1913 nWaitersGone = 0; 1914 } 1915 } 1916 } 1917 else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious 1918semaphore :-) 1919 sem_wait( semBlockLock ); 1920 nWaitersBlocked -= nWaitersGone; // something is going on here - 1921test of timeouts? :-) 1922 sem_post( semBlockLock ); 1923 nWaitersGone = 0; 1924 } 1925 unlock( mtxUnblockLock ); 1926 1927 if ( 1 == nSignalsWasLeft ) { 1928 if ( 0 != nWaitersWasGone ) { 1929 // sem_adjust( -1 ); 1930 sem_wait( semBlockQueue ); // better now than spurious 1931later 1932 } 1933 sem_post( semBlockLock ); // open the gate 1934 } 1935 else if ( 0 != nSignalsWasLeft ) { 1936 sem_post( semBlockQueue ); // unblock next waiter 1937 } 1938 1939 lock( mtxExternal ); 1940 1941 return ( bTimedOut ) ? ETIMEOUT : 0; 1942} 1943 1944signal(bAll) { 1945 1946 [auto: register int result ] 1947 1948 lock( mtxUnblockLock ); 1949 1950 if ( 0 != nWaitersToUnblock ) { // the gate is closed!!! 1951 if ( 0 == nWaitersBlocked ) { // NO-OP 1952 return unlock( mtxUnblockLock ); 1953 } 1954 if (bAll) { 1955 nWaitersToUnblock += nWaitersBlocked; 1956 nWaitersBlocked = 0; 1957 } 1958 else { 1959 nWaitersToUnblock++; 1960 nWaitersBlocked--; 1961 } 1962 unlock( mtxUnblockLock ); 1963 } 1964 else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION! 1965 sem_wait( semBlockLock ); // close the gate 1966 if ( 0 != nWaitersGone ) { 1967 nWaitersBlocked -= nWaitersGone; 1968 nWaitersGone = 0; 1969 } 1970 if (bAll) { 1971 nWaitersToUnblock = nWaitersBlocked; 1972 nWaitersBlocked = 0; 1973 } 1974 else { 1975 nWaitersToUnblock = 1; 1976 nWaitersBlocked--; 1977 } 1978 unlock( mtxUnblockLock ); 1979 sem_post( semBlockQueue ); 1980 } 1981 else { // NO-OP 1982 unlock( mtxUnblockLock ); 1983 } 1984 1985 return result; 1986} 1987 1988---------- Algorithm 8c / IMPL_EVENT,UNBLOCK_STRATEGY == UNBLOCK_ONEBYONE 1989--------- 1990given: 1991hevBlockLock - auto-reset event 1992hevBlockQueue - auto-reset event 1993mtxExternal - mutex or CS 1994mtxUnblockLock - mutex or CS 1995nWaitersGone - int 1996nWaitersBlocked - int 1997nWaitersToUnblock - int 1998 1999wait( timeout ) { 2000 2001 [auto: register int result ] // error checking omitted 2002 [auto: register int nSignalsWasLeft ] 2003 [auto: register int nWaitersWasGone ] 2004 2005 wait( hevBlockLock,INFINITE ); 2006 nWaitersBlocked++; 2007 set_event( hevBlockLock ); 2008 2009 unlock( mtxExternal ); 2010 bTimedOut = wait( hevBlockQueue,timeout ); 2011 2012 lock( mtxUnblockLock ); 2013 if ( 0 != (SignalsWasLeft = nWaitersToUnblock) ) { 2014 if ( bTimeout ) { // timeout (or canceled) 2015 if ( 0 != nWaitersBlocked ) { 2016 nWaitersBlocked--; 2017 nSignalsWasLeft = 0; // do not unblock next waiter 2018below (already unblocked) 2019 } 2020 else { 2021 nWaitersGone = 1; // spurious wakeup pending!! 2022 } 2023 } 2024 if ( 0 == --nWaitersToUnblock ) 2025 if ( 0 != nWaitersBlocked ) { 2026 set_event( hevBlockLock ); // open the gate 2027 nSignalsWasLeft = 0; // do not open the gate below 2028again 2029 } 2030 else if ( 0 != (nWaitersWasGone = nWaitersGone) ) { 2031 nWaitersGone = 0; 2032 } 2033 } 2034 } 2035 else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious 2036event :-) 2037 wait( hevBlockLock,INFINITE ); 2038 nWaitersBlocked -= nWaitersGone; // something is going on here - 2039test of timeouts? :-) 2040 set_event( hevBlockLock ); 2041 nWaitersGone = 0; 2042 } 2043 unlock( mtxUnblockLock ); 2044 2045 if ( 1 == nSignalsWasLeft ) { 2046 if ( 0 != nWaitersWasGone ) { 2047 reset_event( hevBlockQueue ); // better now than spurious 2048later 2049 } 2050 set_event( hevBlockLock ); // open the gate 2051 } 2052 else if ( 0 != nSignalsWasLeft ) { 2053 set_event( hevBlockQueue ); // unblock next waiter 2054 } 2055 2056 lock( mtxExternal ); 2057 2058 return ( bTimedOut ) ? ETIMEOUT : 0; 2059} 2060 2061signal(bAll) { 2062 2063 [auto: register int result ] 2064 2065 lock( mtxUnblockLock ); 2066 2067 if ( 0 != nWaitersToUnblock ) { // the gate is closed!!! 2068 if ( 0 == nWaitersBlocked ) { // NO-OP 2069 return unlock( mtxUnblockLock ); 2070 } 2071 if (bAll) { 2072 nWaitersToUnblock += nWaitersBlocked; 2073 nWaitersBlocked = 0; 2074 } 2075 else { 2076 nWaitersToUnblock++; 2077 nWaitersBlocked--; 2078 } 2079 unlock( mtxUnblockLock ); 2080 } 2081 else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION! 2082 wait( hevBlockLock,INFINITE ); // close the gate 2083 if ( 0 != nWaitersGone ) { 2084 nWaitersBlocked -= nWaitersGone; 2085 nWaitersGone = 0; 2086 } 2087 if (bAll) { 2088 nWaitersToUnblock = nWaitersBlocked; 2089 nWaitersBlocked = 0; 2090 } 2091 else { 2092 nWaitersToUnblock = 1; 2093 nWaitersBlocked--; 2094 } 2095 unlock( mtxUnblockLock ); 2096 set_event( hevBlockQueue ); 2097 } 2098 else { // NO-OP 2099 unlock( mtxUnblockLock ); 2100 } 2101 2102 return result; 2103} 2104 2105---------- Algorithm 8d / IMPL_EVENT,UNBLOCK_STRATEGY == UNBLOCK_ALL ------ 2106given: 2107hevBlockLock - auto-reset event 2108hevBlockQueueS - auto-reset event // for signals 2109hevBlockQueueB - manual-reset even // for broadcasts 2110mtxExternal - mutex or CS 2111mtxUnblockLock - mutex or CS 2112eBroadcast - int // 0: no broadcast, 1: broadcast, 2: 2113broadcast after signal(s) 2114nWaitersGone - int 2115nWaitersBlocked - int 2116nWaitersToUnblock - int 2117 2118wait( timeout ) { 2119 2120 [auto: register int result ] // error checking omitted 2121 [auto: register int eWasBroadcast ] 2122 [auto: register int nSignalsWasLeft ] 2123 [auto: register int nWaitersWasGone ] 2124 2125 wait( hevBlockLock,INFINITE ); 2126 nWaitersBlocked++; 2127 set_event( hevBlockLock ); 2128 2129 unlock( mtxExternal ); 2130 bTimedOut = waitformultiple( hevBlockQueueS,hevBlockQueueB,timeout,ONE ); 2131 2132 lock( mtxUnblockLock ); 2133 if ( 0 != (SignalsWasLeft = nWaitersToUnblock) ) { 2134 if ( bTimeout ) { // timeout (or canceled) 2135 if ( 0 != nWaitersBlocked ) { 2136 nWaitersBlocked--; 2137 nSignalsWasLeft = 0; // do not unblock next waiter 2138below (already unblocked) 2139 } 2140 else if ( 1 != eBroadcast ) { 2141 nWaitersGone = 1; 2142 } 2143 } 2144 if ( 0 == --nWaitersToUnblock ) { 2145 if ( 0 != nWaitersBlocked ) { 2146 set_event( hevBlockLock ); // open the gate 2147 nSignalsWasLeft = 0; // do not open the gate below 2148again 2149 } 2150 else { 2151 if ( 0 != (eWasBroadcast = eBroadcast) ) { 2152 eBroadcast = 0; 2153 } 2154 if ( 0 != (nWaitersWasGone = nWaitersGone ) { 2155 nWaitersGone = 0; 2156 } 2157 } 2158 } 2159 else if ( 0 != eBroadcast ) { 2160 nSignalsWasLeft = 0; // do not unblock next waiter 2161below (already unblocked) 2162 } 2163 } 2164 else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious 2165event :-) 2166 wait( hevBlockLock,INFINITE ); 2167 nWaitersBlocked -= nWaitersGone; // something is going on here - 2168test of timeouts? :-) 2169 set_event( hevBlockLock ); 2170 nWaitersGone = 0; 2171 } 2172 unlock( mtxUnblockLock ); 2173 2174 if ( 1 == nSignalsWasLeft ) { 2175 if ( 0 != eWasBroadcast ) { 2176 reset_event( hevBlockQueueB ); 2177 } 2178 if ( 0 != nWaitersWasGone ) { 2179 reset_event( hevBlockQueueS ); // better now than spurious 2180later 2181 } 2182 set_event( hevBlockLock ); // open the gate 2183 } 2184 else if ( 0 != nSignalsWasLeft ) { 2185 set_event( hevBlockQueueS ); // unblock next waiter 2186 } 2187 2188 lock( mtxExternal ); 2189 2190 return ( bTimedOut ) ? ETIMEOUT : 0; 2191} 2192 2193signal(bAll) { 2194 2195 [auto: register int result ] 2196 [auto: register HANDLE hevBlockQueue ] 2197 2198 lock( mtxUnblockLock ); 2199 2200 if ( 0 != nWaitersToUnblock ) { // the gate is closed!!! 2201 if ( 0 == nWaitersBlocked ) { // NO-OP 2202 return unlock( mtxUnblockLock ); 2203 } 2204 if (bAll) { 2205 nWaitersToUnblock += nWaitersBlocked; 2206 nWaitersBlocked = 0; 2207 eBroadcast = 2; 2208 hevBlockQueue = hevBlockQueueB; 2209 } 2210 else { 2211 nWaitersToUnblock++; 2212 nWaitersBlocked--; 2213 return unlock( mtxUnblockLock ); 2214 } 2215 } 2216 else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION! 2217 wait( hevBlockLock,INFINITE ); // close the gate 2218 if ( 0 != nWaitersGone ) { 2219 nWaitersBlocked -= nWaitersGone; 2220 nWaitersGone = 0; 2221 } 2222 if (bAll) { 2223 nWaitersToUnblock = nWaitersBlocked; 2224 nWaitersBlocked = 0; 2225 eBroadcast = 1; 2226 hevBlockQueue = hevBlockQueueB; 2227 } 2228 else { 2229 nWaitersToUnblock = 1; 2230 nWaitersBlocked--; 2231 hevBlockQueue = hevBlockQueueS; 2232 } 2233 } 2234 else { // NO-OP 2235 return unlock( mtxUnblockLock ); 2236 } 2237 2238 unlock( mtxUnblockLock ); 2239 set_event( hevBlockQueue ); 2240 return result; 2241} 2242---------------------- Forwarded by Alexander Terekhov/Germany/IBM on 224302/21/2001 09:13 AM --------------------------- 2244 2245Alexander Terekhov 224602/20/2001 04:33 PM 2247 2248To: Louis Thomas <lthomas@arbitrade.com> 2249cc: 2250 2251From: Alexander Terekhov/Germany/IBM@IBMDE 2252Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_* implementatio 2253 n questions 2254Importance: Normal 2255 2256>Sorry, gotta take a break and work on something else for a while. 2257>Real work 2258>calls, unfortunately. I'll get back to you in two or three days. 2259 2260ok. no problem. here is some more stuff for pauses you might have 2261in between :) 2262 2263---------- Algorithm 7d / IMPL_EVENT,UNBLOCK_STRATEGY == UNBLOCK_ALL ------ 2264given: 2265hevBlockLock - auto-reset event 2266hevBlockQueueS - auto-reset event // for signals 2267hevBlockQueueB - manual-reset even // for broadcasts 2268mtxExternal - mutex or CS 2269mtxUnblockLock - mutex or CS 2270bBroadcast - int 2271nWaitersGone - int 2272nWaitersBlocked - int 2273nWaitersToUnblock - int 2274 2275wait( timeout ) { 2276 2277 [auto: register int result ] // error checking omitted 2278 [auto: register int bWasBroadcast ] 2279 [auto: register int nSignalsWasLeft ] 2280 2281 wait( hevBlockLock,INFINITE ); 2282 nWaitersBlocked++; 2283 set_event( hevBlockLock ); 2284 2285 unlock( mtxExternal ); 2286 bTimedOut = waitformultiple( hevBlockQueueS,hevBlockQueueB,timeout,ONE ); 2287 2288 lock( mtxUnblockLock ); 2289 if ( 0 != (SignalsWasLeft = nWaitersToUnblock) ) { 2290 if ( bTimeout ) { // timeout (or canceled) 2291 if ( 0 != nWaitersBlocked ) { 2292 nWaitersBlocked--; 2293 nSignalsWasLeft = 0; // do not unblock next waiter 2294below (already unblocked) 2295 } 2296 else if ( !bBroadcast ) { 2297 wait( hevBlockQueueS,INFINITE ); // better now than spurious 2298later 2299 } 2300 } 2301 if ( 0 == --nWaitersToUnblock ) { 2302 if ( 0 != nWaitersBlocked ) { 2303 if ( bBroadcast ) { 2304 reset_event( hevBlockQueueB ); 2305 bBroadcast = false; 2306 } 2307 set_event( hevBlockLock ); // open the gate 2308 nSignalsWasLeft = 0; // do not open the gate below 2309again 2310 } 2311 else if ( false != (bWasBroadcast = bBroadcast) ) { 2312 bBroadcast = false; 2313 } 2314 } 2315 else { 2316 bWasBroadcast = bBroadcast; 2317 } 2318 } 2319 else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spurious 2320event :-) 2321 wait( hevBlockLock,INFINITE ); 2322 nWaitersBlocked -= nWaitersGone; // something is going on here - 2323test of timeouts? :-) 2324 set_event( hevBlockLock ); 2325 nWaitersGone = 0; 2326 } 2327 unlock( mtxUnblockLock ); 2328 2329 if ( 1 == nSignalsWasLeft ) { 2330 if ( bWasBroadcast ) { 2331 reset_event( hevBlockQueueB ); 2332 } 2333 set_event( hevBlockLock ); // open the gate 2334 } 2335 else if ( 0 != nSignalsWasLeft && !bWasBroadcast ) { 2336 set_event( hevBlockQueueS ); // unblock next waiter 2337 } 2338 2339 lock( mtxExternal ); 2340 2341 return ( bTimedOut ) ? ETIMEOUT : 0; 2342} 2343 2344signal(bAll) { 2345 2346 [auto: register int result ] 2347 [auto: register HANDLE hevBlockQueue ] 2348 2349 lock( mtxUnblockLock ); 2350 2351 if ( 0 != nWaitersToUnblock ) { // the gate is closed!!! 2352 if ( 0 == nWaitersBlocked ) { // NO-OP 2353 return unlock( mtxUnblockLock ); 2354 } 2355 if (bAll) { 2356 nWaitersToUnblock += nWaitersBlocked; 2357 nWaitersBlocked = 0; 2358 bBroadcast = true; 2359 hevBlockQueue = hevBlockQueueB; 2360 } 2361 else { 2362 nWaitersToUnblock++; 2363 nWaitersBlocked--; 2364 return unlock( mtxUnblockLock ); 2365 } 2366 } 2367 else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION! 2368 wait( hevBlockLock,INFINITE ); // close the gate 2369 if ( 0 != nWaitersGone ) { 2370 nWaitersBlocked -= nWaitersGone; 2371 nWaitersGone = 0; 2372 } 2373 if (bAll) { 2374 nWaitersToUnblock = nWaitersBlocked; 2375 nWaitersBlocked = 0; 2376 bBroadcast = true; 2377 hevBlockQueue = hevBlockQueueB; 2378 } 2379 else { 2380 nWaitersToUnblock = 1; 2381 nWaitersBlocked--; 2382 hevBlockQueue = hevBlockQueueS; 2383 } 2384 } 2385 else { // NO-OP 2386 return unlock( mtxUnblockLock ); 2387 } 2388 2389 unlock( mtxUnblockLock ); 2390 set_event( hevBlockQueue ); 2391 return result; 2392} 2393 2394 2395---------------------------------------------------------------------------- 2396 2397Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_* implementatio 2398 n questions 2399Date: Mon, 26 Feb 2001 22:20:12 -0600 2400From: Louis Thomas <lthomas@arbitrade.com> 2401To: "'TEREKHOV@de.ibm.com'" <TEREKHOV@de.ibm.com> 2402CC: rpj@ise.canberra.edu.au, Thomas Pfaff <tpfaff@gmx.net>, 2403 Nanbor Wang 2404 <nanbor@cs.wustl.edu> 2405 2406Sorry all. Busy week. 2407 2408> this insures the fairness 2409> which POSIX does not (e.g. two subsequent broadcasts - the gate does 2410insure 2411> that first wave waiters will start the race for the mutex before waiters 2412> from the second wave - Linux pthreads process/unblock both waves 2413> concurrently...) 2414 2415I'm not sure how we are any more fair about this than Linux. We certainly 2416don't guarantee that the threads released by the first broadcast will get 2417the external mutex before the threads of the second wave. In fact, it is 2418possible that those threads will never get the external mutex if there is 2419enough contention for it. 2420 2421> e.g. i was thinking about implementation with a pool of 2422> N semaphores/counters [...] 2423 2424I considered that too. The problem is as you mentioned in a). You really 2425need to assign threads to semaphores once you know how you want to wake them 2426up, not when they first begin waiting which is the only time you can assign 2427them. 2428 2429> well, i am not quite sure that i've fully understood your scenario, 2430 2431Hmm. Well, it think it's an important example, so I'll try again. First, we 2432have thread A which we KNOW is waiting on a condition. As soon as it becomes 2433unblocked for any reason, we will know because it will set a flag. Since the 2434flag is not set, we are 100% confident that thread A is waiting on the 2435condition. We have another thread, thread B, which has acquired the mutex 2436and is about to wait on the condition. Thus it is pretty clear that at any 2437point, either just A is waiting, or A and B are waiting. Now thread C comes 2438along. C is about to do a broadcast on the condition. A broadcast is 2439guaranteed to unblock all threads currently waiting on a condition, right? 2440Again, we said that either just A is waiting, or A and B are both waiting. 2441So, when C does its broadcast, depending upon whether B has started waiting 2442or not, thread C will unblock A or unblock A and B. Either way, C must 2443unblock A, right? 2444 2445Now, you said anything that happens is correct so long as a) "a signal is 2446not lost between unlocking the mutex and waiting on the condition" and b) "a 2447thread must not steal a signal it sent", correct? Requirement b) is easy to 2448satisfy: in this scenario, thread C will never wait on the condition, so it 2449won't steal any signals. Requirement a) is not hard either. The only way we 2450could fail to meet requirement a) in this scenario is if thread B was 2451started waiting but didn't wake up because a signal was lost. This will not 2452happen. 2453 2454Now, here is what happens. Assume thread C beats thread B. Thread C looks to 2455see how many threads are waiting on the condition. Thread C sees just one 2456thread, thread A, waiting. It does a broadcast waking up just one thread 2457because just one thread is waiting. Next, before A can become unblocked, 2458thread B begins waiting. Now there are two threads waiting, but only one 2459will be unblocked. Suppose B wins. B will become unblocked. A will not 2460become unblocked, because C only unblocked one thread (sema_post cond, 1). 2461So at the end, B finishes and A remains blocked. 2462 2463We have met both of your requirements, so by your rules, this is an 2464acceptable outcome. However, I think that the spec says this is an 2465unacceptable outcome! We know for certain that A was waiting and that C did 2466a broadcast, but A did not become unblocked! Yet, the spec says that a 2467broadcast wakes up all waiting threads. This did not happen. Do you agree 2468that this shows your rules are not strict enough? 2469 2470> and what about N2? :) this one does allow almost everything. 2471 2472Don't get me started about rule #2. I'll NEVER advocate an algorithm that 2473uses rule 2 as an excuse to suck! 2474 2475> but it is done (decrement)under mutex protection - this is not a subject 2476> of a race condition. 2477 2478You are correct. My mistake. 2479 2480> i would remove "_bTimedOut=false".. after all, it was a real timeout.. 2481 2482I disagree. A thread that can't successfully retract its waiter status can't 2483really have timed out. If a thread can't return without executing extra code 2484to deal with the fact that someone tried to unblock it, I think it is a poor 2485idea to pretend we 2486didn't realize someone was trying to signal us. After all, a signal is more 2487important than a time out. 2488 2489> when nSignaled != 0, it is possible to update nWaiters (--) and do not 2490> touch nGone 2491 2492I realize this, but I was thinking that writing it the other ways saves 2493another if statement. 2494 2495> adjust only if nGone != 0 and save one cache memory write - probably much 2496slower than 'if' 2497 2498Hmm. You are probably right. 2499 2500> well, in a strange (e.g. timeout test) program you may (theoretically) 2501> have an overflow of nWaiters/nGone counters (with waiters repeatedly 2502timing 2503> out and no signals at all). 2504 2505Also true. Not only that, but you also have the possibility that one could 2506overflow the number of waiters as well! However, considering the limit you 2507have chosen for nWaitersGone, I suppose it is unlikely that anyone would be 2508able to get INT_MAX/2 threads waiting on a single condition. :) 2509 2510Analysis of 8a: 2511 2512It looks correct to me. 2513 2514What are IPC semaphores? 2515 2516In the line where you state, "else if ( nWaitersBlocked > nWaitersGone ) { 2517// HARMLESS RACE CONDITION!" there is no race condition for nWaitersGone 2518because nWaitersGone is never modified without holding mtxUnblockLock. You 2519are correct that there is a harmless race on nWaitersBlocked, which can 2520increase and make the condition become true just after we check it. If this 2521happens, we interpret it as the wait starting after the signal. 2522 2523I like your optimization of this. You could improve Alg. 6 as follows: 2524---------- Algorithm 6b ---------- 2525signal(bAll) { 2526 _nSig=0 2527 lock counters 2528 // this is safe because nWaiting can only be decremented by a thread that 2529 // owns counters and nGone can only be changed by a thread that owns 2530counters. 2531 if (nWaiting>nGone) { 2532 if (0==nSignaled) { 2533 sema_wait gate // close gate if not already closed 2534 } 2535 if (nGone>0) { 2536 nWaiting-=nGone 2537 nGone=0 2538 } 2539 _nSig=bAll?nWaiting:1 2540 nSignaled+=_nSig 2541 nWaiting-=_nSig 2542 } 2543 unlock counters 2544 if (0!=_nSig) { 2545 sema_post queue, _nSig 2546 } 2547} 2548---------- ---------- ---------- 2549I guess this wouldn't apply to Alg 8a because nWaitersGone changes meanings 2550depending upon whether the gate is open or closed. 2551 2552In the loop "while ( nWaitersWasGone-- ) {" you do a sema_wait on 2553semBlockLock. Perhaps waiting on semBlockQueue would be a better idea. 2554 2555What have you gained by making the last thread to be signaled do the waits 2556for all the timed out threads, besides added complexity? It took me a long 2557time to figure out what your objective was with this, to realize you were 2558using nWaitersGone to mean two different things, and to verify that you 2559hadn't introduced any bug by doing this. Even now I'm not 100% sure. 2560 2561What has all this playing about with nWaitersGone really gained us besides a 2562lot of complexity (it is much harder to verify that this solution is 2563correct), execution overhead (we now have a lot more if statements to 2564evaluate), and space overhead (more space for the extra code, and another 2565integer in our data)? We did manage to save a lock/unlock pair in an 2566uncommon case (when a time out occurs) at the above mentioned expenses in 2567the common cases. 2568 2569As for 8b, c, and d, they look ok though I haven't studied them thoroughly. 2570What would you use them for? 2571 2572 Later, 2573 -Louis! :) 2574 2575----------------------------------------------------------------------------- 2576 2577Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_* implementatio 2578 n questions 2579Date: Tue, 27 Feb 2001 15:51:28 +0100 2580From: TEREKHOV@de.ibm.com 2581To: Louis Thomas <lthomas@arbitrade.com> 2582CC: rpj@ise.canberra.edu.au, Thomas Pfaff <tpfaff@gmx.net>, 2583 Nanbor Wang <nanbor@cs.wustl.edu> 2584 2585Hi Louis, 2586 2587>> that first wave waiters will start the race for the mutex before waiters 2588>> from the second wave - Linux pthreads process/unblock both waves 2589>> concurrently...) 2590> 2591>I'm not sure how we are any more fair about this than Linux. We certainly 2592>don't guarantee that the threads released by the first broadcast will get 2593>the external mutex before the threads of the second wave. In fact, it is 2594>possible that those threads will never get the external mutex if there is 2595>enough contention for it. 2596 2597correct. but gate is nevertheless more fair than Linux because of the 2598barrier it establishes between two races (1st and 2nd wave waiters) for 2599the mutex which under 'normal' circumstances (e.g. all threads of equal 2600priorities,..) will 'probably' result in fair behaviour with respect to 2601mutex ownership. 2602 2603>> well, i am not quite sure that i've fully understood your scenario, 2604> 2605>Hmm. Well, it think it's an important example, so I'll try again. ... 2606 2607ok. now i seem to understand this example. well, now it seems to me 2608that the only meaningful rule is just: 2609 2610a) "a signal is not lost between unlocking the mutex and waiting on the 2611condition" 2612 2613and that the rule 2614 2615b) "a thread must not steal a signal it sent" 2616 2617is not needed at all because a thread which violates b) also violates a). 2618 2619i'll try to explain.. 2620 2621i think that the most important thing is how POSIX defines waiter's 2622visibility: 2623 2624"if another thread is able to acquire the mutex after the about-to-block 2625thread 2626has released it, then a subsequent call to pthread_cond_signal() or 2627pthread_cond_broadcast() in that thread behaves as if it were issued after 2628the about-to-block thread has blocked. " 2629 2630my understanding is the following: 2631 26321) there is no guarantees whatsoever with respect to whether 2633signal/broadcast 2634will actually unblock any 'waiter' if it is done w/o acquiring the mutex 2635first 2636(note that a thread may release it before signal/broadcast - it does not 2637matter). 2638 26392) it is guaranteed that waiters become 'visible' - eligible for unblock as 2640soon 2641as signalling thread acquires the mutex (but not before!!) 2642 2643so.. 2644 2645>So, when C does its broadcast, depending upon whether B has started 2646waiting 2647>or not, thread C will unblock A or unblock A and B. Either way, C must 2648>unblock A, right? 2649 2650right. but only if C did acquire the mutex prior to broadcast (it may 2651release it before broadcast as well). 2652 2653implementation will violate waiters visibility rule (signal will become 2654lost) 2655if C will not unblock A. 2656 2657>Now, here is what happens. Assume thread C beats thread B. Thread C looks 2658to 2659>see how many threads are waiting on the condition. Thread C sees just one 2660>thread, thread A, waiting. It does a broadcast waking up just one thread 2661>because just one thread is waiting. Next, before A can become unblocked, 2662>thread B begins waiting. Now there are two threads waiting, but only one 2663>will be unblocked. Suppose B wins. B will become unblocked. A will not 2664>become unblocked, because C only unblocked one thread (sema_post cond, 1). 2665>So at the end, B finishes and A remains blocked. 2666 2667thread C did acquire the mutex ("Thread C sees just one thread, thread A, 2668waiting"). beginning from that moment it is guaranteed that subsequent 2669broadcast will unblock A. Otherwise we will have a lost signal with respect 2670to A. I do think that it does not matter whether the signal was physically 2671(completely) lost or was just stolen by another thread (B) - in both cases 2672it was simply lost with respect to A. 2673 2674>..Do you agree that this shows your rules are not strict enough? 2675 2676probably the opposite.. :-) i think that it shows that the only meaningful 2677rule is 2678 2679a) "a signal is not lost between unlocking the mutex and waiting on the 2680condition" 2681 2682with clarification of waiters visibility as defined by POSIX above. 2683 2684>> i would remove "_bTimedOut=false".. after all, it was a real timeout.. 2685> 2686>I disagree. A thread that can't successfully retract its waiter status 2687can't 2688>really have timed out. If a thread can't return without executing extra 2689code 2690>to deal with the fact that someone tried to unblock it, I think it is a 2691poor 2692>idea to pretend we 2693>didn't realize someone was trying to signal us. After all, a signal is 2694more 2695>important than a time out. 2696 2697a) POSIX does allow timed out thread to consume a signal (cancelled is 2698not). 2699b) ETIMEDOUT status just says that: "The time specified by abstime to 2700pthread_cond_timedwait() has passed." 2701c) it seem to me that hiding timeouts would violate "The 2702pthread_cond_timedwait() 2703function is the same as pthread_cond_wait() except that an error is 2704returned if 2705the absolute time specified by abstime passes (that is, system time equals 2706or 2707exceeds abstime) before the condition cond is signaled or broadcasted" 2708because 2709the abs. time did really pass before cond was signaled (waiter was 2710released via semaphore). however, if it really matters, i could imaging 2711that we 2712can save an abs. time of signal/broadcast and compare it with timeout after 2713unblock to find out whether it was a 'real' timeout or not. absent this 2714check 2715i do think that hiding timeouts would result in technical violation of 2716specification.. but i think that this check is not important and we can 2717simply 2718trust timeout error code provided by wait since we are not trying to make 2719'hard' realtime implementation. 2720 2721>What are IPC semaphores? 2722 2723<sys/sem.h> 2724int semctl(int, int, int, ...); 2725int semget(key_t, int, int); 2726int semop(int, struct sembuf *, size_t); 2727 2728they support adjustment of semaphore counter (semvalue) 2729in one single call - imaging Win32 ReleaseSemaphore( hsem,-N ) 2730 2731>In the line where you state, "else if ( nWaitersBlocked > nWaitersGone ) { 2732>// HARMLESS RACE CONDITION!" there is no race condition for nWaitersGone 2733>because nWaitersGone is never modified without holding mtxUnblockLock. You 2734>are correct that there is a harmless race on nWaitersBlocked, which can 2735>increase and make the condition become true just after we check it. If 2736this 2737>happens, we interpret it as the wait starting after the signal. 2738 2739well, the reason why i've asked on comp.programming.threads whether this 2740race 2741condition is harmless or not is that in order to be harmless it should not 2742violate the waiters visibility rule (see above). Fortunately, we increment 2743the counter under protection of external mutex.. so that any (signalling) 2744thread which will acquire the mutex next, should see the updated counter 2745(in signal) according to POSIX memory visibility rules and mutexes 2746(memory barriers). But i am not so sure how it actually works on 2747Win32/INTEL 2748which does not explicitly define any memory visibility rules :( 2749 2750>I like your optimization of this. You could improve Alg. 6 as follows: 2751>---------- Algorithm 6b ---------- 2752>signal(bAll) { 2753> _nSig=0 2754> lock counters 2755> // this is safe because nWaiting can only be decremented by a thread 2756that 2757> // owns counters and nGone can only be changed by a thread that owns 2758>counters. 2759> if (nWaiting>nGone) { 2760> if (0==nSignaled) { 2761> sema_wait gate // close gate if not already closed 2762> } 2763> if (nGone>0) { 2764> nWaiting-=nGone 2765> nGone=0 2766> } 2767> _nSig=bAll?nWaiting:1 2768> nSignaled+=_nSig 2769> nWaiting-=_nSig 2770> } 2771> unlock counters 2772> if (0!=_nSig) { 2773> sema_post queue, _nSig 2774> } 2775>} 2776>---------- ---------- ---------- 2777>I guess this wouldn't apply to Alg 8a because nWaitersGone changes 2778meanings 2779>depending upon whether the gate is open or closed. 2780 2781agree. 2782 2783>In the loop "while ( nWaitersWasGone-- ) {" you do a sema_wait on 2784>semBlockLock. Perhaps waiting on semBlockQueue would be a better idea. 2785 2786you are correct. my mistake. 2787 2788>What have you gained by making the last thread to be signaled do the waits 2789>for all the timed out threads, besides added complexity? It took me a long 2790>time to figure out what your objective was with this, to realize you were 2791>using nWaitersGone to mean two different things, and to verify that you 2792>hadn't introduced any bug by doing this. Even now I'm not 100% sure. 2793> 2794>What has all this playing about with nWaitersGone really gained us besides 2795a 2796>lot of complexity (it is much harder to verify that this solution is 2797>correct), execution overhead (we now have a lot more if statements to 2798>evaluate), and space overhead (more space for the extra code, and another 2799>integer in our data)? We did manage to save a lock/unlock pair in an 2800>uncommon case (when a time out occurs) at the above mentioned expenses in 2801>the common cases. 2802 2803well, please consider the following: 2804 28051) with multiple waiters unblocked (but some timed out) the trick with 2806counter 2807seem to ensure potentially higher level of concurrency by not delaying 2808most of unblocked waiters for semaphore cleanup - only the last one 2809will be delayed but all others would already contend/acquire/release 2810the external mutex - the critical section protected by mtxUnblockLock is 2811made smaller (increment + couple of IFs is faster than system/kernel call) 2812which i think is good in general. however, you are right, this is done 2813at expense of 'normal' waiters.. 2814 28152) some semaphore APIs (e.g. POSIX IPC sems) do allow to adjust the 2816semaphore counter in one call => less system/kernel calls.. imagine: 2817 2818if ( 1 == nSignalsWasLeft ) { 2819 if ( 0 != nWaitersWasGone ) { 2820 ReleaseSemaphore( semBlockQueue,-nWaitersWasGone ); // better now 2821than spurious later 2822 } 2823 sem_post( semBlockLock ); // open the gate 2824 } 2825 28263) even on win32 a single thread doing multiple cleanup calls (to wait) 2827will probably result in faster execution (because of processor caching) 2828than multiple threads each doing a single call to wait. 2829 2830>As for 8b, c, and d, they look ok though I haven't studied them 2831thoroughly. 2832>What would you use them for? 2833 28348b) for semaphores which do not allow to unblock multiple waiters 2835in a single call to post/release (e.g. POSIX realtime semaphores - 2836<semaphore.h>) 2837 28388c/8d) for WinCE prior to 3.0 (WinCE 3.0 does have semaphores) 2839 2840ok. so, which one is the 'final' algorithm(s) which we should use in 2841pthreads-win32?? 2842 2843regards, 2844alexander. 2845 2846---------------------------------------------------------------------------- 2847 2848Louis Thomas <lthomas@arbitrade.com> on 02/27/2001 05:20:12 AM 2849 2850Please respond to Louis Thomas <lthomas@arbitrade.com> 2851 2852To: Alexander Terekhov/Germany/IBM@IBMDE 2853cc: rpj@ise.canberra.edu.au, Thomas Pfaff <tpfaff@gmx.net>, Nanbor Wang 2854 <nanbor@cs.wustl.edu> 2855Subject: RE: FYI/comp.programming.threads/Re: pthread_cond_* implementatio 2856 n questions 2857 2858Sorry all. Busy week. 2859 2860> this insures the fairness 2861> which POSIX does not (e.g. two subsequent broadcasts - the gate does 2862insure 2863> that first wave waiters will start the race for the mutex before waiters 2864> from the second wave - Linux pthreads process/unblock both waves 2865> concurrently...) 2866 2867I'm not sure how we are any more fair about this than Linux. We certainly 2868don't guarantee that the threads released by the first broadcast will get 2869the external mutex before the threads of the second wave. In fact, it is 2870possible that those threads will never get the external mutex if there is 2871enough contention for it. 2872 2873> e.g. i was thinking about implementation with a pool of 2874> N semaphores/counters [...] 2875 2876I considered that too. The problem is as you mentioned in a). You really 2877need to assign threads to semaphores once you know how you want to wake 2878them 2879up, not when they first begin waiting which is the only time you can assign 2880them. 2881 2882> well, i am not quite sure that i've fully understood your scenario, 2883 2884Hmm. Well, it think it's an important example, so I'll try again. First, we 2885have thread A which we KNOW is waiting on a condition. As soon as it 2886becomes 2887unblocked for any reason, we will know because it will set a flag. Since 2888the 2889flag is not set, we are 100% confident that thread A is waiting on the 2890condition. We have another thread, thread B, which has acquired the mutex 2891and is about to wait on the condition. Thus it is pretty clear that at any 2892point, either just A is waiting, or A and B are waiting. Now thread C comes 2893along. C is about to do a broadcast on the condition. A broadcast is 2894guaranteed to unblock all threads currently waiting on a condition, right? 2895Again, we said that either just A is waiting, or A and B are both waiting. 2896So, when C does its broadcast, depending upon whether B has started waiting 2897or not, thread C will unblock A or unblock A and B. Either way, C must 2898unblock A, right? 2899 2900Now, you said anything that happens is correct so long as a) "a signal is 2901not lost between unlocking the mutex and waiting on the condition" and b) 2902"a 2903thread must not steal a signal it sent", correct? Requirement b) is easy to 2904satisfy: in this scenario, thread C will never wait on the condition, so it 2905won't steal any signals. Requirement a) is not hard either. The only way 2906we 2907could fail to meet requirement a) in this scenario is if thread B was 2908started waiting but didn't wake up because a signal was lost. This will not 2909happen. 2910 2911Now, here is what happens. Assume thread C beats thread B. Thread C looks 2912to 2913see how many threads are waiting on the condition. Thread C sees just one 2914thread, thread A, waiting. It does a broadcast waking up just one thread 2915because just one thread is waiting. Next, before A can become unblocked, 2916thread B begins waiting. Now there are two threads waiting, but only one 2917will be unblocked. Suppose B wins. B will become unblocked. A will not 2918become unblocked, because C only unblocked one thread (sema_post cond, 1). 2919So at the end, B finishes and A remains blocked. 2920 2921We have met both of your requirements, so by your rules, this is an 2922acceptable outcome. However, I think that the spec says this is an 2923unacceptable outcome! We know for certain that A was waiting and that C did 2924a broadcast, but A did not become unblocked! Yet, the spec says that a 2925broadcast wakes up all waiting threads. This did not happen. Do you agree 2926that this shows your rules are not strict enough? 2927 2928> and what about N2? :) this one does allow almost everything. 2929 2930Don't get me started about rule #2. I'll NEVER advocate an algorithm that 2931uses rule 2 as an excuse to suck! 2932 2933> but it is done (decrement)under mutex protection - this is not a subject 2934> of a race condition. 2935 2936You are correct. My mistake. 2937 2938> i would remove "_bTimedOut=false".. after all, it was a real timeout.. 2939 2940I disagree. A thread that can't successfully retract its waiter status 2941can't 2942really have timed out. If a thread can't return without executing extra 2943code 2944to deal with the fact that someone tried to unblock it, I think it is a 2945poor 2946idea to pretend we 2947didn't realize someone was trying to signal us. After all, a signal is more 2948important than a time out. 2949 2950> when nSignaled != 0, it is possible to update nWaiters (--) and do not 2951> touch nGone 2952 2953I realize this, but I was thinking that writing it the other ways saves 2954another if statement. 2955 2956> adjust only if nGone != 0 and save one cache memory write - probably much 2957slower than 'if' 2958 2959Hmm. You are probably right. 2960 2961> well, in a strange (e.g. timeout test) program you may (theoretically) 2962> have an overflow of nWaiters/nGone counters (with waiters repeatedly 2963timing 2964> out and no signals at all). 2965 2966Also true. Not only that, but you also have the possibility that one could 2967overflow the number of waiters as well! However, considering the limit you 2968have chosen for nWaitersGone, I suppose it is unlikely that anyone would be 2969able to get INT_MAX/2 threads waiting on a single condition. :) 2970 2971Analysis of 8a: 2972 2973It looks correct to me. 2974 2975What are IPC semaphores? 2976 2977In the line where you state, "else if ( nWaitersBlocked > nWaitersGone ) { 2978// HARMLESS RACE CONDITION!" there is no race condition for nWaitersGone 2979because nWaitersGone is never modified without holding mtxUnblockLock. You 2980are correct that there is a harmless race on nWaitersBlocked, which can 2981increase and make the condition become true just after we check it. If this 2982happens, we interpret it as the wait starting after the signal. 2983 2984I like your optimization of this. You could improve Alg. 6 as follows: 2985---------- Algorithm 6b ---------- 2986signal(bAll) { 2987 _nSig=0 2988 lock counters 2989 // this is safe because nWaiting can only be decremented by a thread that 2990 // owns counters and nGone can only be changed by a thread that owns 2991counters. 2992 if (nWaiting>nGone) { 2993 if (0==nSignaled) { 2994 sema_wait gate // close gate if not already closed 2995 } 2996 if (nGone>0) { 2997 nWaiting-=nGone 2998 nGone=0 2999 } 3000 _nSig=bAll?nWaiting:1 3001 nSignaled+=_nSig 3002 nWaiting-=_nSig 3003 } 3004 unlock counters 3005 if (0!=_nSig) { 3006 sema_post queue, _nSig 3007 } 3008} 3009---------- ---------- ---------- 3010I guess this wouldn't apply to Alg 8a because nWaitersGone changes meanings 3011depending upon whether the gate is open or closed. 3012 3013In the loop "while ( nWaitersWasGone-- ) {" you do a sema_wait on 3014semBlockLock. Perhaps waiting on semBlockQueue would be a better idea. 3015 3016What have you gained by making the last thread to be signaled do the waits 3017for all the timed out threads, besides added complexity? It took me a long 3018time to figure out what your objective was with this, to realize you were 3019using nWaitersGone to mean two different things, and to verify that you 3020hadn't introduced any bug by doing this. Even now I'm not 100% sure. 3021 3022What has all this playing about with nWaitersGone really gained us besides 3023a 3024lot of complexity (it is much harder to verify that this solution is 3025correct), execution overhead (we now have a lot more if statements to 3026evaluate), and space overhead (more space for the extra code, and another 3027integer in our data)? We did manage to save a lock/unlock pair in an 3028uncommon case (when a time out occurs) at the above mentioned expenses in 3029the common cases. 3030 3031As for 8b, c, and d, they look ok though I haven't studied them thoroughly. 3032What would you use them for? 3033 3034 Later, 3035 -Louis! :) 3036 3037