mtxExternal - mutex or CSmtxUnblockLock - mutex or CSnWaitersGone - intnWaitersBlocked - intnWaitersToUnblock - intwait( 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 waiterbelow (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 belowagain      }      else if ( 0 != (nWaitersWasGone = nWaitersGone) ) {        nWaitersGone = 0;      }    }  }  else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spuriousevent :-)    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 spuriouslater    }    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 eventhevBlockQueueS - auto-reset event  // for signalshevBlockQueueB - manual-reset even // for broadcastsmtxExternal - mutex or CSmtxUnblockLock - mutex or CSeBroadcast - int                   // 0: no broadcast, 1: broadcast, 2:broadcast after signal(s)nWaitersGone - intnWaitersBlocked - intnWaitersToUnblock - intwait( 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 waiterbelow (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 belowagain      }      else {        if ( 0 != (eWasBroadcast = eBroadcast) ) {          eBroadcast = 0;        }        if ( 0 != (nWaitersWasGone = nWaitersGone ) {          nWaitersGone = 0;        }      }    }    else if ( 0 != eBroadcast ) {      nSignalsWasLeft = 0;                  // do not unblock next waiterbelow (already unblocked)    }  }  else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spuriousevent :-)    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 spuriouslater    }    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 on02/21/2001 09:13 AM ---------------------------Alexander Terekhov02/20/2001 04:33 PMTo:   Louis Thomas <lthomas@arbitrade.com>cc:From: Alexander Terekhov/Germany/IBM@IBMDESubject:  RE: FYI/comp.programming.threads/Re: pthread_cond_* implementatio      n questionsImportance:    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 havein between :)---------- Algorithm 7d / IMPL_EVENT,UNBLOCK_STRATEGY == UNBLOCK_ALL ------given:hevBlockLock - auto-reset eventhevBlockQueueS - auto-reset event  // for signalshevBlockQueueB - manual-reset even // for broadcastsmtxExternal - mutex or CSmtxUnblockLock - mutex or CSbBroadcast - intnWaitersGone - intnWaitersBlocked - intnWaitersToUnblock - intwait( 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 waiterbelow (already unblocked)      }      else if ( !bBroadcast ) {        wait( hevBlockQueueS,INFINITE );    // better now than spuriouslater      }    }    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 belowagain      }      else if ( false != (bWasBroadcast = bBroadcast) ) {        bBroadcast = false;      }    }    else {      bWasBroadcast = bBroadcast;    }  }  else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or spuriousevent :-)    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 questionsDate: Mon, 26 Feb 2001 22:20:12 -0600From: Louis Thomas <lthomas@arbitrade.com>To: "'TEREKHOV@de.ibm.com'" <TEREKHOV@de.ibm.com>CC: rpj@ise.canberra.edu.au, Thomas Pfaff <tpfaff@gmx.net>,     Nanbor Wang     <nanbor@cs.wustl.edu>Sorry all. Busy week.> this insures the fairness> which POSIX does not (e.g. two subsequent broadcasts - the gate doesinsure> 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 certainlydon't guarantee that the threads released by the first broadcast will getthe external mutex before the threads of the second wave. In fact, it ispossible that those threads will never get the external mutex if there isenough 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 reallyneed to assign threads to semaphores once you know how you want to wake themup, not when they first begin waiting which is the only time you can assignthem.> 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, wehave thread A which we KNOW is waiting on a condition. As soon as it becomesunblocked for any reason, we will know because it will set a flag. Since theflag is not set, we are 100% confident that thread A is waiting on thecondition. We have another thread, thread B, which has acquired the mutexand is about to wait on the condition. Thus it is pretty clear that at anypoint, either just A is waiting, or A and B are waiting. Now thread C comesalong. C is about to do a broadcast on the condition. A broadcast isguaranteed 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 waitingor not, thread C will unblock A or unblock A and B. Either way, C mustunblock A, right?Now, you said anything that happens is correct so long as a) "a signal isnot lost between unlocking the mutex and waiting on the condition" and b) "athread must not steal a signal it sent", correct? Requirement b) is easy tosatisfy: in this scenario, thread C will never wait on the condition, so itwon't steal any signals.  Requirement a) is not hard either. The only way wecould fail to meet requirement a) in this scenario is if thread B wasstarted waiting but didn't wake up because a signal was lost. This will nothappen.Now, here is what happens. Assume thread C beats thread B. Thread C looks tosee how many threads are waiting on the condition. Thread C sees just onethread, thread A, waiting. It does a broadcast waking up just one threadbecause just one thread is waiting. Next, before A can become unblocked,thread B begins waiting. Now there are two threads waiting, but only onewill be unblocked. Suppose B wins. B will become unblocked. A will notbecome 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 anacceptable outcome. However, I think that the spec says this is anunacceptable outcome! We know for certain that A was waiting and that C dida broadcast, but A did not become unblocked! Yet, the spec says that abroadcast wakes up all waiting threads. This did not happen. Do you agreethat 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 thatuses 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'treally have timed out. If a thread can't return without executing extra codeto deal with the fact that someone tried to unblock it, I think it is a pooridea to pretend wedidn't realize someone was trying to signal us. After all, a signal is moreimportant than a time out.>